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.
3
votes
1answer
33 views
Snakes and Ladders using a magic die
This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game.
...
4
votes
0answers
52 views
Implementation of BFS on a graph
I have written the code below as a BFS implementation. Could someone please review. In particular, I want to know if there could be a memory leak.
...
0
votes
2answers
33 views
Adjacency list from scratch
Here is my code for implementing an adjacency list from scratch. I would like to get feedback from the experts for optimization.
...
2
votes
1answer
29 views
Get a path between graph nodes using breadth-first search
This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using breadth-first search.
I'm doing this to improve my style ...
1
vote
1answer
28 views
Return a path between graph nodes using depth-first search redo
I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this ...
1
vote
1answer
28 views
Return path between graph nodes using depth-first search
This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search.
I'm doing this to improve my style ...
0
votes
1answer
24 views
Print Connected Components Scala
Given a file containing adjacent IDs:
i1, i2, i5
i3, i4
i2, i6, i7
i4, i8
i9, i3
I would like to print each of the connected components:
...
0
votes
0answers
25 views
Return path between graph nodes using breadth-first search
This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using breadth-first search.
I'm doing this to improve my style ...
4
votes
0answers
51 views
Graph Python challenge 2 (revised)
I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python:
You and your rescued prisoners need to get out of this collapsing
death trap - and fast! ...
2
votes
1answer
61 views
Implementation of a directed graph
I wrote an implementation of a directed graph using the adjacency list representation. My goal was to meet the big O requirements which I'd found here.
Please let me know about any drawbacks of the ...
4
votes
1answer
66 views
Finding the max cost from the minimum cost incurred on travelling
This problem is from INOI 2014 , where I have find out the maximum cost of traveling through the cities but taking the minimum possible route cost , here is an excerpt from it,
Indian National ...
3
votes
1answer
115 views
Python graph challenge
I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python:
You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
2
votes
0answers
40 views
C++ STL graph implementation with out and in adjacency list
I'm looking for a code review on the following C++/STL graph implementation:
Edge
...
1
vote
1answer
44 views
Convert a List of graph edges to a Map of neighboring nodes
What would be best way achieving this? Is it possible to use Immutable map?
...
0
votes
1answer
72 views
Node comparison using priority queue for Dijkstra's Shortest Path Algorithm
Instead of using a MinHeap that will allow me to change the vertex priorities I am using the Java library PriorityQueue.
Here ...
0
votes
1answer
45 views
Directed Acyclic graph implementation in Ruby on Rails
I have an implementation for a graph node class that I'd like to have function as a directed acyclic graph.
The associations are roughly as follows
...
2
votes
2answers
26 views
4
votes
0answers
46 views
Finding connected components in the application task
I have n indexed socks, each of which has one of k colors. I also have a list that states which two socks I must wear at each of ...
0
votes
1answer
35 views
NBA*: Very efficient bidirectional heuristic search algorithm in Java - follow-up
This post elaborates on NBA*: Very efficient bidirectional heuristic search algorithm in Java.
I have made the following changes:
Added an explicit type for representing digraph paths: ...
0
votes
1answer
37 views
Social network broadcast message algorithm (part 2)
This is new code and continue discussion from thread (Social network broadcast message algorithm), and this thread focus on build new graph from strong connected graph part. Let me post the problem ...
0
votes
2answers
62 views
Code for number of routes possible of the given length between 2 given nodes
Recently I came across this problem , here is an excerpt of it,
It is well known that the routing algorithm used on the Internet is
highly non-optimal. A "hop", in Internet jargon, is a pair of ...
1
vote
1answer
86 views
NBA*: Very efficient bidirectional heuristic search algorithm in Java
(See also the next iteration.)
I have implemented NBA* (New Bidirectional A*) in Java and compared it against conventional A* and Dijkstra algorithms. The results may be as optimistic as this:
Seed =...
6
votes
2answers
130 views
Strongly connected component algorithm in Python 2.7
This is my implementation of Kosaraju's algorithm for detecting strongly connected components, post here for advice. Some special areas looking for advice,
Not sure if my current implementation for ...
2
votes
1answer
53 views
Internal method to calculate the distance between all nodes in Kruskal's Importance (Driver) Algorithm
I've been trying to reduce the indentation from a method in my code. The solution will probably be unrelated to the language, in this case python, although it may rely on some python specific ...
4
votes
1answer
79 views
Graph represented by an adjacency matrix in C++
I'm working on my data structures knowledge and wanted to create a graph with a small DFS driver which simply prints the nodes as it visits them. Here's my graph class:
...
4
votes
1answer
146 views
Dijkstra's algorithm using a dictionary for the priority queue
Unrelated to code:
This is my first project in Python using classes and algorithms.
I have spent the last week self teaching myself about queues and stacks, so I am NOT trying to use any Python ...
3
votes
1answer
55 views
Calculating how similar two objects are according to a database
I want to calculate how similar two objects are according to a database. However the code is very slow; it takes around 2 minutes to analyze just 3 objects. How can I speed it up? I have tried to ...
3
votes
1answer
63 views
Implementing an Adjacency List in C
I haven't yet implemented any sort of graph thus far in C and decided to give it a go by trying to implement an adjacency list in C. Is there anything in my code that you see that I can improve and is ...
5
votes
1answer
173 views
Social network broadcast message algorithm
Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am ...
1
vote
0answers
30 views
FindUnion data structure used to find the minimum cut of a graph
I am trying to find the bottleneck in my code for computing the minimum cut of a graph. Currently the program runs in about 40 minutes on the test data set linked below (200 nodes and ~2000 edges). I ...
2
votes
1answer
145 views
Directed weighted Graph Data Structure in Java
I am beginner in Java. I coded Directed weighted Graph data structure by myself without anyone's help i want to have some constructive feedback regarding my program design, weather my code is perfect ...
4
votes
1answer
106 views
Node Graph-based User Interface with python
I'd like to create a pyqt widget similar to the one Blender uses for representing its nodes After wasting some bounties without getting any answers on Stack Overflow, I thought maybe posting a little ...
2
votes
1answer
27 views
Shortest code to generate a full mesh of elements
I am trying to find the shortest code that generates a full mesh of the elements fed into it in graphviz format
e.g. the full mesh of [0, 1, 2] is:
2 -> 0
2 -> 1
1 -> 0
I have the code below and I ...
3
votes
2answers
182 views
My attempt at Dijkstra's Algorithm in Python 3
I am practicing my coding at HackerRank. The exact problem statement can be found here, but to summarize, it is finding the distances of the shortest path from a starting node to every other node in a ...
2
votes
0answers
90 views
Prim's MST Java implementation
Can someone review this code, just have look if it's logically correct
or
If you may point me to a more simple and minimalist program
...
1
vote
0answers
41 views
Storing large maps in memory
Context of the problem:
I have a very large graph that cost about 4GB to store. About 3M nodes and 34M edges. My program takes this large graph and recursively builds smaller graphs from it. At each ...
2
votes
0answers
98 views
Dijkstra's single source shortest path algorithm (with Fibonacci heap)
I implemented a generic Dijkstra algorithm. It's lazy since the vertices with their final distances are request on demand. I used the Fibonacci Heap from this question with a few changes (added a copy ...
2
votes
1answer
98 views
Weighted graph and pathfinding implementation in C#
I am implementing fundamental data structures in C#. I have written a weighted graph in Java so my main motivation here is to sharpen my skills in C#. I have tested with various cases and there seems ...
1
vote
0answers
17 views
Wikipath stack in Java - Part II/IV - The implicit Wikipedia article graph
This question is the continuation of the Wikipath stack series: the two classes that - given a Wikipedia article \$A\$ - return the lists of neighbour articles. The forward node expander return the ...
1
vote
1answer
682 views
Prim's algorithm for finding the minimum spanning tree
So I was coding Prim's algorithm for practice and this is what I wrote. It works for finding the weight of the minimum spanning tree (MST) but I'm wondering if the loop I am doing to add the the edges ...
11
votes
3answers
166 views
Dijkstra's algorithm in C99
I just implement Dijkstra's algorithm in C99. Can you review my code please? I'm looking for any mistake, performance improvement or coding style errors.
main.c
...
16
votes
1answer
195 views
Rainfall - August 2016 Community Challenge (Hooray for graphs!)
A solution for the August 2016 Community Challenge (Rainfall).
I've intentionally left out error checking on the file formatting.
This seems like a very obvious graph problem to me - we want to ...
2
votes
0answers
126 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
...
2
votes
1answer
227 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
57 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
921 views
6
votes
1answer
31 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
383 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 use ...
11
votes
1answer
73 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
(Please ...
5
votes
1answer
336 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.
...
