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
4
votes
1answer
1k views

DFS implementation

I implemented DFS using recursion in Go. When I dfs the graph, I am able to get the path of traversal. But I'm unsure what else could I add to this DFS in order to make the search better. Also, Is ...
3
votes
2answers
954 views

Finding the shortest path (between source and destination) with the least number of edges

I wrote a program which finds the shortest path between a source and a destination in a graph, so that the path will be to one with th least number of edges. In order to write it, I used Dijkstra's ...
5
votes
1answer
344 views

Bare bone implementation of Dijkstra

I am trying to implement Dijkstra without writing lot of code for the Graph class itself. I have implemented it from Wikipedia. However, I am not fond of the way I have handled the minimum distance ...
4
votes
0answers
105 views

Algorithm to find connected tiles (percolation)

I wrote a little program in JavaFX which displays a path of neighbouring open tiles going from top to bottom. It should simulate a percolation. The algorithm iterates through the whole grid (every ...
4
votes
1answer
278 views

Java Node class for a Graph

I'm using ArrayList<Nodes> to store adjacent nodes, and ArrayList<Integer> to store the corresponding weights of the ...
3
votes
1answer
5k views

C++ breadth-first search using adjacency matrix

I have written this Breadth First Search program using Adjacency Matrix, taking help from Introduction to Algorithm(CLSR) and from Internet. I want to optimise this code. ...
3
votes
3answers
119 views

A nice “live” service locator to flatten the object graph

Here is a class that exists in the Framework\ namespace in the xofz.Core library. It is used as a dependency of other ...
2
votes
1answer
189 views

Ruby Connected Components in a Graph

I've written the following code to find the connected components of a graph in ruby, but it is quite slow since I don't use any sensible data structure for the disjoint sets, and hence find_set is ...
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 ...
2
votes
2answers
1k views

DFS implementation in Rust

...
2
votes
0answers
786 views

Graph represented by adjacency list

I've started to learn about graphs and how to represent them in code. Here is my attempt of making an adjacency list for an undirected graph. I'm looking for suggestions on how to improve it and what ...
1
vote
2answers
67 views

Calculating the connectance of a matrix iteratively

I have a performance issue in R. I have a function that iterates over a dataframe for different levels of "site" and "method". The function samples 1:1000 interactions (rows), converts these to ...
3
votes
0answers
82 views

SPOJ Fast Matching challenge

I wrote a solution to the MATCHING challenge on SPOJ: FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, ...
3
votes
2answers
464 views

Comparing Dijkstra's SSSP algorithm against Bellman-Ford in Java

Single source shortest path In SSSP, we choose a node \$s\$ and we compute all the shortest path starting from \$s\$ towards all other nodes, thus computing a shortest path tree. Two most classical ...
3
votes
1answer
146 views

Hackerearth - Learning Graph

Problem: Monk goes to graph city to learn about graphs, and meets an undirected graph having \$ N \$ nodes, where each node has a value \$ i \$ such that \$ 1 \le i \le N \$. Each node of the ...
3
votes
0answers
54 views

Find spanning tree with maximum edges with the same weight

For my university assignment I need to come up with an algorithm to find a spanning tree with maximum number of edges with same weight. I received an algorithm suggestion in this Stack Overflow answer....
2
votes
2answers
620 views

Calculation of Hamming distance between two adjacency lists

I have written a Java program to calculate the Hamming distance between two adjacency lists. The program calculates the Hamming distance correctly, but it takes a very long time, especially when ...
0
votes
2answers
533 views

How to make this code of shortest Path Finder more maintainable,extendable and get better static code analysis result?

I have the below code for finding the shortest path between a source node and destination node in a BiDirectional graph.It is working alright. However, when I am running Static Code Analysis (VS2017), ...
1
vote
0answers
529 views

Sorting directed graph topological using Kahn's algorithm

For a course I'm doing I need to get up to speed with Java, but unfortunately only Java 1.6 - here is a topological sorting algorithm in said Java version, for practice reasons: ...
5
votes
2answers
1k views

Weighted union-find with path compression in Python 3

I implemented the Union-Find data structure and would love to receive some feedback about my code. I have just begun programming and welcome any feedback or constructive criticism which would improve ...
2
votes
0answers
138 views

Network of senders and receivers in C++

I am trying to create a Sender-Receiver Network. What do I mean under a Sender-Receiver Network. That means that there is some structure which consists of Nodes and connections between them which will ...
1
vote
2answers
327 views

Depth-first search of a graph in C# (HackerRank problem)

I'm trying to solve a problem from HackerRank. I got the correct algorithm, but it seems to be too inefficient. After checking the code with 10 given test cases, 3 cases are good and 7 return a ...
2
votes
3answers
1k views

Topological sort of a graph

Please refer following graph. Please review following code for topological sort. I can sense one odd thing in my code, TS() is calling ...
9
votes
1answer
3k views

Prim's Algorithm using heapq module in python

Implementing Prim's with a \$O(m\log n)\$ run time using heaps, similar to Dijkstra heap implementation. Where \$n\$ is the number of nodes, and \$m\$ is the number of edges. Using the ...
4
votes
1answer
1k views

Greedy graph coloring

For taking part in a course, I need to learn some Java. Unfortunately they only teach Java 1.6, so I understand that later versions could simplify the below code a lot, but I have to stick with 1.6 ...
4
votes
2answers
755 views

Given two words and a dictionary's word list, find all shortest transformation sequence

This is a leetcode problem (https://leetcode.com/problems/word-ladder-ii/description/) Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(...
2
votes
3answers
6k views

Finding connected components in Python

I wrote an algorithm for finding the connected components in a 2d-matrix in Python 2.x. I am looking for comments on the quality of my code, organization, formatting/following conventions, etc. For ...
3
votes
3answers
3k views

Topological sort using STL

I am trying to implement topological sort using STL. I have used vector of lists to store adjacency list. Indegree is an array which stores indegree of vertices. ...
5
votes
1answer
200 views

Depth-first Search Non-Reursive Implementation in Clojure

I've created a non-recursive dfs implementation in Clojure. I'm using the wikipedia article on dfs as a guide. I'm very new to Clojure and functional programming in general. Any tips to improve ...
5
votes
1answer
183 views

AIO programming challenge - Friendlist - Who has the most friends?

I attempted this sample question from the Australia Infomatics Competition. TL;DR - Each line of input contains two numbers, representing a mutual friendship relationship. The output needs to be the ...
0
votes
2answers
168 views

Dynamic loading of Javascript dependency graph

I have JavaScript module for loading dynamically script files by dependency graph: ...
5
votes
2answers
222 views

Dijkstra's Algorithm modified to take negative edge weights

In the following Python implementation I have used color coded vertices to implement the Dijkstra's Algorithm in order to take negative edge weights. ...
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 ...
0
votes
1answer
157 views

Implementing a 'TreeGraph' which extends a normal graph

I'm currently trying to build an interactive technology tree for Stellaris. Which normally doesn't come with a tree view. Stellaris is like Civilization 5, where the tree isn't actually a tree, as it ...
1
vote
2answers
248 views

Musical graph algorithm, with an inlined lookup helper function

I am working with bit strings in clojure. My question is less about performance and more about how one should go about it (in particular see the last inlined version) The tonnetz-array represents an ...
5
votes
2answers
2k views

Dijkstra algorithm implementation with adjacency list

I've implemented the Dijkstra Algorithm to obtain the minimum paths between a source node and every other. ...
1
vote
0answers
1k views

Finding largest graph cliques in Java

Introduction A graph clique is a set of nodes \$\mathcal{C}\$ in which each node is connected to all other nodes in \$\mathcal{C}\$. I have this small program for finding largest cliques from ...
2
votes
1answer
2k views

Implementation of Prim's Algorithm to find minimum spanning tree

What is the time complexity of the following code? I'm implementing Prim's Algorithm with adjacency matrix representation of the graph and priority queue. ...
3
votes
1answer
338 views

Path Finding using Dynamic Programming

I was trying to implement a dp + graph problem. After completing the solution I tried to compare it with solution in tutorial to figure out which one was better and to find a way to improve mine if I ...
3
votes
0answers
278 views

Skiena's DFS on unweighted graphs, in Python 3, with adjacency-list implementation

In the Algorithm Design Manual (2nd ed) pp 172 - 173, Skiena writes: As algorithm design paradigms go, a depth-first search isn't particularly intimidating. It is surprisingly subtle, however ...
4
votes
1answer
244 views

Prim's Lazy Minimum Spanning Tree Algorithm in Haskell (Project Euler# 107)

I have implemented Lazy version of Prim's Minimum Spanning Tree Algorithm. I want to improve the code structure, follow prevalent conventions and reduce code size. I am solving Project Euler #107. ...
2
votes
1answer
62 views

Generic A*-Algorithm without clone

I wrote a generic implementation of A* with the focus of not having to clone nodes or actions. Thanks to some very good advice I received on Stack Overflow, I have arrived at the following final ...
4
votes
1answer
809 views

Find Eulerian Tour Algorithm - with multithreading and random permutations

After struggling for a long while on this through the algorithms course on Udacity, I finally understood enough of the concept to develop this implementation. However, it lacks efficiency and finesse. ...
7
votes
2answers
184 views

Degrees of Wikipedia

Here is my attempt on implementing "Degrees of Wikipedia" (much faster version can be seen at degreesofwikipedia.com.It's basically an algorithm which tries to connect two unrelated Wikipedia pages by ...
2
votes
1answer
49 views

Project Euler # 95 in Haskell - kind-of finding longest cycle in a graph

I am trying to solve Project Euler #95 in Haskell, though I have already solved it in Java (see). I found that writing imperatively, we can easily do the task this way: Pseudocode Define cache as an ...
4
votes
3answers
638 views

Find the most-connected nodes in a graph

I feel like this is a simple problem that I have overcomplicated. Any tips or different approach would be greatly appreciated. Problem and goal Given a list of coordinates (each line represents an '...
9
votes
4answers
326 views

Shifting the origin of a large list of coordinates

Problem and goal Given a large edge list file (such as 2 million nodes, 30 million edges) containing source and destination coordinates, I want to 'convert' them in such a way so that the coordinates ...
1
vote
0answers
211 views

Haskell - Adjacency Matrix

This program is used to solve Challenge #140 [Intermediate] on /r/dailyprogrammer. The challenge is, given a input set of directed edges, print the corresponding ...
0
votes
1answer
1k views

Using a hash map in graph design implementation for shortest path

I am working on implementing a graph to solve shortest path between two vertices using Dijkstra's algorithm. Trying to keep it at least somewhat efficient because I know there are some time ...
3
votes
0answers
50 views

SparseGraph: A representation of a mathematical graph

I'm working on a SparseGraph which reflects the mathematical notion of a graph. All code included here works in all of the basic test cases that I've tried. However, I'm most concerned about the ...

1 2 3 4 5 13