Questions tagged [graph]

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.

Filter by
Sorted by
Tagged with
4
votes
1answer
2k views

JFreeChart Dynamic Scatter Chart

I have a model that consists of a 100 'agents' that change their x and y coordinates randomly. I use JFreeChart scatter chart to represent agents' locations. ...
10
votes
2answers
2k views

Missing level of technical depth (Common Ancestor)

I recently have given a coding test in a reputable IT company. There were three coding questions. They refused me by saying that as we felt they didn't demonstrate the level of technical depth we'...
8
votes
1answer
2k views

Escaping the prison - finding the shortest way

I have given an assignment where I have to escape a labyrinth. The goal is to find the shortest way. I have done some research and there seem to be two strategies to solve the problem: the Depth-first ...
3
votes
1answer
366 views

Neo4J Rest Javascript wrapper

As a toy project, I started evaluating the Neo4J graph database and its Rest interface. I'm trying to write a simple graph visualization in JavaScript. In daily business I'm a Java developer and maybe ...
8
votes
3answers
7k views

Depth First Traversal of a Graph

I am learning how to implement a basic undirected graph and perform a depth first traversal. Please critique my code for correctness, best practices, security, and any other comments that may be ...
23
votes
4answers
185k views

Depth First Search & Breadth First Search implementation

I've implemented DFS and BFS implementations. I want to check if the code is readable, contains any issues, and can be improved. GraphImplementation ...
8
votes
1answer
3k views

Tarjan's algorithm for Strongly Connected Components without keeping SCC in stack

I've been looking for an implementation of Tarjan's algorithm in C#/C++ for a strongly-connected components in graphs, and couldn't find any implementation without use of additional Stack - most of ...
2
votes
1answer
111 views

Lift ball which leads to shortest height

There are n balls kept on a table and connected by same singe connected string (which can be cyclic or maynot). Write the code to select a ball such that after lifting the whole structure from that ...
5
votes
1answer
2k views

Strongly connected components algorithm

In my Python application, I am using Tarjan's algorithm to compute strongly connected components. Unfortunately, it shows up under profiling as one of the top functions in my application (at least ...
6
votes
2answers
869 views

Clone of an undirected graph

Perform a graph clone. Verifying complexity to be O(E). Looking for code review, optimizations and best practices. ...
3
votes
1answer
556 views

Clone an undirected graph

I'm looking for code-review, optimization and best practices. Also verifying complexity to be O(E) time and O(V+E) space complexity. ...
6
votes
2answers
5k views

Ford-Fulkerson algorithm

Solved the ford-fulkerson algorithm, which is too vast to explain it comprehensively here. Check Wikipedia for Ford-Fulkerson and Princeton lecture on Ford-Fulkerson. Looking for code review, ...
22
votes
3answers
30k views

Find all paths from source to destination

Given a directed connected graphs, find all paths from source to destination. Looking for code review, optimizations and best practices. Also need help figuring out complexity, which in my best ...
1
vote
0answers
43 views

Completing a Graph in Scheme

For the record, this is part of a homework assignment, but I have already implemented a solution. I am simply wondering if there is a better way to do it. Background: I am asked to write a procedure, ...
15
votes
1answer
17k views

Topological sort in Java

I am learning algorithms in graphs. I have implemented topological sort using Java. Kindly review my code and provide me with feedback. ...
5
votes
2answers
7k views

Constraint Programming: Map color problem

I've written some python code to solve the map coloring problem. In my code, I represent the problem using Territory and MapColor...
6
votes
1answer
974 views

Dijkstra-like routing algorithm

I've got the following code to find the shortest path between two nodes using almost-Dijkstra's-algorithm which was written for an exercise, and I'm looking for things to improve my general Scala ...
4
votes
1answer
130 views

Maximize the number of nodes that could be reachable in a graph

Description of my code: I am trying to maximize the number of nodes that could be reachable in a graph. Please do not consider my main algorithm, I want it to be like that. The only parts that I need ...
5
votes
1answer
425 views

Modified BFS code optimizations

