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

640 questions
Filter by
Sorted by
Tagged with
47 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 ...
85 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. ...
37 views

### A star in C++ path tracing issue [closed]

I am implementing the A* algorithm on a 2D grid of nodes (squares). I am unable to trace back the path from the end node once the path is solved. I think that I am not linking the nodes correctly. If ...
59 views

### Closest Pair heuristics, graph with adjacency matrix in C++17

I was trying to solve a problem that was briefly mentioned at the beginning of the "The Algorithm Design Manual" by Steven Skiena (Ch 1, Problem 26). It took me some time to build a working ...
176 views

### Dijkstra algorithm C#

I have implementing a simple version of Dijkstra's algorithm in C#. Could this be made more efficient? Does it need to be modified? ...
180 views

### Create a build order from a list of projects and their respective prerequisites

Another graph algorithm, this time to create a priority or build order. Provided with a starting List<Project> and ...
35 views

### Representing a graph with passable marks and actions

I wanted to have a framework to build Petri Nets from C# code. Petri net is a digraph with functional transitions and mark types. In books they tend to look like this: Here is what I came up with - ...
308 views

### My Graph Implementation In Python

I have implemented a graph based on theory, and I'd like some advice regarding best practice, and thoughts about what i didn't implement that would make it even more useful, along with ideas that are ...
146 views

### Test the hypothesis that the expected number of edges of a random connected graph is $O(n \log n)$

Motivation The most common model for a random graph is the Erdős–Rényi model. However, it does not guarantee the connectedness of the graph. Instead, let's consider the following algorithm (in python-...
84 views

### Trie implementation for strings in Swift

A trie for handling strings for an autocomplete dictionary. This passes my fairly casual tests, though it's always possible that there are broken edge cases, but I'm mainly concerned about design and ...
48 views

### Routes Between Node, Cracking the coding interview

I am going though Cracking the coding interview and trying to improve my coding interview skills. The question is "Given a directed graph, design an algorithm to find out whether there is a route ...
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 ...
46k views

...
46 views

### Fetching all nodes of a directed graph by an id of any node

Task: Rowset of all reachable(in any direction) nodes from any node in a graph. In other words I need to extract all nodes of a particular graph from a table in the database where graph specified by ...
45 views

### Directed graph and Dijkstra algorithm using heap

I have implemented directed graph and Dijkstra algorithm using heap in Python. I first implemented an abstract base class WeightedGraph, of which ...
64 views

### Kosaraju Algorithm in Java

Problem statement In simple words it say, count total Strongly connected components in the graph. All edges are undirected. I have the following code that uses ...
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 <...
60 views

### Graph coloring in Java

I'm solving the m-coloring problem using java. and I have following code that uses concept of recursion and backtracking. ...
65 views

### How to work in linear time with DFS

I tried a Hackerrank problem and it gives me a successful message, it works fine for Hackerrank criteria. The member states of the UN are planning to send 2 people to the moon. They want them to be ...
7k views

### MST Kruskal's algorithm in Python

I have this code for finding MST for undirected weighted graph, currently works for graphs with maximum 10 vertices. How can I update the code to scale for larger graphs? ...
71 views

### Optimizing nested loop for calculating geodesic distance

I segmented an image into N superpixels and constructed a graph based on that in which each superpixel is considered as a node. The information about neighbor superpixels is stored in ...
89 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 ...
89 views

### friendship program using graph type python/algorithm

I have created a program but I feel the def common(friendships, person1, person2) function can be more efficient, if anyone has any good idea how I can improve it I ...
34 views

### Implementing basic graph theory functions in APL with matrices

I had to solve three problems on graph theory that I solved by implementing a utility function and 3 functions, one for each of the problems. The problem set defines the input for all my functions as ...
72 views

### Prim's Algorithm

Prim's Algorithm This is an implementation of Prim's algorithm in Python. From Wikipedia: Initialize a tree with a single vertex, chosen arbitrarily from the graph. Grow the tree by one edge: ...
59 views

### Finding Build Order For Packages With Dependencies

I gave a shot to infamous finding dependency problem. I highly encourage to give it a go yourself before seeing the solution I came up with. Here is the problem statement: Given a list of ...
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 ...
97 views

