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

99 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
86 views

### Recursive and iterative implementation on Kosaraju algorithm

Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below, For each vertex u of the graph, mark u as ...
74 views

### Frequency analysis for simultaneous dice rolls

My professor told me to optimize my perl code, but he wouldn't tell me what exactly - just make it simpler. I changed some little things but nothing major. Am I missing something? The task was: ...
136 views

### Implementation of container searchable by any element

Writing game engine as a hobby, I've come across many situations where I need a container like a map, but searchable by different keys: a block allocator where a block needs to be searched by either ...
399 views

### Kattis problem Amanda Lounges

I wrote this solution to Kattis problem Amanda Lounges in Scala. TL;DR: It's a graph theory problem where I read in a list of edges from stdin and try to compute the minimum number of nodes that ...
627 views

### Pseudo-parallel depth-first search

I'm writing a small program that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel depth-first search (dfs) on it. ...
80 views

### graphtimer v2 - Utility to plot timings

GitHub repo (MIT) Clone the repo and replace the contents of example.py with the one at the bottom and you'll have everything setup. Explanation of the code A ...
157 views

### Assembling and traversing a graph, given a list of items and parent pointers

I've written a function which takes input such as this: ...
200 views

### Simple graph in Rust

I have written simple code to construct a graph, but I think there are too many different types for such a simple task. In this code I need to store Node structs ...
1k views

### Graph as adjacency lists: BFS DFS Topological Sort

I have written some code to practise graphs. Graph is represented as vector<list<int>> . Would you share some feedback with me? Are algorithms correct ...
64 views

### A generic DFS in JavaScript

I implemented a general function for a depth-first-search (DFS) using JavaScript with default arguments and functions that need to be provided in order for it to work. This function is using ...
67 views

### Two solutions to leetcode 127.wordLadder

I am working on Word Ladder - LeetCode Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such ...
38 views

### Modular graph searcher

some words in forehand: Unfortunately this post is very long, thus I decided to put the whole and compilable code into an online compiler. The link is at the end of this post. In the last few days I ...
115 views

### Algorithm to find connected tiles (percolation)

