A graph is an abstract representation of objects (vertices) connected by links (edges). For questions about plotting data graphically, use the [data-visualization] tag instead.
2
votes
0answers
27 views
Karger's min-cut algorithm implemented in python
I implemented Karger's algorithm with the function find_min_cut and it works, but I don't feel satisfied with the code I wrote.
...
1
vote
0answers
19 views
Parametric HOAS and graph reification
Is it possible to reify the graph of lambda terms expressed as parametric HOAS. Not quite sure if it is
...
5
votes
1answer
81 views
Clustering nodes with Hamming distance < 3
I want to speed up the following code, which is from an algorithm class.
I get a list of 200000 nodes where every node is a tuple of the length of 24 where every item is either a 1 or 0.
These ...
3
votes
2answers
137 views
Connected components in an undirected graph in C#
My knowledge in graph theory is very limited. I have to look for elements in an (undirected) graph who are in the same connected component.
The idea is simple. First, build the graph. Then, allocate ...
2
votes
1answer
99 views
Find the number of possible infinite cycles that Bessie the Cow can get stuck in
Bessie the cow is in Farmer John's field. The field is of size 0..1,000,000,000 for x and y. Farmer John knows that there are N/2 wormholes at certain coordinates, but he does not know which wormholes ...
2
votes
1answer
81 views
Pointer lists for a C++ garbage collector
The problem
My intention is to have a class A and class B. class B has a ...
1
vote
0answers
37 views
Graph (adjacency list) and DFS (topological sort)
The vertices on the graph are numbers from 0 to |V| - 1 for convenience. I was thinking later to use a template wrapper for the graph.
Graph.h:
...
0
votes
1answer
112 views
Shortest path via two intermediate points
My code takes a long time for big graphs.
How can I make it faster?
I'm trying to calculate the shortest path for 3 path's using queue but for big input my program crashes.
I'm stuck here. Can ...
3
votes
1answer
40 views
Reliability polynomial calculation
The reliability polynomial (specifically, the all-terminal reliability polynomial) is, given a value \$0 \le p \le 1\$, outputs the probability that a given graph \$G\$ is connected.
Note: at the ...
6
votes
3answers
118 views
Generic graph implementation in C#
I am implementing fundamental data structures in C# while trying to learn techniques in the language to make my code cleaner, more concise, and reusable. I have implemented a generic graph with a few ...
0
votes
0answers
34 views
Finding shortest paths in a Wikipedia article graph using Java - second attempt
I have improved Finding shortest paths in a Wikipedia article graph using Java.
Now I have this:
AbstractWikipediaShortestPathFinder.java:
...
3
votes
2answers
91 views
Assembling edges of a graph
I'm making a neural network that comprises five populations of feature-selective neurons and one population of non-selective neurons. Each neuron in this network receives connections from
c * f * ...
4
votes
0answers
50 views
Finding shortest paths in a Wikipedia article graph using Java
(See also Finding shortest paths in a Wikipedia article graph using Java - second attempt.)
I have this sort of a web crawler that asks for two (English) Wikipedia article titles (the source and the ...
4
votes
1answer
107 views
Dijkstra's algorithm
Assuming everything else works as expected, is the following a correct - but not the most efficient way - of implementing Dijkstra algorithm? Because I have tested it on several examples and it gives ...
2
votes
1answer
52 views
Maximum clique problem: fast heuristic
I have implemented an algorithm which computes a maximum clique via a heuristic. The pseudo-code can be found in this Paper (see Algorithm 2).
Maximum Clique Problem
Given an undirected, simple ...
5
votes
1answer
36 views
Cyclic “dependency detection” in JavaScript
I have written some simple code to detect cyclic dependencies for a module loading system and I'd like some feedback on how I can go about improving it. The code itself finds the first cycle in the ...
3
votes
2answers
124 views
C++ Graph Class Implementation (adjacency list)
I've got a barebones C++ graph class implemented as an adjacency list. The graph consists of a vector of vertices. Each vertex has a vector of outgoing edges that store the destination vertex id. ...
4
votes
1answer
97 views
Algorithms to find various kinds of paths in graphs
I think many here are familiar with the graph data structure. Not very long ago, I implemented as an exercise a supposedly simple Graph application that does some traversals. To note, the most complex ...
3
votes
0answers
63 views
Time Limit Exceeded with shortest path algorithm
The problem:
SHPATH
You are given a list of cities. Each direct connection between two
cities has its transportation cost (an integer bigger than 0). The
goal is to find the paths of ...
1
vote
0answers
33 views
Checking whether a directed graph contains a cycle
I create a myGraph class as shown below. Then I created an instance of the graph by giving the adjacency list as a NSDictionary and then call the isGraphCycleFree method. Will this answer look good ...
1
vote
1answer
81 views
Graph and minimum spanning tree in Python
Here is my Graph class that implements a graph and has nice a method to generate its spanning tree using Kruskal's algorithm.
I want to:
Make it pythonic
Improve readability
Improve the abstraction ...
2
votes
1answer
126 views
Find shortest paths in a matrix using Dijkstra's algorithm
The problem is as follows:
I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths ...
3
votes
1answer
89 views
Maxflow for baseball elimination game
I have a problem similar to the baseball elimination. Given some teams, the number of wins they have and the number of games they have left between each other I have to find for which team it is still ...
3
votes
0answers
44 views
Comparing linear time strongly connected component algorithms in Java
So I have implemented three linear time (\$\mathcal{O}(V + E)\$) algorithms for finding strongly connected components of a (directed) graph. A strongly connected component is just a maximal subset of ...
0
votes
1answer
43 views
Optimizing and accounting for edge cases in Dijkstra's algorithm
I just recently wrote a program to simulate how multicast routing works.
The program uses a weighted graph to represent the network and simply runs it through the algorithm.
I would like to know if ...
3
votes
0answers
14 views
Data Explorer query that makes bar graphs
I wrote a query for SEDE that I think is pretty cool. It uses the currently available graphing capabilities (scatter plots) to create a bar graph. I have used it as the subject for a self-answer on ...
4
votes
0answers
72 views
Pseudo-parallel depth-first search
I'm writing a small program, that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel dfs on it.
How can I make the ...
7
votes
1answer
54 views
Social network graph of characters in a novel
I wrote a C program that builds a social network graph of characters in a novel. The program takes two text files as input: a list of the names of the characters in the novel, and the file of the ...
0
votes
0answers
33 views
Adjacency List Graph Implementation for search
I wrote this adjacency list graph implementation to learn about implement path finding and graph search. I'm looking to fix any coding style / best practice issues, and performance issues.
Also, the ...
4
votes
0answers
86 views
Plotting charts for a large data set
I have created an automated macro which takes vehicle crash data from a .csv file and automatically creates a pivot table and plots and compares it to the previous year. The code is approximately 1400 ...
1
vote
1answer
109 views
Implementation of Dijkstra's algorithm in C++
This is my implementation of Dijkstra's algorithm. Could you tell me what am I doing wrong and what should be fixed? I was not sure how to keep track of the shortest outgoing edge from a node and I ...
1
vote
1answer
65 views
Implementation of Prim's algorithm in C++
Could anyone comment on what could be done better and if I made any mistakes?
...
5
votes
0answers
80 views
Topological sort using recursive DFS
I am currently learning Graph algorithms by solving questions on online judges. The below code is for implementing Topological sort, using recursive DFS. Also, it is my first time with C++ STL. ...
5
votes
3answers
107 views
Idiomatic ruby to calculate distance to points on a graph
Can this code be made more like idiomatic ruby using methods such as map or inject?
@random_tour is a variable length array of points on a graph:
...
4
votes
0answers
50 views
Simple graph in Rust
I have written simple code to construct a graph, but I think there are too many different types for such a simple task.
In this code I need to store Node structs ...
3
votes
1answer
81 views
Detect cycle in undirected graph
Below is my code to detect cycle in an undirected graph. Could anyone please review and let me know if I have taken care of all the cases?
The basic idea is to use DFS (non-recursive using stack) and ...
2
votes
0answers
62 views
Finding all paths between nodes in a graph
I wanted to write a function paths that returns the possible routes between two nodes in a graph.
For example:
...
3
votes
1answer
120 views
Dijkstra's algorithm: traditional and bidirectional in Python
I have translated Dijkstra's algorithms (uni- and bidirectional variants) from Java to Python, eventually coming up with this:
Dijkstra.py
...
0
votes
1answer
77 views
Simple weighted directed graph in Python
I have this simplistic Python class for representing directed weighted graphs (digraphs for short):
Digraph.py
...
0
votes
0answers
71 views
Hierarchical Data to Graph
I am using vis.js to visualize some hierarchical data. I have created a recursive routine to add nodes and edges for each group and value in the dataset.
I feel like something already exists for this ...
3
votes
0answers
69 views
Graph Library in C
Could you guys please review the Graph Library I developed in C? It's also on GitHub
...
1
vote
0answers
31 views
Minimum number of moves to reach the end - follow-up
I need to calculate the minimum number of jumps to reach the end of an array with dice throws.
Array values may be negative/positive:
When positive - move forward
When negative - go back
The ...
4
votes
1answer
47 views
Minimum number of moves to reach the end
I need to calculate the minimum number of jumps to reach the end of an Array with dice throw.
Array values may be negative/positive:
When positive - move forward
When negative - go back
The ...
3
votes
0answers
83 views
Implementation of Dijkstra's Algorithm in JavaScript that returns both shortestDist/shortestPaths
I decided to try to understand the basic idea behind Dijkstra's algorithm better so I implemented it in JavaScript (the only language I am proficient in as of now) so I could really see what was ...
2
votes
1answer
29 views
Distributed (asynchronous) averaging
This code simulates a distributed averaging protocol. There is a network of nodes, and at the clicks of a Poisson process:
A random node wakes up
Transmits it's current average to all the nodes it ...
4
votes
1answer
132 views
Using the A* algorithm to search a graph generated from a grid
Following on from my previous question, I finally got round to actually doing the A* search for the Graph<MapTile>. The changes to the code from the previous ...
3
votes
1answer
76 views
DFS algorithm too slow
I am practicing my coding on leetcode, and my submission, although correct for small cases, is timing out for large ones. Could you please let me know how to improve my code?
The question is as ...
3
votes
2answers
67 views
Generating a graph from a rectangular grid for graph searching
I recently reviewed some code implementing some heuristics which has piqued my interest in the A* graph searching algorithm. I'm going to do that in a bit but first I need a way to create a graph in ...
3
votes
1answer
120 views
A graph representation of Adjacent Matrix in Python
I'm trying to create a graph representation in Adj Matrix in Python. I'm not sure if this is the best pythonic way.
...
1
vote
2answers
64 views
Check if the undirected graph is cyclic
Here is my approach. Do DFS and check in stack whether the new node is already in the Stack or not.
...