### Graphs and Kruskal's Algorithm - Python OOP

This is my implementation of a graph and Kruskal's algorithm in Python. I wanted to design the graph module myself and I would like some feedback on the design. I tried to follow SOLID throughout. I ...
62 views

### Bellman Ford algorithm using vector

I have written this code for bellman-ford algorithm. Please review and suggest improvements: This code takes input graph as an adjacency matrix, and stores it the ...
70 views

### Directed Graph With Weights in Java

I am learning graph theory and I have implemented a Directed Graph with weights in Java. My next objective with this class is to learn more about algorithms like Dijkstra, Bellman-Ford, etc. I have ...
73 views

### Finding bridges in an Undirected Graph implementation in C#

I am implementing fundamental data structures in C# while trying to learn techniques in the language to make my code cleaner, more concise while using good programming practices. I have implemented ...
33 views

### How can I modify my graph traversal algorithm to increase efficiency?

I have an adjacency matrix "A" which I am using to represent a graph for a social network. Each node of the graph represents a person's name, and I am storing people's names in an 2-d array (the index ...
90 views

### Python implementation of Kahn's Algorithm

Please provide any suggestions on the below code for Kahn's algorithm. Can it be implemented in a better manner, or be improved: ...
63 views

### LeetCode: Network Delay Time Bellman Ford C#

https://leetcode.com/problems/network-delay-time/ There are N network nodes, labelled 1 to N. Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the ...
135 views

### Tarjan's Algorithm Python Implementation

I'm planning to use Tarjan's algorithm for a program in which I would be processing a file, converting the processed data to a dictionary, doing a topological sort on that dictionary (using this ...
49k views

### Depth-first search in Python

I wrote this DFS in Python and I was wondering if it correct. Somehow it seems too simple to me. Each node is a class with attributes: visited: Boolean ...
218 views

### Dijkstra's Algorithm implementation in Java

I am learning graph theory in CS and for practice, I have implemented Djikstra's algorithm in Java. I have created a GraphVertex class that contains information ...
24k views

### Adjacency List Graph representation on python

I began to have my Graph Theory classes on university, and when it comes to representation, the adjacency matrix and adjacency list are the ones that we need to use for our homework and such. At the ...
10k views

### Directed acyclic graph with topological sort

I have here a class which represents a directed acyclic graph (Graph) and a vertex in the graph (Vertex). The vertices are ...
81 views

### Efficient implementation of priority queue

I am trying to solve a maze problem. The input data is a matrix, where the individual element represents the height of the mountain in that particular area, I have to start from position (0,0) and go ...
28 views

### Pseudograph Implementation

I needed a special graph structure for my code and thought I'd write a generic one for later reuse. At first I wanted to use pointers instead of indices as map keys but I quickly forfeited that idea ...
418 views

### LeetCode: Longest String Chain (Java)

For the question, I had a pretty messy solution so I would like some advice on how to better use Java to make the code a bit cleaner. Also, a semi-hack that I did that I'm not proud of is checking if ...
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 ...
235 views

### HackerRank: Friend Circles (DFS in Java)

I got this problem on a HackerRank challenge and this was the best I could come up with. It's basically just using DFS to find connected components (in this case, friend circles). I was having a tough ...
2k views

### Finding a loop in a directed graph in Python

I wrote this code to find if a directed graph contains a loop or not. I am pretty new to graphs and I saw some examples on the internet but couldn't actually understand their implementations. So I ...
67 views

### algorithm to find a zero in a board game [closed]

I got asked this question in an interview and I came up with a solution which I shared in the below but apparently it was not enough to pass. I'm looking forward to hearing how this problem could be ...
1k views

### Graph coloring project in C++

I recently had to submit my 12th grade final project in C++, so I decided to make a game engine! That panned out just as you would expect (I am not touching OpenGL until they touch OOP), so I switched ...
384 views

### Graph Implementation in Java using Set and Map

There is a Graph implementation. I'm using Set to store unique Edges and Map to store Vertices and their associated edges. Assume Vertex and Edge class has been defined somewhere else implementing ...