I wrote a little program in JavaFX which displays a path of neighbouring open tiles going from top to bottom. It should simulate a percolation. The algorithm iterates through the whole grid (every ...
112 views

### Graph Python challenge 2 (revised)

I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python: You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
64 views

### Finding connected components in the application task

I have n indexed socks, each of which has one of k colors. I also have a list that states which two socks I must wear at each of ...
301 views

### Time Limit Exceeded with shortest path algorithm

The problem: SHPATH You are given a list of cities. Each direct connection between two cities has its transportation cost (an integer bigger than 0). The goal is to find the paths of minimum cost ...
2k views

### Finding all paths between nodes in a graph

I wanted to write a function paths that returns the possible routes between two nodes in a graph. For example: ...
91 views

### Minimum amount of edges that needs to be traversed to visit all vertices… or something like that

So I have this problem, where I'm given m connections over n vertices. The vertices are labeled ...
37 views

### Converting a graph to a directed graph with order of the nodes defined by post-order traversal

Background: I'm implementing an algorithm from the paper Polygon Area Decomposition for Multiple-Robot Workspace Division and one of the steps is to represent a polygon as a graph. This is done by ...
44 views

### Breadth First Search Python Implementation

I have the below implementation of the BFS algorithm, in which I've used OrderedDict instead of a list or ...
114 views

### Finding connected components of a graph

I have a graph represented using a dict of sets, e.g. ...
49 views

### Django project for events of the day, grouped by keywords in common

I have made a website where people write about their day and see it analyzed. In particular, the website takes event titles and groups them together if they have any common words (after stemming the ...
59 views

### Graph Search in C++17

Overview I am constructing a Graph with randomly generated nodes called Positions. The Graph has a width and a height and is represented using an adjacency list <...
74 views

I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here. ...
85 views

### SPOJ Fast Matching challenge

I wrote a solution to the MATCHING challenge on SPOJ: FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, ...
55 views

### Find spanning tree with maximum edges with the same weight

For my university assignment I need to come up with an algorithm to find a spanning tree with maximum number of edges with same weight. I received an algorithm suggestion in this Stack Overflow answer....
313 views

### Skiena's DFS on unweighted graphs, in Python 3, with adjacency-list implementation

In the Algorithm Design Manual (2nd ed) pp 172 - 173, Skiena writes: As algorithm design paradigms go, a depth-first search isn't particularly intimidating. It is surprisingly subtle, however ...
50 views

### SparseGraph: A representation of a mathematical graph

I'm working on a SparseGraph which reflects the mathematical notion of a graph. All code included here works in all of the basic test cases that I've tried. However, I'm most concerned about the ...
2k views

### Strongly connected components in a graph: Kosaraju's algorithm

I implemented Kosaraju's algorithm on a graph with 800k vertices and 5100k edges. The time taken by various operations are: building graph took 11.84 seconds ordering took 2.54 seconds ...
661 views

### Comparing linear time strongly connected component algorithms in Java

So I have implemented three linear time ($\mathcal{O}(V + E)$) algorithms for finding strongly connected components of a (directed) graph. A strongly connected component is just a maximal subset of ...
3k views

### Implementation of Dijkstra's Algorithm in JavaScript that returns both shortestDist/shortestPaths

I decided to try to understand the basic idea behind Dijkstra's algorithm better so I implemented it in JavaScript (the only language I am proficient in as of now) so I could really see what was ...
4k views

### Depth first search implementation

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the depth first search section (5.8) using javascript. Note you can execute the code here if you don't ...
2k views

### Brute force shortest path in Java

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
341 views

### Frequent subgraph mining program

I'm trying to make a programme that reads graphs from a .txt file, puts them in a vector, and finally puts the frequent closed graphs in another resulting file. I'...
442 views

### Golang A* Pathfinder

This is a generalized A* pathfinder in Go. I am new to the language and am eager for advice about best practices. In particular, I am not sure if the type assertion I make in ...
1k views

### Efficient compile-time directed graph

During my research in Rigid Body Dynamics, (where Contact Graphs are used to solve the contact problem) I came across the question if it is possible to define at compile time a directed graph (class) ...
2k views

### Bidirectional Edmonds-Karp algorithm in Java

The Edmonds-Karp algorithm relies on breadth-first search in order to find an augmenting path in the residual flow network. This version of the algorithm uses bidirectional breadth-first search in ...
275 views

### Kruskal's algorithm in Java - follow-up

The previous and initial iteration at Kruskal's algorithm in Java Now what I did is remove the fields and let the actual Kruskal-routine create the required data structures in the local scope, ...
43 views

### Generic Graph Traverser

I have built this Generic Graph traverser, I have this implemented with DFS, I feel it will work equally fine with BFS too. What do you think of this implementation? I want help in reviewing the <...
43 views

### Create Graph With Eulerian Tour in Rust

Eulerian Tour is a list of nodes that has a specific way to traverse the graph: it starts at one node, traverses along every edge in the graph exactly once and returns to the starting node. Here is ...
61 views

### Parsing a Graph To Convert It Into Adjacency Lists And CSR And Then Make Connection Queries Using Bidirectional BFS

I was assigned an university project where I had to parse directed graph files coming from SNAP and then convert them into CSR (Compressed Sparse Row) format. Then the client must have the ability to ...
24 views

### Modelling a program with modules, symbols, and dependencies

My scenario is the following: I'm modelling a Program which has many Modules. Each Module has Symbols, some of which pointing at dependencies, which are other Modules. So a Module can be pointed to by ...
92 views

### Project Euler #81 in Haskell: minimal path sum through a matrix

I just completed Project Euler Problem 81 in Haskell: In the 5 by 5 matrix below, ...
68 views

### DFS logic to traverse a graph

I tried to literally convert recursive algorithm taught here to iterative, by simulating the recursive stack exactly as much as possible. I have tested my code and it passed all test cases. Please ...
587 views

### Max flow Ford-Fulkerson using DFS augmented path retrieval

I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably? ...
90 views

### Number of subGraphs with given vertice and degree

Demo: There are three questions: How many subgraphs whose Num(vertices) <= 5 and all vertices have two degrees? How many subgraphs whose Num(vertices) == 4 and all vertices have 3 degrees? If ...
87 views

### Computing most-cost effective loans in financial graphs using Java

Problem statement We are given a directed graph $G = (V, A)$, where $V$ is the set of actors and $A \subseteq V^2$ is the set of directed arcs. Existence of an arc $(u, v) \in A$ is ...
42 views

### Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...