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
20 views

(Feedback) 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 ...
-4
votes
0answers
22 views

Sum of all the values which comes in the path of a graph [closed]

I have written a code. In which I created a graph. Then traverse from source to destination using DFS. I sum up all the values of nodes which I have visited. But I could not know why it is wrong ...
2
votes
1answer
30 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
58 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
41 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
70 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
162 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
49 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
78 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
27 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
188 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
54 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
59 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 considered as a node. The information about neighbor superpixels is stored in ...
5
votes
2answers
121 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
65 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
50 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
33 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
129 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
48 views

Scala graph coloring

i have solved this problem https://leetcode.com/problems/find-eventual-safe-states/submissions/ ...
4
votes
0answers
55 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
69 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
131 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
93 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
95 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
32 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
170 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
103 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
664 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-...
2
votes
1answer
32 views

Finding minimum weighted matching in sink source graph

I have three lists of nodes. sources sinks pipes There is a directed weighted graph from sources to pipes to sinks. Sources are only connected to pipes and pipes only to sinks. But sources are not ...
3
votes
1answer
88 views

Transitive graph

What follows is a small but useful set of functions on transitive graphs and graphs that must be conformed to transitivity. Natural language is rich in transitive relationships expressed in a ...
2
votes
0answers
71 views

Finding connected components of a graph

I have a graph represented using a dict of sets, e.g. ...
4
votes
1answer
68 views

Finding all simple (without internal cycles) paths in a directed graph with total >1.0 weight

Assume directed graph with each edge being weighted by some positive float. Problem: find all simple paths (in other words, ...
1
vote
1answer
63 views

Graph implementation for solving graph problems (java)

I've currently started solving some competitive programming Graph questions. But Started using adjacency list as HashMap<Integer,ArrayList<Integer>> list...
5
votes
1answer
217 views

Change tracking POCO entities

Description In a time where thin clients, web browsers, web services and micro services are prevalent, we tend to forget we still have to deal with thick and smart clients. Many applications in B2B ...
3
votes
0answers
46 views

Django project for events of the day, grouped by keywords in common

I have made a website where people write about their day and see it analyzed. In particular, the website takes event titles and groups them together if they have any common words (after stemming the ...
1
vote
1answer
61 views

Dijkstra's implementation in c++ with STL priority_queue

This is dijkstras shortest path algorithm implementation in c++ using priority_queue STL. Looking for two things: a) Correctness of algorithm itself and b) Any improvement suggestions. ...
4
votes
1answer
72 views

Maximum profit earned on weighted un-directed tree

I came across this problem while giving a sample test. The problem was that we have given a tree which is undirected. We can start from any node of our choice. Initially we have power "P" and ...
3
votes
1answer
304 views

CodeChef's Tree MEX (Minimum Excludant) challenge

This code is a solution for CodeChef's Tree MEX problem: Minimum excludant (or MEX for short) of a collection of integers is the smallest non-negative integer not present in the set. You ...
3
votes
1answer
41 views

Wiki Link Mapper — A webcrawler which crawls links recursively and prints them into a graph

I would like some suggestions on how to make it better and also if any features that i should add to this Script. I am using beautifulsoup,requests for scraping and networkx for plotting the graph. ...
3
votes
1answer
96 views

Kruskals MST Algorithm

This code computes the Minimum Spanning Tree of a given graph using Kruskals Algorithm. It works successfully and I have provided test cases within the code. I would like feedback on code efficiency ...
2
votes
1answer
59 views

Find cycles in Graph using Union Find Algorithm on Adjacency List

My code detects if a cycle is present in a graph using Union find algorithm with Weighted tree analysis and path compression. It works and I have included test cases. ...
2
votes
1answer
68 views

Find articulation points/ cut vertices in graph

I would like to get some feedback on my completed code that finds and displays the articulation vertices in an undirected graph. I included a test case within the code, it should (and does) print <...
1
vote
0answers
62 views

Graph-coloring solution using depth-first search

I'm trying to solve this question: Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them. The park consists of n ...
2
votes
1answer
96 views

Kruskal MST algorithm

I came up with the following code by following Prof. Sedgewick's lecture on Coursera. Please review this code and let me know if there is anything that I got wrong in implementing Kruskal's ...
2
votes
2answers
496 views

Geektrust: Modelling Family Relationships in a OO way

I'm trying to model family relationships in a OO way, i.e. As we update the relationships between two individuals our model must be able to find the people given a person and the type of relationship ...
1
vote
0answers
33 views

Benchmarking k-shortest path algorithms in Java without JMH

In this post, I have the demo driver that benchmarks two \$k\$-shortest path algorithms. The entire GitHub project is here. net.coderodde.graph.kshortest.Demo <...
3
votes
0answers
57 views

Graph Search in C++17

Overview I am constructing a Graph with randomly generated nodes called Positions. The Graph has a width and a height and is represented using an adjacency list <...

1
2 3 4 5
13