‣ NautyGraph( edges, nr ) | ( operation ) |
‣ NautyGraph( arg1, arg2 ) | ( operation ) |
Returns: a NautyGraph
This function creates a nauty graph object for an undirected graph without multiple edges, but possibly with loops, whose edges are given by the list edges. The list edges 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 1, .., nr, where nr is the maximal entry occurring in one of the edges. If the function is called with a second argument nr then nr must be a positive integer which is at least equal to the maximal entry occurring in one of the edges.
gap> ng := NautyGraph( [ [1,2], [2,3], [3,4], [4,1], [3,2] ] ); <An undirected Nauty graph with on 4 vertices> gap> [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 1 ], [ 3, 2 ] ]
‣ NautyDiGraph( edges, nr ) | ( operation ) |
‣ NautyDiGraph( arg1, arg2 ) | ( operation ) |
Returns: a NautyGraph
This function creates a nauty graph object for a directed graph without multiple edges, but possibly with loops, whose edges are given by the list edges. The list edges 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 1, .., nr, where nr is the maximal entry occurring in one of the edges. If the function is called with a second argument nr then nr must be a positive integer which is at least equal to the maximal entry occurring in one of the edges.
gap> nautygraph := NautyDiGraph( [ [1,2],[2,3],[3,4], [4,1] ] ); <A directed Nauty graph on 4 vertices> gap> AutomorphismGroup(nautygraph); Group([ (1,2,3,4) ])
‣ NautyColoredGraph( edges, colours ) | ( operation ) |
Returns: a NautyGraph
This 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 edges. The list edges 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 1, .., nr, where nr is the maximal entry occurring in one of the edges. The list colours must be a list of length nr whose entries are positive integers. The vertex i has colour colours[i].
gap> nautygraph := NautyColoredGraph( [ [1,2],[2,3],[3,4], [4,1] ], [1,2,1,2] ); <An undirected vertex-coloured Nauty graph on 4 vertices> gap> AutomorphismGroup(nautygraph); Group([ (2,4), (1,3) ])
DeclareSynonym( "NautyColouredGraph", NautyColoredGraph );
‣ NautyColoredDiGraph( edges, colours ) | ( operation ) |
Returns: a NautyGraph
This 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 edges. The list edges 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 1, .., nr, where nr is the maximal entry occurring in one of the edges. The list colours must be a list of length nr whose entries are positive integers. The vertex i has colour colours[i].
gap> nautygraph := NautyColoredGraph( [ [1,2],[2,3],[3,4], [4,1] ], [1,2,1,2] ); <An undirected vertex-coloured Nauty graph on 4 vertices> gap> AutomorphismGroup(nautygraph); Group([ (2,4), (1,3) ])
DeclareSynonym( "NautyColouredDiGraph", NautyColoredDiGraph );
‣ NautyEdgeColoredGraph( edgeclasses, colours ) | ( operation ) |
‣ NautyEdgeColoredGraph( arg1, arg2 ) | ( operation ) |
‣ NautyEdgeColoredDiGraph( arg ) | ( operation ) |
‣ NautyEdgeColoredDiGraph( arg1, arg2 ) | ( operation ) |
Returns: a NautyGraph
This 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 edgeclasses as follows. edgeclasses is a list of lists L_i, where each list L_i is a list of edges, that is L_i 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 1, .., nr, where nr is the maximal entry occurring in one of the edges. The edges in the ith list L_i have colour i.
gap> nautygraph := NautyEdgeColoredGraph( [ [[1,2],[2,3]],[[3,4], [4,1]]]); <An undirected edge-coloured Nauty graph on 4 vertices and 2 edge colours> gap> AutomorphismGroup(nautygraph); Group([ (1,3) ])
DeclareSynonym( "NautyEdgeColouredGraph", NautyEdgeColoredGraph ); DeclareSynonym( "NautyEdgeColouredDiGraph", NautyEdgeColoredDiGraph );
‣ AutomorphismGroup( graph ) | ( attribute ) |
Returns: a permutation group
Given a simple (di)graph graph which is a nauty graph object (see 1.1), this function computes the automorphism group of graph as a permutation group on the nodes of graph. As graph is a simple graph, its edges are given as lists [i,j] of length 2 consisting of a pair of nodes in the set N. If an edge is a loop, it is of the form [i,i]. If i,j are different nodes and the graph is undirected, [i,j] and [j,i] refer to the same edge, and to different edges when the graph is directed. A bijection ϕ from N to itself is called an automorphism of the (undirected) graph graph if ϕ maps edges of graph to edges of graph, that is e=[i,j] is an edge of graph if and only if e=[i^ϕ,j^ϕ] or, in the undirected case, e=[j^ϕ,i^ϕ] is an edge of graph. If The automorphism group of graph is returned as a permutation group acting on the set N.
gap> nautygraph := NautyGraph( [ [1,2],[2,3],[3,4], [4,1] ] ); <An undirected Nauty graph with on 4 vertices> gap> AutomorphismGroup(nautygraph); Group([ (2,4), (1,2)(3,4) ])
‣ EdgesOfNautyGraph( graph ) | ( attribute ) |
‣ Edges( arg ) | ( attribute ) |
Returns: a list of lists of length 2 of positive integers
Given a nauty graph graph, this function returns the list of edges of graph, where an edge is a pair of vertices. If the graph is directed, the edge [i,j] is the directed edge from vertex i to vertex j.
gap> nautygraph := NautyGraph( [ [1,2],[2,3],[3,4], [4,1] ] ); <An undirected Nauty graph with on 4 vertices> gap> EdgesOfNautyGraph(nautygraph); [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 1 ] ]
‣ VerticesOfNautyGraph( graph ) | ( attribute ) |
Returns: a list of positive integers
Given a nauty graph graph, this function returns the list of vertices of graph.
gap> nautygraph := NautyGraph( [ [1,2],[2,3],[3,4], [4,1] ] ); #! <An undirected Nauty graph with on 4 vertices> gap> VerticesOfNautyGraph(nautygraph); [ 1 .. 4 ]
‣ VertexColoursOfNautyGraph( graph ) | ( attribute ) |
Returns: a list of positive integers
Given a coloured nauty graph graph, this function returns a list giving the colours of the vertices of graph.
gap> ng := NautyColoredGraph( [ [1,2], [2,3], [3,4], [4,1], [3,2] ], [1,2,1,2] ); <An undirected vertex-coloured Nauty graph on 4 vertices> gap> VertexColoursOfNautyGraph(ng); [ 1, 2, 1, 2 ]
‣ CanonicalForm( graph ) | ( attribute ) |
Returns: a graph
Given a nauty graph graph, this function returns a graph cangraph which lies in the same orbit as graph under the automorphism group of graph. 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.
gap> ng := NautyGraph( [ [1,3], [2,3], [2,5], [4,5], [5,1] ] ); <An undirected Nauty graph with on 5 vertices> gap> canrep := CanonicalForm(ng); <An undirected Nauty graph with on 5 vertices> gap> EdgesOfNautyGraph(canrep); [ [ 1, 5 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ] ]
‣ CanonicalLabeling( graph ) | ( attribute ) |
‣ CanonicalLabelingInverse( graph ) | ( attribute ) |
Returns: a permutation
Given a nauty graph graph, the function CanonicalLabeling returns a permutation perm of the vertices of graph which lies in the automorphism group of graph. If perm is applied to the canoncial representative of graph (see CanonicalForm), by mapping the vertices under perm and mapping the edges accordingly, the resulting graph is input graph. The function CanonicalLabelingInverse returns the inverse permutation of perm. 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.
gap> ng := NautyGraph( [ [1,3], [2,3], [2,5], [4,5], [5,1] ] ); <An undirected Nauty graph with on 5 vertices> gap> perm := CanonicalLabeling(ng); (1,4,3,2) gap> canrep := NautyGraph(List(Set(EdgesOfNautyGraph(ng)),i->OnTuples(i,perm^-1))); <An undirected Nauty graph with on 5 vertices> gap> EdgesOfNautyGraph(canrep); [ [ 2, 4 ], [ 3, 4 ], [ 3, 5 ], [ 1, 5 ], [ 5, 2 ] ] gap> CanonicalLabeling(ng); (1,4,3,2)
‣ IsomorphismGraphs( graph, graph ) | ( operation ) |
‣ IsomorphicGraphs( graph, graph ) | ( operation ) |
‣ IsIsomorphicGraphs( arg1, arg2 ) | ( operation ) |
Returns: a Permutation
Given two nauty (di)graphs graph1 and graph2 we say that graph1 and graph2 are isomorphic, if there is a bijection π from the vertices of graph1 and to the vertices of graph2 such that, e=[i,j] is an edge of of graph1 if and only if e^π=[i^π,j^π] is an edge of of graph2. Such a bijection π is called a graph isomorhism. This function tests whether such a bijection π exists. If so, it returns the permutation π and otherwise fail. If in addition the nauty (di)graphs graph1 and graph2 are both vertex coloured, then a bijection π is additionally required to respect the partition of the node colours, that is, two nodes i, j have the same colour in graph1 if and only if they have the same colour in graph2.
gap> ng := NautyGraph([[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[5,6],[6,7]]); <An undirected Nauty graph with on 7 vertices> gap> ng2 := NautyGraph([[1,2],[1,3],[1,4],[1,6],[2,3],[2,4],[5,6],[5,7]]); <An undirected Nauty graph with on 7 vertices> gap> IsomorphismGraphs(ng,ng2); (5,6)
Given two nauty (di)graphs graph1 and graph2 we say that graph1 and graph2 are isomorphic, if there is a bijection π from the vertices of graph1 and to the vertices of graph2 such that, e=[i,j] is an edge of of graph1 if and only if e^π=[i^π,j^π] is an edge of of graph2. Such a bijection π is called a graph isomorhism.This function tests whether such a bijection π exists. If so, it returns true and otherwise false. If in addition the nauty (di)graphs graph1 and graph2 are both vertex coloured, then a bijection π is additionally required to respect the partition of the node colours, that is, two nodes i, j have the same colour in graph1 if and only if they have the same colour in graph2.
gap> ng := NautyGraph([[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[5,6],[6,7]]); <An undirected Nauty graph with on 7 vertices> gap> ng2 := NautyGraph([[1,2],[1,3],[1,4],[1,6],[2,3],[2,4],[5,6],[5,7]]); <An undirected Nauty graph with on 7 vertices> gap> IsomorphicGraphs(ng,ng2); true
generated by GAPDoc2HTML