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,..., 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, ..., 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,..., |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, ..., |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∈ N. Thus labels is a bijection from {1, ..., |N| } to N. Suppose graph has benn constructed with NautyDiGraphWithNodeLabels(edges, labels). The underlying nauty graph Γ on the nodes {1,..., nr}, is defined such that e=[i,j] is an edge of Γ 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... |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... |N|] to a set of node colours.
This function constructs a nauty graph Γ on the nodes {1,..., |N|}, such that e=[i,j] is an edge of Γ 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, ..., |N|} and we would like to translate the nodes and edges of the graph to the node set {1, ..., |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, ..., |N|} and we would like to translate the nodes and edges of the graph to the node set {1, ..., |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