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.

learn more… | top users | synonyms

9
votes
1answer
46 views

Detecting cycles in a directed graph without using mutable sets of nodes

I recently came across the classic algorithm for detecting cycles in a directed graph using recursive DFS. This implementation makes use of a stack to track nodes currently being visited and an extra ...
5
votes
1answer
63 views

Sort a scrambled itinerary (Google apac test problem)

This is my first time writing ruby - and I was mainly hoping to get some feedback and stylistic pointers. The algorithm is pretty straight-forward, since Google guarantees airports aren't repeated I ...
0
votes
1answer
25 views

Shortest path algorithm in 0-1-unoriented graph

I have an unoriented graph with n vertices and m edges, 1 <= n, m <= 100000. All edges ...
3
votes
1answer
73 views

Graph data structure implementation

I just started using C++, and I was wondering if my code fits the standards so far. Specifically, I was wondering if I did the addEdge, ...
8
votes
1answer
115 views

A rapidly-growing script that visualizes WiFi sniffing

Below is one of the versions of my wifimap script: ...
1
vote
0answers
34 views

Graphs processing in Scala

I've just started to learn Scala and decided to implement small graph library to train. Here is the basic version, that describes graph and nodes structure and also provides implementation of ...
1
vote
2answers
59 views

Data loading Hash Map

I'm trying to improve my code's performance, and I've found an area where the execution time is being significantly increased. I've had a look through the code but I can't see how I can improve it. ...
0
votes
1answer
49 views

Plotting a trigonometric function appears to be too slow

This calculates the mobility and it's derivative of one element. If I calculate with 1 value of w, it's very fast. ...
2
votes
1answer
76 views

Graph representation using adjacency list for BFS, DFS, and Karger's algorithm

I want to implement some graph algorithms for learning purposes (e.g BFS, DFS, Karger's min-cut algo) and before diving into them I want to make sure I have got the graph representation right (using ...
2
votes
2answers
81 views

Implementing Directed and Undirected Graph in C++

I am learning C++ and I decided to implement a Directed and UnDirected graph. (I haven't learned how to do inheritance yet, so they are distinct classes.) I have not handled any error cases (i.e. ...
1
vote
2answers
37 views

A* versus Bidirectional Dijkstra's algorithm

I have added bidirectional Dijkstra's algorithm into my pathfinding "framework", and I would like to make good use of C++ programming idioms, eliminate all possible memory leaks, otherwise improve ...
2
votes
1answer
56 views

Generic pathfinding framework in C++

I have this generic framework for finding (weighted) shortest paths. Also, the program demonstrates the performance of A* and Dijkstra's algorithms on a directed weighted graph. Both run in ...
3
votes
1answer
59 views

Yet another graph search

I noticed there were already countless implementations of graphsearch procedures on here, but there were a couple of features of my approach that I haven't seen in the others, plus I would greatly ...
1
vote
3answers
141 views

Adjacency matrix on undirected graph

Please review my Adjacency Matrix class based on this code. Since I use std::vector to create the matrix, I would like to store as many nodes as possible. Is it ...
1
vote
1answer
70 views

Creating an adjacency list in C++

I want to create an adjacency list based on data I get from a text file. Could I make this simpler? ...
3
votes
1answer
75 views

PHP implementation of “depth-first search” on the graph data structure

As I am a totally self-taught 'person writing code', I decided to learn algorithms with one online course that taught them using Java for demonstrative purposes. The first topic I covered is the graph ...
5
votes
1answer
85 views

Strongly connected components, component graph, semiconnected graph and new graph from SCCs

I have written a program in C to do the following: Read a matrix (in file format, first line you have the size, then next are the entries). This is done by the "input" function. Find the strongly ...
2
votes
2answers
95 views

Graph adjacency list implementation in C++

I have been playing around with an adjacency list implementation of a graph class, on which I'd like to be able to run a build and test several graph algorithms. The code I have below works and I have ...
3
votes
1answer
793 views

Shortest path using Breadth First Search

I have sample graphs like the following(Un-directed un-weighted cyclic graphs). My goal is to find shortest path between a given source and destination. ...
3
votes
1answer
66 views

Graph Adjacency List

Spent some time implementing a graph as an adjacency list. Looking for suggestions on how to improve this implementation. ...
1
vote
2answers
64 views

Passing text through a network of transformation modules (task #4)

About a year ago, I was given a C++ assignment as a preliminary job-interview test. The assignment included 4 different tasks, from which I had to choose one. I actually chose and completed 3 out of ...
2
votes
2answers
85 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: ...
2
votes
1answer
1k 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? ...
1
vote
1answer
79 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
97 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
21 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
50 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
178 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
109 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
300 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
119 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
60 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
89 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
46 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
74 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, ...
3
votes
1answer
643 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
298 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 ...
2
votes
4answers
3k 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
55 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
75 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 ...
2
votes
1answer
76 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
110 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
98 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 ...
10
votes
1answer
307 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
38 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
59 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
274 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
284 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
483 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
79 views

Very slow graph walking

My code is very very slow. Could you give me hints on how I can make it much faster? ...