Skip to main content

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
5 votes
3 answers
307 views

Find highest number of swaps within a set of possible duty swaps with networkx and PuLP

With huge help from Stack Overflow, I have created code which takes possible swap matches with given weights as an input and outputs a set of matches which gives the highest weight with the highest ...
Oehoe's user avatar
  • 53
4 votes
1 answer
108 views

Optimising Graphed Rewards

Relates to this and this. Simply put; I want to be able to distribute a total reward among network, where the distribution diminishes according to the depth of the network but the total sum of ...
Bob's user avatar
  • 149
2 votes
1 answer
220 views

Graphs for distributing rewards

I want to be able to distribute a total reward among referral network, where the distribution diminishes according to the depth of the network but the total sum of distributed rewards equals the ...
Bob's user avatar
  • 149
1 vote
1 answer
101 views

Path Compression Algorithm in C#

Let's consider a simple graph represented by the following edges, where true indicates a visible node and false indicates a non-visible node: ...
Shahar Shokrani's user avatar
0 votes
1 answer
51 views

Performance optimization of traveling salesman like issue

I need help optimizing the performance of this, which is essentially similar to the traveling salesman problem, with the addition that I want to make the graph complete first, with the weight of the ...
Mattis Schulte's user avatar
5 votes
3 answers
671 views

Program that brute forces to find the minimum dominating set

This program solves the minimum dominating set but it takes an insanely long time to run. In case you do not know, in graph theory, a dominating set for a graph G is a subset D of its vertices, such ...
BeginnerProgrammer6's user avatar
0 votes
1 answer
33 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 ...
Ruan's user avatar
  • 101
3 votes
1 answer
207 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 ...
jbduncan's user avatar
  • 151
3 votes
1 answer
117 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 ...
Goubermouche's user avatar
1 vote
0 answers
166 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 ...
WilliamMorris's user avatar
8 votes
1 answer
211 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 ...
Bobray's user avatar
  • 81
5 votes
1 answer
82 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 ...
Jannes Braet's user avatar
0 votes
2 answers
331 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 ...
Exercise To The Reader's user avatar
2 votes
1 answer
275 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 ...
Kalak's user avatar
  • 176
5 votes
1 answer
203 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 ...
coderodde's user avatar
  • 28.3k
3 votes
2 answers
5k 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. ...
James Law's user avatar
  • 497
2 votes
1 answer
114 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 ...
qoqosz's user avatar
  • 123
3 votes
0 answers
146 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 ...
durron597's user avatar
  • 918
6 votes
1 answer
332 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 ...
KetDog's user avatar
  • 209
5 votes
1 answer
114 views

Prune unreachable sections of a directed graph

I have a graph represented with an Adjacency set similar to: ...
Tom McLean's user avatar
1 vote
1 answer
150 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 ...
Janice Lee's user avatar
3 votes
1 answer
226 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'...
Edziju's user avatar
  • 319
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 ...
Ritzy Dev's user avatar
  • 111
1 vote
0 answers
123 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: ...
Lance's user avatar
  • 351
4 votes
1 answer
765 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 ...
average math enjoyer's user avatar
2 votes
0 answers
64 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? ...
Node.JS's user avatar
  • 389
1 vote
0 answers
228 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. ...
Miguel Gil's user avatar
2 votes
0 answers
115 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 ...
coderodde's user avatar
  • 28.3k
2 votes
1 answer
66 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 ...
frozenca's user avatar
  • 1,713
2 votes
1 answer
104 views

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

I wrote an improvement from my previous graph class: Link ...
frozenca's user avatar
  • 1,713
1 vote
1 answer
53 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: ...
coderodde's user avatar
  • 28.3k
1 vote
1 answer
68 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 ...
user1311627's user avatar
1 vote
1 answer
225 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 ...
NBK's user avatar
  • 11
6 votes
1 answer
219 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). ...
lukstru's user avatar
  • 968
3 votes
1 answer
500 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 ...
Node.JS's user avatar
  • 389
1 vote
1 answer
58 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 ...
mclord's user avatar
  • 13
3 votes
1 answer
793 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 ...
Gaslight Deceive Subvert's user avatar
3 votes
1 answer
236 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 ...
return_of_the_kin's user avatar
2 votes
0 answers
135 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'. ...
Kushagr Jaiswal's user avatar
5 votes
0 answers
165 views

Dijkstra's algorithm in Perl

I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
coderodde's user avatar
  • 28.3k
2 votes
2 answers
152 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 ...
coderodde's user avatar
  • 28.3k
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: ...
coderodde's user avatar
  • 28.3k
6 votes
3 answers
487 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 ...
KermitTheFrog's user avatar
1 vote
1 answer
96 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 ...
coderodde's user avatar
  • 28.3k
3 votes
1 answer
162 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 ...
coderodde's user avatar
  • 28.3k
2 votes
0 answers
66 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 ...
coderodde's user avatar
  • 28.3k
4 votes
1 answer
357 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 ...
coderodde's user avatar
  • 28.3k
4 votes
1 answer
214 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 ...
AKSingh's user avatar
  • 141
1 vote
3 answers
90 views

DFS search that returns "not found" or distance

Assuming I've the following code: ...
Regyn's user avatar
  • 143
1 vote
0 answers
47 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: ...
skynaive's user avatar
  • 162

1
2 3 4 5
15