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

A generic implementation of Dijkstra

Here is an implementation of Dijkstra As an rags-to-riches version of this Object oriented approach to Dijkstra's algorithm ...
10
votes
2answers
2k views

Missing level of technical depth (Common Ancestor)

I recently have given a coding test in a reputable IT company. There were three coding questions. They refused me by saying that as we felt they didn't demonstrate the level of technical depth we'...
6
votes
2answers
9k views

Kruskal's algorithm in Java

I have this Java implementation of Kruskal's algorithm. It solves a tiny problem instance correctly, yet I am not quite sure, whether my implementation is correct. The code as follows: MSTFinder....
2
votes
1answer
3k views

Return path between graph nodes using depth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. I'm doing this to improve my style ...
1
vote
1answer
765 views

NBA*: Very efficient bidirectional heuristic search algorithm in Java - follow-up

This post elaborates on NBA*: Very efficient bidirectional heuristic search algorithm in Java. I have made the following changes: Added an explicit type for representing digraph paths: ...
3
votes
1answer
2k views

Simple data structures for representing graphs in Java

Motivation I do a lot of graph-theoretic code, and, by now, I feel substantial need for data structures that can represent weighted graphs, both directed and undirected. Up till now, I was in a habit ...
1
vote
2answers
1k views

Object oriented approach to Dijkstra's algorithm

I'm seeking a code review for the following C++ implementation of Dijkstra's algorithm. I'm trying emphasize code reusability and extensibility but performance is also potentially important. ...
27
votes
4answers
73k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
8
votes
3answers
1k views

Reorder a list of courses, given their prerequisites

I recently graduated from college and applied for a position with a company. I was sent a coding exercise as part of the process. After completing the exercise and submitting it I was told that the ...
6
votes
2answers
2k views

Strongly connected component algorithm in Python 2.7

This is my implementation of Kosaraju's algorithm for detecting strongly connected components, post here for advice. Some special areas looking for advice, Not sure if my current implementation for ...
13
votes
1answer
1k views

Generic Graph Library

I've been working on a generic graph library for a while now, in a bit of an off and on fashion. I realise that boost::graph exists, but it is a complex library ...
12
votes
3answers
380 views

Kosaraju in Scala

I started coding in Scala some time ago, and also learning some fundamental algorithms in CS. Here's a terribly slow implementation of Kosaraju algorithm to find strongly connected components in a ...
5
votes
2answers
1k views

Implementation of a graph in Java

A long time ago I posted my implementation of directed graph is Java. Recently I took a look at @coderodde's implementation and decided to write an implementation of undirected graph and directed ...
5
votes
1answer
562 views

Social network broadcast message algorithm

Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am ...
5
votes
1answer
718 views

Hackerank - value of friendship

Problem statement You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no ...
4
votes
3answers
3k views

Breadth First Search using adjacency list

I want to improve this code using STL. Let me know if I should add any other function in this code. ...
4
votes
1answer
106 views

Generate multi dimensional maze with borders and fixed degree on each node type

IMPORTANT: giving too big combination of node count and edge/neighbor count can overflow your RAM and swap file very quickly, thus I recommend staying below 500 on node count and below 50 on neighbor ...
4
votes
2answers
2k views

Bellman Ford algorithm implementation

Please review my code and help me to improve it. ...
4
votes
3answers
382 views

Algorithm to group connected graphs

I am working on an algorithm, which should group connected Arcs. The situation is described via code examples below. I have Arcs: ...
3
votes
1answer
167 views

Finding smallest number of moves

We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this: ...
3
votes
2answers
3k views

Implementation of Dijkstra's algorithm to find the shortest path in graph

This is my implementation of Dijkstra's algorithm in C++. Please clarify Whether the class design is proper or if it needs to be improved. I am just hard coding the vertex based on the priority of ...
3
votes
1answer
1k views

Graph Implementation in Java using adjacency list - v2

Updated version from Graph Implementation in Java using adjacency list ...
2
votes
1answer
3k views

Implementation of a directed graph

I wrote an implementation of a directed graph using the adjacency list representation. My goal was to meet the big O requirements which I'd found here. Please let me know about any drawbacks of the ...
1
vote
1answer
674 views

NBA*: Very efficient bidirectional heuristic search algorithm in Java

(See also the next iteration.) I have implemented NBA* (New Bidirectional A*) in Java and compared it against conventional A* and Dijkstra algorithms. The results may be as optimistic as this: Seed =...
1
vote
1answer
1k views

Graph Implementation in Java using adjacency list

I am building a Graph class to learn and eventually plan to add Dijkstra's algorithm to this implementation. What do you think of the overall approach? Any feedback on how to improve this? Vertex....
1
vote
1answer
4k views

Implementation of Dijkstra's algorithm in C++

This is my implementation of Dijkstra's algorithm. Could you tell me what am I doing wrong and what should be fixed? I was not sure how to keep track of the shortest outgoing edge from a node and I ...
11
votes
2answers
787 views

