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
27
votes
4answers
74k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
21
votes
4answers
184k 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 ...
21
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 ...
20
votes
1answer
264 views

Rainfall - August 2016 Community Challenge (Hooray for graphs!)

A solution for the August 2016 Community Challenge (Rainfall). I've intentionally left out error checking on the file formatting. This seems like a very obvious graph problem to me - we want to ...
18
votes
1answer
21k views

Check if a directed graph contains a cycle

I am trying to optimize execution time of this function which detects cycle in a directed graph: ...
17
votes
2answers
38k views

BFS Implementation in Python 3

...
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. ...
15
votes
3answers
343 views

Traversing an infinite graph using Dijkstra's algorithm to maximize cookie production speed

Imagine the following situation: It is the year 20XX. You are a prodigious baker, capable of baking cookies at an astonishing rate of 1 cookie per second. Your archnemesis, an equally excellent baker,...
14
votes
2answers
76k 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 ...
14
votes
2answers
927 views

All your bases are belong to Dijkstra

CATS, willing to get a hold of all the bases, asked Dijkstra to give him a hand designing the most powerful algorithm to reach all bases with the least distance travelled. I tried to implement the ...
13
votes
1answer
1k 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 ...
13
votes
1answer
6k 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 ...
13
votes
2answers
732 views

Speeding up Python depth-first search in large graph

I'm building a Markov text poetry generator. The main method, which is attached below, performs a depth-first search through the Markov chain, which is implemented as a NetworkX digraph of Word ...
12
votes
3answers
385 views

Kosaraju in Scala

I started coding in Scala some time ago, and also learning some fundamental algorithms in CS. Here's a terribly slow implementation of Kosaraju algorithm to find strongly connected components in a ...
12
votes
2answers
2k views

Word Morph (changing one letter at a time)

Below is my implementation of Word Morph solver in Python. The challenge consists of transforming one word into another word by changing one letter at a time. Each word in the chain should be an ...
12
votes
1answer
3k views

Variadic function with restricted types

I am designing a class which (among other things) acts as a vertex in an undirected graph. ...
12
votes
1answer
113 views

Create edges from cells

