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.

Filter by
Sorted by
Tagged with
2
votes
1answer
53 views

Dijkstra's algorithm in graph (Python)

I need some help with the graph and Dijkstra's algorithm in Python 3. I tested this code (look below) at one site and it says to me that the code took too long. Can anybody suggest how to solve that? ...
3
votes
0answers
66 views

Modified Tarjan's algorithm for reporting the edges within the strongly connected component

As described in his paper, Tarjan's algorithm reports only the nodes of the strongly connected components. For my use, I would also like to also have the edge list of the components (so that I can run ...
5
votes
1answer
97 views

Kings Tour Python

This is a depth-first search Kings Tour. I call it like this because the king must pass by all coordinates only touching them once (like a knights tour). How could I improve? Thank You ...
1
vote
0answers
27 views

Dijkstra's shortest-path algorithm implemented via Priority Queues and an adjacency matrix represented graph

My adjacency matrix looks like this, where non-zero weights denote edges. [0, 2, 0, 0, 3] [2, 0, 2, 4, 0] [0, 2, 0, 3, 0] [0, 4, 3, 0, 1] [3, 0, 0, 1, 0] Here's my attempt, would appreciate a code ...
2
votes
1answer
86 views

Prim's algorithm via Priority Queues to print the minimum spanning tree of an adjacency matrix undirected graph

My adjacency matrix looks like this, where non-zero weights denote edges. [0, 2, 0, 0, 3] [2, 0, 2, 4, 0] [0, 2, 0, 3, 0] [0, 4, 3, 0, 1] [3, 0, 0, 1, 0] Here's my attempt: ...
3
votes
2answers
63 views

Prim's algorithm via Priority Queues to print the minimum spanning tree of an undirected graph

Here's my attempt, I believe the runtime is O(V*(ElogE + log E)) since the while loop runs V times and it takes ElogE + log E to do the priority queue operations inside the loop. ...
6
votes
1answer
106 views

Graph implementation with Dijkstra

So, here is the code: ...
3
votes
1answer
35 views

Detecting a cycle in a directed graph via an adjacency list implementation and a recursive DFS

Here's my attempt. I iterate through each vertex in the graph and do a DFS to see if I reach back on a vertex I already visited in this vertex's iteration. It seems to work but I am not satisfied with ...
7
votes
1answer
199 views

Path finder for network link wiring

I have created a Path finder. The aim is to find ALL paths that join a Point A to a Point B. I have defined an object Segment which is a link between two assets. It ...
2
votes
0answers
23 views

Data Visualization (rendering env)

How can I improve this code? It renders a ML env with openAI gym and matplotlib. I am new to coding so not sure if my variables or format or any lines can be improved. ...
7
votes
1answer
85 views

Cycle detection in undirected graphs with recursive DFS

I wrote a very simple implementation of cycle detection in an undirected graph; I'm not interested in applying it to any real-life case: it's just for explaining the basic idea behind cycle detection ...
3
votes
0answers
44 views

LeetCode: Number of enclaves C#

https://leetcode.com/problems/number-of-enclaves/ Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land) A move consists of walking from one land square 4-directionally to ...
6
votes
1answer
67 views

Graph: Depth First Search (N citizens with pairs of friends)

I have solved problem 10608 on UVA Online Judge using Python 3.5.1. My solution works, but it takes too long to run when the online judge evaluates it. Problem There is a town with N citizens. It is ...
4
votes
1answer
89 views

Graph implementation in C

I've recently been learning C on my own, and I thought I'd try my hand at writing a graph implementation. ...
4
votes
1answer
91 views

A graphing calculator

I wrote a calculator that can solve equations with variables using matplotlib and sympy. I am looking for tips on performance and style. How can I improve on this calculator? Is it a good idea to use ...
6
votes
1answer
133 views

Air Quality/Environment Monitoring Web App using Plotly Dash

Overview & Motivation This project manages and displays sensor data (temperature, humidity, Air Quality Index). The sensor data is displayed by the sensor manufacturer, PurpleAir, but their tool ...
3
votes
1answer
120 views

Implementing a Directed and Undirected Graph in Java

I am learning Graphs on my own and want to use a graph for a personal small project, so I decided to take a look here in Code Review for some cool implementations and came across this one by Maksim ...
1
vote
0answers
32 views

Finding strongly connected components in a directed graph using Kosaraju's algorithm

I'm working through Stanford's algorithms course on edX. One of the programming assignments is to find strongly connected components using Kosaraju's algorithm, on a graph with ~875,000 vertices. My ...
1
vote
0answers
11 views

LP constraint problem with scipy

For this graph and its vertex cover I try to compare the LP solution with the optimal and the rounded solution. ...
4
votes
2answers
623 views

Floyd-Warshall Path Reconstruction

Below is the implementation for the Floyd-Warshall algorithm, which finds all-pairs shortest paths for a given weighted graph. The function floyd_warshall takes a ...
4
votes
1answer
107 views

Extreme use of pointers in adjacency list graph construction?

Playing around with pointers in C++, implemented an adjacency list graph. Am I going too far/extreme trying to place data onto the heap? graph.h ...
3
votes
2answers
92 views

Independent cascade model for networkx graphs

Similar to this question, I implemented the independent cascade model, but for a given networkx graph (including multigraph with parallel edges). My focus is on readability, pythonic-ness, and ...
5
votes
1answer
64 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 ...
1
vote
0answers
36 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 - ...
4
votes
0answers
50 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 ...
8
votes
2answers
343 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 ...
11
votes
1answer
189 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 ...
7
votes
1answer
255 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? ...
2
votes
1answer
103 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 ...
3
votes
0answers
68 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 ...
3
votes
1answer
150 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-...
3
votes
2answers
47 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 ...
1
vote
0answers
67 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 ...
1
vote
0answers
115 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 ...
2
votes
0answers
45 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 <...
2
votes
1answer
317 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. ...
-2
votes
1answer
73 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 ...
6
votes
0answers
314 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 ...
3
votes
1answer
91 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 ...
1
vote
0answers
81 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 ...
3
votes
1answer
44 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 ...
4
votes
1answer
70 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 ...
2
votes
0answers
44 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 ...
4
votes
1answer
135 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: ...
4
votes
2answers
75 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 ...
1
vote
2answers
168 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 ...
2
votes
1answer
104 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 ...
2
votes
1answer
35 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 ...
3
votes
1answer
67 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 ...
3
votes
1answer
218 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: ...

1
2 3 4 5
14