I need some help reviewing this code in terms of making as fast as possible. This is a modified version of BFS that does quite a bit of processing on the side. Use case: I have a large graph (...
3
votes
1answer
379 views

Actionscript Graph data structure implementation

So, I am not sure if I should have Vertex extend Point, because the equals() and ...
5
votes
1answer
737 views

Dijkstra's and Prim's algorithms: correctness/efficiency

This is in preparation for a competition that only allows C++03. ...
6
votes
1answer
15k views

Code to construct a complete graph

I have tried to design a class for a complete graph. Needless to say, disadvantages of my current solution are very visible: dependent inputs have led to verification headaches. In this code we ...
29
votes
4answers
76k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
8
votes
2answers
8k views

Check if directed graph contains a cycle

I have solved the question, and in turn felt the need to get it reviewed. Any suggestions for clean up and optimization would help. Also please verify my complexity: \$O(V + E)\$. ...
4
votes
2answers
1k views

STL and Dijkstra's algorithm optimization

This is the problem and my solution to this is: ...
5
votes
1answer
8k views

Prims algorithm implementation

Review this code regarding optimization, cleanup, and best practices. ...
14
votes
2answers
78k views

Coding and printing a graph

This is my first attempt at putting the conceptual knowledge I've gained about graphs into code. When searching for examples they all seem overly complicated, and searching for a tutorial or ...
6
votes
2answers
915 views

How to improve this algorithm for building a graphs closures

We have a large directed acyclic graph and a requirement to filter it by allowing a user to select certain nodes and then we remove all nodes that are not selected nodes, ancestors of those nodes, or ...
2
votes
1answer
621 views

Applying Dijkastra's algorithm on a graph of five nodes

Last week I posted a piece of code to apply Dijkastra algorithm to calculate the shortest path between to nodes in a graph. Now, I've made some improvements, but I am still having difficulties. I ...
3
votes
1answer
14k views

Implementation of Prim's minimum spanning tree

Feel free to tell about every possible issue (style, errors, inffective solution etc.) you found. Here is the main part of what I want to be reviewed, through there is some related code on GitHub. ...
1
vote
2answers
794 views

DFS algorithm with generators

Background: I was working on a project were I needed to write some rules for text-processing. After working on this project for a couple of days and implementing some rules, I realized I needed to ...
3
votes
1answer
151 views

Review/rate my new graph class

I have written a PHP class called "graph". It is a class that performs RESTful-like commands to a MySQL database. I have posted the GitHub repo. Here is the code as well: config.php ...
7
votes
3answers
31k views

Implementation of Dijkstra's algorithm

Please pick my code apart and give me some feedback on how I could make it better or more simple. ...
0
votes
1answer
236 views

2003 Canadian Computing Competition, Stage 1 ; Why Is My Solution Invalid?

I am doing old versions of the Canadian Computing Competition, on a website where I can run my solution against some test cases they have. I am failing one of their test cases, and cannot figure out ...
6
votes
1answer
701 views

Shortest Path in a Unit Cost DAG BFS in Hadoop

Just got done implementing a shortest path algo of a unit cost DAG BFS in Hadoop and wanting to get anyone's opinion on how I could have done it better. The main issue I see is that I lose the ...
4
votes
1answer
2k views

Do I need to delete a vector?

I want to make a graph from input from a text file in the format: vertex1 vertex2 cost time where vertex1 and vertex2 are strings that form an edge and cost and ...
4
votes
1answer
1k views

Digraph Code in Java

This is used to create a directed graph of type T. The directed graph has edges and vertices with values but is directional such that nodes can loop unto ...
10
votes
1answer
12k views

BFS and DFS in Scala

I would love it if someone could give me some suggestions for these 2 graph search functions. I am new to scala and would love to get some insight into making these more idiomatic. ...
1
vote
1answer
2k views

Finding strongly connected components of directed graph, kosaraju

Given a graph in [[sourcevertex,targetvertex],...] format with all the directed edges of the graph I am trying to optimize the code here because it still hasn't ...
4
votes
2answers
5k views
5
votes
1answer
1k views

Complete graph traversal algorithm in Prolog

Given a table, I want to explore all possible transition between the elements in the table. ex: for a table with size 3 [0,1,2], the output of the algorithm should be 0->1, 1->0, 0->2, 2->1, 1->2, 2->...
2
votes
1answer
3k views

Strongly-connected component for a graph

I implemented a strongly connected graph code in C++. matrix_graph.h ...
5
votes
1answer
12k views

DFS/BFS implementation of Cormen's pseudo code

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this. ...
4
votes
1answer
19k views

Creating an adjacency list

I've created this adjacency list, but I don't like the design of the graph. The issue is that there is one pointer in the node to its adjacency list and there is a pointer in an ...
7
votes
1answer
1k views

Find almost-shortest path more efficiently

I'm trying to solve a SPOJ problem, which is code SAMER08A at this link. The problem is that when I ran my code in my IDE with all the examples given in the problem, the code works perfectly. But ...
1
vote
1answer
130 views

Small graph API to track vertices and edges added to graph

I'm working on my Scala chops and implemented a small graph API to track vertices and edges added to graph. I have basic GraphLike Trait, and have an Undirected Graph class ( ...
7
votes
2answers
849 views

Simplifying finding neighbors in graph

...
2
votes
1answer
521 views

Is this implementation of Kruskal's algorithm maintainable and efficient?

I'm implementing Kruskal's algorithm in C++11 and would like feedback on style and performance on my graph data structure and algorithm for educational purposes (for production code, I'd use a pre-...
3
votes
3answers
4k views

Finding the closest node

I have a function that I need to optimize: ...
2
votes
1answer
313 views

Is this code for getting the dependency tree of a file correct?

...

1
9 10 11
12
13