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
1 vote
1 answer
38 views

Number of paths in a randomly labeled complete graph

I have a complete graph with n vertices, set W (let's say W = {1,2,3}) and a path ...
user avatar
  • 13
3 votes
1 answer
51 views

Call-flow graph from Python abstract syntax tree

Below is my code for building a call-flow graph from a Python abstract syntax tree. I'm not satisfied with it because the algorithm is very complicated. Perhaps much more complicated than it needs to ...
user avatar
3 votes
1 answer
53 views

Topological Sort C++

Comments on optimizing the code or improving the code are requested. The input parameters to the class constructor are a one dimensional array of job ID's and the second argument is a list of vectors ...
user avatar
2 votes
0 answers
49 views

Bellman-Ford algorithm implementation

I have used an adjacency list to represent the graph. This implementation is based on the procedure given in the book 'Introduction to Algorithms'. ...
user avatar
5 votes
0 answers
63 views

Dijkstra's algorithm in Perl

I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
user avatar
  • 25.3k
2 votes
2 answers
133 views

Much more efficient trisexual genetic algorithm for TSP in Java

(The entire project lives there.) This time, I have made the previous version of the GA for TSP run faster by around the factor of 6+. The idea is to cache the tour costs with the actual tour objects ...
user avatar
  • 25.3k
2 votes
0 answers
64 views

Genetic trisexual algorithm for TSP in Java [duplicate]

(A more efficient version of the GA.) This is my the very first take ever on GA: GeneticTSPSolverV1.java: ...
user avatar
  • 25.3k
3 votes
1 answer
108 views

The shortest path between airports

Airlines need to provide their customers with flights to every corner, so they need an app that allows them to do so. The customer must be able to transfer when there is no direct connection. The ...
user avatar
1 vote
1 answer
45 views

Genetic TSP in Java with graph expansion

This post presents my take on TSP (travelling salesman problem). The idea is to: Take an input node i, Compute the entire graph ...
user avatar
  • 25.3k
3 votes
1 answer
66 views

Traditional vs. bidirectional Dijkstra's algorithm in C

I have this CLion project on GitHub. It constructs a directed, weighted graph consisting of 100 thousand nodes and 500 thousand directed arcs, picks two random nodes, and computes the shortest paths ...
user avatar
  • 25.3k
1 vote
0 answers
27 views

Directed weighted graph in C

I am working on a project that requires a directed weighted graph data structure. It looks like this: graph.h ...
user avatar
  • 25.3k
4 votes
1 answer
328 views

Searching for a performance bug in a C++20 pathfinding algorithm (NBA*) - follow up

I have followed some advice in the previous iteration, yet even the current version is too slow compared to the Java implementation of the same algorithm. (C++ version with ...
user avatar
  • 25.3k
4 votes
1 answer
86 views

Minimum vertex cover in a Bipartite Graph

I have written a function in Java to find minimum vertex cover in a bipartite graph. It is working on all the sample test cases I have used. However, due to lack of implementation and test cases ...
user avatar
  • 141
0 votes
0 answers
96 views

Parallel BFS OpenMP C

I'm trying to develop the code to make a parallel version of the BFS (topDown) algorithm on a graph. This is the code I have developed so far: ...
user avatar
1 vote
3 answers
62 views

DFS search that returns "not found" or distance

Assuming I've the following code: ...
user avatar
  • 143
1 vote
0 answers
33 views

Efficient algorithm to generate random multigraph (undirected) given nodes and degree

I wrote a simple algorithm to generate 1000 random graphs given total nodes and associated node degree. Graph is undirected with multiple edges and no self-loops. My current algorithm is very slow: ...
user avatar
  • 162
0 votes
0 answers
53 views

Efficient way to build random undirected graphs without self loops given total number of graph nodes and associated node degree

I wrote an algorithm to build 1000 different random graphs given number of nodes and node degree. Node degree is maintained between the random graphs. I am building these random graphs to input to a ...
user avatar
  • 162
1 vote
2 answers
81 views

Implementing graph for pathfinding

I need a graph for multiple pathfinding algorithms,so I wanted to ask whether my new graph implementation is ok. Would someone who works as a developer in related fields(Graphs, Pathfinding, ...
user avatar
  • 57
2 votes
2 answers
161 views

Graph Implementation with Dijkstra's Algorithm

Graph Interface: ...
user avatar
  • 51
3 votes
1 answer
78 views

Java Graph Implementation

Attempt to implement undirected graph with intentions of making a directed implementation too. I'm also new to Generics. I'm sure there's a lot of things I can do better ...
user avatar
  • 51
0 votes
0 answers
21 views

Does this dijkstra's implementation work on negative weights?

First of all, I am not exactly sure if this is the traditional Dijkstra's implementation. After polling the vertex, I am relaxing all of the neighbors of the polled vertex. However, according to the ...
user avatar
0 votes
1 answer
56 views

Find the shortest path from bottom left to top right in a maze using dfs and bfs algorithm

The following code is applying the depth-first search and breadth-first search algorithm to find the shortest path from bottom left to top right in a 10 x 10 grid. ...
user avatar
2 votes
1 answer
69 views

Finding cycles in graph

I found this code for Java to find if graph has cycles and I edited it to print out path of cycle. I use adjacency list. As it is directed weighted graph I will need to implement compensations of ...
user avatar
  • 23
2 votes
0 answers
186 views

Parallel Breadth First Traversal in Rust

Overview I have been writing my own graph API for Rust and one thorny problem I wished to tackle was a parallel breadth first traversal of the graph. The API itself will have different graph flavours, ...
user avatar
  • 171
7 votes
3 answers
390 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 ...
user avatar
0 votes
0 answers
77 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: ...
user avatar
  • 993
-1 votes
1 answer
44 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/...
user avatar
0 votes
1 answer
77 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 ...
user avatar
3 votes
2 answers
77 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 ...
user avatar
  • 41
-1 votes
1 answer
79 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 ...
user avatar
2 votes
0 answers
48 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 ...
user avatar
0 votes
0 answers
30 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.) ...
user avatar
  • 25.3k
0 votes
0 answers
29 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: ...
user avatar
  • 25.3k
1 vote
1 answer
50 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 ...
user avatar
  • 25.3k
1 vote
0 answers
37 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, ...
user avatar
4 votes
3 answers
581 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 ...
user avatar
0 votes
2 answers
505 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 ...
user avatar
  • 187
2 votes
1 answer
79 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"...
user avatar
1 vote
0 answers
306 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. ...
user avatar
1 vote
1 answer
186 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 ...
user avatar
4 votes
1 answer
122 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 ...
user avatar
  • 375
1 vote
1 answer
55 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 ...
user avatar
  • 259
1 vote
1 answer
66 views

Checking whether a graph is connected in an immutable way

I have this function at the moment ...
user avatar
0 votes
0 answers
65 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,...
user avatar
9 votes
1 answer
407 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 ...
user avatar
2 votes
0 answers
41 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, 𝑢 ...
user avatar
0 votes
0 answers
39 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 ...
user avatar
4 votes
2 answers
167 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/ ...
user avatar
  • 105
2 votes
0 answers
435 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 ...
user avatar
  • 57
3 votes
1 answer
226 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 ...
user avatar

1
2 3 4 5
15