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

605 questions
Filter by
Sorted by
Tagged with
40 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 ...
45 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 ...
90 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 ...
2k views

### Finding a loop in a directed graph in Python

I wrote this code to find if a directed graph contains a loop or not. I am pretty new to graphs and I saw some examples on the internet but couldn't actually understand their implementations. So I ...
64 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 ...
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 ...
189 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 ...
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. ...
173 views

### Computing resilience of the network presented as an undirected graph in Python

The idea is to compute resilience of the network presented as an undirected graph in form {node: (set of its neighbors)} for each node in the graph}. The function ...
54 views

### Data Explorer query that makes bar graphs

I wrote a query for SEDE that I think is pretty cool. It uses the currently available graphing capabilities (scatter plots) to create a bar graph. I have used it as the subject for a self-answer on ...
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 ...
32 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 ...
44 views

### Scala graph coloring

i have solved this problem https://leetcode.com/problems/find-eventual-safe-states/submissions/ ...
68 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: ...
48 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 ...
85 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 ...
105 views

### Shortest code to generate a full mesh of elements

I am trying to find the shortest code that generates a full mesh of the elements fed into it in graphviz format e.g. the full mesh of [0, 1, 2] is: 2 -> 0 ...
129 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 ...
372 views

### Snakes and Ladders using a magic die

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game. ...
28 views

### Correctness and Performance of graph plotting on R

Current State: I have two CSV files, their sample attached below: FileOutputWithoutBuffer-Metrics.csv ...
90 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 ...
61 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. ...
30 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 ...
974 views

### Canvas animation of network nodes and edges

This code generates an animation that gives the idea of an ever changing network of nodes (each with different impact and possibly more than one color) connecting each other to create something. I ...
742 views

### Strongly connected component finding based on the guava graph library with Kosaraju

I have been writing a small compiler generator for which I need to solve the strongly connected component problem. As the Guava library contains, to my knowledge, no implementation for that problem, I ...
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 ...
12k views

### BFS and DFS in Scala

I would love it if someone could give me some suggestions for these 2 graph search functions. I am new to scala and would love to get some insight into making these more idiomatic. ...
146 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. ...
208 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 ...
100 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 ...
608 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-...
31 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 ...
86 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 ...
143 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 ...
60 views

### Finding connected components of a graph

I have a graph represented using a dict of sets, e.g. ...
57 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, ...
90 views

### Minimum amount of edges that needs to be traversed to visit all vertices… or something like that

So I have this problem, where I'm given m connections over n vertices. The vertices are labeled ...
581 views

### Pseudo-parallel depth-first search

I'm writing a small program that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel depth-first search (dfs) on it. ...
60 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...
2k views

### Finding all paths between nodes in a graph

I wanted to write a function paths that returns the possible routes between two nodes in a graph. For example: ...
422 views

### Finding cycles in a graph that pass through a vertex at most k times

I have a project that relies on finding all cycles in a graph that pass through a vertex at most k times. Naturally, I'm sticking with the case of k=1 for the sake of development right now. I've come ...
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 ...
178 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 ...
140 views

### Add an edge to a graph to minimize the average shortest path length

This program is used to find the nodes in a grid network, between which, if an edge is added, the average shortest path length of the entire grid reduces by the most. "Average shortest path length" ...
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 ...
4k views

### Dijkstra in C++ to find shortest path for every vertex of a directed graph

I am trying to implement the Dijkstra algorithm in C++ that finds the shortest path for a graph from a text file. The text file contains a matrix that represents a directed graph. What I am trying ...
85 views

### Dijkstra implementation for large graphs

I am implementing the Dijkstra algorithm for a large graph (40k nodes, 100k arcs). For shorter paths the searchtime is under a second for larger ones (from one end to the other) it takes quite some ...
54 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. ...
157 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 ...
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. ...