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
2 votes
0 answers
48 views

Advent of Code 2021 Day 19

I am taking advantage of the recent layoffs to teach myself Kotlin. I am a career Java programmer, I've touched Kotlin before but not actively, and not for a few years. I wrote it all in one file ...
  • 958
6 votes
1 answer
243 views

Implementation of DFS algorith as described by Algorithms - Dasgupta, Papadimitrious, Umesh Vazirani

I just want feedback regarding C++ coding style and if in any way I can optimize my code (e.g. to use a different data structure). I'm only trying to use up to C++ 14 standard code. Any other ...
  • 163
5 votes
1 answer
72 views

Prune unreachable sections of a directed graph

I have a graph represented with an Adjacency set similar to: ...
2 votes
1 answer
75 views

A graph interface for Wikipedia

I'm building a graph-based interface to explore Wikipedia, but I'm not really familiar with TypeScript/React (especially state management), so I really feel like I'm just Frankensteining things ...
3 votes
1 answer
65 views

Node graph implementation for a material system

I'm working on a material/shader graph system. I came up with a simple solution, but nodes that weren't connected were used in some situations. So, I thought of using Kahn's algorithm to execute nodes'...
  • 137
1 vote
0 answers
21 views

Figure out all paths of all nodes up to k depth

I'm trying to figure out all the paths of all the nodes up to K depth. It seems to be a dynamic programming problem, my attempt seems to be working however its slower than I expected I would think ...
0 votes
0 answers
61 views

Searching for all paths between two terminal nodes in an undirected, unweighted graph using DFS in Java

I have this small program for building undirected, unweighted graphs and finding all the paths between two given terminal nodes: ...
  • 26.5k
1 vote
0 answers
36 views

How to simplify Tarjan's algorithm implementation in JavaScript and make it non-recursive (i.e. iterative)?

I adapted this Tarjan algorithm in JavaScript to be a little more functional and not pollute the Vertex object with temporary metadata, and arrived here: ...
  • 351
4 votes
1 answer
450 views

Find center of an undirected graph

Task: implement an algorithm to find graph center \$Z(G)\$ given undirected tree \$G\$. This is my first time programming in C++ so any (elementary) feedback is appreciated. The way I did it is: Run ...
2 votes
0 answers
33 views

C Finding strongly connected graph components in linear time using Kosaraju's algorithm

I followed this algorithm to find strongly connected graph components in C and this code works (I think ... maybe there are bugs I am not aware of). I am wondering can I please get some feedback? ...
  • 389
1 vote
0 answers
94 views

Find shortest knight's path between two chessboard squares

My function is a solution to the Knight's Travails problem. It receives start and end point coordinates on a chess board, and must return the shortest path from start to end. ...
2 votes
0 answers
80 views

Iterating over all simple unique cycles in an undirected graph in Java - brute-force approach

This post is about an Iterator iterating over simple loops of an undirected graph. In the above graph, the cycle \$\langle 1, 2, 3, 4, 5, 3, 1 \rangle\$ is not ...
  • 26.5k
2 votes
1 answer
60 views

C++ Refactored graph again, separated property maps from Graph type

This is yet another improvement from my graph class - Link Now property maps are no longer parts of Graph type, they are just stored in a member variable. This ...
  • 1,683
2 votes
1 answer
74 views

C++ Graph class with multiple property maps (edit)

I wrote an improvement from my previous graph class: Link ...
  • 1,683
0 votes
0 answers
25 views

Shortest path in dags: Part 3/3 - the demo benchmark

Part 1/3 Part 2/3 In this post, I will present the benchmark code from this project. com.github.coderodde.graph.benchmark.DemoDagProvider.java: ...
  • 26.5k
1 vote
1 answer
50 views

Shortest path in dags: Part 1/3 - the graph data structure

Part 2/3 Part 3/3 I have this library for performing shortest path queries on dags (directed acyclic graphs). This post presents the graph data structure: ...
  • 26.5k
1 vote
1 answer
59 views

Library to represent graphs

I have been working on a library to represent graphs (directed graphs and undirected graphs). I know that there are already many such libraries but I wanted to create my own as a learning exercise. I ...
1 vote
1 answer
97 views

Optimizing BFS code to find connected components in a graph

I am writing a Python code to find the connected components of a graph using BFS. The code works but takes a long time to run. Please suggest possible optimizations of my code. The graph is stored as ...
  • 11
6 votes
1 answer
87 views

Python code to contract (shrink) a graph

To better understand a paragraph, I implemented the intent behind the paragraph. In this case, it was a formal definition of a graph contraction: Suppose we have an undirected graph G and X ⊆ V(G). ...
  • 821
3 votes
1 answer
307 views

Kosaraju's algorithm in C simple implementation

I am wondering can I please get some feedback for my simple implementation of the Kosaraju algorithm. More specifically how I de-allocate the things I allocated using ...
  • 389
1 vote
1 answer
51 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
4 votes
1 answer
97 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 ...
3 votes
1 answer
124 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 ...
2 votes
0 answers
95 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'. ...
5 votes
0 answers
97 views

Dijkstra's algorithm in Perl

I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
  • 26.5k
2 votes
2 answers
148 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 ...
  • 26.5k
2 votes
0 answers
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: ...
  • 26.5k
3 votes
1 answer
230 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
1 answer
62 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 ...
  • 26.5k
3 votes
1 answer
128 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 ...
  • 26.5k
2 votes
0 answers
38 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 ...
  • 26.5k
4 votes
1 answer
346 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 ...
  • 26.5k
4 votes
1 answer
160 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
0 votes
0 answers
167 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
3 answers
79 views

DFS search that returns "not found" or distance

Assuming I've the following code: ...
  • 143
1 vote
0 answers
40 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
0 votes
0 answers
58 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
2 answers
101 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, ...
  • 157
2 votes
2 answers
263 views

Graph Implementation with Dijkstra's Algorithm

Graph Interface: ...
  • 51
3 votes
1 answer
87 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
0 votes
1 answer
194 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. ...
2 votes
1 answer
112 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 ...
  • 123
2 votes
0 answers
361 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
7 votes
3 answers
443 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 ...
-1 votes
1 answer
48 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/...
0 votes
1 answer
108 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 ...
3 votes
2 answers
96 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
-1 votes
1 answer
94 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 ...
2 votes
0 answers
50 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 ...
1 vote
1 answer
61 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 ...
  • 26.5k

1
2 3 4 5
15