# Tagged Questions

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

0answers
38 views

### How to describe a set of paths in a graph with as few nodes as possible?

I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few ...
0answers
123 views

### Modelling a complex schedule of work

I've got a real-world problem that I'm trying to represent and automate. I've simplified and abstracted it down to the following: There are n places of work (P1, P2, ..., Pn). Each place, Pn has a ...
0answers
42 views

### All minimum cuts in flow network [migrated]

I'm trying to prove that for a flow network, maximum flow f, and each minimum cut S that f(S)=c(S). Max flow min cut promises that there exists a cut where f(S)=c(S); I want to prove that given ...
2answers
147 views

### The way to implement a configurable (at run-time) default style

I am coding a visualizer of graph algorithms. Each vertex of the graph has a style (color, size etc.). As long as the algorithm has done nothing to a vertex, that vertex has a default style. The ...
2answers
58 views

### Graph database keeping historical relationships

I'm starting the modeling of the following problem: I have many clients (millions) that interact in a network forming a graph. At the highest granularity of my business problem, each realationship ...
1answer
204 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 ...
0answers
32 views

### efficient graph clustering algorithm for weighted directed graphs based on node and edge weights

I'm looking for an algorithm to cluster weighted directed graphs that have weights on both edges and vertices. I'm using graphs with multiple weights(labels) on vertices and a weight on edges that ...
0answers
32 views

### Finding subgraphs in non-directed graph

Problem at hand: Finding separate subgraphs. Update on adding or removing edges. First I've been thinking about running DFS after every operation from both ends of the edge, but if I keep ...
1answer
95 views

### What Graph Theory approaches or algorithms are useful for designing a House?

