We’re rewarding the question askers & reputations are being recalculated! Read more.

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
53 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 ...
-2
votes
0answers
20 views

Histogram building in python, specific on one variable [on hold]

Below is the dataset im using to build the histogram. I want to build a histogram which specifies on the 'EL' variable and where we have the frequency on the y-axis. Is it possible to group the 'EL' ...
0
votes
0answers
58 views

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

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
28 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
50 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
92 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
93 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
335 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
27 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
83 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
52 views

Finding connected components of a graph

I have a graph represented using a dict of sets, e.g. ...
4
votes
1answer
49 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
55 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...
4
votes
1answer
109 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
42 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
49 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
65 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
100 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
38 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
52 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
46 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
41 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
53 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
86 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
263 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
31 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
53 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 <...
5
votes
1answer
84 views

3-function program computing connected components of a point cloud given a distance matrix

I wrote this code in Haskell (instead of Python) for the educational benefit. Can anyone suggest ways to improve this code? I'm guessing that I'm using fromIntegral...
2
votes
0answers
24 views

Modelling a program with modules, symbols, and dependencies

My scenario is the following: I'm modelling a Program which has many Modules. Each Module has Symbols, some of which pointing at dependencies, which are other Modules. So a Module can be pointed to by ...
1
vote
2answers
114 views

Dijkstra's Algorithm C++

This is a basic implementation of Dijkstra's Shortest Path Algorithm for Graphs. I am looking for any kind of improvement. ...
2
votes
2answers
46 views

Graph library - graph interface

I am trying to write simple graph lib in C++, BFS, DFS etc.. I want to create class GraphI which will represent any graph and will include necessary methods so my ...
6
votes
1answer
118 views

Longest carbon chain

My Code measures the longest path, not allowing cycles. For the example input below, the longest chain would be 4 Please can you review my code? ...
3
votes
1answer
53 views

Find number of islands Leetcode

Here is the question: Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally ...
7
votes
1answer
172 views

Hackerrank: Computer Game (max-flow problem with integer factorization)

I am working on a coding challenge from the Hackerrank site. Given two equal-length arrays of integers, with values from 2 to 109, find the maximum number of times we can remove a pair (Ai, Bj) where ...
2
votes
1answer
38 views

Strongly connected component in graph

My goal is to calculate the length of each strongly connected component (SCC) I have an input that looks like this: ...
2
votes
1answer
106 views

Graph implementation using FIFO lists

I've made a little implementation of an undirected graph, using FIFO lists, for one of my homeworks. Never really knew how to write a proper FIFO data structure, so I would be glad to see some opinion ...
5
votes
1answer
65 views

Optimizing graph partitioning by connected components of generated subgraph

I'm trying to optimize a function in a process which is going to be run millions of times. The function is supposed to partition the vertices of a graph, which will be used to make a quotient graph. ...
9
votes
5answers
260 views

Sort a list of pairs representing an acyclic, partial automorphism

I have this sample data: let trips = [ { from: "DEN", to: "JFK" }, { from: "SEA", to: "DEN" }, { from: 'JFK', to: 'SEA' }, ]; ...
4
votes
1answer
86 views

C++ graph class

What can be done better? My future plans is to implement algorithms such as: DFS, BFS, Prims, Dijkstra, Kruskal, ... Faults I know of: Not implementing rule of five Vertex.h: ...
1
vote
1answer
183 views

Leetcode online Find the judge, graph with highest degree

Here is the problem. In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town ...
4
votes
0answers
39 views

Two solutions to leetcode 127.wordLadder

I am working on Word Ladder - LeetCode Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such ...
2
votes
1answer
44 views

Kahn's algorithms to arrange CouseSchedule

I wrote a solution to Course Schedule II - LeetCode There are a total of n courses you have to take, labeled from 0 to n-1. ...
2
votes
1answer
56 views

Maximize Path Value

I recently had to code an algorithm that will, for an input of: matrix of up to 5x5 size and a defined path length, find a path of this given length from the first top left matrix element (0, 0) to ...
7
votes
2answers
141 views

Heights of Cats

I have an assignment to solve this problem. However, I have exceeded the time limit required, can anyone suggest where to improve my code? Cats like to sit in high places. It is not uncommon to see ...
3
votes
2answers
318 views

Graph using adjacency list in Java [closed]

This is the main code. Here I'm joining vertices by edges. ...
4
votes
1answer
72 views

Swift Prim's algorithm

Lots of Prim's algorithm implementations seem long, and rely on a priority queue implementation. If I use an adjacency matrix I can then calculate the next item to take using functional programming ...
5
votes
0answers
68 views

graphtimer v2 - Utility to plot timings

GitHub repo (MIT) Clone the repo and replace the contents of example.py with the one at the bottom and you'll have everything setup. Explanation of the code A ...
1
vote
2answers
108 views

Determine whether a node is reachable

I am working on this HackerRank problem but running into time constraint issues. Basically, given two arrays, we need to determine if the ith element of the second array is reachable by the ith ...
5
votes
1answer
233 views

Graph puzzle resolver

I've solved test task for job vacancy. Need your feedback about my solution. Task The image below shows the puzzle in the solved state. The puzzle consists of 10 cells. Among the cells one is empty, ...
2
votes
1answer
61 views

Modelling Immerman–Szelepcsényi in Haskell

I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here. ...