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.
4
votes
1answer
42 views
Code to calculate minimum number of pushes required to put the whole dominoes set down
The question is this one on UVa, and it basically gives us n, the number of dominoes and (a,b) relations such that pushing ...
-5
votes
0answers
43 views
Knight shortest path c++ [closed]
I have an exercise that gives 2 inputs:where knight is,where it should go.
And i have to find the shortest path of it.Here is the code i wrote
...
3
votes
2answers
66 views
Dijkstra's algorithm using a specific structure
I have implemented Dijkstra's algorithm using a slightly modified version of the structure and class posted here. Unfortunately, I have ruined the efficiency. I am intent on using this structure. I ...
3
votes
3answers
75 views
Graph representation implementation
I wanted to represent graphs in Python, and wrote the following class. I don't care about values associated with nodes or the weights of the connections between them, simply the connections between ...
1
vote
1answer
34 views
BFS' shortest path unweighted directed graph
The code I have is based on BFS and a little bit of Dijkstra and returns the shortest path of an unweighted directed graph as an integer. I was wondering if someone could take a look at my code too ...
3
votes
1answer
53 views
Topologial Sort in Python
I am trying to self study algorithms and this is my attempt at topological sort using Tarjan's version of DFS. It runs correctly for the graph I included. Can someone tell me if this is correct and if/...
3
votes
1answer
34 views
3
votes
2answers
84 views
CLRS Implementation of BFS and DFS in C++
I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code?
GraphStructures.h
...
1
vote
1answer
34 views
Tarjan's strongly connected components algorithm
Can anyone suggest to me how I can make this "nicer"? If you can see any glaring details that I could change to speed things up too, that would be great -- though it's not priority.
...
3
votes
1answer
58 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
1answer
96 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
39 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.
...
3
votes
1answer
36 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
34 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
39 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
26 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
32 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
54 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
73 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
85 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
132 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
46 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
53 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
142 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 ...
1
vote
1answer
52 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
28 views
4
votes
0answers
48 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
38 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
39 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
67 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
91 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
143 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 ...
1
vote
1answer
166 views
A*, Uniform cost and Greedy Best first search implementations
I am writing the code for A*, Uniform cost search and Greedy best first search algorithms in Java. I have finished the code which is working fine but I have used a bit different design strategy while ...
2
votes
1answer
54 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
103 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
170 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
58 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
70 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
183 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
32 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
197 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
151 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
190 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
122 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
44 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
118 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
129 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
19 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 ...
2
votes
1answer
937 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 ...
