  
  [1X2 [33X[0;0YNauty Graphs with labels[133X[101X
  
  
  [1X2.1 [33X[0;0YWorking with Nauty Graphs with labels[133X[101X
  
  [33X[0;0YThe  package NautyTracesInterface allows working with graphs whose nodes are
  labelled. This feature is useful when working with graphs whose set of nodes
  is  not  equal to a set [22X{1,..., n}[122X for some positive integer [22Xn[122X. For example,
  consider  the  (di)  graph on the nodes [22XN={2,4,6}[122X with edges [22X[ [2,4], [4,6],
  [2,6]  ][122X.  To  work  with  this  graph  in  nauty and traces directly, it is
  considerted to be a graph with nodes [22X{1, ..., 6}[122X. However, using [3Xnode labels[103X
  we  can view this as a graph on three nodes, namely [22X1,2,3[122X and attach a label
  to  each  of  these  nodes.  The  labels are recorded in a list [3Xlabels[103X which
  defines  a  map  from  the default nodes [22X{1,..., |N|}[122X to the set of nodes on
  which  the  edges  are  defined.  In  this example, [22Xlabels = [ 2, 4, 6][122X. The
  function  [3XNautyGraphWithNodeLabels[103X  called  with  the  edges [22X[ [2,4], [4,6],
  [2,6]  ][122X and labels [22X[ 2, 4, 6][122X then returns a graph on 3 nodes. The graph on
  the default node set is called the [3Xunderlying nauty graph[103X.[133X
  
  [1X2.1-1 NodeLabeling[101X
  
  [33X[1;0Y[29X[2XNodeLabeling[102X( [3Xgraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya [9Xlist[109X[133X
  
  [33X[0;0YGiven a nauty (di)graph [3Xgraph[103X with node labels this function returns a dense
  list  of  positive  integers,  which are the node labels of [3Xgraph[103X. If [22Xi[122X is a
  node  in  the underlying nauty graph, then [3Xlabels[i] = j[103X means that the [22Xi[122X-th
  node has label [22Xj[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xlabels := [4,3,5,2,1];;[127X[104X
    [4X[25Xgap>[125X [27Xng := NautyDiGraphWithNodeLabels([[1,2],[1,3],[1,4],[1,5]], labels);[127X[104X
    [4X[28X<An undirected Nauty graph with on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XNodeLabeling(ng);[127X[104X
    [4X[28X[ 4, 3, 5, 2, 1 ][128X[104X
  [4X[32X[104X
  
  [1X2.1-2 UnderlyingNautyGraph[101X
  
  [33X[1;0Y[29X[2XUnderlyingNautyGraph[102X( [3Xgraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya [9Xlist[109X[133X
  
  [33X[0;0YA  nauty  (di)graph  [3Xgraph[103X  with  node labels [3Xlabels[103X is a nauty graph object
  containing  an  [3Xunderlying  nauty  graph[103X. The graph has a set [22XN[122X of nodes and
  edges between these nodes. The underlying nauty graph has nodes [22X{1, ..., |N|
  }[122X.  If  [22Xi[122X  is a node in the underlying nauty graph, then [3Xlabels[i] = j[103X means
  that  the [22Xi[122X-th node has label [22Xj[122X, where [22Xj∈ N.[122X Thus [3Xlabels[103X is a bijection from
  [22X{1,   ...,   |N|   }[122X   to   [22XN[122X.  Suppose  [3Xgraph[103X  has  benn  constructed  with
  [9XNautyDiGraphWithNodeLabels(edges,  labels)[109X.  The underlying nauty graph [22XΓ[122X on
  the  nodes  [22X{1,..., nr}[122X, is defined such that [22Xe=[i,j][122X is an edge of [22XΓ[122X if and
  only if [22X[label[i[,label[j]][122X is in the input list [3Xedges[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xlabels := [4,3,5,2,1];;[127X[104X
    [4X[25Xgap>[125X [27Xng := NautyDiGraphWithNodeLabels([[1,2],[1,3],[1,4],[1,5]], labels);[127X[104X
    [4X[28X<An undirected Nauty graph with on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XNodeLabeling(ng);[127X[104X
    [4X[28X[ 4, 3, 5, 2, 1 ][128X[104X
    [4X[28XEdgesOfNautyGraph(UnderlyingNautyGraph(ng));[128X[104X
    [4X[28X[ [ 5, 4 ], [ 5, 2 ], [ 5, 1 ], [ 5, 3 ] ][128X[104X
    [4X[25Xgap>[125X [27Xlabels := [10,11,12,13,9];;[127X[104X
    [4X[25Xgap>[125X [27Xng := NautyDiGraphWithNodeLabels([[10,11],[10,12],[10,13],[10,9]], labels);[127X[104X
    [4X[28X<A directed Nauty graph on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XEdgesOfNautyGraph(ng);[127X[104X
    [4X[28X[ [ 10, 11 ], [ 10, 12 ], [ 10, 13 ], [ 10, 9 ] ][128X[104X
    [4X[25Xgap>[125X [27XEdgesOfNautyGraph(UnderlyingNautyGraph(ng));[127X[104X
    [4X[28X[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ] ][128X[104X
    [4X[25Xgap>[125X [27XVerticesOfNautyGraph(ng);[127X[104X
    [4X[28X[ 9, 10, 11, 12, 13 ][128X[104X
    [4X[25Xgap>[125X [27XVerticesOfNautyGraph(UnderlyingNautyGraph(ng));[127X[104X
    [4X[28X[ 1 .. 5 ][128X[104X
  [4X[32X[104X
  
  [1X2.1-3 NautyGraphWithNodeLabels[101X
  
  [33X[1;0Y[29X[2XNautyGraphWithNodeLabels[102X( [3Xedges[103X, [3Xlabeling[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyDiGraphWithNodeLabels[102X( [3Xedges[103X, [3Xlabeling[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyColoredGraphWithNodeLabels[102X( [3Xedges[103X, [3Xcolours[103X, [3Xlabeling[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyColoredDiGraphWithNodeLabels[102X( [3Xedges[103X, [3Xcolours[103X, [3Xlabeling[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XNautyGraph[109X[133X
  
  [33X[0;0YConstruct  a nauty (di)graph with node labels and optional vertex colouring,
  which  is  an  object  that has an underlying nauty graph. Suppose we have a
  graph  given  by  a  list  [3Xedges[103X  of edges, where each edge is a list of two
  positive integers.[133X
  
  [33X[0;0YArguments:[133X
  
  [30X    [33X[0;6Y[3Xedges[103X: dense list of edges, encoded as pairs of positive integers. Let
        [22XN[122X  denote  the  set  of  all  (not  necessarily  consecutive) positive
        integers occuring in the entries of [3Xedges[103X.[133X
  
  [30X    [33X[0;6Y[3Xlabels[103X:  dense  list  of  positive  integers which is a map [22Xlabel[122X from
        [22X[1... |N|][122X to [22XM[122X.[133X
  
  [30X    [33X[0;6Y[3Xcolouring[103X  (optional):  dense  list  of  colours  (positive integers),
        indexed  by the nodes of the underlying nauty graph, that is [3Xcolouring[103X
        is a map from [22X[1... |N|][122X to a set of node colours.[133X
  
  [33X[0;0YThis  function  constructs  a  nauty graph [22XΓ[122X on the nodes [22X{1,..., |N|}[122X, such
  that  [22Xe=[i,j][122X  is  an edge of [22XΓ[122X if and only if [22X[label[i],label[j]][122X is in the
  input list [3Xedges[103X.[133X
  
  [33X[0;0YThis  function  is  useful, for example, if we are given a graph on a set of
  nodes  [22XN[122X  which  is  not equal to the set [22X{1, ..., |N|}[122X and we would like to
  translate  the nodes and edges of the graph to the node set [22X{1, ..., |N|}[122X to
  obtain a more compact description of the graph.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng :=  NautyDiGraphWithNodeLabels( [[1,8],[1,12],[1,7],[1,5]],[127X[104X
    [4X[28X             [7,12,5,1,8]);[128X[104X
    [4X[28X<A directed Nauty graph on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XEdgesOfNautyGraph(ng);[127X[104X
    [4X[28X[ [ 1, 8 ], [ 1, 12 ], [ 1, 7 ], [ 1, 5 ] ][128X[104X
    [4X[25Xgap>[125X [27Xung := UnderlyingNautyGraph(ng);[127X[104X
    [4X[28X<A directed Nauty graph on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XEdgesOfNautyGraph(ung);[127X[104X
    [4X[28X[ [ 4, 5 ], [ 4, 2 ], [ 4, 1 ], [ 4, 3 ] ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YDeclareSynonym("NautyColouredGraphWithNodeLabels",NautyColouredGraphWithNodeLabels);
  DeclareSynonym("NautyColouredDiGraphWithNodeLabels",NautyColouredDiGraphWithNodeLabels);[133X
  
  [1X2.1-4 NautyGraphNodeLabels[101X
  
  [33X[1;0Y[29X[2XNautyGraphNodeLabels[102X( [3Xarg[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Ya [9XList[109X[133X
  
  [33X[0;0YReturns  the  list  of node labels for a nauty (di)graph with node labels or
  fail else.[133X
  
  [33X[0;0YNauty  graphs  with  node  labels are useful, for example, if we are given a
  graph on a set of nodes [22XN[122X which is not equal to the set [22X{1, ..., |N|}[122X and we
  would like to translate the nodes and edges of the graph to the node set [22X{1,
  ..., |N|}[122X to obtain a more compact description of the graph.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xng :=  NautyDiGraphWithNodeLabels( [[1,8],[1,12],[1,7],[1,5]],[127X[104X
    [4X[28X             [7,12,5,1,8]);[128X[104X
    [4X[28X<A directed Nauty graph on 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XEdgesOfNautyGraph(ng);[127X[104X
    [4X[28X[ [ 1, 8 ], [ 1, 12 ], [ 1, 7 ], [ 1, 5 ] ][128X[104X
    [4X[25Xgap>[125X [27XNautyGraphNodeLabels(ng);[127X[104X
    [4X[28X[ 7, 12, 5, 1, 8 ][128X[104X
  [4X[32X[104X
  
