Goto Chapter: Top 1 2 3 4 5 6 A B C Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

A Directed graphs
 A.1 Directed graphs

A Directed graphs

Automata are frequently described through directed labeled graphs. This appendix on directed graphs (digraphs) is devoted to some functions designed with the purpose of being used as auxiliary functions to deal with automata, but may have independent interest.

A.1 Directed graphs

A directed graph with \(n\) vertices is represented by an adjacency list. For example, the list G = [[2,4],[3],[1,4],[]] represents a directed graph with 4 (= Length(G)) vertices; the sublist in position i is the list of endpoints of the edges beginning in vertex \(i\).


A.1-1 RandomDiGraph
‣ RandomDiGraph( n )( function )

Produces a pseudo random digraph with \(n\) vertices

gap> RandomDiGraph(4);
[ [  ], [ 1, 2, 4 ], [  ], [  ] ]

A.1-2 VertexInDegree
‣ VertexInDegree( DG, v )( function )

Computes the in degree of the vertex v of the directed graph DG

gap> G:= [ [ 1 ], [ 1, 2, 4 ], [  ], [ 1, 2, 3 ] ];;
gap> VertexInDegree(G,2);
2

A.1-3 VertexOutDegree
‣ VertexOutDegree( DG, v )( function )

Computes the out degree of the vertex v of the directed graph DG

gap> G:=[ [ 1 ], [ 1, 2, 4 ], [  ], [ 1, 2, 3 ] ];;
gap> VertexOutDegree(G,2);
3

A.1-4 AutoVertexDegree
‣ AutoVertexDegree( DG, v )( function )

Computes the degree of the vertex v of the directed graph DG

gap> G:=[ [ 1 ], [ 1, 2, 4 ], [  ], [ 1, 2, 3 ] ];;
gap> AutoVertexDegree(G,2);
5

A.1-5 ReversedGraph
‣ ReversedGraph( G )( function )

Computes the reversed graph of the directed graph G. It is the graph obtained from G by reversing the edges.

gap> G:=[ [  ], [ 4 ], [ 2 ], [ 1, 4 ] ];;
gap> ReversedGraph(G);
[ [ 4 ], [ 3 ], [  ], [ 2, 4 ] ]

We say that a digraph is connected when for every pair of vertices there is a path consisting of directed or reversed edges from one vertex to the other.

A.1-6 AutoConnectedComponents
‣ AutoConnectedComponents( G )( function )

Computes a list of the connected components of the digraph

gap> G:=[ [  ], [ 1, 4, 5, 6 ], [  ], [ 1, 3, 5, 6 ], [ 2, 3 ], [ 2, 4, 6 ] ];;
gap> AutoConnectedComponents(G);
[ [ 1, 2, 3, 4, 5, 6 ] ]

Two vertices of a digraph belong to a strongly connected component if there is a directed path from each one to the other.

A.1-7 GraphStronglyConnectedComponents
‣ GraphStronglyConnectedComponents( G )( function )

Produces the strongly connected components of the digraph G.

gap> G:=[ [  ], [ 4 ], [  ], [ 4, 6 ], [  ], [ 1, 4, 5, 6 ] ];;
gap> Set(GraphStronglyConnectedComponents(G));
[ [ 1 ], [ 2 ], [ 3 ], [ 5 ], [ 6, 4 ] ]

A.1-8 UnderlyingMultiGraphOfAutomaton
‣ UnderlyingMultiGraphOfAutomaton( A )( function )

A is an automaton. The output is the underlying directed multi-graph.

gap> a := Automaton("det",3,"ab",[ [ 0, 3, 0 ], [ 1, 2, 3 ] ],[ 1 ],[ 1 ]);;
gap> Display(a);
   |  1  2  3  
--------------
 a |     3     
 b |  1  2  3  
Initial state:   [ 1 ]
Accepting state: [ 1 ]
gap> UnderlyingMultiGraphOfAutomaton(a);
[ [ 1 ], [ 3, 2 ], [ 3 ] ]

A.1-9 UnderlyingGraphOfAutomaton
‣ UnderlyingGraphOfAutomaton( A )( function )

A is an automaton. The output is the underlying directed graph.

gap> a := Automaton("det",3,"ab",[ [ 2, 3, 0 ], [ 0, 1, 3 ] ],[ 2 ],[ 1, 2, 3 ]);;
gap> Display(a);
   |  1  2  3  
--------------
 a |  2  3     
 b |     1  3  
Initial state:    [ 2 ]
Accepting states: [ 1, 2, 3 ]
gap> UnderlyingGraphOfAutomaton(a);
[ [ 2 ], [ 1, 3 ], [ 3 ] ]

A.1-10 DiGraphToRelation
‣ DiGraphToRelation( D )( function )

Returns the relation corresponding to the digraph. Note that a directed graph may be seen in a natural way as a binary relation on the set of vertices.

gap> G:=[ [  ], [  ], [ 4 ], [ 4 ] ];;
gap> DiGraphToRelation(G);
[ [ 3, 4 ], [ 4, 4 ] ]

A.1-11 MSccAutomaton
‣ MSccAutomaton( A )( function )

Produces an automaton where, in each strongly connected component, edges labeled by inverses are added. (M stands for modified.)

This construction is useful in Finite Semigroup Theory.

gap> a := Automaton("det",3,"ab",[ [ 0, 2, 0 ], [ 1, 2, 0 ] ],[ 3 ],[ 1, 3 ]);;
gap> Display(a);
   |  1  2  3  
--------------
 a |     2     
 b |  1  2     
Initial state:    [ 3 ]
Accepting states: [ 1, 3 ]
gap> MSccAutomaton(a);
< deterministic automaton on 4 letters with 3 states >
gap> Display(last);
   |  1  2  3  
--------------
 a |     2     
 b |  1  2     
 A |     2     
 B |  1  2     
Initial state:    [ 3 ]
Accepting states: [ 1, 3 ]

A.1-12 AutoIsAcyclicGraph
‣ AutoIsAcyclicGraph( G )( function )

The argument is a graph's list of adjacencies and this function returns true if the argument is an acyclic graph and false otherwise.

gap> G := [ [  ], [ 3 ], [ 2 ] ];;
gap> AutoIsAcyclicGraph(last);
false
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 A B C Bib Ind

generated by GAPDoc2HTML