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
53 views

Generate another random path through a complete graph

What this does is generate a random path of cities to later calculate the length of the newly generated tour of cities, the TSP. I am trying to figure out if there is a more efficient way to write ...
1
vote
0answers
163 views

Adjacency List C++14

I would like to create a graph library for fun and run various searching algorithms on it. For now, all I have is an adjacency list that I threw together. The adjacency list currently only supports ...
1
vote
0answers
196 views

Kruskal Algorithm in C++

After studying from CLSR, I have implemented this algorithm. It prints the minimum cost. Help me to improve it. ...
2
votes
0answers
86 views

Computing most-cost effective loans in financial graphs using Java

Problem statement We are given a directed graph \$G = (V, A)\$, where \$V\$ is the set of actors and \$A \subseteq V^2\$ is the set of directed arcs. Existence of an arc \$(u, v) \in A\$ is ...
0
votes
1answer
529 views

Dijkstra's Algorithm implementation in C++

After applying suggestions from here about Bellman Ford Algorithm. Help me to improve this program. ...
4
votes
2answers
2k views

Bellman Ford algorithm implementation

Please review my code and help me to improve it. ...
0
votes
2answers
471 views

Eulerian Circuit algorithm

This method draws an Eulerian Circuit from a directed graph. The graph is represented by an array of Deques representing outgoing edges. It does not have to be Deques if there is a more efficient data ...
3
votes
1answer
282 views

Speed up a simple edge connecting algorithm