I have a set of data about a family, and I want the software to find a house design that fits the data (which includes stuff like preferences and whether they want a pool. The current way I am going ...
2answers
348 views

### Euclidean Space Fully Connected Nondirectional Graph: Shortest Path to all nodes

So this may be a question that is born of my inability to properly express my intentions to Google. In a fully connected non-directional graph such that any three points can be properly represented ...
1answer
55 views

### The maximum number of induced cycle in a simple directed graph

Given a simple directed graph G=(V,E) an induced cycle is a cycle where no two vertices of the cycle have an edge that is not in the cycle. (Chordless cycles are induced cycles with at lease 4 ...
1answer
214 views

### Are there multiple Hamiltonian Paths on a Graph?

Can anyone suggest an algorithm for this problem. Given an undirected unweighted cyclic graph, and a given start and end node in that graph, I'd like to determine if there is exactly one valid path ...
1answer
84 views

### Yen's k shortest paths algorithm

I'm currently trying to understand Yen's k shortest paths algorithm. I based myself on the original paper as well as on the Wikipedia article, but still cannot see why it is correct if k > 2. In fact, ...
1answer
142 views

### Word ladder efficency problem

I have a problem dealing with word ladders. The problem is: given two words and a dictionary file, find the shortest word ladder between the two words. So if given the words cat and pot: cat -> ...
3answers
248 views

### Algorithm to determine the fastest route passing in all points

Given a starting point A and an end point E, I need an algorithm to determine the minimum transit route in a city that passes through all points (A, B, C, D, E) and is the fastest possible. I know I ...
0answers
160 views

### Approaches to Modeling a Graph Database over the Google App Engine Datastore?

I want to model a graph database over the Google App Engine Datastore. I am currently working on creating a Link entity to model the concepts of link/edge/relationship to the graph of objects. I am ...
1answer
869 views

### Understanding Tarjan's Bridge-finding algorithm

Tarjan's algorithm for finding bridges in a graph is found here: http://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan.27s_Bridge-finding_algorithm. However, I don't understand the condition for ...
1answer
69 views

### How many vertices/nodes are too many in a graph and stop being beneficial?

Background I'm working on a project that requires me to keep track of transactions as well as the flow of items in a game. In order to do that, I'm storing those transaction in a graph db (Orient-DB)....
1answer
65 views

### Dynamic Programming: Shortest path with exactly k edges in a directed and weighted graph

I came across this problem of finding the shortest path with exactly k edges. After some searching, I found the code below. It uses a 3D DP. States are there for number of edges used, source vertex ...
1answer
38 views

### Partition edges into areas

If I have a series of edges that branch and curve, such as in a road network, is there an algorithm that will identify the areas (defined by sequence of geographic points) defined between those lines? ...
0answers
46 views

### Benefit and graphical representation of directed acyclic graph in code development

I think the relationship amongst the modules of a code can be represented by a directed acyclic graph (DAG) where a vertex represents a module and a directed edge from vertex a to vertex b represents ...
3answers
1k 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 ...
0answers
78 views

### Determine equality of a DAG

Given a fairly traditional node class (below), whats the best way to implement equality on a given graph? If our node looks like this public abstract class Node{ private final Set<Node> ...
8answers
15k 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 ...
0answers
89 views

### Decision making algorithm

I'm currently solving an optimisation problem of my own design, just to experiment and learn a little something. Here's the concept: I have a user that starts at home. The objective of this user is ...
1answer
327 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 ...
2answers
346 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. ...
0answers
46 views

### Graph grouping with criteria

I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...
1answer
133 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 graph....
1answer
477 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 ...
1answer
159 views

### undirected c++ graph with a direction [closed]

I want to create a Graph in C++ that has directions, with directions I don't mean the direction of an edge but what I want is an undirected graph where the edges have a direction to the next vertex, ...
2answers
250 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 order-...
1answer
96 views

### Are these graph coloring algorithms equivalent?

Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. The goal is to avoid giving two adjacent (linked by an edge) vertices the same ...
0answers
93 views

### Belman-Ford 2d array variation problem

I've got a problem with applying a Bellman-Ford algorithm to 2D Array (not to graph) Input array has m x n dimensions: s[1,1] s[1,2] ... s[1,n] -> Exit s[2,1] s[2,2] ... s[2,...
0answers
42 views

### Filter out noise in line graphs

I have a question regarding finding relevant events in a line graph. The following graphs show the views (y-axis) of a video over time (x-axis). Certain events lead to an huge increase in views and ...
2answers
951 views

### Connected components of a graph using Prolog

Given a corner x of an undirected Graph G I would like to ask for the connected component of x, but my first try does not work as desired. Here it is: edge( a,b ). edge( b,a ). edge( b,c ). edge( c,...
1answer
307 views

### Dependency ordering algorithm of a compiler

Let's say, hypothetically, I'm writing a Java compiler. And we assume that in my case a class can't be fully compiled until all signatures of dependencies (imports and other used classes) are known. ...
1answer
239 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 ...
1answer
61 views

### How an add vertex operation could be performed in constant time for a graph represented using adjacency list?

Adding a vertex in a graph that is represented using an adjacency list takes O(1) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency list > add vertex). It is said ...
1answer
264 views

### Does a tree node have an ancestor?

Below is a rooted tree, where any node C except root has one parent P Ancestors of a node C are the nodes on path from C to root, including P,P's parent,P's grandparent, .... till root. My ...
6answers
1k 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 ...
1answer
160 views

### Efficient algorithm for hierarchical traversing? JSON hydration, for example

I'm writing a small library that helps you hydrate JSON data into objects. Given this JSON example: { "date": "1970-01-01 00:00:00", "foobar": "baz", "user": { "name": "foobar", ...
2answers
385 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 (...
1answer
259 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 ...
4answers
147 views

### How definite of an order is there to a depth-first search of a graph?

I have the following graph that I need to simulate a depth-first search of; starting at g: My question is: How definite of an order is there when performing a depth-first search? When doing a DFS of ...
1answer
35 views

### How can I avoid needing to check for the existence another vertex when adding to an adjacency list?

I'm writing a Graph, and decided to make the Adjacency List its own class. Right now, (stripped down) it looks like this: public class AdjacencyList<Vertex> { //A map between a vertex, ...
2answers
295 views

### Big graph traversal with OOP

I'm trying to solve a algorithmic contest's problem. I have a matrix 2000x2000. I want to represent it as graph and traverse it with BFS/DFS. I have time limits on app running (2s). Simple vertices ...
2answers
315 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 ...
1answer
141 views

### Graphs and minimum spanning trees?

I am having a hard time finding information on how Graphs and spanning tree's work and how to construct/structure them. The reason is that I'm using a Delaunay Triangulation algorithm within the ...
1answer
242 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 ...