[1XA Directed graphs[0X 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. [1XA.1 Directed graphs[0X A directed graph with n vertices is represented by an adjacency list. For example, the list [10XG = [[2,4],[3],[1,4],[]][0m represents a directed graph with [10X4 (= Length(G))[0m vertices; the sublist in position [10Xi[0m is the list of endpoints of the edges beginning in vertex i. [1XA.1-1 RandomDiGraph[0m [2X> RandomDiGraph( [0X[3Xn[0X[2X ) _______________________________________________[0Xfunction Produces a pseudo random digraph with n vertices [4X--------------------------- Example ----------------------------[0X [4Xgap> RandomDiGraph(4);[0X [4X[ [ ], [ 1, 2, 4 ], [ ], [ ] ][0X [4X------------------------------------------------------------------[0X [1XA.1-2 VertexInDegree[0m [2X> VertexInDegree( [0X[3XDG, v[0X[2X ) __________________________________________[0Xfunction Computes the in degree of the vertex [3Xv[0m of the directed graph [3XDG[0m [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=RandomDiGraph(4);[0X [4X[ [ 1 ], [ 1, 2, 4 ], [ ], [ 1, 2, 3 ] ][0X [4Xgap> VertexInDegree(G,2);[0X [4X2[0X [4X------------------------------------------------------------------[0X [1XA.1-3 VertexOutDegree[0m [2X> VertexOutDegree( [0X[3XDG, v[0X[2X ) _________________________________________[0Xfunction Computes the out degree of the vertex [3Xv[0m of the directed graph [3XDG[0m [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=RandomDiGraph(4);[0X [4X[ [ 1 ], [ 1, 2, 4 ], [ ], [ 1, 2, 3 ] ][0X [4Xgap> VertexOutDegree(G,2);[0X [4X3[0X [4X------------------------------------------------------------------[0X [1XA.1-4 AutoVertexDegree[0m [2X> AutoVertexDegree( [0X[3XDG, v[0X[2X ) ________________________________________[0Xfunction Computes the degree of the vertex [3Xv[0m of the directed graph [3XDG[0m [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=RandomDiGraph(4);[0X [4X[ [ 1 ], [ 1, 2, 4 ], [ ], [ 1, 2, 3 ] ][0X [4Xgap> AutoVertexDegree(G,2);[0X [4X5[0X [4X------------------------------------------------------------------[0X [1XA.1-5 ReversedGraph[0m [2X> ReversedGraph( [0X[3XG[0X[2X ) _______________________________________________[0Xfunction Computes the reversed graph of the directed graph G. It is the graph obtained from G by reversing the edges. [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=RandomDiGraph(4);[0X [4X[ [ ], [ 4 ], [ 2 ], [ 1, 4 ] ][0X [4Xgap> ReversedGraph(G);[0X [4X[ [ 4 ], [ 3 ], [ ], [ 2, 4 ] ][0X [4X------------------------------------------------------------------[0X 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. [1XA.1-6 AutoConnectedComponents[0m [2X> AutoConnectedComponents( [0X[3XG[0X[2X ) _____________________________________[0Xfunction Computes a list of the connected components of the digraph [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=RandomDiGraph(6);[0X [4X[ [ ], [ 1, 4, 5, 6 ], [ ], [ 1, 3, 5, 6 ], [ 2, 3 ], [ 2, 4, 6 ] ][0X [4Xgap> AutoConnectedComponents(G);[0X [4X[ [ 1, 2, 3, 4, 5, 6 ] ][0X [4X------------------------------------------------------------------[0X Two vertices of a digraph belong to a strongly connected component if there is a directed path from each one to the other. [1XA.1-7 GraphStronglyConnectedComponents[0m [2X> GraphStronglyConnectedComponents( [0X[3XG[0X[2X ) ____________________________[0Xfunction Produces the strongly connected components of the digraph [3XG[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=RandomDiGraph(6);[0X [4X[ [ ], [ 4 ], [ ], [ 4, 6 ], [ ], [ 1, 4, 5, 6 ] ][0X [4Xgap> GraphStronglyConnectedComponents(G);[0X [4X[ [ 1 ], [ 2 ], [ 3 ], [ 4, 6 ], [ 5 ] ][0X [4X------------------------------------------------------------------[0X [1XA.1-8 UnderlyingMultiGraphOfAutomaton[0m [2X> UnderlyingMultiGraphOfAutomaton( [0X[3XA[0X[2X ) _____________________________[0Xfunction [3XA[0m is an automaton. The output is the underlying directed multi-graph. [4X--------------------------- Example ----------------------------[0X [4Xgap> a:=RandomAutomaton("det",3,2);;Display(a);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 3[0X [4X b | 2 3[0X [4XInitial state: [ 1 ][0X [4XAccepting states: [ 1, 2 ][0X [4Xgap> UnderlyingMultiGraphOfAutomaton(a);[0X [4X[ [ 1 ], [ 3, 2 ], [ 3 ] ][0X [4X------------------------------------------------------------------[0X [1XA.1-9 UnderlyingGraphOfAutomaton[0m [2X> UnderlyingGraphOfAutomaton( [0X[3XA[0X[2X ) __________________________________[0Xfunction [3XA[0m is an automaton. The output is the underlying directed graph. [4X--------------------------- Example ----------------------------[0X [4Xgap> a:=RandomAutomaton("det",3,2);;Display(a);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 2[0X [4X b | 1 2[0X [4XInitial state: [ 2 ][0X [4XAccepting state: [ 2 ][0X [4Xgap> UnderlyingGraphOfAutomaton(a);[0X [4X[ [ 1 ], [ 1, 2 ], [ 2 ] ][0X [4X------------------------------------------------------------------[0X [1XA.1-10 DiGraphToRelation[0m [2X> DiGraphToRelation( [0X[3XD[0X[2X ) ___________________________________________[0Xfunction 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. [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=RandomDiGraph(4);[0X [4X[ [ ], [ ], [ 4 ], [ 4 ] ][0X [4Xgap> DiGraphToRelation(G);[0X [4X[ [ 3, 4 ], [ 4, 4 ] ][0X [4X------------------------------------------------------------------[0X [1XA.1-11 MSccAutomaton[0m [2X> MSccAutomaton( [0X[3XA[0X[2X ) _______________________________________________[0Xfunction 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. [4X--------------------------- Example ----------------------------[0X [4Xgap> a:=RandomAutomaton("det",3,2);;Display(a);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 3[0X [4X b | 2 3[0X [4XInitial state: [ 1 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4Xgap> MSccAutomaton(a);[0X [4X< deterministic automaton on 4 letters with 3 states >[0X [4Xgap> Display(last);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 3[0X [4X b | 2 3[0X [4X A | 1[0X [4X B |[0X [4XInitial state: [ 1 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4X------------------------------------------------------------------[0X [1XA.1-12 AutoIsAcyclicGraph[0m [2X> AutoIsAcyclicGraph( [0X[3XG[0X[2X ) __________________________________________[0Xfunction The argument is a graph's list of adjacencies and this function returns true if the argument is an acyclic graph and false otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> RandomDiGraph(3);[0X [4X[ [ ], [ 3 ], [ 2 ] ][0X [4Xgap> AutoIsAcyclicGraph(last);[0X [4Xfalse[0X [4X------------------------------------------------------------------[0X