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

2
votes
0answers
33 views

Dijkstra's algorithm in Python [on hold]

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 ...
0
votes
0answers
44 views

Weekly report of control charts [on hold]

I am looking to make this macro run faster and more efficiently (less code). I have a weekly report of control charts that was handed down to me and I am looking to automate it. Pulling in the data ...
3
votes
3answers
92 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
175 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
20 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
46 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
50 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
78 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
26 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
83 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
28 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
43 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
83 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
43 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
56 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
75 views

Very slow graph walking

My code is very very slow. Could you give me hints on how I can make it much faster? ...
3
votes
0answers
85 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
137 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
29 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
83 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
89 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
566 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
138 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
148 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
67 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
52 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
60 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
208 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 ...
-1
votes
3answers
285 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
171 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 ...
4
votes
1answer
144 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
230 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
78 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
315 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
91 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 ...
5
votes
3answers
475 views

Trip Advisor - Train routes

Gives advice to the user on which trains to take to reach a destination ...
5
votes
2answers
190 views

More optimized approach of Dijkstra's algorithm

I need a graph-search algorithm that is enough in our application of robot navigation and I chose Dijkstra's algorithm. We are given the gridmap which contains free, occupied and unknown cells where ...
6
votes
1answer
138 views

Breadth First Search not SOLID enough v2.0

Here is a link to my original question: Breadth First Search not SOLID enough Here is my first attempt at refactoring. Instead of using a Tuple, I used a ...
5
votes
2answers
754 views

Graph vertex class implementation with adjacency lists

I wrote an implementation of a graph with each vertex storing a std::vector of vertices it's adjacent to. Please critique this. ...
1
vote
1answer
143 views

Speed optimization for girth-counting algorithm

I have the following girth-counting algorithm on a large 0-1 matrix and I need to optimize it for speed: ...
5
votes
1answer
229 views

Implementing graph search

I am very new in Python, I would like to know if the style presented below attends a good implementation in Python. ...
4
votes
2answers
119 views

Efficiency and design of Dijkstra's algorithm modified for connected nodes

I've written an AI (well... it's not really that intelligent) that plays the board game Ticket to Ride. In that game, cities are essentially nodes of a graph, linked together by train tracks (the ...
3
votes
1answer
62 views

Comparing data to model and returning a chi squared value

This is quite basic but useful to test various (9) different models using one set of data. I have tried to make it clear and use the PEP8 formatting. I am currently creating a version that can read ...
4
votes
1answer
327 views

Graph (adjacency list) for BFS and DFS in Golang

I am trying to implement a Graph data structure in Golang and choose to use adjacency list representation. When starting to implement adjacency list, I have an idea ...
4
votes
1answer
73 views

Detecting connected acyclic through Tarjan strongly connected components variant

I want to verify that a given directed graph is connected and acyclic (DAG). I have implemented a modification of the Tarjan's strongly connected components algorithm in imperative style (as the ...
7
votes
1answer
242 views

Topological Sort and Graphing in Python 3

I wrote a program for DFS traversal, topological sort, find all vertices, and has_cycle methods. Can you please suggest more elegant and eloquent ways for this program? (Perhaps better ways to ...
6
votes
1answer
314 views

Getting all likes from a specific user on a news wall with fewer graph API calls

Right now, my solution counting likes of a specific user is Starting a recursive call on the "/{user-id}/posts" edge Iterate through all posts On each post iterate through each like on the likes ...
6
votes
1answer
595 views

Finding all paths from a given graph

I need to find all paths from a given graph. I can do that for now, however my recursive code is not efficient and my graphs are very complicated, hence I need a better algorithm. ...
6
votes
1answer
73 views

Extracting nodes from a road network

My code takes 143.023 seconds for extracting nodes from a road network of city like Göteborg in Sweden. Please check it out if I can optimize it. ...