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

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

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