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
3
votes
2answers
611 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 ...
1
vote
3answers
2k 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
165 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
166 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
164 views

Dynamic loading of Javascript dependency graph

I have JavaScript module for loading dynamically script files by dependency graph: ...
5
votes
2answers
196 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. ...
5
votes
1answer
644 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
151 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
245 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
284 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
212 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
199 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
60 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
736 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
178 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
45 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
575 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
323 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
178 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 ...
4
votes
2answers
892 views

Python breadth first search algorithm

Any pointers, or any advice on how to clean up my code/make more pythonic would be appreciated. ...
7
votes
1answer
14k views

Adjacency List Graph representation on python

I began to have my Graph Theory classes on university, and when it comes to representation, the adjacency matrix and adjacency list are the ones that we need to use for our homework and such. At the ...
4
votes
2answers
296 views

Forming sets from pairs of numbers

I do not want to use a new data structure but the existing APIs in Java. Here's a solution. I am thinking if this can be made simpler. Input say ...
7
votes
2answers
990 views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
5
votes
1answer
280 views

Hackerrank - Maximum Disjoint Subtree Product

Problem statement We define an unrooted tree, T, with the following properties: T is a connected graph with nodes ...
4
votes
1answer
83 views

Sort and describe itinerary segments

Given some incoming some data in JSON format, representing unsorted train, bus, and flight tickets: ...
3
votes
2answers
7k views

Java: Given a list of edges, build a tree and return the root

In an interview I was asked to write Java code to build a tree and return the root, given a list of edges. It was a fairly open ended question where the interviewer left all the decisions up to me. I ...
2
votes
1answer
6k views

Adjacency List implementation for Graph in Java

I am building up a Graph repository which I am planing to use for exploring all the Graph algorithms. This is more from a learning perspective only. I have implemented a basic ...
3
votes
2answers
119 views

Computing most reliable path in undirected probabilistic graphs using Java

(See the next iteration.) Problem definition We are given an undirected graph \$G = (V, E)\$ and a weight function \$w \colon E \to (0, 1]\$. The weight of the edge \$e \in E\$, \$w(e)\$, ...
1
vote
0answers
116 views

Calculating distances between nodes in graph with negative cycles

Full disclosure: this is for an online course. The code calculates the distances between a starting node in a graph and all other nodes using the Bellman-Ford algorithm. The graph may contain ...
2
votes
1answer
222 views

Most efficient implementation of Djisktra's shortest path using vectors and pairs in C++ stl

If std::vector<vector<pair<int,int> > > v(n) represents the adjacency list of the graph with ...
3
votes
1answer
383 views

CodeFights Quora bot

This isn't any homework questions or assignments, only my practice. In the CodeFights Quora bot. My code cannot pass even the first hidden input because of the execution time. I'm only a first-month ...
2
votes
0answers
128 views

Neo4j traversal algorithm to find dense nodes

I am trying to get familiar with traversals algorithms implementations in Neo4j and to practice I am implementing classic graph algorithms (not judging if is the best approach or not, just for the ...
3
votes
1answer
3k views

Undirected Unweighted Graph Implementation - C++

For a class we needed to implement an undirected unweighted graph that: Maintains a distance matrix that can be printed Supports the computation of the graph's diameter (uses dist matrix) Prints the ...
2
votes
1answer
3k views

Finding minimal spanning tree of a graph using Kruskal's algorithm

I am doing some practice interview questions for class, one of the questions is: Given an undirected graph G, find the minimum spanning tree. Function should take in and output an adjacency list. ...
3
votes
1answer
303 views

Lissajous pattern simulator

I had seen a YouTube video making actual Lissajous patterns with sand falling from a pendulum with 2 different periods and looking in the Wikipedia page the looked very easy to simulate. I made a ...
1
vote
1answer
5k views

MST Kruskal's algorithm in Python

I have this code for finding MST for undirected weighted graph, currently works for graphs with maximum 10 vertices. How can I update the code to scale for larger graphs? ...
4
votes
2answers
1k views

Depth and breadth first search

I am practicing interview questions, I wrote this code to perform BFS and DFS on a graph in Python. How can it be optimized, and how can it be made more readable? ...
4
votes
1answer
2k views

Undirected graph implementation

I have implemented in C# a graph data structure (undirected graph) using TDD technique, tests are provided upfront. This implementation provides common graph methods also it traverses graph using DFS ...
1
vote
3answers
1k views

Dijkstra implementation for maze solving that works fine and returns shortest path

I would like to make my code "prettier" and also speed up the runtime of my implementation. Nodeinfo is literally just an object that holds its "parent node"(the node it came from) and its distance. i ...
5
votes
1answer
1k views

Karger's min cut algorithm

I have implemented a simple version of Karger's min cut algorithm. The algorithm takes a graph and repeatedly contracts randomly selected edges until only two nodes are left. By repeating this ...
8
votes
1answer
1k views

Flight combinations between two cities

I am trying to obtain all possible ways to go from a city A to a city B on a given day by plane, with a maximum of 2 stops. I have as input a list of dictionaries: ...
6
votes
0answers
312 views

Kattis problem Amanda Lounges

I wrote this solution to Kattis problem Amanda Lounges in Scala. TL;DR: It's a graph theory problem where I read in a list of edges from stdin and try to compute the minimum number of nodes that ...
9
votes
1answer
2k views

Hacker Rank: Journey to the Moon (Graph Theory)

I am attempting to complete the "Journey to the Moon" problem described below: There are N trained astronauts numbered from 0 to N-1. But those in charge of the mission did not receive ...
1
vote
2answers
155 views

Java sequential BFS

I am currently working on optimizing my code. In order to do that, I have to make sure that my sequential BFS works perfectly. Then, I should I apply threads or executor service to run it in parallel. ...