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
0 answers
61 views

Find shortest knight's path between two chessboard squares

My function is a solution to the Knight's Travails problem. It receives start and end point coordinates on a chess board, and must return the shortest path from start to end. ...
2 votes
0 answers
67 views

Iterating over all simple unique cycles in an undirected graph in Java - brute-force approach

This post is about an Iterator iterating over simple loops of an undirected graph. In the above graph, the cycle \$\langle 1, 2, 3, 4, 5, 3, 1 \rangle\$ is not ...
  • 26.1k
2 votes
1 answer
55 views

C++ Refactored graph again, separated property maps from Graph type

This is yet another improvement from my graph class - Link Now property maps are no longer parts of Graph type, they are just stored in a member variable. This ...
  • 1,643
2 votes
1 answer
68 views

C++ Graph class with multiple property maps (edit)

I wrote an improvement from my previous graph class: Link ...
  • 1,643
0 votes
0 answers
23 views

Shortest path in dags: Part 3/3 - the demo benchmark

Part 1/3 Part 2/3 In this post, I will present the benchmark code from this project. com.github.coderodde.graph.benchmark.DemoDagProvider.java: ...
  • 26.1k
1 vote
1 answer
46 views

Shortest path in dags: Part 1/3 - the graph data structure

Part 2/3 Part 3/3 I have this library for performing shortest path queries on dags (directed acyclic graphs). This post presents the graph data structure: ...
  • 26.1k
1 vote
1 answer
56 views

Library to represent graphs

I have been working on a library to represent graphs (directed graphs and undirected graphs). I know that there are already many such libraries but I wanted to create my own as a learning exercise. I ...
1 vote
1 answer
59 views

Optimizing BFS code to find connected components in a graph

I am writing a Python code to find the connected components of a graph using BFS. The code works but takes a long time to run. Please suggest possible optimizations of my code. The graph is stored as ...
  • 11
6 votes
1 answer
81 views

Python code to contract (shrink) a graph

To better understand a paragraph, I implemented the intent behind the paragraph. In this case, it was a formal definition of a graph contraction: Suppose we have an undirected graph G and X ⊆ V(G). ...
  • 821
3 votes
1 answer
252 views

Kosaraju's algorithm in C simple implementation

I am wondering can I please get some feedback for my simple implementation of the Kosaraju algorithm. More specifically how I de-allocate the things I allocated using ...
  • 359
1 vote
1 answer
48 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 ...
  • 13
3 votes
1 answer
64 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 ...
3 votes
1 answer
87 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 ...
2 votes
0 answers
66 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'. ...
5 votes
0 answers
76 views

Dijkstra's algorithm in Perl

I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
  • 26.1k
2 votes
2 answers
143 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 ...
  • 26.1k
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: ...
  • 26.1k
3 votes
1 answer
170 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 ...
1 vote
1 answer
52 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 ...
  • 26.1k
3 votes
1 answer
92 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 ...
  • 26.1k
1 vote
0 answers
30 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 ...
  • 26.1k
4 votes
1 answer
336 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 ...
  • 26.1k
4 votes
1 answer
124 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 ...
  • 141
0 votes
0 answers
118 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: ...
1 vote
3 answers
74 views

DFS search that returns "not found" or distance

Assuming I've the following code: ...
  • 143
1 vote
0 answers
35 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: ...
  • 162
0 votes
0 answers
56 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 ...
  • 162
1 vote
2 answers
89 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, ...
  • 57
2 votes
2 answers
203 views

Graph Implementation with Dijkstra's Algorithm

Graph Interface: ...
  • 51
3 votes
1 answer
85 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 ...
  • 51
0 votes
0 answers
23 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 ...
0 votes
1 answer
84 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. ...
2 votes
1 answer
89 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 ...
  • 123
2 votes
0 answers
261 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, ...
  • 171
7 votes
3 answers
404 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
0 answers
92 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,003
-1 votes
1 answer
48 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
1 answer
91 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
2 answers
87 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 ...
  • 41
-1 votes
1 answer
88 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 ...
2 votes
0 answers
50 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 ...
1 vote
1 answer
59 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 ...
  • 26.1k
1 vote
0 answers
40 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
3 answers
587 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
2 answers
820 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 ...
  • 187
2 votes
1 answer
103 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
0 answers
412 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
1 answer
243 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
1 answer
138 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 ...
  • 375
1 vote
1 answer
57 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 ...
  • 259

1
2 3 4 5
15