The 2024 Developer Survey results are live! See the results

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

722 questions
Filter by
Sorted by
Tagged with
25 views

### Numerical Solution of Geodesic Equations with Schwarzschild Metric [closed]

I tried to numerically solve the geodesic equation's in Schwarzchild spacetime. The program for my knowledge is working but when I modified the metric the graph was the same. Please let me know if ...
1 vote
46 views

### How to count disconnected components in grid efficiently, if we can move left, right, down and top from any cell

I solved this problem: A. Ice Skating, Codeforces My approach was to create grid from given snow drifts coordinates, then convert this grid into graph and then count how many disconnected components ...
• 161
41 views

### Graph Neural Network (GNN) (2)

This is an implementation of a graph neural network. Edges are represented by an egde-list. ...
• 607
1 vote
129 views

### Graph Neural Network (GNN) (1)

The given datasets are graph data structure that represents social interactions. The nodes will be represented as People{node_id, edge, gender, occupation} and the ...
• 607
2k views

### Bug Byte puzzle from Jane Street

This is a puzzle from Jane Street. Given this graph: Fill in the edge weights in the graph with the numbers 1 through 24, using each number exactly once. Labeled nodes provide some additional ...
• 5,604
69 views

### Clique Connect: minimum spanning tree

Problem Statement You are given a weighted undirected graph G with N vertices, numbered 1 to N. Initially, G has no edges. You will perform M operations to add edges to G. The i-th operation (1≤i≤M) ...
• 244
312 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 ...
• 53
114 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 ...
• 63
228 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 ...
• 63
1 vote
111 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: ...
53 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 ...
699 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 ...
35 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
302 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 ...
• 151
129 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 ...
1 vote
183 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 ...
230 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
85 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
365 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 ...
302 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
213 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 ...
• 29k
6k 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
116 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
147 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
337 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
118 views

### Prune unreachable sections of a directed graph

I have a graph represented with an Adjacency set similar to: ...
• 153
1 vote
151 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 ...
243 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'...
• 319
1 vote
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
128 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: ...
• 341
800 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 ...
65 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
238 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. ...
120 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 ...
• 29k
67 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,703
104 views

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

I wrote an improvement from my previous graph class: Link ...
• 1,703
1 vote
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: ...
• 29k
1 vote
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 ...
• 165
1 vote
239 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
228 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). ...
• 968
531 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
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 ...
• 13
862 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 ...
240 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 ...
138 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'. ...
171 views

### Dijkstra's algorithm in Perl

I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
• 29k
154 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 ...
• 29k
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: ...
• 29k