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

713 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### Number of paths in a randomly labeled complete graph

I have a complete graph with n vertices, set W (let's say W = {1,2,3}) and a path ...
• 13
51 views

### Call-flow graph from Python abstract syntax tree

Below is my code for building a call-flow graph from a Python abstract syntax tree. I'm not satisfied with it because the algorithm is very complicated. Perhaps much more complicated than it needs to ...
• 1,250
53 views

### Topological Sort C++

Comments on optimizing the code or improving the code are requested. The input parameters to the class constructor are a one dimensional array of job ID's and the second argument is a list of vectors ...
49 views

### Bellman-Ford algorithm implementation

I have used an adjacency list to represent the graph. This implementation is based on the procedure given in the book 'Introduction to Algorithms'. ...
63 views

### Dijkstra's algorithm in Perl

I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
• 25.3k
133 views

### Much more efficient trisexual genetic algorithm for TSP in Java

(The entire project lives there.) This time, I have made the previous version of the GA for TSP run faster by around the factor of 6+. The idea is to cache the tour costs with the actual tour objects ...
• 25.3k
64 views

### Genetic trisexual algorithm for TSP in Java [duplicate]

(A more efficient version of the GA.) This is my the very first take ever on GA: GeneticTSPSolverV1.java: ...
• 25.3k
108 views

### The shortest path between airports

Airlines need to provide their customers with flights to every corner, so they need an app that allows them to do so. The customer must be able to transfer when there is no direct connection. The ...
1 vote
45 views

### Genetic TSP in Java with graph expansion

This post presents my take on TSP (travelling salesman problem). The idea is to: Take an input node i, Compute the entire graph ...
• 25.3k
66 views

### Traditional vs. bidirectional Dijkstra's algorithm in C

I have this CLion project on GitHub. It constructs a directed, weighted graph consisting of 100 thousand nodes and 500 thousand directed arcs, picks two random nodes, and computes the shortest paths ...
• 25.3k
1 vote
27 views

### Directed weighted graph in C

I am working on a project that requires a directed weighted graph data structure. It looks like this: graph.h ...
• 25.3k
328 views

### Searching for a performance bug in a C++20 pathfinding algorithm (NBA*) - follow up

I have followed some advice in the previous iteration, yet even the current version is too slow compared to the Java implementation of the same algorithm. (C++ version with ...
• 25.3k
86 views

### Minimum vertex cover in a Bipartite Graph

I have written a function in Java to find minimum vertex cover in a bipartite graph. It is working on all the sample test cases I have used. However, due to lack of implementation and test cases ...
• 141
96 views

### Parallel BFS OpenMP C

I'm trying to develop the code to make a parallel version of the BFS (topDown) algorithm on a graph. This is the code I have developed so far: ...
1 vote
62 views

Assuming I've the following code: ...
• 143
1 vote
33 views

### Efficient algorithm to generate random multigraph (undirected) given nodes and degree

I wrote a simple algorithm to generate 1000 random graphs given total nodes and associated node degree. Graph is undirected with multiple edges and no self-loops. My current algorithm is very slow: ...
• 162
53 views

### Efficient way to build random undirected graphs without self loops given total number of graph nodes and associated node degree

I wrote an algorithm to build 1000 different random graphs given number of nodes and node degree. Node degree is maintained between the random graphs. I am building these random graphs to input to a ...
• 162
1 vote
81 views

### Implementing graph for pathfinding

I need a graph for multiple pathfinding algorithms,so I wanted to ask whether my new graph implementation is ok. Would someone who works as a developer in related fields(Graphs, Pathfinding, ...
• 57
161 views

### Graph Implementation with Dijkstra's Algorithm

Graph Interface: ...
• 51
78 views

### Java Graph Implementation

Attempt to implement undirected graph with intentions of making a directed implementation too. I'm also new to Generics. I'm sure there's a lot of things I can do better ...
• 51
21 views

### Does this dijkstra's implementation work on negative weights?

First of all, I am not exactly sure if this is the traditional Dijkstra's implementation. After polling the vertex, I am relaxing all of the neighbors of the polled vertex. However, according to the ...
56 views

### Find the shortest path from bottom left to top right in a maze using dfs and bfs algorithm

The following code is applying the depth-first search and breadth-first search algorithm to find the shortest path from bottom left to top right in a 10 x 10 grid. ...
69 views

### Finding cycles in graph

I found this code for Java to find if graph has cycles and I edited it to print out path of cycle. I use adjacency list. As it is directed weighted graph I will need to implement compensations of ...
• 23
186 views

### Parallel Breadth First Traversal in Rust

Overview I have been writing my own graph API for Rust and one thorny problem I wished to tackle was a parallel breadth first traversal of the graph. The API itself will have different graph flavours, ...
• 171
390 views

### Draw a 2d graph using slashes

Given a list of integers a 2D graph has to be plotted taking 1st, 3rd, 5th, ... numbers as upward slope and 2nd, 4th, ... numbers as downward slope. I have used a Python list to do it. Is there any ...
77 views

### Kosaraju's algorithm is too slow

I just implemented the Kosaraju's algorithm in Go. I tried to implement the same algorithm that is described in the relevant Wikipedia page: ...
• 993
44 views

### is my Prim's MST implementation terse enough?

I did research because I want to learn Kruskal's and Prim's MSTs. I did research and after a solid understanding, I went to my textbook and got their libraries: https://algs4.cs.princeton.edu/code/...
77 views

### Recursive DFS to find Euler Cycle

I have referred to this for what constitutes as an Euler Cycle: https://xlinux.nist.gov/dads/HTML/eulercycle.html This assignment required me to use Depth First Search and have the methods I have ...
77 views

### Finding Number of Objects in Image

I wrote a program that, given a 2D array representing pixels in a birds eye view image, it returns the number of Objects in the image. Pixels that are connected in the up, down, left, and right ...
• 41
79 views

### Graph coloring problem with Spark (JAVA)?

I am trying to create the algorithm described in the image from this link Simply put any two adjacent nodes must not share tuples and if they do they are colored with the same color. If there's a ...
48 views

### Bad performance of a Graph Algorithm

I implemented a solution for the problem below, but its performance is not good. I know I can find the solution online, I'm trying to understand what is causing the bad performance in ...
30 views

### Loan graph simplification in Java: an arc minimization algorithm

In this post, I will present an interesting (to me) algorithm for reducing the number of arcs in a financial loan graphs. (The class belongs to this GitHub repository.) ...
• 25.3k
29 views

### Loan graph simplification in Java: the graph data structures

This post presents the loan graph implementation. The class belongs to this GitHub repository. net.coderodde.loan.model.Node: ...
• 25.3k
1 vote
50 views

### Loan graph simplification in Java: the recursive DFS for searching for directed cycles

The class in this post returns a directed cycle in a financial loan graph. A financial loan graph consists of nodes and directed arcs. If there is an arc $(u, v)$ with weight $w = w(u, v)$, then ...
• 25.3k
1 vote
37 views

### Graph stored as adjacency list or as endpoints and intervals

I tried speeding up my Graph class, so I removed the Node class and Edge class, and decided to use arrays and ArrayLists. My 2 implementations seem very similar, ...
• 111
581 views

### Compute shortest path in undirected graph

In a recent coding interview I was asked to write a program which takes as input two text lines: The first one represents a graph, formatted as a sequence of undirected edges like ...
505 views

### Build order from a dependency graph (Python)

Below is my attempt at the challenge found here. The challenge is "Find a build order given a list of projects and dependencies." Already given are the classes Node and Graph (which I can ...
• 187
79 views

### Turn an array of pairs of start and end points into an ordered series

Given an array of pairs, for example: [["Denver", "Miami"], ["Miami", "Tulsa"], ["LA", "Okmulgee"], ["Mobile", "Portland"...
1 vote
306 views

### Python, create a network with a given node and edges from pandas dataframe

I'm working on a code snippet that generates a network graph. ...
• 133
1 vote
186 views

### Cheapest flights within k stops algorithm in JavaScript

The problem: There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is ...
122 views

### Python leetcode: scheduling courses to meet prerequisite requirements

This is my solution to Leetcode #210, Course Schedule II. There are a total of numCourses courses you have to take, labeled from ...
• 375
1 vote
55 views

For context, I wrote a function, get_servers, for the game Bitburner which is usually played by writing JavaScript code. Instead, I used PureScript to write the ...
• 259
1 vote
66 views

### Checking whether a graph is connected in an immutable way

I have this function at the moment ...
65 views

### Graph Implementation for Social Network

I'm trying to implement a graph structure in python, making use of the classes Vertex, Edge and Graph. The goal is to read a csv file that contains users names and a number (weight), like such Lynch,...
407 views

### Find all paths in a graph

My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved? Can some form of memoization be used here? There are cases ...
• 155
41 views

### Dijkstra from scratch

I implemented the Dijkstra algorithm from scrath and wonder if I can save some code? The whole algorithm is here. n is the number of nodes, and m the number of edges. 1 ≤ 𝑛 ≤ 10^4, 0 ≤ 𝑚 ≤ 10^5, 𝑢 ...
• 325
39 views

### Enumerating all fixed-length paths from a vertex in a graph

Enumerating all fixed-length paths from a vertex in a graph 1. Graph-related classes Base implementations of the relevant classes in my graph library. I'm using C#9 in a .NET 5 project. I opted to use ...
• 178
167 views

### Leetcode: number of islands

I am on my second iteration of the famous "Number Of Islands" graph problem on Leetcode. https://leetcode.com/problems/number-of-islands/ ...
• 105