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
10
votes
1answer
147 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
81 views

Dijkstra algorithm C#

I have implementing a simple version of Dijkstra's algorithm in C#. I found it really confusing, and I'm not 100% if I've implemented it correctly. Could this be made more efficient? Does it need to ...
2
votes
1answer
66 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 ...
2
votes
0answers
38 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
138 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-...
2
votes
2answers
42 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
44 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
57 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
42 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
54 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
64 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
75 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
88 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
44 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
32 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
57 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
42 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
62 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
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 ...
1
vote
2answers
88 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
69 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
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 ...
3
votes
1answer
62 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
65 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: ...
5
votes
1answer
113 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 ...
4
votes
3answers
202 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 ...
4
votes
1answer
65 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 ...
5
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
2answers
327 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 ...
2
votes
0answers
59 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 ...
4
votes
2answers
70 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 ...
5
votes
2answers
179 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 ...
-1
votes
2answers
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 ...
10
votes
2answers
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 ...
3
votes
1answer
52 views

Creating valid words on an n-by-n grid of characters using depth-first search

I am trying to create a word-finder game. There will be an n-by-n Board filled with Tiles. ...
0
votes
1answer
35 views

Graph degree as solution for undirected graph paint

The problem is: Given an undirected graph represented as an adjacency matrix and an integer k, write a function to determine whether each vertex in the graph can be coloured such that no two ...
6
votes
1answer
132 views

City Construction Solution times out for large input

Problem The country of Hackerland has n cities connected by m uni-directional roads. The cities are numbered from ...
1
vote
1answer
54 views

Scala graph coloring

i have solved this problem https://leetcode.com/problems/find-eventual-safe-states/submissions/ ...
4
votes
0answers
63 views

A generic DFS in JavaScript

I implemented a general function for a depth-first-search (DFS) using JavaScript with default arguments and functions that need to be provided in order for it to work. This function is using ...
7
votes
0answers
73 views

Frequency analysis for simultaneous dice rolls

My professor told me to optimize my perl code, but he wouldn't tell me what exactly - just make it simpler. I changed some little things but nothing major. Am I missing something? The task was: ...
5
votes
0answers
135 views

Implementation of container searchable by any element

Writing game engine as a hobby, I've come across many situations where I need a container like a map, but searchable by different keys: a block allocator where a block needs to be searched by either ...
0
votes
1answer
28 views

Correctness and Performance of graph plotting on R

Current State: I have two CSV files, their sample attached below: FileOutputWithoutBuffer-Metrics.csv ...
2
votes
1answer
101 views

Prim's Algorithm - Minimum Spanning Tree

I have implemented Prim's Algorithm from Introduction to Algorithms. I have observed that the code is similar to Dijkstra's Algorithm, so I have used my Dijkstra's Algorithm implementation. Please ...
0
votes
0answers
111 views

Recursion on graphs - networkx VS adjacency lists with native lists, sets or numpy vectors ( python )

Hope someone can help me out in reviewing this code to make it faster. My goal is to create a graph recursively: query for a node and its neighbors from a db (not present here) add it and its ...
0
votes
0answers
34 views

Incremental Floyd Warshall on directed graph

Given a directed graph with \$n\le 500\$ vertices I want to find sum of minimum distances between each pair. This can be done using Floyd-Warshall in \$O(n^3)\$. Now I remove a vertex and do so again ...
3
votes
1answer
53 views

Find the lengths of strongly connected components in a graph

I wrote a code to calculate the lengths of strongly connected components in a graph. The results I get are correct but it scales horribly. This is the code I have. I understand that the runtime ...
1
vote
2answers
197 views

Breadth-first search(BFS) Implementation in Python 3 [closed]

I have implemented a BFS. Does this look like a proper implementation of BFS in Python 3? And if you think something needs to be improved, say it. ...
4
votes
1answer
111 views

A Graph implementation in C++

I am building a generic Graph. I want to know whether the current design is fine. Are there any memory leaks ? Any suggestions are deeply appreciated. GraphCode ...
1
vote
0answers
744 views

LeetCode: critical connections in a network C# (Tarjan's algorithm)

https://leetcode.com/problems/critical-connections-in-a-network/ Please review for memory and runtime performance. There are n servers numbered from 0 to n-1 connected by undirected server-to-...

1
2 3 4 5
13