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
60 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
34 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
30 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
54 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
28 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
43 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
47 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
28 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
125 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
61 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
59 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
50 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
0answers
27 views
Depth Limited Search for Map Coloring Graph in Python [closed]
Hey I'm trying to solve the Map Coloring Problem using a Depth Limited Search. I found an example of the problem here (https://courses.cs.washington.edu/courses/cse473/10au/slides/chapter05-6pp.pdf), ...
1
vote
2answers
53 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.
...
1
vote
1answer
34 views
Check directed graph is tree or not
Here is my approach.
1. Checking there is no cycle.(Using BFS)
2. All nodes are connected. (visited)
...
3
votes
0answers
59 views
CLRS(Introduction To Algorithms) implementation of BFS and DFS in Java
This is the implementation of BFS and DFS i have tried to follow from CLRS.Please suggest what can be improved in this code.
...
0
votes
2answers
58 views
Check if path exists directed graph, without using collection
I have written code to find whether the path exists between source and destination in a directed graph. I have used BFS and instead of ArrayList or queue. I have ...
5
votes
1answer
72 views
Find the largest continuous descending sum in a 2d matrix
Given a 2d array, the problem is to find the largest sum, where each subsequent is >= the previous digit but < all of the 'neighbour' digits. You can only move up, down, left and right.
My ...
2
votes
1answer
70 views
Finding smallest number of moves
We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this:
...
5
votes
3answers
385 views
“Researcher Hatim is right or wrong” challenge
I wrote a program to solve a problem, I am not so good in python so want help to find areas where this program can be improved or simplified and readable too:-
I got this problem in a code challenge
...
2
votes
1answer
74 views
Find all the countries I can visit by just crossing direct borders
I was helping on this question. There you have a table border to indicate countryA and countryB have a common border. And want ...
1
vote
1answer
78 views
Computing the distance and weight matrix of a graph
I would like to create an igraph object. First, I set up the size of igraph object — n, m, then create a random matrix. As a result matrix ...
2
votes
0answers
68 views
Dijkstra algorithm implementation in F#
I'm trying to implement Dijkstra algorithm in F# for finding the shortest path in a undirected tree using a heap.
I've used the type PriorityQueue found here and the code can be found here.
...
2
votes
0answers
75 views
Dynamic graph in C++11 with shortest path algorithm
I've been designing a dynamic graph to improve my understanding of C++11. The dynamic aspect means that it could represent the hyperlink structure of a chunk of the internet, with node deletion ...
11
votes
1answer
102 views
Glue Shredded Pieces (CodeEval)
I have solved problem 185 on CodeEval, Glue Shredded Pieces.
The solution got a 100% score on all tests (edit: see comments), within the allotted time and memory constraints. I'm looking mostly ...
1
vote
1answer
112 views
Iterative depth-first search and topological sort in Java
This is the iterative depth-first search, that does not abuse the stack. Also, I gathered some information from DFS that may be useful; for example, I am able to do topological sort using the result ...
1
vote
1answer
75 views
3
votes
1answer
64 views
Simple data structures for representing graphs in Java
Motivation
I do a lot of graph-theoretic code, and, by now, I feel substantial need for data structures that can represent weighted graphs, both directed and undirected. Up till now, I was in a habit ...
1
vote
2answers
97 views
Traversing a stack in my DFS algorithm for finding a path in a maze
I am trying to get this code running as fast as possible when traversing through my stack of my DFS currently the input files are like so:
...
1
vote
0answers
33 views
Prim's MST implementation
This is my full working code. I am a bit confused about how I was able to use the structure MinHeapNode's variable in my Graph.cpp file. I used its ...
5
votes
0answers
103 views
A generic implementation of Dijkstra
Here is an implementation of Dijkstra
As an rags-to-riches version of this Object oriented approach to Dijkstra's algorithm
...
1
vote
2answers
116 views
Object oriented approach to Dijkstra's algorithm
I'm seeking a code review for the following C++ implementation of Dijkstra's algorithm. I'm trying emphasize code reusability and extensibility but performance is also potentially important.
...
3
votes
1answer
80 views
Prove that the graph is a valid tree in Python
I recently solved this leetcode problem:
Given n nodes labeled from 0 to n - 1 and a list of undirected edges
(each edge is a pair of nodes), write a function to check whether
these edges ...
5
votes
2answers
63 views
Bob the (Graph) Builder
I'm starting a project in which I'll generate random graphs and use algorithms to solve them. The first necessary step is obviously to build a graph.
My graph has the following characteristics :
...
5
votes
0answers
146 views
Graph as adjacency lists: BFS DFS Topological Sort
I have written some code to practise graphs. Graph is represented as vector<list<int>> . Would you share some feedback with me?
Are algorithms correct ...
14
votes
2answers
255 views
All your bases are belong to Dijkstra
CATS, willing to get a hold of all the bases, asked Dijkstra to give him a hand designing the most powerful algorithm to reach all bases with the least distance travelled.
I tried to implement ...
7
votes
1answer
160 views
Graph theory using C++ STL
I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object.
Any feedback would be ...
10
votes
1answer
111 views
Simple Oriented Graph implementation in Java
I wanted to implement a simple oriented graph as part of an exercise in both Object Oriented Programming and Data Structures. I wanted to make it as class-focused as possible, so I don't know if my ...
8
votes
2answers
404 views
C++ Graph Implementation
My data set is a list of Edges which are passed as a pair of integers. Based on that, I have the following graph implementation for BFS. Could someone please review ...
4
votes
2answers
46 views
Vertex cover approximation in JavaScript
I believe this runs in \$O(V+E)\$ but I wouldn't be able to explain the reasons why. I was looking for some general code review and any help on understanding the runtime.
...
2
votes
0answers
18 views
Return the Euler Cycle for a graph with es6
My algorithm for finding an Euler tour of a digraph, G⃗, if such a tour exists, starting from some vertex, v.
...
4
votes
3answers
95 views
Finding a loop in a directed graph in Python
I wrote this code to find if a directed graph contains a loop or not. I am pretty new to graphs and I saw some examples on the internet but couldn't actually understand their implementations. So I ...
3
votes
0answers
391 views
Depth first search implementation
I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the depth first search section (5.8) using javascript. Note you can execute the code here if you don't ...
2
votes
1answer
78 views
Graph radius in Java - follow-up
See the previous and initial iteration.
Terminology
Given an undirected graph \$G = (V, E)\$, the eccentricity of a node \$u \in V\$, \$e(u)\$, is the maximum length (number of edges) of a shortest ...
6
votes
1answer
155 views
Breadth first search implementation (also includes functions for finding shortest path and number of connected components)
I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the breadth first search section (5.7) using javascript. I also have a ...
1
vote
1answer
92 views
Graph radius in Java
(See the next iteration.)
The following snippet is a brute-force algorithm for computing a graph radius in time \$\Theta(V^2 + VE)\$ and space \$\Theta(V)\$ simply by doing \$|V|\$ breadth-first ...
2
votes
1answer
132 views
Graph Interface: Storing Vertices in an Array vs HashTable
I have just started learning graph algorithms and am trying to arrive at an ideal interface. I understand that this code will not be used anywhere else (I will certainly use Boost::Graph) but I just ...
1
vote
0answers
136 views
Random Contraction Min Cut (Karger) - performance issues
(Offtopic note: I can't add a "networkx" tag.)
I reworked an old algorithm, this time not implementing the graph on my own, but building on the networkx module.
Script works fine for the tests and ...
3
votes
1answer
50 views
Finding all backedges in an undirected graph
I have tried to implement the DFS algorithm to find all the back-edges in a graph that lead to a cycle in the graph:
...
2
votes
1answer
132 views
BFS for modified shortest path
Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of ...
