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.

Filter by
Sorted by
Tagged with
3
votes
1answer
1k views

Graph Implementation in Java using adjacency list - v2

Updated version from Graph Implementation in Java using adjacency list ...
1
vote
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....
2
votes
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? ...
0
votes
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? ...
2
votes
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 ...
2
votes
1answer
163 views

Implement a graph in Python

Question : Build a graph in python, given its edge representation. ...
2
votes
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 ...
2
votes
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 ...
3
votes
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 ...
0
votes
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 ...
1
vote
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 ...
4
votes
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 ...
7
votes
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\$. ...
2
votes
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. ...
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
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 ...
1
vote
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. ...
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
542 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
3k views

Bellman Ford algorithm implementation

Please review my code and help me to improve it. ...
0
votes
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 ...
3
votes
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 (...
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
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 ...
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
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 ...
3
votes
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 ...
6
votes
2answers
239 views

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

I have an object like this: ...
2
votes
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 / ...
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
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 ...
6
votes
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 ...
3
votes
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 ...
3
votes
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 ...
5
votes
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 ...
4
votes
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 ...
4
votes
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 ...
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
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 ...
2
votes
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 ...
2
votes
2answers
771 views

DFS implementation in Rust

...
2
votes
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 ...
1
vote
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 ...
3
votes
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, ...
3
votes
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 ...
3
votes
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 ...
3
votes
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....
2
votes
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 ...
0
votes
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), ...