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.

learn more… | top users | synonyms

-3
votes
0answers
30 views

Finding the Diameter of a graph [on hold]

Diameter of a graph is the maximum value of pairwise shortest distances over all pairs of vertices of the graph. Following is the algorithm for diameter of an undirected unweighted connected graph ...
5
votes
3answers
291 views

“Researcher Hatim is right or wrong” challenge

I wrote a program to solve a problem, I am not so good in python so want help to find areas where this program can be improved or simplified and readable too:- I got this problem in a code challenge ...
1
vote
0answers
36 views

Find all the countries I can visit by just crossing direct borders

I was helping on this question. There you have a table border to indicate countryA and countryB have a common border. And want ...
1
vote
1answer
72 views

Computing the distance and weight matrix of a graph

I would like to create an igraph object. First, I set up the size of igraph object — n, m, then create a random matrix. As a result matrix ...
2
votes
0answers
46 views

Dijkstra algorithm implementation in F#

I'm trying to implement Dijkstra algorithm in F# for finding the shortest path in a undirected tree using a heap. I've used the type PriorityQueue found here and the code can be found here. ...
2
votes
0answers
51 views

Dynamic graph in C++11 with shortest path algorithm

I've been designing a dynamic graph to improve my understanding of C++11. The dynamic aspect means that it could represent the hyperlink structure of a chunk of the internet, with node deletion ...
11
votes
1answer
93 views

Glue Shredded Pieces (CodeEval)

I have solved problem 185 on CodeEval, Glue Shredded Pieces. The solution got a 100% score on all tests (edit: see comments), within the allotted time and memory constraints. I'm looking mostly ...
1
vote
1answer
47 views

Iterative depth-first search and topological sort in Java

This is the iterative depth-first search, that does not abuse the stack. Also, I gathered some information from DFS that may be useful; for example, I am able to do topological sort using the result ...
1
vote
1answer
61 views

Check if a given path exists in a graph

I'm using BFS to see if a given path exists in a graph: ...
3
votes
1answer
55 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
62 views

Traversing a stack in my DFS algorithm for finding a path in a maze

I am trying to get this code running as fast as possible when traversing through my stack of my DFS currently the input files are like so: ...
1
vote
0answers
33 views

Prim's MST implementation

This is my full working code. I am a bit confused about how I was able to use the structure MinHeapNode's variable in my Graph.cpp file. I used its ...
5
votes
0answers
94 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 ...
1
vote
2answers
101 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. ...
4
votes
1answer
75 views

Prove that the graph is a valid tree in Python

I recently solved this leetcode problem: Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges ...
5
votes
2answers
59 views

Bob the (Graph) Builder

I'm starting a project in which I'll generate random graphs and use algorithms to solve them. The first necessary step is obviously to build a graph. My graph has the following characteristics : ...
5
votes
0answers
73 views

Graph as adjacency lists: BFS DFS Topological Sort

I have written some code to practise graphs. Graph is represented as vector<list<int>> . Would you share some feedback with me? Are algorithms correct ...
13
votes
2answers
226 views

All your bases are belong to Dijkstra

CATS, willing to get a hold of all the bases, asked Dijkstra to give him a hand designing the most powerful algorithm to reach all bases with the least distance travelled. I tried to implement ...
7
votes
1answer
109 views

Graph theory using C++ STL

I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object. Any feedback would be ...
10
votes
1answer
81 views

Simple Oriented Graph implementation in Java

I wanted to implement a simple oriented graph as part of an exercise in both Object Oriented Programming and Data Structures. I wanted to make it as class-focused as possible, so I don't know if my ...
8
votes
2answers
353 views

C++ Graph Implementation

My data set is a list of Edges which are passed as a pair of integers. Based on that, I have the following graph implementation for BFS. Could someone please review ...
4
votes
2answers
41 views

Vertex cover approximation in JavaScript

I believe this runs in \$O(V+E)\$ but I wouldn't be able to explain the reasons why. I was looking for some general code review and any help on understanding the runtime. ...
2
votes
0answers
16 views

Return the Euler Cycle for a graph with es6

My algorithm for finding an Euler tour of a digraph, G⃗, if such a tour exists, starting from some vertex, v. ...
4
votes
3answers
83 views

Finding a loop in a directed graph in Python

I wrote this code to find if a directed graph contains a loop or not. I am pretty new to graphs and I saw some examples on the internet but couldn't actually understand their implementations. So I ...
3
votes
0answers
156 views

Depth first search implementation

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the depth first search section (5.8) using javascript. Note you can execute the code here if you don't ...
2
votes
1answer
74 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 ...
5
votes
1answer
97 views

