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
687 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
10k 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
4k 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
821 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
74k 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 ...
12
votes
3answers
385 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 ...
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 ...
6
votes
2answers
185 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 ...
5
votes
0answers
62 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 ...
5
votes
1answer
833 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 ...
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
571 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 ...
4
votes
3answers
390 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: ...
4
votes
1answer
110 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
3k views

Bellman Ford algorithm implementation

Please review my code and help me to improve it. ...
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. ...
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 ...
3
votes
1answer
169 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: ...
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
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 ...
1
vote
1answer
757 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....
11
votes
2answers
796 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
79 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
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
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
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:...
5
votes
1answer
247 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 ...
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
1answer
91 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 ...
4
votes
2answers
173 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 ...
4
votes
1answer
763 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. ...
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
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)\$, ...
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
1answer
191 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
162 views

Implement a graph in Python

Question : Build a graph in python, given its edge representation. ...
2
votes
2answers
325 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 ...
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
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 ...
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
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 ...