Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# 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.

588 questions
Filter by
Sorted by
Tagged with
1answer
1k views

### Graph Implementation in Java using adjacency list - v2

Updated version from Graph Implementation in Java using adjacency list ...
1answer
1k views

### Graph Implementation in Java using adjacency list

I am building a Graph class to learn and eventually plan to add Dijkstra's algorithm to this implementation. What do you think of the overall approach? Any feedback on how to improve this? Vertex....
0answers
404 views

### Max flow Ford-Fulkerson using DFS augmented path retrieval

I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably? ...
1answer
1k views

### Depth First Search of graph in Python

Task: Do DFS traversal from a given given graph and print output. Is this code the correct implementation of DFS traversal in Graph? ...
1answer
82 views

### Dijkstra implementation for large graphs

I am implementing the Dijkstra algorithm for a large graph (40k nodes, 100k arcs). For shorter paths the searchtime is under a second for larger ones (from one end to the other) it takes quite some ...
1answer
163 views

### Implement a graph in Python

Question : Build a graph in python, given its edge representation. ...
0answers
80 views

### Number of subGraphs with given vertice and degree

Demo: There are three questions: How many subgraphs whose Num(vertices) <= 5 and all vertices have two degrees? How many subgraphs whose Num(vertices) == 4 and all vertices have 3 degrees? If ...
1answer
371 views

### Player Marking , Optimal Marking Using Graph

I was asked this problem for a challenge, and I decided to share my solution here to review the code: Here is the problem statement: For this challenge, we are going to cover some graph problems. We ...
1answer
2k views

### Generic Graph using Adjacency matrix - Java

The main purpose of representing Graph using adjacency matrix method is, to check the vertex and its neighbor's existence in constant time proportional to $\mathcal{O}(n)$. In the various ...
1answer
207 views

### Java agent-based model

I've been working on an agent-based model as part of my PhD and I've hit a roadblock. I started learning Java by doing this project and I definitely started to run before I could walk. The problem is ...
1answer
977 views

### Graph Representation using smart pointers. Kosaraju's algorithm implementation

Coming from a Java background, and being fairly new to C++ as well as code review, I am trying to get accustomed to C++11/14 concepts. I have been reading Modern Effective C++ by Scott Meyers to ...
1answer
121 views

### Levenshtein Distance of transitively similar words

The code's purpose is this: Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social ...
1answer
518 views

### Cheapest flights with at most k stops

This is the Cheapest Flights Within K Stops problem from leetcode.com: There are $n$ cities connected by $m$ flights. Each fight starts from city $u$ and arrives at $v$ with a price $w$. ...
1answer
2k views

### Calculating Euclidean distance

Code: I have a list of ~15,000 Euclidean points which represent a connected graph. I'm trying to solve/approximate the traveling salesman problem with this graph. Problem: Finding neighbors, i.e. ...
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 ...
0answers
167 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 ...
0answers
205 views

### Kruskal Algorithm in C++

After studying from CLSR, I have implemented this algorithm. It prints the minimum cost. Help me to improve it. ...
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 ...
1answer
542 views

### Dijkstra's Algorithm implementation in C++

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

### Bellman Ford algorithm implementation

Please review my code and help me to improve it. ...
2answers
511 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 ...
1answer
315 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 (...
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 ...
0answers
787 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 ...
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. ...
1answer
549 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 ...
1answer
636 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 ...
2answers
239 views

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

I have an object like this: ...
1answer
6k 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 / ...
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 ...
1answer
171 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 ...
1answer
528 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 ...
1answer
845 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 ...
2answers
908 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 ...
1answer
321 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 ...
0answers
98 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 ...
1answer
232 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 ...
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. ...
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 ...
1answer
173 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 ...
1answer
127 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 ...
2answers
771 views

...
0answers
778 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 ...
2answers
63 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 ...
0answers
76 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, ...
2answers
414 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 ...
1answer
134 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 ...
0answers
53 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....
2answers
575 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 ...
2answers
507 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), ...