a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices

learn more… | top users | synonyms

33
votes
8answers
13k views

When to use DAG (Directed Acyclic Graph) in programming?

I recently found a framework named ecto. In this framework, a basic component named "plasm", which is the ecto Directed Acyclic Graph.In ecto, plasm can be operated by ecto scheduler. I am ...
18
votes
6answers
788 views

Visiting points on a number line while minimizing a cost not related to distance

I need some help on this ACM ICPC problem. My current idea is to model this as a shortest path problem, which is described under the problem statement. Problem There are N = 1000 nuclear waste ...
16
votes
5answers
3k views

Algorithm to determine fastest route?

Let's say we're going from 1 to 5. The shortest route will be 1-4-3-5 (total: 60 km). We can use Dijkstra's algorithm to do that. Now the problem is, the shortest route is not always the fastest ...
16
votes
7answers
893 views

How do you unit-test code using graphs?

I am writing (recursive) code that is navigating a dependency graph looks for cycles or contradictions in the dependencies. However, I am not sure how to approach unit testing this. The problem is ...
15
votes
3answers
9k views

Efficient graph clustering algorithm

I'm looking for an efficient algorithm to find clusters on a large graph (It has approximately 5000 vertices and 10000 edges). So far I am using the Girvan–Newman algorithm implemented in the JUNG ...
11
votes
3answers
936 views

Randomly generate directed graph on a grid

I am trying to randomly generate a directed graph for the purpose of making a puzzle game similar to the ice sliding puzzles from Pokemon. This is essentially what I want to be able to randomly ...
10
votes
2answers
1k views

How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear

I'm trying to figure out what sort of data structure to use for modeling some hypothetical, idealized network usage. In my scenario, a number of users who are hostile to each other are all trying to ...
10
votes
1answer
6k views

Am I right about the differences between Floyd-Warshall, Dijkstra's and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra's algorithm is used only ...
8
votes
2answers
309 views

Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data

I would like to learn how to make graphs and perform some local operations on them in Haskell, but the question is not specific to Haskell, and instead of graphs we may consider doubly linked lists. ...
7
votes
4answers
3k views

What are graphs in laymen's terms

What are graphs, in computer science, and what are they used for? In laymen's terms preferably. I have read the definition on Wikipedia: In computer science, a graph is an abstract data type ...
7
votes
2answers
158 views

spotting graph cycles - simple explanation

could some please help me understand how to find cycles in graphs in laymans terms? I have read other questions, such as This one and also some of the wikipedia pages, but they seem to descend rather ...
7
votes
3answers
349 views

Algorithm or domain for finding cheapest subgraphs that connect vertex pairs

I am currently working on a project inspired by the Ticket to Ride board game. This board game is played on an undirected graph where each vertex represents a city and each edge represents a ...
6
votes
3answers
2k views

Cyclomatic complexity with two IFs - why it is 3?

I have read an article with following example: void func() { if (condition1) a = a + 1; if (condition2) a = a - 1; } It says the CC is 3 as there are three possible paths. How come? Why not 4? I ...
6
votes
1answer
1k views

Where to learn graph theory applications [closed]

I am completely new to designing algorithms with graphs. I am following CLRS and other video lectures in Youtube, notably from IIT/MIT. They are pretty good, and I currently have decent idea about ...
6
votes
3answers
2k views

What algorithm should I use to find the shortest path in this graph?

I have a graph with about a billion vertices, each of which is connected to about 100 other vertices at random. I want to find the length of the shortest path between two points. I don't care about ...
6
votes
6answers
811 views

Finding most Important Node(s) in a Directed Graph

I have a large (≈ 20 million nodes) directed Graph with in-edges & out-edges. I want to figure out which parts of of the graph deserve the most attention. Often most of the graph is boring, or at ...
6
votes
1answer
146 views

Detecting areas of isotropic vs anisotropic diffusion in a flood-fill (or similar) operation

Hello fellow programmers! I have a 2D graph which is best described as a Cartesian grid with traversible and non-traversible cells. I'd like to be able to detect subsets of this graph where the ...
6
votes
1answer
207 views

Heuristic Approach for Flexible DIFF Implementation

I have created a DIFF implementation to compare document revisions at work. It is based on An O(ND) Difference Algorithm and Its Variations. One thing that has become important is to take the list ...
5
votes
2answers
1k views

Algorithm for an exact solution to the Travelling Purchaser Problem

do you know of any algorithms which give an exact solution for the Traveling Purchaser Problem. I can only find heuristic and probabilistic approaches. I do have implemented a genetic algorithm so ...
5
votes
1answer
964 views

Merging similar graphs based solely on the graph structure?

I am looking for (or attempting to design) a technique for matching nodes from very similar graphs based on the structure of the graph*. In the examples below, the top graph has 5 nodes, and the ...
5
votes
2answers
240 views

How to optimize/parallelize the following clustering/joining algorithm:

I have relatively-small algorithm that takes up ~60% of the total run-time of my scientific code (57 lines of 3600), so I would like to find a way to optimize what I'm doing and make the code ...
5
votes
1answer
618 views

Algorithm for perfect non-binary graph layout

