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 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\).
‣ RandomDiGraph( n ) | ( function ) |
Produces a pseudo random digraph with \(n\) vertices
gap> RandomDiGraph(4); [ [ ], [ 1, 2, 4 ], [ ], [ ] ]
‣ 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
‣ 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
‣ 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
‣ 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.
‣ 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.
‣ 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 ] ]
‣ 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 ] ]
‣ 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 ] ]
‣ 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 ] ]
‣ 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 ]
‣ 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
generated by GAPDoc2HTML