# 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.

627 questions
Filter by
Sorted by
Tagged with
76 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 ...
368 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 ...
44 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. ...
115 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 ...
65 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. ...
85 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 <...
67 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 ...
99 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 ...
542 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 ...
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 <...
59 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 <...
97 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...
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 ...
174 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. ...
88 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 ...
123 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? ...
102 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 ...
288 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 ...
54 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: ...
113 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 ...
74 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. ...
262 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' }, ]; ...
92 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: ...
365 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 ...
61 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 ...
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. ...
73 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 ...
146 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 ...
811 views

### Graph using adjacency list in Java [closed]

This is the main code. Here I'm joining vertices by edges. ...
79 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 ...
77 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 ...
149 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 ...
259 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, ...
74 views

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. ...
398 views

### Traversing an infinite graph using Dijkstra's algorithm to maximize cookie production speed

Imagine the following situation: It is the year 20XX. You are a prodigious baker, capable of baking cookies at an astonishing rate of 1 cookie per second. Your archnemesis, an equally excellent baker,...
331 views

### Dijkstra algorithm implementation in Swift

I've implemented Dijkstra's algorithm to find the minimum path between two nodes. ...
90 views

### Yet Another Dijkstra with real data and drawing

I've been assigned to use Dijkstra's algorithm in order to find the shortest path on real data, more specifically on Luxembourg's map. The map is an .xml file with the following structure. ...
1k views

### Get all node descendants in a tree

I have a CSV holding a "flat" table of a tree's edges (NOT binary, but a node cannot have two parents), ~1M edges: ...
376 views

### Implementation of generic Graph class and Dijkstras

I participate in competitive programming contests, and I found myself implementing and re-implementing graphs constantly. So I decided to create a reusable implementation of a Graph class, and ...
286 views

### Dijkstra - shortest Path implementation - STL

I have implemented Dijkstra algorithm to perform Shortest Path problem. Input: Adjacency List(Directed Graph): Description is like that {Source Node, {edge_1, .. , edge_N}} Cost Matrix (Same ...
604 views

### Vertex Cover Problem Greedy Solution [closed]

As far as I understood this problem, it is a subset of vertices of Graph G, such that every edge has at least one endpoint in the subset. This problem is considered to be NP Complete. However I think ...
51 views

### Vertical Bar Graph Generator

I have created a python program that prints a vertical bar graph made from fields and values inputted by the user. It works by first creating a horizontal bar graph and then going through each layer ...
74 views

### Graph implementation from adjacency list

I've implemented a graph for a course and i'd like to know what i could improve. The graph is created from a adjacency list from a file with the following format per row: ...
322 views

### Graph Implementation in Java using Set and Map

There is a Graph implementation. I'm using Set to store unique Edges and Map to store Vertices and their associated edges. Assume Vertex and Edge class has been defined somewhere else implementing ...
211 views

### Map coloring with MRV and Degree heuristics in Python

I am relatively new to Python. I wrote this solution to the well known map coloring problem and also implemented the MRV and Degree heuristics. Here, I am considering the map of Australia - ...
91 views

### Project Euler #81 in Haskell: minimal path sum through a matrix

I just completed Project Euler Problem 81 in Haskell: In the 5 by 5 matrix below, ...
712 views

### Find all shortest paths between 2 nodes in a directed, unweighted, SQL graph

I want to find all shortest paths between a pair of vertices in a unweighted graph i.e all paths that have the same length as the shortest. The edges of the graph are stored in a SQL database. The ...
170 views

### Performing unit conversions using intermediate conversions

Challenge: Two input files are given The first contains |N| ratios in the form of two labels and a ratio: USD, GBP, 0.69 Meter, Yard, 1.09 YEN, EUR, 0.0077 GBP, YEN, 167.75 ...