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.
0
votes
0answers
14 views
Puzzle 8 Resolver in Python - I can't find frontier neighbors correctly and quickly [on hold]
I have to do a 8 puzzle resolver with bfs, dfs and A* algorithms in python, but I have some issue(s).
This is my output for python driver_3.py bfs 1,2,5,3,4,0,6,7,8:...
0
votes
0answers
4 views
Distance in a tree
I have implemented the code of a codeforces problem. But after trying it for alot of time I was not able to implement a dp solution of the question. So, can anyone tell me how can i change and improve ...
2
votes
1answer
47 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 ...
-2
votes
0answers
46 views
Google Foobar Level 4 Running With Bunnies [closed]
This is the Problem i am having problem with. I have written the code for it. but it is arrayoutofbound exeception for some unknown input.
You and your rescued ...
2
votes
0answers
12 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
...
0
votes
0answers
21 views
Adjacency List representation of Graph using array versus Hashmap [closed]
Is it better to use an array or hashmap to store the graph?
I'm not sure which is more efficient way to store the nodes of the graph. I like the hashmap better because it seems more flexible.
...
4
votes
1answer
39 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
47 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
67 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. ...
4
votes
1answer
76 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
37 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
400 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 '...
10
votes
4answers
283 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
28 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
82 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
36 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
90 views
Python breadth first search algorithm
Any pointers, or any advice on how to clean up my code/make more pythonic would be appreciated.
...
2
votes
1answer
152 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
70 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
91 views
4
votes
0answers
113 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
55 views
Sort and describe itinerary segments
Given some incoming some data in JSON format, representing unsorted train, bus, and flight tickets:
...
3
votes
2answers
95 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 ...
1
vote
1answer
76 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 ...
1
vote
2answers
62 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
31 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
75 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
102 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
34 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 ...
2
votes
1answer
181 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
65 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.
...
1
vote
1answer
241 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?
...
2
votes
2answers
156 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?
...
3
votes
1answer
170 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
111 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
0answers
128 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 ...
7
votes
1answer
94 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:
...
5
votes
0answers
78 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 ...
8
votes
1answer
320 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
56 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. ...
5
votes
2answers
131 views
Is there a circular reference in a set of template substitutions?
I have a configuration engine that allows the user to specify a dictionary with text templates (read from a JSON file) where each placeholder like {x} can be ...
3
votes
2answers
155 views
Dijkstra's algorithm in JavaScript
I'm trying to implement Dijkstra's algorithm to find the shortest path. This is from a challenge on CodeWars.
In this scenario there is a map:
...
4
votes
1answer
63 views
8
votes
2answers
192 views
Rock, Paper, Whatever - A small commandline game
My rational for this program, was to learn more of Python's standard library, I didn't actually know cmd was even in it until I started this program. It's also the ...
4
votes
2answers
44 views
Split DAG into disjoint sets
I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding ...
3
votes
1answer
45 views
Circle check algorithm optimization for directed graph
Here is my two versions of code to check if there is a circle for a directed graph. Any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are highly ...
1
vote
1answer
89 views
Leetcode 210. Course Schedule II
Problem statement
There are a total of \$n\$ courses you have to take, labeled from
\$0\$ to \$n - 1\$.
Some courses may have prerequisites, for example to take course \$0\$
you have to ...
2
votes
0answers
20 views
Modeling a control polygon for a piecewise spline curve
Aim
I'm modeling a control polygon for a piecewise spline curve. Each sub-spline is defined by a location the spline must pass through, as well as a forward tangent, and a backwards tangent. The ...
2
votes
1answer
204 views
Representing an adjacency list (graph) using a hash table of lists
While writing a C++ implementation for weighed, labeled graphs, I started to doubt the effectiveness/correctness of my chosen structure and I would like to hear some reviews.
I tried to implement the ...
0
votes
2answers
97 views
BFS in a grid with wall breaking saldo in Java
In this problem, we are given a 2-dimentional grid, with each cell being walkable or holding a wall. Given an integer \$s \geq 0\$, find the shortest path from the source node to target node breaking ...
