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
4
votes
1answer
717 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 make ...
6
votes
2answers
159 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
1k 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 ...
14
votes
2answers
932 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 the ...
9
votes
1answer
915 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
2k 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
4k 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 ...
3
votes
2answers
152 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
229 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
2answers
2k 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
3k 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
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 ...
6
votes
1answer
3k 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 ...
0
votes
1answer
735 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
866 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
1k 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
73 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: ...
3
votes
1answer
1k 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
3k 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
617 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, ...
13
votes
2answers
735 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
84 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 ...
9
votes
1answer
2k 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
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 ...
3
votes
1answer
38 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
2answers
3k 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. Question: Is there any ...
3
votes
0answers
2k 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 ...
3
votes
1answer
401 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 ...
1
vote
0answers
333 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 ...
4
votes
2answers
1k 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
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 \...
4
votes
0answers
951 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
751 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
75 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
2answers
2k 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? ...
7
votes
1answer
4k 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, v...
12
votes
1answer
3k views

IDA*: Iterative Deepening A* implementation

I created a generic version of IDA*. I am attempting to create the following code with exceptional quality and performance. I'm hoping to try and create short code tutorials regarding. However, the ...
3
votes
1answer
499 views

Solving Project Euler problem #60 in C++

I have implemented a solution to Project Euler problem #60. In summary, the problem asks to find the smallest sum of a set of five prime numbers such that the decimal strings of any two numbers in 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 ...
3
votes
1answer
103 views

Directed graph path enumerator in Java - follow-up

I have refactored the graph path enumerator. DirectedGraphNode was not changed, so refer to the link above in case you want to have a look at it. The node type is ...
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 ...
-2
votes
1answer
615 views

Shortest path in dag saga: Dijkstra's algorithm [closed]

I have this Dijkstra's shortest path algorithm: net.coderodde.graph.pathfinding.AbstractWeightedPathFinder: ...
2
votes
1answer
377 views

Maximum matching in graph

I'm currently working on this problem for my own practice. It's a paintball problem where I should determine if everyone can get a unique target. The problem is as follows I get a number of pair like: ...
1
vote
0answers
534 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: ...
7
votes
1answer
112 views

Animating a 2D particle “web”

I have written a small class to generate and animate one of those trendy particle webs. I plan to use this as the main background of my personal website, so naturally I'm concerned about the ...
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 ...
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:...
2
votes
2answers
2k views

Java DFS Implementation that tracks time and parent node

I have a project where I'm to implement a DFS using a direct graph. The implementation should print the currently visited vertex, the parent (the node from which the current node was reached), and the ...
1
vote
2answers
614 views

Graph implementation to be used for finding Cycles, Paths, closest path between two nodes, etc

I am restudying graph theories and I want to write a Graph class that would allow me to implement those methods. Is there a better way of implementing a general <...
1
vote
1answer
197 views

Find unconnected nodes of a graph

It is a set of edges of a graph given. An edge is given as an array of its endpoints, e.g. [:a, :b]. The array can contain an arbitrary amount of endpoints. ...