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
22 views
Strongly connected components in a graph: Kosaraju's algorithm
I implemented Kosaraju's algorithm on a graph with 800k vertices and 5100k edges.
The time taken by various operations are:
building graph took 11.84 seconds
ordering took 2.54 seconds
...
0
votes
0answers
37 views
C++ simple graph and Dijkstra's algorithm [on hold]
I have this code demo of a graph structure and an implementation of Dijkstra's algorithm which returns a shortest path tree. I've received two comments.
The use of named nodes and edges is a bad ...
2
votes
1answer
52 views
Sum of all paths between all pairs of nodes in a tree
I'm trying to solve a competitive programming problem. It basically gives a undirected graph (tree-like: no multiple paths between two nodes...) and asks for the sum of all possible paths between any ...
2
votes
2answers
37 views
Converting XML to DOT
I would like to show an XML tree as a tree using GraphViz Dot tool. Then I must convert it to a DOT file.
It is what I have tried
...
7
votes
1answer
369 views
6
votes
1answer
27 views
Counting single degree vertex removal rounds (from a graph)
Problem:
In this problem I had to remove all vertices with degree one from a given graph in rounds and count how many rounds are required to remove all possible vertices with degree 1.
e.g. ...
4
votes
1answer
72 views
Undirected graph implementation in java
Here is my code which implements a undirected graph in java. I'm fairly new to java(I come from C) and I am not sure if this is a good implementation. Here are a few things i worry about -
Did I ...
11
votes
1answer
67 views
Create edges from cells
I have a (large) number of nodes and (triangular) cells, e.g.,
cells_nodes = [
[0, 3, 1],
[0, 2, 3]
]
This example represents the small mesh
(...
3
votes
1answer
99 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
25 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
94 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
143 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
86 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
49 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
119 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
42 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
128 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
36 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
94 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
59 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
117 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
58 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
50 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
141 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
100 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 ...
4
votes
0answers
72 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
37 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
121 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
144 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
92 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
48 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 ...
2
votes
1answer
54 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
16 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
80 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
55 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
37 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 ...
5
votes
0answers
95 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
125 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
71 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
103 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. ...
6
votes
3answers
119 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
56 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
92 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
87 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
139 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
85 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
73 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 ...
5
votes
0answers
74 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
32 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 ...
