Stack Overflow
Stack Overflow

Questions tagged [directed-graph]

A directed graph is a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph or a directed network.

A directed graph (or digraph) is a , or set of nodes connected by edges, where the edges have a direction associated with them

686 questions
451
votes
14 answers

Best algorithm for detecting cycles in a directed graph

Is there an efficient algorithm for detecting cycles within a directed graph? I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a dependency being an edge. I need to detect the error case of a…
Peauters
  • 4,773
  • 3
  • 18
  • 11
226
votes
4 answers

GraphViz - How to connect subgraphs?

In the DOT language for GraphViz, I'm trying to represent a dependency diagram. I need to be able to have nodes inside a container and to be able to make nodes and/or containers dependent on other nodes and/or containers. I'm using subgraph to…
Winston Smith
  • 21,585
  • 10
  • 60
  • 75
157
votes
6 answers

how to draw directed graphs using networkx in python?

I have some nodes coming from a script that I want to map on to a graph. In the below, I want to use Arrow to go from A to D and probably have the edge colored too in (red or something). This is basically, like a path from A to D when all other…
brain storm
  • 30,124
  • 69
  • 225
  • 393
90
votes
12 answers

How do I check if a directed graph is acyclic?

How do I check if a directed graph is acyclic? And how is the algorithm called? I would appreciate a reference.
nes1983
  • 15,209
  • 4
  • 44
  • 64
46
votes
4 answers

Graph serialization

I'm looking for a simple algorithm to 'serialize' a directed graph. In particular I've got a set of files with interdependencies on their execution order, and I want to find the correct order at compile time. I know it must be a fairly common thing…
Kieron
  • 11,588
  • 5
  • 34
  • 29
40
votes
5 answers

How to detect if adding an edge to a directed graph results in a cycle?

I came upon wait-for graphs and I wonder, are there any efficient algorithms for detecting if adding an edge to a directed graph results in a cycle? The graphs in question are mutable (they can have nodes and edges added or removed). And we're not…
Petr
  • 62,528
  • 13
  • 153
  • 317
39
votes
1 answer

Getting the root (head) of a DiGraph in networkx (Python)

I'm trying to use networkx to do some graph representation in a project, and I'm not sure how to do a few things that should be simple. I created a directed graph with a bunch of nodes and edges, such that there is only one root element in this…
mindthief
  • 12,755
  • 14
  • 57
  • 61
33
votes
3 answers

Tarjan cycle detection help C#

Here is a working C# implementation of tarjan's cycle detection. The algorithm is found here: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm public class TarjanCycleDetect { private static…
user623879
  • 4,066
  • 9
  • 38
  • 53
32
votes
14 answers

What options are available for the layout of directed or undirected graphs in .NET?

By graph here I mean something resembling these images: The ideal solution would: use only managed code allow output to a bitmap image allow output to WPF elements include some kind of interactive surface for displaying the graph that supports…
Drew Noakes
  • 300,895
  • 165
  • 679
  • 742
29
votes
3 answers

Finding separate graphs within a graph object in networkx

I have an enormous graph dataset - let's say it is like this, but on a much bigger level: 1 -> 2 3 -> 4 1,2,3,4 are nodes and the arrows are directed edges. Let's say that they are all in a single graph object: import networkx as nx G =…
LittleBobbyTables
  • 4,361
  • 9
  • 38
  • 67
28
votes
1 answer

Graphviz Dot Algorithm

Is there any documentation (full pseudo code?) on the algorithm from dot within the Graphviz Library? I only found some partial pseudo code documentation.
RaphaelH
  • 2,144
  • 2
  • 30
  • 43
27
votes
6 answers

How to detect if a directed graph is cyclic?

How can we detect if a directed graph is cyclic? I thought using breadth first search, but I'm not sure. Any ideas?
iva123
  • 3,395
  • 10
  • 47
  • 68
26
votes
5 answers

Are Trees Directed or Undirected Graphs?

I have read that Trees are special cases of Graphs. Graphs can be directed or undirected. But if we consider tree as a data structure is it directed or undirected graph?
Faizan
  • 1,847
  • 8
  • 40
  • 63
23
votes
7 answers

Implementing a node-based graphical interface?

I would like to implement a nodal-interface, basically a DAG where each node performs an operation on it's input connections, and outputs something (which you can connect to another node) Some example applications: Apples "Shake" - screenshot The…
dbr
  • 165,801
  • 69
  • 278
  • 343
23
votes
5 answers

Most elegant way to find node's predecessors with networkX

I'm working on a graphical model project with python using NetworkX. NetworkX provides simple and good functionality using dictionaries: import networkx as nx G = nx.DiGraph() # a directed graph G.add_edge('a', 'b') print G['a'] # prints {'b':…
user
  • 7,123
  • 7
  • 48
  • 90
1
2 3
…
45 46