  
  [1X1 [33X[0;0YNauty Graphs[133X[101X
  
  
  [1X1.1 [33X[0;0YWorking with Nauty Graphs[133X[101X
  
  [1X1.1-1 NautyGraph[101X
  
  [33X[1;0Y[29X[2XNautyGraph[102X( [3Xedges[103X, [3Xnr[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyGraph[102X( [3Xarg1[103X, [3Xarg2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XNautyGraph[109X[133X
  
  [33X[0;0YThis  function  creates a nauty graph object for an undirected graph without
  multiple  edges,  but possibly with loops, whose edges are given by the list
  [3Xedges[103X.  The  list  [3Xedges[103X  is  a  list  whose  entries are lists of length 2,
  consisting  of  the two (possibly equal) vertices of the edges. If two edges
  are either equal or one is the reversed of the other, the graph created will
  still  only  have  a  single  undirected  edge.  The graph created is on the
  vertices  [3X1,  .., nr, [103X where [3Xnr[103X is the maximal entry occurring in one of the
  edges. If the function is called with a second argument [3Xnr[103X then [3Xnr[103X must be a
  positive  integer  which is at least equal to the maximal entry occurring in
  one of the edges.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng := NautyGraph( [ [1,2], [2,3], [3,4], [4,1], [3,2] ] );[127X[104X
    [4X[28X<An undirected Nauty graph with on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27X    [127X[104X
    [4X[28X[ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 1 ], [ 3, 2 ] ][128X[104X
  [4X[32X[104X
  
  [1X1.1-2 NautyDiGraph[101X
  
  [33X[1;0Y[29X[2XNautyDiGraph[102X( [3Xedges[103X, [3Xnr[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyDiGraph[102X( [3Xarg1[103X, [3Xarg2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XNautyGraph[109X[133X
  
  [33X[0;0YThis  function  creates  a  nauty  graph object for a directed graph without
  multiple  edges,  but possibly with loops, whose edges are given by the list
  [3Xedges[103X.  The  list  [3Xedges[103X  is  a  list  whose  entries are lists of length 2,
  consisting  of  the two (possibly equal) vertices of the edges. If two edges
  are equal the graph created will still only have a single directed edge. The
  graph  created  is on the vertices [3X1, .., nr, [103X where [3Xnr[103X is the maximal entry
  occurring  in  one  of  the  edges.  If the function is called with a second
  argument  [3Xnr[103X  then  [3Xnr[103X must be a positive integer which is at least equal to
  the maximal entry occurring in one of the edges.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xnautygraph := NautyDiGraph( [ [1,2],[2,3],[3,4], [4,1] ] );[127X[104X
    [4X[28X<A directed Nauty graph on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(nautygraph);[127X[104X
    [4X[28XGroup([ (1,2,3,4) ])[128X[104X
  [4X[32X[104X
  
  [1X1.1-3 NautyColoredGraph[101X
  
  [33X[1;0Y[29X[2XNautyColoredGraph[102X( [3Xedges[103X, [3Xcolours[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XNautyGraph[109X[133X
  
  [33X[0;0YThis function creates a nauty graph object for an undirected vertex coloured
  graph without multiple edges, but possibly with loops, whose edges are given
  by  the  list  [3Xedges[103X.  The  list  [3Xedges[103X is a list whose entries are lists of
  length  2,  consisting of the two (possibly equal) vertices of the edges. If
  two  edges  are equal or reversed to each other the graph created will still
  only  have a single undirected edge. The graph created is on the vertices [3X1,
  ..,  nr,  [103X  where [3Xnr[103X is the maximal entry occurring in one of the edges. The
  list  [3Xcolours[103X  must  be  a  list  of  length  [3Xnr[103X  whose entries are positive
  integers. The vertex [3Xi[103X has colour [3Xcolours[i][103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xnautygraph := NautyColoredGraph( [ [1,2],[2,3],[3,4], [4,1] ], [1,2,1,2] );[127X[104X
    [4X[28X<An  undirected vertex-coloured Nauty graph on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(nautygraph);[127X[104X
    [4X[28XGroup([ (2,4), (1,3) ])[128X[104X
  [4X[32X[104X
  
  [33X[0;0YDeclareSynonym( "NautyColouredGraph", NautyColoredGraph );[133X
  
  [1X1.1-4 NautyColoredDiGraph[101X
  
  [33X[1;0Y[29X[2XNautyColoredDiGraph[102X( [3Xedges[103X, [3Xcolours[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XNautyGraph[109X[133X
  
  [33X[0;0YThis function creates a nauty graph object for an undirected vertex coloured
  graph without multiple edges, but possibly with loops, whose edges are given
  by  the  list  [3Xedges[103X.  The  list  [3Xedges[103X is a list whose entries are lists of
  length  2,  consisting of the two (possibly equal) vertices of the edges. If
  two  edges  are equal or reversed to each other the graph created will still
  only  have a single undirected edge. The graph created is on the vertices [3X1,
  ..,  nr,  [103X  where [3Xnr[103X is the maximal entry occurring in one of the edges. The
  list  [3Xcolours[103X  must  be  a  list  of  length  [3Xnr[103X  whose entries are positive
  integers. The vertex [3Xi[103X has colour [3Xcolours[i][103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xnautygraph := NautyColoredGraph( [ [1,2],[2,3],[3,4], [4,1] ], [1,2,1,2] );[127X[104X
    [4X[28X<An  undirected vertex-coloured Nauty graph on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(nautygraph);[127X[104X
    [4X[28XGroup([ (2,4), (1,3) ])[128X[104X
  [4X[32X[104X
  
  [33X[0;0YDeclareSynonym( "NautyColouredDiGraph", NautyColoredDiGraph );[133X
  
  [1X1.1-5 NautyEdgeColoredGraph[101X
  
  [33X[1;0Y[29X[2XNautyEdgeColoredGraph[102X( [3Xedgeclasses[103X, [3Xcolours[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyEdgeColoredGraph[102X( [3Xarg1[103X, [3Xarg2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyEdgeColoredDiGraph[102X( [3Xarg[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyEdgeColoredDiGraph[102X( [3Xarg1[103X, [3Xarg2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XNautyGraph[109X[133X
  
  [33X[0;0YThis  function  creates a nauty graph object for an undirected edge coloured
  graph  without  multiple  edges,  but  possibly with loops. The edges of the
  graph are specified in the argument [3Xedgeclasses[103X as follows. [3Xedgeclasses[103X is a
  list  of lists [22XL_i[122X, where each list [22XL_i[122X is a list of edges, that is [22XL_i[122X is a
  list  a  list  whose  entries  are  lists of length 2, consisting of the two
  (possibly  equal)  vertices of the edges. If two edges are equal or reversed
  to  each  other  the  graph created will still only have a single undirected
  edge.  The  graph  created  is  on  the vertices [3X1, .., nr, [103X where [3Xnr[103X is the
  maximal  entry  occurring in one of the edges. The edges in the [22Xi[122Xth list [22XL_i[122X
  have colour [22Xi[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xnautygraph := NautyEdgeColoredGraph( [ [[1,2],[2,3]],[[3,4], [4,1]]]);[127X[104X
    [4X[28X<An undirected edge-coloured Nauty graph on 4 vertices and 2 edge colours>[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(nautygraph);[127X[104X
    [4X[28XGroup([ (1,3) ])[128X[104X
  [4X[32X[104X
  
  [33X[0;0YDeclareSynonym(     "NautyEdgeColouredGraph",    NautyEdgeColoredGraph    );
  DeclareSynonym( "NautyEdgeColouredDiGraph", NautyEdgeColoredDiGraph );[133X
  
  [1X1.1-6 AutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XAutomorphismGroup[102X( [3Xgraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya [9Xpermutation group[109X[133X
  
  [33X[0;0YGiven a simple (di)graph [3Xgraph[103X which is a [3Xnauty graph[103X object (see [14X1.1[114X), this
  function  computes the automorphism group of [3Xgraph[103X as a permutation group on
  the nodes of [3Xgraph[103X. As [3Xgraph[103X is a simple graph, its edges are given as lists
  [22X[i,j][122X  of length 2 consisting of a pair of nodes in the set [22XN[122X. If an edge is
  a loop, it is of the form [22X[i,i][122X. If [22Xi,j[122X are different nodes and the graph is
  undirected,  [22X[i,j][122X  and [22X[j,i][122X refer to the same edge, and to different edges
  when  the  graph  is  directed.  A bijection [22Xϕ[122X from [22XN[122X to itself is called an
  [3Xautomorphism[103X  of  the  (undirected)  graph [3Xgraph[103X if [22Xϕ[122X maps edges of [3Xgraph[103X to
  edges  of  [3Xgraph[103X,  that  is  [22Xe=[i,j][122X  is  an  edge  of  [3Xgraph[103X if and only if
  [22Xe=[i^ϕ,j^ϕ][122X  or, in the undirected case, [22Xe=[j^ϕ,i^ϕ][122X is an edge of [3Xgraph[103X. If
  The [3Xautomorphism group[103X of [3Xgraph[103X is returned as a permutation group acting on
  the set [22XN[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xnautygraph := NautyGraph( [ [1,2],[2,3],[3,4], [4,1] ] );[127X[104X
    [4X[28X<An undirected Nauty graph with on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(nautygraph);[127X[104X
    [4X[28XGroup([ (2,4), (1,2)(3,4) ])[128X[104X
  [4X[32X[104X
  
  [1X1.1-7 EdgesOfNautyGraph[101X
  
  [33X[1;0Y[29X[2XEdgesOfNautyGraph[102X( [3Xgraph[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XEdges[102X( [3Xarg[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of lists of length 2 of positive integers[133X
  
  [33X[0;0YGiven a nauty graph [3Xgraph[103X, this function returns the list of edges of [3Xgraph[103X,
  where  an  edge  is  a  pair of vertices. If the graph is directed, the edge
  [3X[i,j][103X is the directed edge from vertex [3Xi[103X to vertex [3Xj[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xnautygraph := NautyGraph( [ [1,2],[2,3],[3,4], [4,1] ] );[127X[104X
    [4X[28X<An undirected Nauty graph with on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27XEdgesOfNautyGraph(nautygraph);[127X[104X
    [4X[28X[ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 1 ] ][128X[104X
  [4X[32X[104X
  
  [1X1.1-8 VerticesOfNautyGraph[101X
  
  [33X[1;0Y[29X[2XVerticesOfNautyGraph[102X( [3Xgraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of positive integers[133X
  
  [33X[0;0YGiven  a  nauty  graph  [3Xgraph[103X, this function returns the list of vertices of
  [3Xgraph[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xnautygraph := NautyGraph( [ [1,2],[2,3],[3,4], [4,1] ] );[127X[104X
    [4X[28X#! <An undirected Nauty graph with on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27XVerticesOfNautyGraph(nautygraph);[127X[104X
    [4X[28X[ 1 .. 4 ][128X[104X
  [4X[32X[104X
  
  [1X1.1-9 VertexColoursOfNautyGraph[101X
  
  [33X[1;0Y[29X[2XVertexColoursOfNautyGraph[102X( [3Xgraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of positive integers[133X
  
  [33X[0;0YGiven  a coloured nauty graph [3Xgraph[103X, this function returns a list giving the
  colours of the vertices of [3Xgraph[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng := NautyColoredGraph( [ [1,2], [2,3], [3,4], [4,1], [3,2] ], [1,2,1,2] );[127X[104X
    [4X[28X<An  undirected vertex-coloured Nauty graph on 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27XVertexColoursOfNautyGraph(ng);[127X[104X
    [4X[28X[ 1, 2, 1, 2 ][128X[104X
  [4X[32X[104X
  
  [1X1.1-10 CanonicalForm[101X
  
  [33X[1;0Y[29X[2XCanonicalForm[102X( [3Xgraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya graph[133X
  
  [33X[0;0YGiven a nauty graph [3Xgraph[103X, this function returns a graph [3Xcangraph[103X which lies
  in  the  same  orbit as [3Xgraph[103X under the automorphism group of [3Xgraph[103X. For the
  definition  of which graph in the orbit is the canonical representatives see
  the  documentation  of  Nauty  and  Traces. The computation of the canonical
  representative is performed by the Nauty and Traces.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng := NautyGraph( [ [1,3], [2,3], [2,5], [4,5], [5,1] ] );[127X[104X
    [4X[28X<An undirected Nauty graph with on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xcanrep := CanonicalForm(ng);[127X[104X
    [4X[28X<An undirected Nauty graph with on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XEdgesOfNautyGraph(canrep);[127X[104X
    [4X[28X[ [ 1, 5 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ] ][128X[104X
  [4X[32X[104X
  
  [1X1.1-11 CanonicalLabeling[101X
  
  [33X[1;0Y[29X[2XCanonicalLabeling[102X( [3Xgraph[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XCanonicalLabelingInverse[102X( [3Xgraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya permutation[133X
  
  [33X[0;0YGiven  a  nauty  graph  [3Xgraph[103X,  the  function  [3XCanonicalLabeling[103X  returns  a
  permutation  [3Xperm[103X  of  the  vertices of [3Xgraph[103X which lies in the automorphism
  group  of [3Xgraph[103X. If [3Xperm[103X is applied to the canoncial representative of [3Xgraph[103X
  (see  [3XCanonicalForm[103X),  by  mapping  the  vertices under [3Xperm[103X and mapping the
  edges  accordingly,  the  resulting  graph  is  input  [3Xgraph[103X.  The  function
  [3XCanonicalLabelingInverse[103X  returns  the  inverse permutation of [3Xperm[103X. For the
  definition  of  the  canonical representatives in the orbit of a graph under
  its  automorphism  group,  see  the  documentation  of Nauty and Traces. The
  computation  of  the  canonical representative is performed by the Nauty and
  Traces.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng := NautyGraph( [ [1,3], [2,3], [2,5], [4,5], [5,1] ] );[127X[104X
    [4X[28X<An undirected Nauty graph with on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xperm := CanonicalLabeling(ng);[127X[104X
    [4X[28X(1,4,3,2)[128X[104X
    [4X[25Xgap>[125X [27Xcanrep := NautyGraph(List(Set(EdgesOfNautyGraph(ng)),i->OnTuples(i,perm^-1)));[127X[104X
    [4X[28X<An undirected Nauty graph with on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27X EdgesOfNautyGraph(canrep);[127X[104X
    [4X[28X[ [ 2, 4 ], [ 3, 4 ], [ 3, 5 ], [ 1, 5 ], [ 5, 2 ] ][128X[104X
    [4X[25Xgap>[125X [27XCanonicalLabeling(ng);     [127X[104X
    [4X[28X(1,4,3,2)[128X[104X
  [4X[32X[104X
  
  [1X1.1-12 IsomorphismGraphs[101X
  
  [33X[1;0Y[29X[2XIsomorphismGraphs[102X( [3Xgraph[103X, [3Xgraph[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsomorphicGraphs[102X( [3Xgraph[103X, [3Xgraph[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsIsomorphicGraphs[102X( [3Xarg1[103X, [3Xarg2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XPermutation[109X[133X
  
  [33X[0;0YGiven  two  nauty (di)graphs [3Xgraph1[103X and [3Xgraph2[103X we say that [3Xgraph1[103X and [3Xgraph2[103X
  are isomorphic, if there is a bijection [22Xπ[122X from the vertices of [3Xgraph1[103X and to
  the  vertices  of  [3Xgraph2[103X  such that, [22Xe=[i,j][122X is an edge of of [3Xgraph1[103X if and
  only  if [22Xe^π=[i^π,j^π][122X is an edge of of [3Xgraph2[103X. Such a bijection [22Xπ[122X is called
  a  [3Xgraph  isomorhism[103X. This function tests whether such a bijection [22Xπ[122X exists.
  If  so,  it returns the permutation [22Xπ[122X and otherwise [9Xfail[109X. If in addition the
  nauty  (di)graphs  [3Xgraph1[103X  and  [3Xgraph2[103X  are  both  vertex  coloured,  then a
  bijection  [22Xπ[122X  is  additionally required to respect the partition of the node
  colours,  that is, two nodes [22Xi, j[122X have the same colour in [3Xgraph1[103X if and only
  if they have the same colour in [3Xgraph2[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng :=  NautyGraph([[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[5,6],[6,7]]); [127X[104X
    [4X[28X<An undirected Nauty graph with on 7 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xng2 :=  NautyGraph([[1,2],[1,3],[1,4],[1,6],[2,3],[2,4],[5,6],[5,7]]);[127X[104X
    [4X[28X<An undirected Nauty graph with on 7 vertices>[128X[104X
    [4X[25Xgap>[125X [27XIsomorphismGraphs(ng,ng2);[127X[104X
    [4X[28X(5,6)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YGiven  two  nauty (di)graphs [3Xgraph1[103X and [3Xgraph2[103X we say that [3Xgraph1[103X and [3Xgraph2[103X
  are isomorphic, if there is a bijection [22Xπ[122X from the vertices of [3Xgraph1[103X and to
  the  vertices  of  [3Xgraph2[103X  such that, [22Xe=[i,j][122X is an edge of of [3Xgraph1[103X if and
  only  if [22Xe^π=[i^π,j^π][122X is an edge of of [3Xgraph2[103X. Such a bijection [22Xπ[122X is called
  a [12Xgraph isomorhism[112X.This function tests whether such a bijection [22Xπ[122X exists. If
  so, it returns [9Xtrue[109X and otherwise [9Xfalse[109X. If in addition the nauty (di)graphs
  [3Xgraph1[103X  and  [3Xgraph2[103X  are  both  vertex  coloured,  then  a  bijection  [22Xπ[122X  is
  additionally required to respect the partition of the node colours, that is,
  two  nodes  [22Xi, j[122X have the same colour in [3Xgraph1[103X if and only if they have the
  same colour in [3Xgraph2[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng :=  NautyGraph([[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[5,6],[6,7]]); [127X[104X
    [4X[28X<An undirected Nauty graph with on 7 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xng2 :=  NautyGraph([[1,2],[1,3],[1,4],[1,6],[2,3],[2,4],[5,6],[5,7]]);[127X[104X
    [4X[28X<An undirected Nauty graph with on 7 vertices>[128X[104X
    [4X[25Xgap>[125X [27XIsomorphicGraphs(ng,ng2);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
