The 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 \(\{1,\ldots, n\}\) for some positive integer \(n\). For example, consider the (di) graph on the nodes \(N=\{2,4,6\}\) with edges \([ [2,4], [4,6], [2,6] ]\). To work with this graph in nauty and traces directly, it is considerted to be a graph with nodes \(\{1, \ldots, 6\}\). However, using node labels we can view this as a graph on three nodes, namely \(1,2,3\) and attach a label to each of these nodes. The labels are recorded in a list labels which defines a map from the default nodes \(\{1,\ldots, |N|\}\) to the set of nodes on which the edges are defined. In this example, \(labels = [ 2, 4, 6]\). The function NautyGraphWithNodeLabels called with the edges \([ [2,4], [4,6], [2,6] ]\) and labels \([ 2, 4, 6]\) then returns a graph on 3 nodes. The graph on the default node set is called the underlying nauty graph.
‣ NodeLabeling( graph ) | ( attribute ) |
Returns: a list
Given a nauty (di)graph graph with node labels this function returns a dense list of positive integers, which are the node labels of graph. If \(i\) is a node in the underlying nauty graph, then labels[i] = j means that the \(i\)-th node has label \(j\).
gap> labels := [4,3,5,2,1];; gap> ng := NautyDiGraphWithNodeLabels([[1,2],[1,3],[1,4],[1,5]], labels); <An undirected Nauty graph with on 5 vertices> gap> NodeLabeling(ng); [ 4, 3, 5, 2, 1 ]
‣ UnderlyingNautyGraph( graph ) | ( attribute ) |
Returns: a list
A nauty (di)graph graph with node labels labels is a nauty graph object containing an underlying nauty graph. The graph has a set \(N\) of nodes and edges between these nodes. The underlying nauty graph has nodes \( \{1, \ldots, |N| \}\). If \(i\) is a node in the underlying nauty graph, then labels[i] = j means that the \(i\)-th node has label \(j\), where \(j\in N.\) Thus labels is a bijection from \( \{1, \ldots, |N| \}\) to \(N\). Suppose graph has benn constructed with NautyDiGraphWithNodeLabels(edges, labels). The underlying nauty graph \(\Gamma\) on the nodes \(\{1,\ldots, nr\}\), is defined such that \(e=[i,j]\) is an edge of \(\Gamma\) if and only if \([label[i[,label[j]]\) is in the input list edges.
gap> labels := [4,3,5,2,1];; gap> ng := NautyDiGraphWithNodeLabels([[1,2],[1,3],[1,4],[1,5]], labels); <An undirected Nauty graph with on 5 vertices> gap> NodeLabeling(ng); [ 4, 3, 5, 2, 1 ] EdgesOfNautyGraph(UnderlyingNautyGraph(ng)); [ [ 5, 4 ], [ 5, 2 ], [ 5, 1 ], [ 5, 3 ] ] gap> labels := [10,11,12,13,9];; gap> ng := NautyDiGraphWithNodeLabels([[10,11],[10,12],[10,13],[10,9]], labels); <A directed Nauty graph on 5 vertices> gap> EdgesOfNautyGraph(ng); [ [ 10, 11 ], [ 10, 12 ], [ 10, 13 ], [ 10, 9 ] ] gap> EdgesOfNautyGraph(UnderlyingNautyGraph(ng)); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ] ] gap> VerticesOfNautyGraph(ng); [ 9, 10, 11, 12, 13 ] gap> VerticesOfNautyGraph(UnderlyingNautyGraph(ng)); [ 1 .. 5 ]
‣ NautyGraphWithNodeLabels( edges, labeling ) | ( operation ) |
‣ NautyDiGraphWithNodeLabels( edges, labeling ) | ( operation ) |
‣ NautyColoredGraphWithNodeLabels( edges, colours, labeling ) | ( operation ) |
‣ NautyColoredDiGraphWithNodeLabels( edges, colours, labeling ) | ( operation ) |
Returns: a NautyGraph
Construct 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 edges of edges, where each edge is a list of two positive integers.
Arguments:
edges: dense list of edges, encoded as pairs of positive integers. Let \(N\) denote the set of all (not necessarily consecutive) positive integers occuring in the entries of edges.
labels: dense list of positive integers which is a map \(label\) from \([1\ldots |N|]\) to \(M\).
colouring (optional): dense list of colours (positive integers), indexed by the nodes of the underlying nauty graph, that is colouring is a map from \([1\ldots |N|]\) to a set of node colours.
This function constructs a nauty graph \(\Gamma\) on the nodes \(\{1,\ldots, |N|\}\), such that \(e=[i,j]\) is an edge of \(\Gamma\) if and only if \([label[i],label[j]]\) is in the input list edges.
This function is useful, for example, if we are given a graph on a set of nodes \(N\) which is not equal to the set \(\{1, \ldots, |N|\}\) and we would like to translate the nodes and edges of the graph to the node set \(\{1, \ldots, |N|\}\) to obtain a more compact description of the graph.
gap> ng := NautyDiGraphWithNodeLabels( [[1,8],[1,12],[1,7],[1,5]], [7,12,5,1,8]); <A directed Nauty graph on 5 vertices> gap> EdgesOfNautyGraph(ng); [ [ 1, 8 ], [ 1, 12 ], [ 1, 7 ], [ 1, 5 ] ] gap> ung := UnderlyingNautyGraph(ng); <A directed Nauty graph on 5 vertices> gap> EdgesOfNautyGraph(ung); [ [ 4, 5 ], [ 4, 2 ], [ 4, 1 ], [ 4, 3 ] ]
DeclareSynonym("NautyColouredGraphWithNodeLabels",NautyColouredGraphWithNodeLabels); DeclareSynonym("NautyColouredDiGraphWithNodeLabels",NautyColouredDiGraphWithNodeLabels);
‣ NautyGraphNodeLabels( arg ) | ( operation ) |
Returns: a List
Returns the list of node labels for a nauty (di)graph with node labels or fail else.
Nauty graphs with node labels are useful, for example, if we are given a graph on a set of nodes \(N\) which is not equal to the set \(\{1, \ldots, |N|\}\) and we would like to translate the nodes and edges of the graph to the node set \(\{1, \ldots, |N|\}\) to obtain a more compact description of the graph.
gap> ng := NautyDiGraphWithNodeLabels( [[1,8],[1,12],[1,7],[1,5]], [7,12,5,1,8]); <A directed Nauty graph on 5 vertices> gap> EdgesOfNautyGraph(ng); [ [ 1, 8 ], [ 1, 12 ], [ 1, 7 ], [ 1, 5 ] ] gap> NautyGraphNodeLabels(ng); [ 7, 12, 5, 1, 8 ]
generated by GAPDoc2HTML