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.
723
questions
0
votes
1
answer
30
views
Change the appearance of a log graph with two x axes
I would like to improve the overall look and feel of the two log graphs generated by the Python code below. The first graph represents the optimized methods while the second graph represents the ...
- 101
2
votes
1
answer
83
views
Non-recursive topological ordering, starting from given nodes, for Guava graphs
This method returns the topological ordering of a Guava graph starting from a given set of nodes. It's from my personal project github.com/jbduncan/guava-graph-utils, where I'm exploring utilities for ...
- 141
3
votes
1
answer
84
views
Parallel semi-sequential bottom-up tree traversal algorithm
I'm trying to traverse a tree-like structure from the bottom-up, and in parallel. Due to some other constraints I also have to allow for thread counts that may be lower than the width of a given set ...
- 55
1
vote
0
answers
93
views
Backtracking graph algorithms for a word puzzle in Python
Motivation
Recently, Buzzfeed released a browser-based puzzle game called "Pyramid Scheme." It is available at the following link. The puzzle in an initial state looks like this:
To solve ...
- 153
8
votes
1
answer
173
views
Lightweight general-purpose graph library in C++
As a personal side project I started building a graph library in C++ (I know, very original). The code is open source, but for the purpose of this question I will provide the relevant details and the ...
- 81
5
votes
1
answer
71
views
Checking if a graph is fully connected
After reading the rust book for some time I decided to create my first program which implements a graph.
There are a few things I was wondering about, such as if the file structure is appropriate (the ...
- 153
0
votes
2
answers
185
views
Union-find disjoint set solution to calculating sizes of connected components
I'm given a distance and a list of points in a plane, where I have to return a sorted list of the size of each connected component where each edge is shorter or equal to the distance threshold.
I've ...
2
votes
1
answer
169
views
Deletion of nodes of degree <=1 from a Python igraph graph
I have a working way of deleting all vertices of degree less than 2 in a graph until no more can be found.
But my solution has a significant issue which is that it calls ...
- 176
4
votes
1
answer
161
views
A simple probabilistic AI for generating random sentences in Java
Motivation
I have this repository. It contains a program that analyzes an input text file and builds a word graph: in the graph, each node represents a word in the analyzed text. Now, if there are two ...
- 27k
3
votes
2
answers
3k
views
Detecting Intersections of a Collection of Singly-Linked Lists
I was recently presented with the following problem...
You are given a collection of singly-linked lists (SLLs).
Return true if any of them share a common node (or “intersect”), or false otherwise.
...
- 497
2
votes
1
answer
86
views
Rust - implementation of multiple type of graphs with shared code
I am trying to improve my Rust coding skills. One thing which I find hard to tackle is how to shift from a polymorphism you can observe in e.g. Python to sth. similar in Rust?
Let me give you a ...
- 123
3
votes
0
answers
142
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 ...
- 918
6
votes
1
answer
314
views
Implementation of DFS algorithm 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 ...
- 209
5
votes
1
answer
108
views
Prune unreachable sections of a directed graph
I have a graph represented with an Adjacency set similar to:
...
- 153
1
vote
1
answer
139
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 ...
- 13
3
votes
1
answer
157
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'...
- 299
1
vote
0
answers
25
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 ...
- 111
1
vote
0
answers
107
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
690
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
56
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
199
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.
...
- 11
2
votes
0
answers
100
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 ...
- 27k
2
votes
1
answer
63
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,693
2
votes
1
answer
100
views
C++ Graph class with multiple property maps (edit)
I wrote an improvement from my previous graph class: Link
...
- 1,693
1
vote
1
answer
51
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:
...
- 27k
1
vote
1
answer
67
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 ...
- 65
1
vote
1
answer
178
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
167
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). ...
- 958
3
votes
1
answer
453
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
57
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
3
votes
1
answer
541
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,342
3
votes
1
answer
203
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
127
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'.
...
- 311
5
votes
0
answers
122
views
Dijkstra's algorithm in Perl
I have this Perl module project.
My implementation of the Dijkstra's algorithm follows:
...
- 27k
2
votes
2
answers
151
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 ...
- 27k
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:
...
- 27k
6
votes
3
answers
437
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 ...
- 337
1
vote
1
answer
89
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 ...
- 27k
3
votes
1
answer
158
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 ...
- 27k
1
vote
0
answers
56
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
...
- 27k
4
votes
1
answer
350
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 ...
- 27k
4
votes
1
answer
198
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
673
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
86
views
1
vote
0
answers
44
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
76
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
132
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
376
views
3
votes
1
answer
114
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
218
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. ...
- 157