# Tagged Questions

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

20 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 ...
115 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 ...
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 ...
93 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 ...
342 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 ...
181 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 ...
50 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 ...
211 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 ...
73 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, ...
137 views

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 -> ...
76 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 ...
224 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 ...
145 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 ...
832 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 ...
65 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)....
52 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 ...
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? ...
42 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 ...
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 ...
77 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> ...
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 ...
84 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 ...
303 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 ...
344 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. ...
45 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 ...
131 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....
465 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 ...
155 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, ...
247 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-...
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 ...
89 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,...
41 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 ...
934 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,...
297 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. ...
220 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 ...
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 ...
255 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 ...
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 ...
154 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", ...
360 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 (...
247 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 ...
128 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 ...
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, ...
288 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 ...
305 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 ...
135 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 ...
232 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 ...
187 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 ...