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
6
votes
0answers
330 views

Kattis problem Amanda Lounges

I wrote this solution to Kattis problem Amanda Lounges in Scala. TL;DR: It's a graph theory problem where I read in a list of edges from stdin and try to compute the minimum number of nodes that ...
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 ...
1
vote
2answers
156 views

Java sequential BFS

I am currently working on optimizing my code. In order to do that, I have to make sure that my sequential BFS works perfectly. Then, I should I apply threads or executor service to run it in parallel. ...
6
votes
2answers
184 views

Is there a circular reference in a set of template substitutions?

I have a configuration engine that allows the user to specify a dictionary with text templates (read from a JSON file) where each placeholder like {x} can be ...
3
votes
2answers
1k views

Dijkstra's algorithm in JavaScript

I'm trying to implement Dijkstra's algorithm to find the shortest path. This is from a challenge on CodeWars. In this scenario there is a map: ...
6
votes
2answers
498 views

Simple Graph in Python

Just the beginning of graphs API in Python: ...
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 ...
4
votes
2answers
335 views

Split DAG into disjoint sets

I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding ...
2
votes
1answer
96 views

Circle check algorithm optimization for directed graph

Here is my two versions of code to check if there is a circle for a directed graph. Any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are highly ...
1
vote
1answer
187 views

Leetcode 210. Course Schedule II

Problem statement There are a total of \$n\$ courses you have to take, labeled from \$0\$ to \$n - 1\$. Some courses may have prerequisites, for example to take course \$0\$ you have to ...
2
votes
0answers
42 views

Modeling a control polygon for a piecewise spline curve

Aim I'm modeling a control polygon for a piecewise spline curve. Each sub-spline is defined by a location the spline must pass through, as well as a forward tangent, and a backwards tangent. The ...
2
votes
1answer
1k views

Representing an adjacency list (graph) using a hash table of lists

While writing a C++ implementation for weighed, labeled graphs, I started to doubt the effectiveness/correctness of my chosen structure and I would like to hear some reviews. I tried to implement the ...
0
votes
2answers
362 views

BFS in a grid with wall breaking saldo in Java

In this problem, we are given a 2-dimentional grid, with each cell being walkable or holding a wall. Given an integer \$s \geq 0\$, find the shortest path from the source node to target node breaking ...
2
votes
0answers
374 views

Second degree connection ranking

