improve handling edge weights in computing automorphisms of graphs

[dimpase]

Presently computing the automorphism group of a graph G on n vertices and m edges, with weighted edges, involves reducing this to computing the automorphism groups of a vertex-weighted graph on n+m vertices.This is too much if m is big.

There is a much better reduction, using only $n(1+\lceil\log_2 M\rceil)$ vertices, with M being the number of different weights.

Assume that each vertex a of G has integer weight d_a (for unweighted vertices case, assign the same weight to them all). Then, make $b:=1+\lceil\log_2 M\rceil$ copies Vⁱ of vertices of G; each edge weight of G is encoded by b bits, as follows: if (a,b) is an edge of G of c-th weight (with weights numbered from 1 to M), then take the binary expansion $c_1,...,c_b$ of c, and join aⁱ and bⁱ in Vⁱ for all i s.t. c_i=1. Futher, join aⁱ and a^j by an edge, and assign the weight d_a+i to each aⁱ, for all i.

The automorphism group of the resulting graph on bn vertices is the automorphism group of edge (and vertex)-weighted G, when restricted to any Vⁱ.

CC: @nathanncohen

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/17188

[dimpase]

Description changed:

--- 
+++ 
@@ -1,7 +1,7 @@
 Presently computing the automorphism group of a graph G on n vertices and m edges, with weighted edges, involves reducing this to computing the automorphism groups of a vertex-weighted graph on n+m(m-1)/2 vertices.This is too much if m is big. 

-There is a much better reduction, using only `$n(1+\lceil\log_2 M\rceil)$` vertices, with M being the number of different colours. 
+There is a much better reduction, using only `$n(1+\lceil\log_2 M\rceil)$` vertices, with M being the number of different weights. 

-Assume that each vertex a of G has integer weight d_a (for unweighted vertices case, assign the same weight to them all). Then, make `$b:=1+\lceil\log_2 M\rceil$` copies V<sup>i</sup> of vertices of G; each edge weight of G is encoded by b bits, as follows: if (a,b) is an edge of G of c-th weight (with weights numbered from 1 to M), then take the binary expansion `$c_1,...,c_b$` of c, and join a<sup>i</sup> and b<sup>i</sup> in V<sup>i</sup> for all i s.t. c_i=1. Futher, join a<sup>i</sup> and a<sup>j</sup> by an edge, and assign the colour d_a+i to each a<sup>i</sup>, for all i.
+Assume that each vertex a of G has integer weight d_a (for unweighted vertices case, assign the same weight to them all). Then, make `$b:=1+\lceil\log_2 M\rceil$` copies V<sup>i</sup> of vertices of G; each edge weight of G is encoded by b bits, as follows: if (a,b) is an edge of G of c-th weight (with weights numbered from 1 to M), then take the binary expansion `$c_1,...,c_b$` of c, and join a<sup>i</sup> and b<sup>i</sup> in V<sup>i</sup> for all i s.t. c_i=1. Futher, join a<sup>i</sup> and a<sup>j</sup> by an edge, and assign the weight d_a+i to each a<sup>i</sup>, for all i.

-The automorphism group of the resulting graph on bn vertices is the automorphism group of G, when restricted to any V<sup>i</sup>.
+The automorphism group of the resulting graph on bn vertices is the automorphism group of edge (and vertex)-weighted G, when restricted to any V<sup>i</sup>.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Presently computing the automorphism group of a graph G on n vertices and m edges, with weighted edges, involves reducing this to computing the automorphism groups of a vertex-weighted graph on n+m(m-1)/2 vertices.This is too much if m is big. 
+Presently computing the automorphism group of a graph G on n vertices and m edges, with weighted edges, involves reducing this to computing the automorphism groups of a vertex-weighted graph on n+m vertices.This is too much if m is big. 

 There is a much better reduction, using only `$n(1+\lceil\log_2 M\rceil)$` vertices, with M being the number of different weights.