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
7
votes
3answers
303 views

Draw a 2d graph using slashes

Given a list of integers a 2D graph has to be plotted taking 1st, 3rd, 5th, ... numbers as upward slope and 2nd, 4th, ... numbers as downward slope. I have used a Python list to do it. Is there any ...
0
votes
0answers
63 views

Kosaraju's algorithm is too slow

I just implemented the Kosaraju's algorithm in Go. I tried to implement the same algorithm that is described in the relevant Wikipedia page: ...
-1
votes
1answer
41 views

is my Prim's MST implementation terse enough?

I did research because I want to learn Kruskal's and Prim's MSTs. I did research and after a solid understanding, I went to my textbook and got their libraries: https://algs4.cs.princeton.edu/code/...
0
votes
1answer
47 views

Recursive DFS to find Euler Cycle

I have referred to this for what constitutes as an Euler Cycle: https://xlinux.nist.gov/dads/HTML/eulercycle.html This assignment required me to use Depth First Search and have the methods I have ...
3
votes
2answers
73 views

Finding Number of Objects in Image

I wrote a program that, given a 2D array representing pixels in a birds eye view image, it returns the number of Objects in the image. Pixels that are connected in the up, down, left, and right ...
-1
votes
1answer
67 views

Graph coloring problem with Spark (JAVA)?

I am trying to create the algorithm described in the image from this link Simply put any two adjacent nodes must not share tuples and if they do they are colored with the same color. If there's a ...
1
vote
0answers
46 views

Bad performance of a Graph Algorithm

I implemented a solution for the problem below, but its performance is not good. I know I can find the solution online, I'm trying to understand what is causing the bad performance in ...
0
votes
0answers
23 views

Loan graph simplification in Java: an arc minimization algorithm

In this post, I will present an interesting (to me) algorithm for reducing the number of arcs in a financial loan graphs. (The class belongs to this GitHub repository.) ...
0
votes
0answers
22 views

Loan graph simplification in Java: the graph data structures

This post presents the loan graph implementation. The class belongs to this GitHub repository. net.coderodde.loan.model.Node: ...
1
vote
1answer
42 views

Loan graph simplification in Java: the recursive DFS for searching for directed cycles

The class in this post returns a directed cycle in a financial loan graph. A financial loan graph consists of nodes and directed arcs. If there is an arc \$(u, v)\$ with weight \$w = w(u, v)\$, then ...
1
vote
0answers
36 views

Graph stored as adjacency list or as endpoints and intervals

I tried speeding up my Graph class, so I removed the Node class and Edge class, and decided to use arrays and ArrayLists. My 2 implementations seem very similar, ...
4
votes
3answers
571 views

Compute shortest path in undirected graph

In a recent coding interview I was asked to write a program which takes as input two text lines: The first one represents a graph, formatted as a sequence of undirected edges like ...
0
votes
2answers
229 views

Build order from a dependency graph (Python)

Below is my attempt at the challenge found here. The challenge is "Find a build order given a list of projects and dependencies." Already given are the classes Node and Graph (which I can ...
2
votes
1answer
59 views

Turn an array of pairs of start and end points into an ordered series

Given an array of pairs, for example: [["Denver", "Miami"], ["Miami", "Tulsa"], ["LA", "Okmulgee"], ["Mobile", "Portland"...
1
vote
0answers
61 views

Python, create a network with a given node and edges from pandas dataframe

I'm working on a code snippet that generates a network graph. ...
1
vote
1answer
135 views

Cheapest flights within k stops algorithm in JavaScript

The problem: There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is ...
4
votes
1answer
98 views

Python leetcode: scheduling courses to meet prerequisite requirements

This is my solution to Leetcode #210, Course Schedule II. There are a total of numCourses courses you have to take, labeled from ...
1
vote
1answer
45 views

PureScript breadth-first search implementation

For context, I wrote a function, get_servers, for the game Bitburner which is usually played by writing JavaScript code. Instead, I used PureScript to write the ...
1
vote
1answer
56 views

Checking whether a graph is connected in an immutable way

I have this function at the moment ...
0
votes
0answers
64 views

Graph Implementation for Social Network

I'm trying to implement a graph structure in python, making use of the classes Vertex, Edge and Graph. The goal is to read a csv file that contains users names and a number (weight), like such Lynch,...
8
votes
1answer
191 views

Find all paths in a graph

My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved? Can some form of memoization be used here? There are cases ...
2
votes
0answers
34 views

Dijkstra from scratch

I implemented the Dijkstra algorithm from scrath and wonder if I can save some code? The whole algorithm is here. n is the number of nodes, and m the number of edges. 1 ≤ 𝑛 ≤ 10^4, 0 ≤ 𝑚 ≤ 10^5, 𝑢 ...
0
votes
0answers
35 views

Enumerating all fixed-length paths from a vertex in a graph

Enumerating all fixed-length paths from a vertex in a graph 1. Graph-related classes Base implementations of the relevant classes in my graph library. I'm using C#9 in a .NET 5 project. I opted to use ...
4
votes
2answers
131 views

Leetcode: number of islands

I am on my second iteration of the famous "Number Of Islands" graph problem on Leetcode. https://leetcode.com/problems/number-of-islands/ ...
2
votes
0answers
218 views

Slow render of a graph path using python matplotlib animation

I am computing shortest paths of graphs using Python Networkx and Matplotlib. I'm focused on animating the route inspection problem path in particular here. My goal is to smoothly render such ...
0
votes
0answers
17 views

Add an edge to a directed acyclic graph such that it stay acyclic

My code doesn't actually do that per se, but rather it find every possible edge that can be added without creating a cycle. The return value of the function ...
3
votes
1answer
129 views

Optimizing Dijkstra on grid Python (Microsoft Interview)

Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which ...
3
votes
1answer
53 views

Collect distances from 1 point to all others in a graph

Problem: I have a weighted graph. I want to get distance from definite point to all other points in the graph.(and then get path to them) I used modified dijkstra algorithm So, here is code: ...
0
votes
1answer
69 views

BFS implementation in JAVA

...
-3
votes
1answer
240 views

HackerRank | Roads and Libraries - Code Optimization

Major Edit: I wish people threw in a comment regarding what they are expecting instead of downvoting this question. I am quite appreciative of constructive feedback. I know it is only 3 people out of ...
0
votes
2answers
65 views

Generating a random directed graph

I wrote a function that returns a directed graph as an adjacency matrix. The function requires two arguments: the amount of nodes and the amount of edges. At first, nodes are placed and instantly ...
2
votes
1answer
120 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
80 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
194 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
126 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
612 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
144 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
126 views

Graph implementation with Dijkstra

So, here is the code: ...
3
votes
1answer
68 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
202 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
26 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
105 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 ...
2
votes
0answers
49 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
115 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
207 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
135 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
407 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
414 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
72 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
15 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. ...

1
2 3 4 5
14