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
1
vote
0answers
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 ...
4
votes
2answers
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 ...
5
votes
2answers
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 ...
4
votes
2answers
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 ...
-1
votes
2answers
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 ...
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 ...
2
votes
1answer
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 ...
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. ...
4
votes
1answer
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 ...
6
votes
1answer
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 ...
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 ...
0
votes
1answer
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 ...
1
vote
1answer
44 views

Scala graph coloring

i have solved this problem https://leetcode.com/problems/find-eventual-safe-states/submissions/ ...
7
votes
0answers
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: ...
4
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
5
votes
0answers
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 ...
4
votes
1answer
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. ...
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
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 ...
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. ...
0
votes
0answers
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 ...
5
votes
1answer
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 ...
6
votes
1answer
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 ...
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 ...
9
votes
1answer
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. ...
2
votes
2answers
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. ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
1
vote
0answers
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-...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
7
votes
2answers
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 ...
2
votes
0answers
60 views

Finding connected components of a graph

I have a graph represented using a dict of sets, e.g. ...
4
votes
1answer
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, ...
4
votes
0answers
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 ...
6
votes
0answers
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. ...
1
vote
1answer
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...
4
votes
0answers
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: ...
5
votes
1answer
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 ...
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 ...
5
votes
1answer
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 ...
6
votes
1answer
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" ...
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 ...
1
vote
3answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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. ...
3
votes
1answer
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 ...
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. ...

1 2 3 4 5 13