Directed Graphs

Directed Graphs

The SimpleGraphs module contains modest support for directed graphs. A DirectedGraph (or DG) contains directed edges. There can be at most one edge from a vertex v to a vertex w; it is possible for there to be a pair of antiparallel edges between two vertices. By default a DirectedGraph may have loops, but at most one loop per vertex.

This page gives an overview of the functions for dealing with directed graphs. One may also look in the src directory at files that begin d_ for additional insights.

A directed graph can be converted to an ordinary simple graph like this: G = simplify(D). The vertices of G are the same as those in D. There is an edges between two vertices of G if there is either directed edge is present between them in D. Loops are not carried over to G.

Vertices and edges

Create a new directed graph by D = DirectedGraph() or D = DirectedGraph{T}() where T is the vertex type (defaults to Any). Special cases of this include IntDigraph() (Int vertices) and StringDigraph() (String vertices).

Vertices may be added with add!(D,v) and directed edges added with add!(D,v,w). Conversely, vertices/edges may be deleted with delete!.

Lists of the vertices and edges are returned by vlist(D) and elist(D) respectively. NV(D) and NE(G) return the number of vertices and edges, respectively.

Loops are permitted by default and add!(D,v,v) will place a loop at vertex v. The following functions are provided for dealing with loops:

• is_looped(D) returns true if D permits loops.
• allow_loops!(D) enables D to have loops.
• forbid_loops!(D) disables the ability of D to have loops (and removes any loops it may have).
• loops(D) returns a list of loops (if any) as a list of the vertices where a loop is present.
• remove_loops!(D) removes all loops from D.

Neighbors and degrees

For a vertex v of a digraph D we have the following:

• in_neighbors(D,v) is a list of vertices that have a directed edge pointing into v.
• out_neighbors(D,v) is a list of vertices that have a directed edge emanating from `v.
• in_deg(D,v) is the in-degree of v.
• out_deg(D,v) is the out-degree of v.
• dual_deg(D,v) is a 2-tuple of the in- and out-degrees.
• deg(D,v) is the sum of the in- and out-degrees of v.

Standard digraphs

• DirectedPath(n) creates an n-vertex directed path.
• DirectedCycle(n) creates an n-vertex directed cycle.
• DirectedComplete(n) creates an n vertex graph with all possible edges (including loops). To prevent the inclusion of loops, use DirectedComplete(n,false).
• RandomDigraph(n,p) creates an Erdos-Renyi style random digraph with no loops (with p=0.5 by default). Use RandomDigraph(n,p,true) to allow the creation of loops (each with probability p).
• RandomTournament(n) creates a random digraph with n vertices and n*(n-1)/2 edges. For distinct vertices u and v, the edge is (u,v) of (v,u), each with probability 1/2.
• TorusDigraph(n,m) creates an n-by-m torus digraph (Cartesian product of a directed n-cycle with a directed m-cycle).

Connection

• find_path(D,u,v) finds a shortest directed path from u to v.
• is_strongly_connected(D) determines if D is strongly connected.
• diam(D) returns the diameter of D (maximum distance between vertices).

Matrices

• adjacency(D) returns the adjacency matrix.
• incidence(D) returns the (signed) incidence matrix.
• dist_matrix(D) returns a matrix of the inter-vertex directed distances.

Euler/Hamiltonian

• euler(D,u,v) returns a directed Euler trail in D starting at u and ending at v.
• euler(D) returns a directed Euler tour of D.
• hamiltonian_cycle(D) returns a Hamiltonian cycle of D.