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
  
  ---------------------------  Example  ----------------------------
    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
  
  ---------------------------  Example  ----------------------------
    gap> G:=RandomDiGraph(4);
    [ [ 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
  
  ---------------------------  Example  ----------------------------
    gap> G:=RandomDiGraph(4);
    [ [ 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
  
  ---------------------------  Example  ----------------------------
    gap> G:=RandomDiGraph(4);
    [ [ 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.
  
  ---------------------------  Example  ----------------------------
    gap> G:=RandomDiGraph(4);
    [ [  ], [ 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
  
  ---------------------------  Example  ----------------------------
    gap> G:=RandomDiGraph(6);
    [ [  ], [ 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.
  
  ---------------------------  Example  ----------------------------
    gap> G:=RandomDiGraph(6);
    [ [  ], [ 4 ], [  ], [ 4, 6 ], [  ], [ 1, 4, 5, 6 ] ]
    gap> GraphStronglyConnectedComponents(G);
    [ [ 1 ], [ 2 ], [ 3 ], [ 4, 6 ], [ 5 ] ]
  ------------------------------------------------------------------
  
  A.1-8 UnderlyingMultiGraphOfAutomaton
  
  > UnderlyingMultiGraphOfAutomaton( A ) _____________________________function
  
  A is an automaton. The output is the underlying directed multi-graph.
  
  ---------------------------  Example  ----------------------------
    gap> a:=RandomAutomaton("det",3,2);;Display(a);
       |  1  2  3
    --------------
     a |  1  3
     b |     2  3
    Initial state:    [ 1 ]
    Accepting states: [ 1, 2 ]
    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.
  
  ---------------------------  Example  ----------------------------
    gap> a:=RandomAutomaton("det",3,2);;Display(a);
       |  1  2  3
    --------------
     a |     1  2
     b |  1  2
    Initial state:   [ 2 ]
    Accepting state: [ 2 ]
    gap> UnderlyingGraphOfAutomaton(a);
    [ [ 1 ], [ 1, 2 ], [ 2 ] ]
  ------------------------------------------------------------------
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> G:=RandomDiGraph(4);
    [ [  ], [  ], [ 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.
  
  ---------------------------  Example  ----------------------------
    gap> a:=RandomAutomaton("det",3,2);;Display(a);
       |  1  2  3
    --------------
     a |  1  3
     b |  2  3
    Initial state:    [ 1 ]
    Accepting states: [ 1, 2, 3 ]
    gap> MSccAutomaton(a);
    < deterministic automaton on 4 letters with 3 states >
    gap> Display(last);
       |  1  2  3
    --------------
     a |  1  3
     b |  2  3
     A |  1
     B |
    Initial state:    [ 1 ]
    Accepting states: [ 1, 2, 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.
  
  ---------------------------  Example  ----------------------------
    gap> RandomDiGraph(3);
    [ [  ], [ 3 ], [ 2 ] ]
    gap> AutoIsAcyclicGraph(last);
    false
  ------------------------------------------------------------------