I have a complex non-binary graph model. Each tree node can have multiple children&parents (a node can also have a connection to it's "brother"). A node is represented as square on screen with ...
5
votes
1answer
183 views

What is the maximum number of steps to find a bug using bisecting?

Assume that a node A in the commit tree of a codebase contains a bug but some ancestor B of A is clean from that very bug. Given the topology of the commit tree [B,A] leading from B to A, can we ...
5
votes
1answer
204 views

Graph visualization algorithm

I need a 2d or 3d graph visualization algorithm by which adding/removing a node or a relationship does not have a butterfly effect on the positions of other nodes. (We are talking about a directed ...
5
votes
1answer
2k views

Building a Graph Editor - How to create a data driven graph

I am developing a graph-editor that uses drag and drop to build hierarchical graphs (containing nodes and links). Each node in the graph should be linked to a table in our database (SQL Server). I did ...
5
votes
0answers
59 views

Algorithm to generate Edges and Vertexes outwards from origin with max multiplicity of 3

I am creating a 2d game for a website where the universe can grow extremely large (basically infinitely large). Initially, the universe is composed of 6 stars that are an equal distance from the ...
5
votes
3answers
3k views

What is an algorithm to find simple cycles?

I have a graph with an Eulerian cycle and no Hamiltonian cycles. I would like to divide this graph into simple cycles. Edges may not be repeated in simple cycles. How can this be done?
4
votes
4answers
457 views

Building a route creator

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework. Route ...
4
votes
2answers
221 views

Algorithm to find the optimal trade route (negative cycle with lowest cost per edge in a digraph)

Given the following problem (a slightly simplified description of trading in the computer game Escape Velocity: Nova (system map)): Given a set of (solar) systems. Each system is connected by ...
4
votes
1answer
455 views

Shortest Path Between Two Nodes in a +10 Million Nodes Graph

I have my own knowledge graph representation, read from ConceptNet and NELL, containing tens of millions of nodes in which I want to calculate the nearest distance (if any) between two concept nodes. ...
4
votes
3answers
864 views

Optimal “if-else” tree algorithm to minimize duplicate code

I'm having trouble formulating this problem as an algorithm: I have a set of conditionals (combined with &&) and operations, for example: if (A && B) execute C else if (D ...
4
votes
1answer
115 views

Single Source Shortest Path

In the lecture we are taught that we can solve All Pairs Shortest Path(APSP) with matrix multiplication. In APSP we are creating a distance table for all the distances between each nodes in the ...
4
votes
1answer
121 views

Mathematically correct A* heuristic / distance estimator for a latitude / longitude graph

I have a graph in which each node is a geographical point on the surface of the earth, defined by it's latitude / longitude coordinates. Correct ways to calculate the distance between two such points ...
4
votes
1answer
234 views

How to implement efficient heterogeneous microservice data queries?

Our team has an idea of implementing a simple declarative DSL that would let users query the enterprise's domain model via a single interface without caring which specific microservices to call to get ...
4
votes
1answer
161 views

Algorithm to find whether there is a path (any path) above length X between two vertices

We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than ...
4
votes
1answer
365 views

Data structures and algorithms for a directed rooted tree with inherited properties?

I need to represent a directed rooted tree in memory. The caveat is, that nodes have properties. And those properties are inherited (but not 100%) by the child nodes, recursively. What would be a ...
4
votes
2answers
119 views

Placing elements in graph with a streaming/online algorthm

We have a stream of points with about 1000 points per second. For each point, we have a complex vector (hundreds of dimensions). Our goal, for each point is to link it to the 5 closest points that ...
4
votes
2answers
249 views

Merge directed acyclic graphs minimizing number of nodes

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free). These four different DAGs ...
3
votes
2answers
297 views

Chambers In A Castle Algorithm

Problem Statement - Given a NxM grid of 1s & 0s (1s mark walls, while 0s indicate empty chambers), the task is to identify the number of chambers & the size of the largest. And just to ...
3
votes
1answer
200 views

Finding the optimal root

I am trying to solve a quora hackathon challenge question. The question descrpition is as follows : For the purposes of this problem, suppose Quora has N questions, and question i (1≤i≤N) takes ...
3
votes
2answers
580 views

Is it possible to represent mutation of object-graph efficiently with immutable states?

I am practicing using of immutable object in C++. My personal goal is representing generic object graph (in heap) with sequence of immutable graphs. Building the multi-version graph itself isn't that ...
3
votes
2answers
2k views

When can I be sure a directed graph is acyclic?

The definition for directed acyclic graph is this: "there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again." So far so good, but I am trying to ...
3
votes
2answers
432 views

How can I find the shortest path between two subgraphs of a larger graph?

I'm working with a weighted, undirected multigraph (loops not permitted; most node connections have multiplicity 1; a few node connections have multiplicity 2). I need to find the shortest path ...
3
votes
2answers
453 views

How to find number of points with same minimal distances on matrix

I'm trying to find the number of points in a matrix with the same minimal distances. Start with a MxN matrix, where M and N < 50000. There is given a set of fixed points, with their respective ...
3
votes
2answers
890 views

Breadth-first graph search problem

I thought I was doing breadth-first graph search correctly, but my instructor's grading script is telling me that my answer is incorrect. From the instructions: Consider a breadth-first graph ...
3
votes
1answer
336 views

How to solve binary labeling with graph cut?

Many literature references suggest that the binary labeling problem can be converted into a graph cut problem and solved with the max flow/min cut algorithm. I'm trying to understand the formulation ...
3
votes
2answers
202 views

Custom graph comparison?

I'm trying to compare two graphs using hash value ( i.e, at the time of comparison, try to avoid traversing the graph ) Is there a way to make a function such that the hash values compared can also ...
3
votes
1answer
140 views

why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?

Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex). But ...
3
votes
1answer
361 views

Is there some structured format for drawing source control branching diagrams?

Everyone on my team draws branch diagrams differently, including how branches exit or reintegrate to the parent, how cherry-pick merges are shown, and a host of other aesthetic choices. Is there some ...
3
votes
1answer
202 views

Class instance clustering in object reference graph for multi-entries serialization

My question is on the best way to cluster a graph of class instances around specifically marked objects (objects are the graph nodes and the references to each other are the directed edges of the ...