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.

87 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
300 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 ...
5
votes
1answer
622 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
150 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
516 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 dfs on it. How can I make the ...
5
votes
0answers
192 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
2answers
113 views

Heights of Cats

I have an assignment to solve this problem. However, I have exceeded the time limit required, can anyone suggest where to improve my code? Cats like to sit in high places. It is not uncommon to see ...
4
votes
0answers
51 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 ...
4
votes
0answers
34 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
107 views

Add an edge to a graph to minimize the average shortest path length

This program is used to find the nodes in a grid network, between which, if an edge is added, the average shortest path length of the entire grid reduces by the most. "Average shortest path length" ...
4
votes
0answers
104 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
203 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
944 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 ...
3
votes
0answers
43 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
0answers
31 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 ...
3
votes
1answer
92 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
90 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 ...
3
votes
0answers
75 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
52 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
207 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
1k 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
602 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
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
324 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
345 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
402 views

Finding cycles in a graph that pass through a vertex at most k times

I have a project that relies on finding all cycles in a graph that pass through a vertex at most k times. Naturally, I'm sticking with the case of k=1 for the sake of development right now. I've come ...
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
57 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
74 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
65 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
382 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
78 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
765 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
103 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
127 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
40 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
366 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
376 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
163 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. ...
2
votes
0answers
528 views

C++ STL graph implementation with out and in adjacency list

I'm looking for a code review on the following C++/STL graph implementation: Edge ...
2
votes
0answers
2k views

Prim's MST Java implementation

Can someone review this code, just have look if it's logically correct or If you may point me to a more simple and minimalist program ...