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

30
votes
7answers
6k 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
609 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
2k 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 ...
12
votes
3answers
5k 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
747 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 ...
9
votes
1answer
3k 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 ...
6
votes
3answers
1k 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
494 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
1k 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
2answers
135 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 ...
6
votes
1answer
127 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
156 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
4answers
1k 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 ...
5
votes
2answers
919 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
603 views

Nearest color algorithm using Hex Triplet

Following page list colors with names http://en.wikipedia.org/wiki/List_of_colors. For example #5D8AA8 Hex Triplet is "Air Force Blue". This information will be stored in a databse table (tbl_Color ...
5
votes
1answer
460 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
1answer
454 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
5answers
415 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 ...
5
votes
3answers
2k 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
420 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
3answers
340 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
2answers
97 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
1answer
828 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 ...
3
votes
2answers
230 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
2answers
256 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
377 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
2answers
889 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
1answer
199 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
1answer
241 views

Graph/diagram editor that works with pseudographics

Is there a graph/diagram editing tool that can output (or even better also parse) pseudographics, that can be easily inserted into source code comments? Like this: +---------------+ | ...
3
votes
2answers
183 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
160 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 ...
2
votes
3answers
669 views

How can you prove an acyclic graph has n-1 edges? [closed]

I'm not so hot on the maths for this but for what I understand... A graph g exists with v vertices and edges. g = (V,E); The spanning graph for this is an acyclic copy of this where all the vertices ...
2
votes
5answers
614 views

Programming language with native concurrency support for large graphs?

I'm currently looking for a new programming language to learn (currently working through some C++, know some C and Python), specifically one that has built-in concurrency support? I want to try to ...
2
votes
1answer
1k views

Networkx / Python : Is using a class for a node better practice than defining multiple attributes?

I've read through the NetworkX tutorial and documentation, but was unable to find real world answers for this question. Usually when using NetworkX, I might use strings to define nodes, then set ...
2
votes
2answers
271 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 ...
2
votes
2answers
284 views

Tool for large scale graph analysis

What are the best tools / frameworks / libraries available to implement and run algorithms on graphs? In particular I need a tool that can load a set of nodes, edges and values assigned to these ...
2
votes
1answer
101 views

Improving the running time of Breadth First Search and Adjacency List creation

We are given an array of integers where all elements are between 0-9. have to start from the 1st position and reach end in minimum no of moves such that we can from an index i move 1 position back and ...
2
votes
1answer
75 views

Maze generation given intersection tree

Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied ...
2
votes
1answer
189 views

Algorithm in undirected BFS graph

I'm trying to put together an algorithm that will display the node degree for every node in a breadth first tree graph (assume BFS was called). Assume it's an undirected graph. I'm not sure how to ...
2
votes
1answer
343 views

Finding subtree in a tree

I have a tree: a / \ b c / \ d f / \ g h And the pattern: x / \ y z / \ q p As output I would like to have: x: a y: b z: c q: d p: f and x: b y: f z: c q: ...
1
vote
2answers
901 views

Tree vs Graphs in search

Could anyone give a clear and concise explanation for when you use graphs vs when to use trees for data structures?
1
vote
3answers
147 views

Storing a drawn graph information in database for web application

Well while developing a web application that allow users to draw graphs (flow charts, ER diagram , UML, .... etc) the information of drawn items and their relation to each other and position on canvas ...
1
vote
1answer
283 views

Languages with graph data structures and algorithms in standard library

I am trying to improve my knowledge and ability with graphs and graph algorithms and have noticed something curious: as far as I can tell no "mainstream" language contains support for graphs in its ...
1
vote
1answer
36 views

Equidistant polygons

Consider these polygons: For reasons of simplicity I only consider triangles or polygons with 4 vertices. These shapes are specified by the vertices, the output of the program should be modified ...
1
vote
1answer
119 views

Question on Graph

I am trying to implement a graph data structure in C#. I have the following interfaces: public interface IVertex<TValue> { TValue Value { get;} ...
1
vote
1answer
214 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( ...
1
vote
1answer
120 views

How to canonise a road network

I am working on geographical data which represents the road network of some city and I need to automatically fix inaccuracies in the data. Data was manually produced by “drawing” the road network ...
1
vote
2answers
122 views

Algorithm for defragmenting cross-pipe issues in a network for routing signals through?

I have a network I'm responsible for routing signals through. You can think of the network as a directed graph of nodes (hardware) but each edge is really a pipe capable of fitting a specific ...
1
vote
1answer
85 views

How can I find all connections in a mesh network/graph?

Suppose I have a mesh of relationships, such as Friends who trust some friends and not others A IPv6 router that needs to locate peers across the Internet A PGP Web Of Trust that needs two people ...
1
vote
1answer
157 views

Implementing a sort of navigation system

So I am undertaking a project which does navigation sort of thing. So here is how the problem statement looks like. Say, given a map of a floor, with different rooms, now somehow, this information is ...