Milking order compatible with maximum number of observations

I'm using some old USA Computing Olympiad (USACO) problems to help teach me. This is the "Milking order" problem: Farmer John has \$N\$ cows (\$1≤N≤10^5\$), numbered \$1…N\$. He has made \$M\$ ...
8
votes
1answer
329 views

Breadth First Search not SOLID enough v2.0

Original question: Breadth First Search not SOLID enough Here is my first attempt at refactoring. Instead of using a Tuple, I used a ...
5
votes
1answer
69 views

3-function program computing connected components of a point cloud given a distance matrix

I wrote this code in Haskell (instead of Python) for the educational benefit. Can anyone suggest ways to improve this code? I'm guessing that I'm using fromIntegral...
5
votes
1answer
234 views

Sort a scrambled itinerary (Google apac test problem)

This is my first time writing ruby - and I was mainly hoping to get some feedback and stylistic pointers. The algorithm is pretty straight-forward, since Google guarantees airports aren't repeated I ...
5
votes
4answers
7k views

Sum of all paths between all pairs of nodes in a tree

I'm trying to solve a competitive programming problem. It basically gives a undirected graph (tree-like: no multiple paths between two nodes...) and asks for the sum of all possible paths between any ...
5
votes
2answers
6k views

Graph vertex class implementation with adjacency lists

I wrote an implementation of a graph with each vertex storing a std::vector of vertices it's adjacent to. Please critique this. ...
5
votes
1answer
5k views

Generalized Missionaries and Cannibals in Java

See the next iteration. I was in the mood for some basic AI, and decided to code up an algorithm for solving "\$M\$ missionaries, \$C\$ cannibals in the boat with \$B\$ places" -algorithm: Demo.java:...
4
votes
0answers
51 views

graphtimer v2 - Utility to plot timings

GitHub repo (MIT) Clone the repo and replace the contents of example.py with the one at the bottom and you'll have everything setup. Explanation of the code A ...
4
votes
1answer
727 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
2k views

Removing graph nodes of a specific type and with exactly two neighbors

I am working with an undirected, weighted graph. It contains two types of nodes, called "A-type" and "B-type". I am starting with a set of tuples of the following ...
4
votes
2answers
167 views

Directed graph path enumerator in Java

I have this iterator class that expects in its constructor two directed graph nodes, source and target, and upon each ...
3
votes
2answers
118 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)\$, ...
3
votes
1answer
2k views

Dijkstra's algorithm: traditional and bidirectional in Python

I have translated Dijkstra's algorithms (uni- and bidirectional variants) from Java to Python, eventually coming up with this: Dijkstra.py ...
3
votes
1answer
2k views

Graph implementation adjacency list 1.0

Please note the following: All edges are directed Removal of edges/nodges is not implemented yet A user of the class Graph can never (hopefully) access a ...
3
votes
1answer
67 views

Binary Bayes network classifier in Java - Part I/II - follow-up

TERMINOLOGY We are given a directed acyclic graph (dag) \$G = (V, A)\$, where \$V\$ is the set of nodes and \$A \subseteq V \times V\$ is the set of directed arcs, and a weight function \$p \colon V \...
2
votes
3answers
89 views

Prim's algorithm in CoffeeScript

I'm just starting to learn CoffeeScript and am trying to work through simple examples, this one being Prim's algorithm. I'd like feedback on everything but especially on making this script take ...
2
votes
1answer
1k views

2D Histogram class

I scraped some data looking at trajectories of popular posts on Reddit, and now I want to group and histogram them by type. I put this class together in C++ to do so. Characteristics of the data are ...
2
votes
1answer
190 views

Graph radius in Java - follow-up

See the previous and initial iteration. Terminology Given an undirected graph \$G = (V, E)\$, the eccentricity of a node \$u \in V\$, \$e(u)\$, is the maximum length (number of edges) of a shortest ...
2
votes
1answer
159 views

Implement a graph in Python

Question : Build a graph in python, given its edge representation. ...
2
votes
2answers
304 views

Generating a graph from a rectangular grid for graph searching

I recently reviewed some code implementing some heuristics which has piqued my interest in the A* graph searching algorithm. I'm going to do that in a bit but first I need a way to create a graph in ...
1
vote
0answers
24 views

Wikipath stack in Java - Part II/IV - The implicit Wikipedia article graph

This question is the continuation of the Wikipath stack series: the two classes that - given a Wikipedia article \$A\$ - return the lists of neighbour articles. The forward node expander return the ...
1
vote
1answer
299 views

Return a path between graph nodes using depth-first search redo

I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this ...
1
vote
1answer
49 views

C++ - Graph implementation for data types other than int

I am learning graphs and most of the implementations that I see are meant for int. So, I decided to code an example that can take other data types such as ...
1
vote
0answers
509 views

Generalized Missionaries and Cannibals in Java - follow-up

See the previous and initial iteration. Now I have incorporated all the points suggested by mdfst13, and have the following: StateNode.java: ...