I have a list of edges and a similar list of links (linking edges) telling which edges to connect (how to order them). Connected edges form polygons and there can be many disconnected polygons (...
2
votes
1answer
2k views

Finding an Eulerian cycle in a graph

Given a graph that has an Eulerian cycle, write a function which returns the cycle in tuple form. I came up with following solution for this problem and am stuck trying to make it faster. Do you have ...
1
vote
0answers
764 views

Depth First Search using Adjacency List

My aim to implement adjacency list correctly. After takin help from here, I have implemented it. I have tried to implement it here, but it was suggested that it is most likely adjacency matrix. Help ...
4
votes
3answers
3k views

Breadth First Search using adjacency list

I want to improve this code using STL. Let me know if I should add any other function in this code. ...
5
votes
1answer
521 views

Dijkstra finding shortest path satisfying given constraints

The question is originated from Hackerrank. Suppose there are 1 to N stores in a city which are connected by bidirectional roads associated with traveling ...
3
votes
1answer
561 views

BFS to check if path from start node to end node exists

I'm trying to solve a problem from leetcode called Jump Game and it seems to be a pretty simple graph problem where we have to find if a path exists from a start node to an end node. I personally ...
6
votes
2answers
230 views

Given {origin, destination} objects, find all the paths from a place to another

I have an object like this: ...
1
vote
1answer
5k views

Directed Graph Implementation in Java

Here I've attached my java implementation of a directed graph. I've used a modified adjacency-list mechanic to utilize a map instead of a list for quicker lookup times. Looking for comments / ...
2
votes
0answers
39 views

Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...
4
votes
1answer
169 views

Finding many paths in a graph

I have a graph which we can think of is representing a network of train tracks. Each node is a station and each edge is a piece of track connecting two stations. Each station node may be connected by ...
6
votes
1answer
510 views

Read CSV and use bidirectional BFS to find the shortest connections between actors

I have a really huge file¹ with 17 million records in it. Here is a sample of the file: Actor Movie 1,2 2,2 3,1 4,3 2,3 ...
3
votes
1answer
694 views

DFS implementation

I implemented DFS using recursion in Go. When I dfs the graph, I am able to get the path of traversal. But I'm unsure what else could I add to this DFS in order to make the search better. Also, Is ...
3
votes
2answers
847 views

Finding the shortest path (between source and destination) with the least number of edges

I wrote a program which finds the shortest path between a source and a destination in a graph, so that the path will be to one with th least number of edges. In order to write it, I used Dijkstra's ...
5
votes
1answer
298 views

Bare bone implementation of Dijkstra

I am trying to implement Dijkstra without writing lot of code for the Graph class itself. I have implemented it from Wikipedia. However, I am not fond of the way I have handled the minimum distance ...
3
votes
0answers
90 views

Algorithm to find connected tiles (percolation)

I wrote a little program in JavaFX which displays a path of neighbouring open tiles going from top to bottom. It should simulate a percolation. The algorithm iterates through the whole grid (every ...
4
votes
1answer
205 views

Java Node class for a Graph

I'm using ArrayList<Nodes> to store adjacent nodes, and ArrayList<Integer> to store the corresponding weights of the ...
3
votes
1answer
5k views

C++ breadth-first search using adjacency matrix

I have written this Breadth First Search program using Adjacency Matrix, taking help from Introduction to Algorithm(CLSR) and from Internet. I want to optimise this code. ...
3
votes
3answers
118 views

A nice “live” service locator to flatten the object graph

Here is a class that exists in the Framework\ namespace in the xofz.Core library. It is used as a dependency of other ...
2
votes
1answer
158 views

Ruby Connected Components in a Graph

I've written the following code to find the connected components of a graph in ruby, but it is quite slow since I don't use any sensible data structure for the disjoint sets, and hence find_set is ...
2
votes
1answer
114 views

Computing resilience of the network presented as an undirected graph in Python

The idea is to compute resilience of the network presented as an undirected graph in form {node: (set of its neighbors)} for each node in the graph}. The function ...
2
votes
2answers
626 views

DFS implementation in Rust

...
2
votes
0answers
765 views

Graph represented by adjacency list

I've started to learn about graphs and how to represent them in code. Here is my attempt of making an adjacency list for an undirected graph. I'm looking for suggestions on how to improve it and what ...
1
vote
2answers
62 views

Calculating the connectance of a matrix iteratively

I have a performance issue in R. I have a function that iterates over a dataframe for different levels of "site" and "method". The function samples 1:1000 interactions (rows), converts these to ...
3
votes
0answers
75 views

SPOJ Fast Matching challenge

I wrote a solution to the MATCHING challenge on SPOJ: FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, ...
3
votes
2answers
407 views

Comparing Dijkstra's SSSP algorithm against Bellman-Ford in Java

Single source shortest path In SSSP, we choose a node \$s\$ and we compute all the shortest path starting from \$s\$ towards all other nodes, thus computing a shortest path tree. Two most classical ...
3
votes
1answer
124 views

Hackerearth - Learning Graph

Problem: Monk goes to graph city to learn about graphs, and meets an undirected graph having \$ N \$ nodes, where each node has a value \$ i \$ such that \$ 1 \le i \le N \$. Each node of the ...
3
votes
0answers
52 views

Find spanning tree with maximum edges with the same weight

For my university assignment I need to come up with an algorithm to find a spanning tree with maximum number of edges with same weight. I received an algorithm suggestion in this Stack Overflow answer....
2
votes
2answers
538 views

Calculation of Hamming distance between two adjacency lists

I have written a Java program to calculate the Hamming distance between two adjacency lists. The program calculates the Hamming distance correctly, but it takes a very long time, especially when ...
0
votes
2answers
473 views

How to make this code of shortest Path Finder more maintainable,extendable and get better static code analysis result?

I have the below code for finding the shortest path between a source node and destination node in a BiDirectional graph.It is working alright. However, when I am running Static Code Analysis (VS2017), ...
1
vote
0answers
456 views

Sorting directed graph topological using Kahn's algorithm

For a course I'm doing I need to get up to speed with Java, but unfortunately only Java 1.6 - here is a topological sorting algorithm in said Java version, for practice reasons: ...
5
votes
2answers
966 views

Weighted union-find with path compression in Python 3

I implemented the Union-Find data structure and would love to receive some feedback about my code. I have just begun programming and welcome any feedback or constructive criticism which would improve ...
2
votes
0answers
103 views

Network of senders and receivers in C++

I am trying to create a Sender-Receiver Network. What do I mean under a Sender-Receiver Network. That means that there is some structure which consists of Nodes and connections between them which will ...
1
vote
2answers
280 views

Depth-first search of a graph in C# (HackerRank problem)

I'm trying to solve a problem from HackerRank. I got the correct algorithm, but it seems to be too inefficient. After checking the code with 10 given test cases, 3 cases are good and 7 return a ...
2
votes
3answers
1k views

Topological sort of a graph

Please refer following graph. Please review following code for topological sort. I can sense one odd thing in my code, TS() is calling ...
8
votes
1answer
2k views

Prim's Algorithm using heapq module in python

Implementing Prim's with a \$O(m\log n)\$ run time using heaps, similar to Dijkstra heap implementation. Where \$n\$ is the number of nodes, and \$m\$ is the number of edges. Using the ...
4
votes
1answer
1k views

Greedy graph coloring

For taking part in a course, I need to learn some Java. Unfortunately they only teach Java 1.6, so I understand that later versions could simplify the below code a lot, but I have to stick with 1.6 ...
3
votes
2answers
589 views

Given two words and a dictionary's word list, find all shortest transformation sequence

This is a leetcode problem (https://leetcode.com/problems/word-ladder-ii/description/) Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(...
2
votes
3answers
5k views

Finding connected components in Python

I wrote an algorithm for finding the connected components in a 2d-matrix in Python 2.x. I am looking for comments on the quality of my code, organization, formatting/following conventions, etc. For ...
1
vote
3answers
2k views

Topological sort using STL

I am trying to implement topological sort using STL. I have used vector of lists to store adjacency list. Indegree is an array which stores indegree of vertices. ...
5
votes
1answer
162 views

Depth-first Search Non-Reursive Implementation in Clojure

I've created a non-recursive dfs implementation in Clojure. I'm using the wikipedia article on dfs as a guide. I'm very new to Clojure and functional programming in general. Any tips to improve ...
5
votes
1answer
164 views

AIO programming challenge - Friendlist - Who has the most friends?

I attempted this sample question from the Australia Infomatics Competition. TL;DR - Each line of input contains two numbers, representing a mutual friendship relationship. The output needs to be the ...
0
votes
2answers
161 views

Dynamic loading of Javascript dependency graph

I have JavaScript module for loading dynamically script files by dependency graph: ...
5
votes
2answers
192 views

Dijkstra's Algorithm modified to take negative edge weights

In the following Python implementation I have used color coded vertices to implement the Dijkstra's Algorithm in order to take negative edge weights. ...