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.

88 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
339 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 ...
6
votes
0answers
546 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. ...
5
votes
0answers
62 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 ...
5
votes
1answer
672 views

Strongly connected component finding based on the guava graph library with Kosaraju

I have been writing a small compiler generator for which I need to solve the strongly connected component problem. As the Guava library contains, to my knowledge, no implementation for that problem, I ...
5
votes
0answers
153 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: ...
5
votes
0answers
194 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 ...
5
votes
0answers
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 ...
4
votes
0answers
38 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 ...
4
votes
0answers
36 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 ...
4
votes
0answers
97 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 ...
4
votes
0answers
106 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! ...
4
votes
0answers
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 ...
4
votes
0answers
208 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 ...
4
votes
0answers
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: ...
4
votes
0answers
951 views

Canvas animation of network nodes and edges

Having to give the idea of an ever changing network of nodes (each with different impact and possibly more than one color) connecting each other to create something. I wanted to give it depth ...
4
votes
0answers
88 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 ...
3
votes
0answers
40 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 ...
3
votes
0answers
49 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 <...
3
votes
1answer
115 views

Implementation of generic Graph class and Dijkstras

I participate in competitive programming contests, and I found myself implementing and re-implementing graphs constantly. So I decided to create a reusable implementation of a Graph class, and ...
3
votes
0answers
76 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, ...
3
votes
0answers
53 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....
3
votes
0answers
230 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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
619 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 ...
3
votes
0answers
34 views

Data Explorer query that makes bar graphs

I wrote a query for SEDE that I think is pretty cool. It uses the currently available graphing capabilities (scatter plots) to create a bar graph. I have used it as the subject for a self-answer on ...
3
votes
0answers
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 ...
3
votes
0answers
3k 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 ...
3
votes
0answers
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 ...
3
votes
0answers
335 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'...
3
votes
0answers
373 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 ...
3
votes
0answers
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) ...
3
votes
0answers
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 ...
3
votes
0answers
266 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, ...
2
votes
0answers
50 views

Finding connected components of a graph

I have a graph represented using a dict of sets, e.g. ...
2
votes
0answers
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 ...
2
votes
1answer
58 views

Modelling Immerman–Szelepcsényi in Haskell

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. ...
2
votes
0answers
78 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, ...
2
votes
0answers
67 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 ...
2
votes
0answers
394 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? ...
2
votes
0answers
79 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 ...
2
votes
0answers
86 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 ...
2
votes
0answers
39 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 ...
2
votes
0answers
778 views

Graph represented by adjacency list

I've started to learn about graphs and how to represent them in code. Here is my attempt of making an adjacency list for an undirected graph. I'm looking for suggestions on how to improve it and what ...
2
votes
0answers
110 views

Network of senders and receivers in C++

I am trying to create a Sender-Receiver Network. What do I mean under a Sender-Receiver Network. That means that there is some structure which consists of Nodes and connections between them which will ...
2
votes
0answers
129 views

Neo4j traversal algorithm to find dense nodes

I am trying to get familiar with traversals algorithms implementations in Neo4j and to practice I am implementing classic graph algorithms (not judging if is the best approach or not, just for the ...
2
votes
0answers
42 views

Modeling a control polygon for a piecewise spline curve

Aim I'm modeling a control polygon for a piecewise spline curve. Each sub-spline is defined by a location the spline must pass through, as well as a forward tangent, and a backwards tangent. The ...
2
votes
0answers
377 views

Second degree connection ranking

Problem Find 2nd degree connections ( friends’ friends), output these 2nd degree connections ranked by number of common friends (i.e 1st degree connections) with you, (example: if 2nd degree ...
2
votes
0answers
408 views

Tarjan's strongly connected component finding algorithm

Here is my code for Tarjan's strongly connected component algorithm. Please point out any bugs, performance/space (algorithm time/space complexity) optimization or code style issues. ...
2
votes
0answers
171 views

unordered_multimap approach to adjacency list and graph search

I'm looking for suggestions on how to improve the usage of modern C++ features with this simple graph search algorithm, particularly with regard to the use of STL containers and lambda expressions. ...