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.
-1
votes
0answers
17 views
find shortest path with SPFA [closed]
I want to use Spfa to find the shortest path in a undirectly graph, and use linked list to store the graph, [ statement : find the shortest path between A and G(1st node and last node), we have the ...
2
votes
2answers
50 views
DFS Undirected Graph Code
The code included below was written in response to a programming exercise that was sent to me by a company that I am applying to. The purpose of the code is explained at the following link: ...
3
votes
1answer
81 views
Depth First Search and Breadth First Search in C++
I am trying to learn DFS and BFS. However, I just want to make sure that I am not doing anything wrong. Would you please determine if the BFS and DFS functions are correct?
...
0
votes
1answer
35 views
Networkx VS graph-tool
I'm working on graph mining, so I'm trying to find the best library to do that.
I've read in here that "graph-tool" is faster, so I tried the same program who count the duplicated graphs (I call them ...
2
votes
0answers
58 views
Efficient compile-time directed graph
During my research in Rigid Body Dynamics, (where Contact Graphs are used to solve the contact problem) I came across the question if it is possible to define at compile time a directed graph (class) ...
1
vote
0answers
13 views
Removing Graph Nodes of a Specific Type and with Exactly Two Neighbors
Problem Description
I am working with an undirected, weighted graph. It contains two types of nodes, called "A-type" and "B-type". I am starting with a set of ...
1
vote
0answers
47 views
Minimum amount of edges that needs to be traversed to visit all vertices… or something like that
So I have this problem, where I'm given m connections over n vertices. The vertices are labeled ...
4
votes
1answer
88 views
Shortest path through a maze
I was trying to solve this problem in Java:
Given a 2-D array of black and white entries representing a maze with designated entrance and exit points, find the shortest path from entrance to exit, ...
1
vote
1answer
53 views
Creating a graph in Java
I'm building an application that implements the A* algorithm to calculate a route between two rooms. I am trying to create a graph which the algorithm can operate on and I am not sure if this is the ...
2
votes
0answers
34 views
Directed Acyclic Graph with topological sort
I have here a class which represents a directed acyclic graph (Graph) and a vertex in the graph (Vertex).
The vertices are ...
3
votes
2answers
52 views
Determining if there is a route between two nodes in a directed graph
This algorithm should return a boolean value, telling if there is a path between two nodes in a given directed graph.
...
2
votes
1answer
45 views
Improving time complexity of cheapest travel route algorithm
Below is the code to find the cheapest route for a passenger. stationsUnexplored is a Queue to which stations are added and ...
3
votes
0answers
45 views
Bidirectional Edmonds-Karp algorithm in Java
The Edmonds-Karp algorithm relies on breadth-first search in order to find an augmenting path in the residual flow network. This version of the algorithm uses bidirectional breadth-first search in ...
3
votes
0answers
44 views
Edmonds-Karp algorithm for maximum flow in Java [duplicate]
I have this implementation of Edmonds-Karp algorithm for finding maximum flow in networks. It runs in \$\mathcal{O}(VE^2)\$ time.
What do you think?
AbstractMaximumFlowFinder.java:
...
2
votes
0answers
40 views
Kruskal's algorithm in Java - follow-up
The previous and initial iteration at Kruskal's algorithm in Java
Now what I did is remove the fields and let the actual Kruskal-routine create the required data structures in the local scope, ...
2
votes
1answer
114 views
Dijkstra's algorithm in Python
I was hoping that some more experienced programmers could help me make my implementation of Dijkstra's algorithm more efficient.
So far, I think that the most susceptible part is how I am looping ...
3
votes
3answers
132 views
Pouring water between two jugs to get a certain amount in one of the jugs
I wrote a solution for a jug problem (given two jugs of water of different sizes find the steps needed to get specific amount of water in one of the jugs). I'm hoping for some input on my code. How ...
1
vote
4answers
836 views
Depth-first search in Python
I wrote this DFS in Python and I was wondering if it correct. Somehow it seems too simple to me.
Each node is a class with attributes:
visited: Boolean
...
1
vote
0answers
35 views
Max independent set of a sequence
This is the code I've written to find the maximum-weight independent set of a graph path. It's a standard problem with a well-known dynamic programming solution of linear complexity. Since it's a ...
4
votes
0answers
57 views
Finding cycles in a graph that pass through a vertex at most k times
I have a project that relies on finding all cycles in a graph that pass through a vertex at most k times. Naturally, I'm sticking with the case of k=1 for the sake of development right now. I've come ...
1
vote
1answer
64 views
Calculating Euclidean distance and performing unit-testing
The method creates a link, an edge between two nodes, and calculates the Euclidean distance.
I'm testing that after linking, the link does indeed exist, and that the distance is correct.
I've used ...
1
vote
1answer
96 views
What could I possibly change with this BFS and code to enhance its performance?
This code is supposed to find, in a graph, the node with the smallest maximum distance to all the other nodes. The problem can be found here.
For instance, in this example graph:
2 is the node ...
0
votes
1answer
45 views
Iteratively-Deepening Depth First Search (queue and non-queue)
I am aware that most 'generic' BFS algorithms that use a queue also check for uniqueness of visitation to 'speed things up' as it were, but I'm a bit unclear as to how to implement such a method as ...
5
votes
0answers
102 views
Graph implementation adjacency list 2.0
Version 1:
Graph implementation adjacency list 1.0
Please note the following:
All edges are directed
A user of the class Graph shall never be able to aces an object of type ...
2
votes
1answer
33 views
Parsing DAG from text
This module allows to parse indented text file into Map from node to child nodes identified by Coordinate. This module seems way ...
2
votes
1answer
49 views
Small generic path search framework in Java
I have this small generic path search library. It's not perfect at all, so I need some comments as to have a chance to improve it.
com.stackexchange.codereview.graph.model:
...
3
votes
2answers
124 views
Implementation of Dijkstra's algorithm to find the shortest path in graph
This is my implementation of Dijkstra's algorithm in C++.
Please clarify
Whether the class design is proper or if it needs to be improved.
I am just hard coding the vertex based on the priority of ...
2
votes
1answer
107 views
Optimizing for data import in Neo4j using py2neo
Here is my code for importing from a .csv to a neo4j graph using py2neo and cypher statements. I've noticed that it slows down significantly the bigger the graph gets. It takes several seconds just to ...
4
votes
0answers
143 views
Dijkstra's algorithm in PHP
This is Dijkstra's algorithm in PHP. Regarding the data structure, I use a 2-dimensional array $_distArr[m][n]=length to store it. Are there any improvements for ...
2
votes
1answer
77 views
Very slow graph walking
My code is very very slow. Could you give me hints on how I can make it much faster?
...
7
votes
2answers
204 views
Kruskal's algorithm in Java
I have this Java implementation of Kruskal's algorithm. It solves a tiny problem instance correctly, yet I am not quite sure, whether my implementation is correct.
The code as follows:
...
2
votes
1answer
166 views
Graph implementation adjacency list 1.0
Please note the following:
All edges are directed
Removal of edges/nodges is not implemented yet
A user of the class Graph can never (hopefully) access a ...
-1
votes
2answers
87 views
Cycles of pointers
I'm really inexperienced with cycles, so I want to make this code shorter. As far as I know, I've made a recursive cycle.
...
1
vote
0answers
32 views
A scalable function for get boundary vertices in a graph
Given a community division I need a list of vertices that have edges in more than one community, i.e., boundary vertices.
I've tried this:
...
7
votes
3answers
89 views
Removing equivalent authors in a list
I have a list of authors, where seeking duplicity. The indexes of these duplicates are stored in a list of lists named duplicity. For example, at index 0 in the list duplicity is nested list, which ...
1
vote
1answer
127 views
Minimum Spanning Tree using Prim's algorithm and an indexed minimum priority queue
I have written some basic implementation of a Minimum Spanning Tree using a indexed minimum priority queue.
For the implementation of the Priority Queue I used Sedgewick's Tutorials.
However, it seems ...
3
votes
1answer
2k views
Shortest path Dijkstra's algorithm
I'm trying to implement Dijkstra's algorithm to find the shortest path from a starting node to the last node of a 250px by 200px raw image file (e.g. starting node = [0][0], ending node = [250][200]). ...
3
votes
1answer
244 views
Prim algorithm implementation for adjacency list represented graph
Please review the implementation of Prim algorithm. Points on which I have doubt:
My Graph doesn't have any ID for nodes. Nodes are accessed based on their data. ...
1
vote
0answers
204 views
Kruskal algorithm implementation for adjacency list represented graph
Please review the implementation of Kruskal algorithm. Points on which I have doubt:
My Graph doesn't have any ID for nodes. Nodes are accessed based on their ...
3
votes
0answers
79 views
Djkistra shortest path implementation for adjacency list represented graph
Please review the implementation of Djkistra algorithms. Points on which I have doubt:
My Graph doesn't have any ID for nodes. Nodes are accessed based on their ...
2
votes
1answer
53 views
Extracting a subgraph
Given a huge graph, I want to traverse it, in the fastest way possible, and extract a subgraph with the following properties:
the starting node is specified
the maximum number of elements and max ...
1
vote
1answer
63 views
MinCostMaxFlow implementation is not fast enough
I'm trying to solve this problem:
A root tree is a directed acyclic graph that contains one node (root),
from which there is exactly one path to any other node.
A root tree is binary if ...
5
votes
2answers
240 views
Constructing a graph and performing a depth-first traversal
Please review the use of pointers and design in graph construction code and its depth first traversal. I haven't used smart pointers as I want to understand any issues in following implementation with ...
0
votes
3answers
408 views
Dijkstra in C++ to find shortest path for every vertex of a directed graph
I am trying to implement the Dijkstra algorithm in C++ that finds the shortest path for a graph from a text file. The text file contains a matrix that represents a directed graph.
What I am trying ...
10
votes
2answers
177 views
Is this Bridges code F# idiomatic?
Introduction
I'm primarily a C# programmer, just starting out with learning F#. I found myself with a problem which felt like it was appropriate for a functional language, and now that I have the ...
5
votes
1answer
170 views
Adjacency-list graph implementation in C++ (redone from scratch)
I had posted here before, but I decided that the approach used earlier - where every Vertex stores a vector of pointers to ...
0
votes
2answers
460 views
Optimizing Dijkstra implementation using PriorityQueue in Java
I am trying to make Dijkstra implementation more efficient. Below is the code for class Node which implements Comparable so it ...
3
votes
1answer
91 views
Improving efficiency of Prim's Algorithm
I have implemented Prim's Algorithm in Java. I am wondering how it can be made more efficient.
Below is the class Node for vertices.
...
4
votes
2answers
374 views
Minimum Spanning Tree using Prim's algorithm
I have implemented a Minimum Spanning Tree using Prim's Algorithm. Could someone give some about some improvements for code structure, conventions, performance, etc?
...
2
votes
2answers
108 views
has_cycle in directed and undirected graphs
I wrote a program that can tell if a graph has_cycle or not.
Can you please suggest more elegant and eloquent ways for this program?
(Perhaps better ways to represent a graph with vertices and ...
