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
2answers
97 views
Dijkstra's algorithm in JavaScript
I'm trying to implement Dijkstra's algorithm to find the shortest path. This is from a challenge on CodeWars.
In this scenario there is a map:
...
4
votes
1answer
47 views
8
votes
2answers
154 views
Rock, Paper, Whatever - A small commandline game
My rational for this program, was to learn more of Python's standard library, I didn't actually know cmd was even in it until I started this program. It's also the ...
4
votes
2answers
29 views
Split DAG into disjoint sets
I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding ...
3
votes
1answer
34 views
Circle check algorithm optimization for directed graph
Here is my two versions of code to check if there is a circle for a directed graph. Any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are highly ...
1
vote
1answer
79 views
Leetcode 210. Course Schedule II
Problem statement
There are a total of \$n\$ courses you have to take, labeled from
\$0\$ to \$n - 1\$.
Some courses may have prerequisites, for example to take course \$0\$
you have to ...
2
votes
0answers
15 views
Modeling a control polygon for a piecewise spline curve
Aim
I'm modeling a control polygon for a piecewise spline curve. Each sub-spline is defined by a location the spline must pass through, as well as a forward tangent, and a backwards tangent. The ...
2
votes
1answer
84 views
Representing an adjacency list (graph) using a hash table of lists
While writing a C++ implementation for weighed, labeled graphs, I started to doubt the effectiveness/correctness of my chosen structure and I would like to hear some reviews.
I tried to implement the ...
0
votes
2answers
69 views
BFS in a grid with wall breaking saldo in Java
In this problem, we are given a 2-dimentional grid, with each cell being walkable or holding a wall. Given an integer \$s \geq 0\$, find the shortest path from the source node to target node breaking ...
2
votes
0answers
50 views
Second degree connection ranking
Problem
Find 2nd degree connections ( friends’ friends), output these 2nd
degree connections ranked by number of common friends (i.e 1st degree
connections) with you, (example: if 2nd degree ...
6
votes
1answer
76 views
Minimum number of flight segments using breadth-first search
I'm practising with graphs, and trying to solve a problem of calculating the minimum number of flight segments, applying breadth-first search.
The code is working, but I think, that it's not clean.
...
7
votes
1answer
125 views
Hackerrank - value of friendship (II)
Problem statement
You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no ...
3
votes
1answer
79 views
Eulerian Path algorithm
I'm doing a project to find the Eulerian path. Cane someone find an example where the algorithm is wrong? The function EulerianPath recursively prints the Eulerian ...
5
votes
1answer
181 views
Hackerank - value of friendship
Problem statement
You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no ...
3
votes
0answers
42 views
Tarjan's strongly connected component finding algorithm
Here is my code for Tarjan's strongly connected component algorithm. Please point out any bugs, performance/space (algorithm time/space complexity) optimization or code style issues.
...
0
votes
0answers
24 views
Prosemirror AST -> Pandoc AST converter
This converts from Prosemirror AST to Pandoc AST, and I am having some issues with the complexity of the code, and want to simplify it and make sure I am not doing anything silly.
Essentially, I am ...
4
votes
2answers
96 views
Implementation of a graph in Java
A long time ago I posted my implementation of directed graph is Java. Recently I took a look at @coderodde's implementation and decided to write an implementation of undirected graph and directed ...
2
votes
0answers
68 views
unordered_multimap approach to adjacency list and graph search
I'm looking for suggestions on how to improve the usage of modern C++ features with this simple graph search algorithm, particularly with regard to the use of STL containers and lambda expressions.
...
4
votes
2answers
90 views
Dijkstra's algorithm using priority queue running slower than without PQ
I need to implement dijkstra's algorithm and I've done so using this Wikipedia page. I've done it both with priority queue and without.
Both versions work 100% correct, however I need the faster one ...
4
votes
1answer
51 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 ...
4
votes
2answers
93 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
91 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
52 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/...
4
votes
1answer
80 views
3
votes
2answers
87 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
58 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
79 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
107 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
45 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
44 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
36 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
63 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
48 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
46 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
65 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
126 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
111 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
169 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
62 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
67 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
200 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
101 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
50 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
54 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
52 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
70 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
106 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
201 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 ...
