A graph can refer to a graphic (such as a chart or diagram) showing or displaying the relationship between two or more variables used, for instance, in visualizing scientific data.

learn more… | top users | synonyms

0
votes
1answer
37 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
48 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. ...
0
votes
0answers
5 views

How to make a smiley face in Turtle? [migrated]

First time ever using Turtle. My assignment is to make a smiley face, any size and any position. I just can't get the mouth right because I really don't know what I'm doing. I've read quite a bit and ...
4
votes
2answers
86 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
37 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
420 views

Trip Advisor - Train routes

Gives advice to the user on which trains to take to reach a destination ...
5
votes
2answers
96 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
78 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
115 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
126 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
177 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
66 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
45 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
73 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
58 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
130 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
109 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
186 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
62 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. ...
5
votes
0answers
86 views

Thinking in 'Haskell' - when to use (state) Monads

I really enjoy Haskell but feel I still have a total beginner's style, and would like to move beyond that. The code below - for Dijkstra's shortest path algorithm - is a case in point. I feel as ...
5
votes
1answer
76 views

Generic Graph Library Part 2 : Algorithms

(This is a follow on to this question). Having given an implementation for some of the graph structures, here is a portion of the algorithms that are defined to work over them: graph_degree.hpp ...
10
votes
1answer
119 views

Generic Graph Library

I've been working on a generic graph library for a while now, in a bit of an off and on fashion. I realise that boost::graph exists, but it is a complex library ...
3
votes
2answers
85 views

Simplify an if else construct with assignment before if and else

I want to simplify an if: .. else: .. construct: ...
2
votes
1answer
60 views

M coloring problem

Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a ...
0
votes
2answers
84 views

Detect cycle in an undirected graph

This code detects cycle in acyclic graph. The assumption of this approach is that there are no parallel edges between any two vertices. Looking for code review, best practices and optimizations. ...
4
votes
1answer
144 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. ...
8
votes
2answers
447 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 ...
6
votes
1answer
184 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 ...
7
votes
3answers
554 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 ...
1
vote
0answers
45 views

How to design a user defined graph structure?

First, my code to review: ...
3
votes
4answers
13k 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 ...
3
votes
1answer
285 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
91 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
123 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
184 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
79 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
882 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, ...
11
votes
3answers
3k 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
20 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, ...
11
votes
1answer
2k 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. ...
0
votes
0answers
67 views

Iterative DFS algorithm

I've written an iterative version for DFS. For a quick overview of the benchmark results for a complete graph: So it looks like it behaves within the boundaries of the theoretical complexity. ...
5
votes
2answers
350 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 ...
6
votes
1answer
217 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
60 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 ...
4
votes
1answer
139 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 ...
2
votes
0answers
94 views

Actionscript Graph data structure implementation

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

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

This is in preparation for a competition that only allows C++03. ...
5
votes
1answer
223 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 ...
10
votes
2answers
6k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
7
votes
2answers
2k 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)\$. ...