I have a (large) number of nodes and (triangular) cells, e.g., cells_nodes = [ [0, 3, 1], [0, 2, 3] ] This example represents the small mesh (Please ...
12
votes
1answer
214 views

Glue Shredded Pieces (CodeEval)

I have solved problem 185 on CodeEval, Glue Shredded Pieces. The solution got a 100% score on all tests (edit: see comments), within the allotted time and memory constraints. I'm looking mostly ...
12
votes
1answer
1k 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 ...
12
votes
1answer
3k views

IDA*: Iterative Deepening A* implementation

I created a generic version of IDA*. I am attempting to create the following code with exceptional quality and performance. I'm hoping to try and create short code tutorials regarding. However, the ...
11
votes
2answers
795 views

Milking order compatible with maximum number of observations

I'm using some old USA Computing Olympiad (USACO) problems to help teach me. This is the "Milking order" problem: Farmer John has \$N\$ cows (\$1≤N≤10^5\$), numbered \$1…N\$. He has made \$M\$ ...
11
votes
3answers
535 views

Dijkstra's algorithm in C99

I just implement Dijkstra's algorithm in C99. Can you review my code please? I'm looking for any mistake, performance improvement or coding style errors. main.c ...
10
votes
1answer
14k 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. ...
10
votes
1answer
462 views

Graph generator for undirected graphs

I am still pretty new to Haskell and am working on a graph generator for undirected unlabeled graphs containing loops and I have a bottleneck in the following functions. So far, I have not given any ...
10
votes
2answers
229 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 ...
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'...
10
votes
1answer
221 views

Displaying programming languages on a timeline

I did the following two exercises in Programming: Principles and Practice Using C++ (2nd Edition), by Stroustrup, which build upon each other: From Chapter 22 (Ideals and History), Write a ...
10
votes
1answer
2k views

A rapidly-growing script that visualizes WiFi sniffing

Below is one of the versions of my wifimap script: ...
10
votes
2answers
13k 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 ...
10
votes
1answer
2k views

Simple Oriented Graph implementation in Java

I wanted to implement a simple oriented graph as part of an exercise in both Object Oriented Programming and Data Structures. I wanted to make it as class-focused as possible, so I don't know if my ...
9
votes
5answers
255 views

Sort a list of pairs representing an acyclic, partial automorphism

I have this sample data: let trips = [ { from: "DEN", to: "JFK" }, { from: "SEA", to: "DEN" }, { from: 'JFK', to: 'SEA' }, ]; ...
9
votes
3answers
415 views

Function, taking up to 27 parameters, that checks for the existence of a path in a graph

There's got to be a better way than this that preserves the logic while sparing me the multitude of lines: ...
9
votes
1answer
11k 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. ...
9
votes
4answers
325 views

Shifting the origin of a large list of coordinates

Problem and goal Given a large edge list file (such as 2 million nodes, 30 million edges) containing source and destination coordinates, I want to 'convert' them in such a way so that the coordinates ...
9
votes
1answer
2k views

Hacker Rank: Journey to the Moon (Graph Theory)

I am attempting to complete the "Journey to the Moon" problem described below: There are N trained astronauts numbered from 0 to N-1. But those in charge of the mission did not receive ...
9
votes
2answers
322 views

Rock, Paper, Whatever - A small commandline game

My rational for this program, was to learn more of Python's standard library, I didn't actually know cmd was even in it until I started this program. It's also the ...
9
votes
1answer
912 views

Graph theory using C++ STL

I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object. Any feedback would be ...
9
votes
1answer
2k views

Directed graph isomorphism in Java

Given two input directed graphs \$G_1 = (V_1, A_1)\$ and \$G_2 = (V_2, A_2)\$, the problem of isomorphism asks whether the two directed graphs are isomorphic, or in other words, whether the two input ...
9
votes
1answer
3k 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 ...
8
votes
3answers
1k views

Reorder a list of courses, given their prerequisites

I recently graduated from college and applied for a position with a company. I was sent a coding exercise as part of the process. After completing the exercise and submitting it I was told that the ...
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 ...
8
votes
3answers
16k views

Generic graph implementation in C#

I am implementing fundamental data structures in C# while trying to learn techniques in the language to make my code cleaner, more concise, and reusable. I have implemented a generic graph with a few ...
8
votes
3answers
678 views

Dijkstra's algorithm without relaxation

I'm trying to implement Dijkstra's algorithm in Python, but the issue is that Python doesn't have support for key-based heaps out of the box, so applying relaxation step of the classical algorithm ...
8
votes
1answer
11k 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 ...
8
votes
2answers
4k views

C++ Graph Implementation

My data set is a list of Edges which are passed as a pair of integers. Based on that, I have the following graph implementation for BFS. Could someone please review ...
8
votes
2answers
6k views

D3 visualization of a Facebook friend graph

I've been learning Python for about a year and now I'm trying to improve my JavaScript. I wrote this simple d3 visualization that shows your Facebook friends as a force-directed graph. Here's a live ...
8
votes
2answers
11k views

Implementation of Kosaraju's algorithm for strongly connected components

To learn and practice coding in C++, I wrote an implementation of Kosaraju's two-pass algorithm for computing the strongly connected components in a directed graph, using depth-first search. This was ...
8
votes
1answer
1k views

Flight combinations between two cities

I am trying to obtain all possible ways to go from a city A to a city B on a given day by plane, with a maximum of 2 stops. I have as input a list of dictionaries: ...
8
votes
1answer
329 views

Breadth First Search not SOLID enough v2.0

Original question: Breadth First Search not SOLID enough Here is my first attempt at refactoring. Instead of using a Tuple, I used a ...
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)\$. ...