Breadth first search implementation (also includes functions for finding shortest path and number of connected components)

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the breadth first search section (5.7) using javascript. I also have a ...
1
vote
1answer
78 views

Graph radius in Java

(See the next iteration.) The following snippet is a brute-force algorithm for computing a graph radius in time \$\Theta(V^2 + VE)\$ and space \$\Theta(V)\$ simply by doing \$|V|\$ breadth-first ...
2
votes
1answer
82 views

Graph Interface: Storing Vertices in an Array vs HashTable

I have just started learning graph algorithms and am trying to arrive at an ideal interface. I understand that this code will not be used anywhere else (I will certainly use Boost::Graph) but I just ...
1
vote
0answers
95 views

Random Contraction Min Cut (Karger) - performance issues

(Offtopic note: I can't add a "networkx" tag.) I reworked an old algorithm, this time not implementing the graph on my own, but building on the networkx module. Script works fine for the tests and ...
3
votes
1answer
48 views

Finding all backedges in an undirected graph

I have tried to implement the DFS algorithm to find all the back-edges in a graph that lead to a cycle in the graph: ...
2
votes
1answer
108 views

BFS for modified shortest path

Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ? The itinerary of ...
3
votes
1answer
166 views

Converting a List of arcs into Adjacency list representation for graph using dictionary

I was reading up on implementing Graphs in Python and I came across this Essay at python.org about graphs, so I decided to implement it, but with weighted edges. I start with arcs and their cost ...
2
votes
1answer
60 views

Shortest path from U to V using at most k nodes

I'm trying to solve a problem that asks for a shortest path between two cities with at most k nodes. The first line of input has the number of test cases. On the second line 3 integers are given, ...
5
votes
0answers
125 views

Speeding up Python depth-first search in large graph

I'm building a Markov text poetry generator. The main method, which is attached below, performs a depth-first search through the Markov chain, which is implemented as a NetworkX digraph of Word ...
1
vote
1answer
44 views

Kruskal's algorithm

I'm working through Coffeescript implementing simple algorithms (started with Prim's as reviewed in this previous post) and wrote out Kruskal's algorithm as below, with a few helper functions. I'd ...
4
votes
0answers
106 views

Directed graph isomorphism in Java

Given two input directed graphs \$G_1 = (V_1, A_1)\$ and \$G_2 = (V_2, A_2)\$, the problem of isomorphism asks whether the two directed graphs are isomorphic, or in other words, whether the two input ...
2
votes
3answers
69 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 ...
3
votes
1answer
27 views

Find order to install dependencies

Given a JavaScript map object of dependencies and their dependencies, determine order to install them: Example: Input: ...
7
votes
1answer
508 views

Ford-Fulkerson Algorithm: Max flow

I have worked on the Ford-Fulkerson algorithm and have following code. The code works fine, but I fill I could do more code optimization, I have worked on it for few days. Question1: Is there any ...
1
vote
0answers
184 views

Brute force shortest path in Java

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
2
votes
1answer
63 views

Creating a time-course dependent, correlation-based directed graph with Networkx

I have a correlation matrix containing 4 time points, each with multiple samples. Each sample is identified with a time point with its name. What I am trying to accomplish here is to create a directed ...
0
votes
0answers
36 views

TrieMap based Simple Graph API

Looking for some feedback regarding elegance, about my code below implementing a simple graph API basing on scala.collection.concurrent.TrieMap. Background: I am ...
5
votes
2answers
275 views

Maze solver for 2D matrix in Ruby

I got rejected for a junior Ruby job entry where I had to solve a 2D matrix as a maze with walls. This is the main class: solver.rb ...
3
votes
1answer
51 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 ...
4
votes
0answers
124 views

Canvas animation of network nodes and edges

Having to give the idea of an ever changing network of nodes (each with different impact and possibly more than one color) connecting each other to create something. I wanted to give it depth ...
2
votes
0answers
146 views

A simple graph walk interception algorithm in Java

I have that girl whose graph walk I want to intercept, but because I am not good at running algorithms in my head, I had to program my computer to do that for me. I would not consider the problem to ...
5
votes
2answers
47 views

Creating nodes and edges

I'm looking for a way to optimize this piece of code in Python. all_users holds all the Twitter users and friends_ids is an ...
0
votes
1answer
129 views

Eulerian Tour in Python

This is a recursive algorithm implementation of Eulerian tour search. I guess there is no way to make it more efficient (except rewriting with loops instead of recursion). Any advice on style? ...
4
votes
1answer
124 views

Find a triangle in a graph represented as an adjacency list

I have a graph represented as an adjacency list. I need to find a triangle in this graph. A triangle is a triple of vertices u, ...