Problem Find 2nd degree connections ( friends’ friends), output these 2nd degree connections ranked by number of common friends (i.e 1st degree connections) with you, (example: if 2nd degree ...
6
votes
1answer
249 views

Minimum number of flight segments using breadth-first search

I'm practising with graphs, and trying to solve a problem of calculating the minimum number of flight segments, applying breadth-first search. The code is working, but I think, that it's not clean. ...
8
votes
2answers
1k views

Hackerrank - value of friendship (II)

Problem statement You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no ...
3
votes
1answer
1k views

Eulerian Path algorithm

I'm doing a project to find the Eulerian path. Cane someone find an example where the algorithm is wrong? The function EulerianPath recursively prints the Eulerian ...
5
votes
1answer
817 views

Hackerank - value of friendship

Problem statement You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no ...
2
votes
0answers
395 views

Tarjan's strongly connected component finding algorithm

Here is my code for Tarjan's strongly connected component algorithm. Please point out any bugs, performance/space (algorithm time/space complexity) optimization or code style issues. ...
5
votes
2answers
1k views

Implementation of a graph in Java

A long time ago I posted my implementation of directed graph is Java. Recently I took a look at @coderodde's implementation and decided to write an implementation of undirected graph and directed ...
2
votes
0answers
171 views

unordered_multimap approach to adjacency list and graph search

I'm looking for suggestions on how to improve the usage of modern C++ features with this simple graph search algorithm, particularly with regard to the use of STL containers and lambda expressions. ...
4
votes
3answers
2k views

Dijkstra's algorithm using priority queue running slower than without PQ

I need to implement dijkstra's algorithm and I've done so using this Wikipedia page. I've done it both with priority queue and without. Both versions work 100% correct, however I need the faster one ...
4
votes
1answer
157 views

Code to calculate minimum number of pushes required to put the whole dominoes set down

The question is this one on UVa, and it basically gives us n, the number of dominoes and (a,b) relations such that pushing ...
4
votes
2answers
473 views

Dijkstra's algorithm using a specific structure

I have implemented Dijkstra's algorithm using a slightly modified version of the structure and class posted here. Unfortunately, I have ruined the efficiency. I am intent on using this structure. I ...
3
votes
3answers
577 views

Graph representation implementation

I wanted to represent graphs in Python, and wrote the following class. I don't care about values associated with nodes or the weights of the connections between them, simply the connections between ...
3
votes
1answer
2k views

BFS' shortest path unweighted directed graph

The code I have is based on BFS and a little bit of Dijkstra and returns the shortest path of an unweighted directed graph as an integer. I was wondering if someone could take a look at my code too ...
3
votes
1answer
112 views

Topologial Sort in Python

I am trying to self study algorithms and this is my attempt at topological sort using Tarjan's version of DFS. It runs correctly for the graph I included. Can someone tell me if this is correct and if/...
6
votes
1answer
4k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
3
votes
2answers
660 views

CLRS Implementation of BFS and DFS in C++

I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code? GraphStructures.h ...
1
vote
1answer
773 views

Tarjan's strongly connected components algorithm

Can anyone suggest to me how I can make this "nicer"? If you can see any glaring details that I could change to speed things up too, that would be great -- though it's not priority. ...
3
votes
1answer
345 views

Snakes and Ladders using a magic die

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game. ...
4
votes
1answer
1k views

Implementation of BFS on a graph

I have written the code below as a BFS implementation. Could someone please review. In particular, I want to know if there could be a memory leak. ...
0
votes
2answers
241 views

Adjacency list from scratch

Here is my code for implementing an adjacency list from scratch. I would like to get feedback from the experts for optimization. ...
2
votes
1answer
992 views

Get a path between graph nodes using breadth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using breadth-first search. I'm doing this to improve my style ...
1
vote
1answer
340 views

Return a path between graph nodes using depth-first search redo

I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this ...
2
votes
1answer
3k views

Return path between graph nodes using depth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. I'm doing this to improve my style ...
1
vote
1answer
455 views

Print Connected Components Scala

Given a file containing adjacent IDs: i1, i2, i5 i3, i4 i2, i6, i7 i4, i8 i9, i3 I would like to print each of the connected components: ...
4
votes
0answers
106 views

Graph Python challenge 2 (revised)

I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python: You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
2
votes
1answer
3k views

Implementation of a directed graph

I wrote an implementation of a directed graph using the adjacency list representation. My goal was to meet the big O requirements which I'd found here. Please let me know about any drawbacks of the ...
5
votes
0answers
153 views

Assembling and traversing a graph, given a list of items and parent pointers

I've written a function which takes input such as this: ...
4
votes
1answer
649 views

Finding the max cost from the minimum cost incurred on travelling

This problem is from INOI 2014 , where I have find out the maximum cost of traveling through the cities but taking the minimum possible route cost , here is an excerpt from it, Indian National ...
3
votes
1answer
303 views

Python graph challenge

I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python: You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
2
votes
0answers
537 views

C++ STL graph implementation with out and in adjacency list

I'm looking for a code review on the following C++/STL graph implementation: Edge ...
1
vote
1answer
487 views

Convert a List of graph edges to a Map of neighboring nodes

What would be best way achieving this? Is it possible to use Immutable map? ...
0
votes
1answer
601 views

Node comparison using priority queue for Dijkstra's Shortest Path Algorithm

Instead of using a MinHeap that will allow me to change the vertex priorities I am using the Java library PriorityQueue. Here ...
1
vote
1answer
589 views

Directed Acyclic graph implementation in Ruby on Rails

I have an implementation for a graph node class that I'd like to have function as a directed acyclic graph. The associations are roughly as follows ...
2
votes
2answers
49 views

Longest way for all vertex

how can I optimalize this code? ...
4
votes
0answers
64 views

Finding connected components in the application task

I have n indexed socks, each of which has one of k colors. I also have a list that states which two socks I must wear at each of ...
1
vote
1answer
804 views

NBA*: Very efficient bidirectional heuristic search algorithm in Java - follow-up

This post elaborates on NBA*: Very efficient bidirectional heuristic search algorithm in Java. I have made the following changes: Added an explicit type for representing digraph paths: ...
0
votes
1answer
87 views

Social network broadcast message algorithm (part 2)

This is new code and continue discussion from thread (Social network broadcast message algorithm), and this thread focus on build new graph from strong connected graph part. Let me post the problem ...