MATLAB Examples

# Manipulating digraphs with Vertex labels

## Contents

Many directed graph, or digraph, applications drop the vertex labels to focus on computations of the Adjacency Matrix, referring to the vertices only by their indices. The digraph class attempts to provide a convenient interface for those that require to know what the vertex actually represents.

This is a quick introduction to how to get started using digraph, but executing

help digraph


methods digraph


lists all valid functions that can be used with the digraph.

## Construct a new digraph

Start by creating a blank digraph object:

dg = digraph 
dg = digraph with properties: AdjMat: [] Vertex: {} NumVertices: 0 NumEdges: 0 

## Vertices

Add vertex labels to the digraph. The labels must be strings.

addVertex(dg,'A') addVertex(dg,'B') addVertex(dg,'C') addVertex(dg,'D') addVertex(dg,'E') addVertex(dg,'F') addVertex(dg,'G') addVertex(dg,'H') addVertex(dg,'I') addVertex(dg,'J') addVertex(dg,'K') 

## Edges

To represent an edge from A onto B, the syntax is predictably

addEdge(dg,'A','B') 

Add others one at a time:

addEdge(dg,'B','I') addEdge(dg,'C','D') addEdge(dg,'D','I') addEdge(dg,'I','E') addEdge(dg,'E','F') addEdge(dg,'I','F') addEdge(dg,'I','G') addEdge(dg,'G','H') addEdge(dg,'F','K') 

Now our digraph is something substantial:

dg 
dg = digraph with properties: AdjMat: [11x11 double] Vertex: {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K'} NumVertices: 11 NumEdges: 10 

The Adjacency Matrix, shortened to AdjMat, is a matrix representation of the edges. AdjMat(i, j) is true if and only if there is an edge from vertex i to vertex j.

Thus the following are equivalent, either using the succinct hasEdge function:

hasEdge(dg,'A','B') 
ans = 1 

Or by using Vertex indices to access the AdjMat directly:

[foundA,i] = hasVertex(dg,'A'); [foundB,j] = hasVertex(dg,'B'); if foundA && foundB % make sure they were each found edge = dg.AdjMat(i,j) end 
edge = (1,1) 1 

See assertVertex for a stricter version of hasVertex and removeVertex to learn more about accessing indices directly. Using the indices is a more advanced maneuver, to be used only when it is more convenient. The beauty of the digraph implementation is that you don't (and shouldn't!) have to track the corresponding index.

As gleened from the output above, the AdjMat is stored as a sparse matrix, whose display can be hard to read:

dg.AdjMat 
ans = (1,2) 1 (3,4) 1 (9,5) 1 (5,6) 1 (9,6) 1 (9,7) 1 (7,8) 1 (2,9) 1 (4,9) 1 (6,11) 1 

View it as a full matrix by using full. This is not advised for large matrices for the sake of memory.

full(dg.AdjMat) 
ans = 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

## Subgraphs

Create subgraphs of your digraph by specifying the vertices. This will return a new digraph:

subgraph(dg,{'C','D','G','H'}) 
ans = digraph with properties: AdjMat: [4x4 double] Vertex: {'C' 'D' 'G' 'H'} NumVertices: 4 NumEdges: 2 

## Finding Edges

Find all vertices that I directly (explicitly) points to:

findall(dg,'I',1) 
ans = 'E' 'F' 'G' 

and those that directly point to I:

findall(dg,'I',-1) 
ans = 'B' 'D' 

Find all vertices that I directly or indirectly (implicitly) points to:

findall(dg,'I',Inf) 
ans = 'E' 'F' 'G' 'H' 'K' 

and those that directly or indirectly point to I:

findall(dg,'I',-Inf) 
ans = 'A' 'B' 'C' 'D' 

Find all vertices that are at most 3 edges "ahead" of A:

findall(dg,'A',3) 
ans = 'B' 'E' 'F' 'G' 'I' 

findall will always return a sorted cell array.

## Finding Paths

See if two vertices are linked by an edge directly:

hasEdge(dg,'A','K') 
ans = 0 

or indirectly.

hasPath(dg,'A','K') 
ans = 1 

Find the shortest path from one to the other. This implements Dijkstra's algorithm.

shortestPath(dg,'A','K') 
ans = 'A' 'B' 'I' 'F' 'K' 

P = shortestPath(DG,SOURCE,TARGET) will return a sequential cell array P. If hasPath from SOURCE to TARGET returns false, then P will be empty, otherwise P will have a sequence of vertex names such that

SOURCE = P{1} P{2} P{end} = TARGET.

If SOURCE and TARGET are the same, hasPath will always return true and shortestPath will have exactly one element.

## Union, Intersect, and Copy

Combine and copy entire digraphs:

c = copy(dg) 
c = digraph with properties: AdjMat: [11x11 double] Vertex: {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K'} NumVertices: 11 NumEdges: 10 

This makes a "deep" copy, such that dg and c are completely independent:

addVertex(c,'foo') hasVertex(c,'foo') % c should contain "foo" hasVertex(dg,'foo') % dg should NOT contain "foo" 
ans = 1 ans = 0 

Taking the union of dg and c will use the union of the vertices and the edges available in either digraph:

union(dg,c) 
ans = digraph with properties: AdjMat: [12x12 double] Vertex: {1x12 cell} NumVertices: 12 NumEdges: 10 

Taking the intersect of dg and c will use the intersect of the vertices and the edges between them that are found in both digraphs:

intersect(dg,c) 
ans = digraph with properties: AdjMat: [11x11 double] Vertex: {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K'} NumVertices: 11 NumEdges: 10 

## Transitive Closure

The transitive closure of a digraph makes all implicit edges explicit. In other words, if you have that A B C, then C is in A's transitive closure. The transitiveClosure function will create a new digraph with an additional edge from A onto C.

Here, notice how NumEdges grows to 35:

tc = transitiveClosure(dg) 
tc = digraph with properties: AdjMat: [11x11 double] Vertex: {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K'} NumVertices: 11 NumEdges: 35 

The original digraph will be a subset of its transitive closure:

isEquivalent(tc, union(dg,tc)) 
ans = 1 
isEquivalent(dg, intersect(dg,tc)) 
ans = 1 

## Minimal Edges

This is in a sense the converse of transitiveClosure. If you have that A B C and A C, then the edge from A onto C is redundant since there is already an indirect edge through B. The minimalEdges function will create a new digraph that has the edge from A onto C removed.

Here, notice how NumEdges shrinks to 9:

me = minimalEdges(dg) 
me = digraph with properties: AdjMat: [11x11 double] Vertex: {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K'} NumVertices: 11 NumEdges: 9 

This will (conversely to the transitive closure) be a subset of the original:

isEquivalent(dg, union(dg,me)) 
ans = 1 
isEquivalent(me, intersect(dg,me)) 
ans = 1