# Assigning weights to edges of a hypercube based on the Gray code labels for vertices being connected

Say I want to construct an $n$-dimensional hypercube graph $G$ using the command: G = HypercubeGraph[n]. I'd like to assign edge weights to the $2^{(n-1)}n$ edges in $G$, $(e_1,e_2,...)$, with something like a function assignWeights[G,weightList] where weightList is of the form:

weightList = {{grayCodeA, grayCodeB, w1},{grayCode..., grayCode..., w2}, ...};


Here, each entry in weightList specifies a weight $w_i$ for an edge between vertices in the hypercube correspond to specific Gray codes (e.g. between "0010" and "0110" codes for the $n = 4$ dimensional hypercube in this picture: http://en.wikipedia.org/wiki/File:Hamming_distance_4_bit_binary.svg). Nothing's better than an example, so let's construct one for the $n = 3$ dimensional hypercube, where our edgeweights are just random real numbers over the interval $[0,1]$:

n = 3;

tupleSet = Tuples[{0, 1}, n];
weightList = Array[{} &, 2^(n - 1)*n];

counter = 0;
For[a = 1, a <= Length[tupleSet], a++,
For[b = a + 1, b <= Length[tupleSet], b++,
If[HammingDistance[tupleSet[[a]], tupleSet[[b]]] == 1,
counter += 1;
weightList[[counter]] = {tupleSet[[a]], tupleSet[[b]], RandomReal[{0, 1}]};
];
];
];

weightList


(Please let me know if you there's a nice built-in way to generate these tuple pairs without nested loops...)

How would we write something like assignWeights[G,weightList]? Once we assign the weights, can we color code the edges to visually represent the weight assignments?

Based on application example in FindHamiltonianCycle, define function to generate hypercube graph with digit vertex:

graycodeGraph[n_, opt : OptionsPattern[]] :=
VertexReplace[HypercubeGraph[n, opt],
Table[i + 1 -> IntegerString[i, 2, n], {i, 0, 2^n - 1}]]


n = 4 case:

g = graycube[4, VertexShapeFunction -> "Name"]


EdgeList[g]


{"0000" [UndirectedEdge] "0001", "0000" [UndirectedEdge] "0010",
"0000" [UndirectedEdge] "0100", "0000" [UndirectedEdge] "1000",
"0001" [UndirectedEdge] "0011", "0001" [UndirectedEdge] "0101",
"0001" [UndirectedEdge] "1001", "0010" [UndirectedEdge] "0011",
"0010" [UndirectedEdge] "0110", "0010" [UndirectedEdge] "1010",
"0011" [UndirectedEdge] "0111", "0011" [UndirectedEdge] "1011",
"0100" [UndirectedEdge] "0101", "0100" [UndirectedEdge] "0110",
"0100" [UndirectedEdge] "1100", "0101" [UndirectedEdge] "0111",
"0101" [UndirectedEdge] "1101", "0110" [UndirectedEdge] "0111",
"0110" [UndirectedEdge] "1110", "0111" [UndirectedEdge] "1111",
"1000" [UndirectedEdge] "1001", "1000" [UndirectedEdge] "1010",
"1000" [UndirectedEdge] "1100", "1001" [UndirectedEdge] "1011",
"1001" [UndirectedEdge] "1101", "1010" [UndirectedEdge] "1011",
"1010" [UndirectedEdge] "1110", "1011" [UndirectedEdge] "1111",
"1100" [UndirectedEdge] "1101", "1100" [UndirectedEdge] "1110",
"1101" [UndirectedEdge] "1111", "1110" [UndirectedEdge] "1111"}

You could set edge weights using SetProperty:

g2 = SetProperty[g, EdgeWeight -> RandomReal[{0, 1}, EdgeCount[g]]];


And here's the one way to set different color based on edgeweight:

SetProperty[g2, {EdgeStyle ->
Thread[EdgeList[g2] -> Hue /@ PropertyValue[g2, EdgeWeight]],
BaseStyle -> Thick}]


• Ah, this is very close to what I'm looking for! However, ultimately I'd like to set the edge weight based on a computation having to do with the two strings assigned to adjacent vertices (e.g. the difference in the number of zeroes). Is there a nice way for me to do this using the data in EdgeList? – 110110 Jan 22 '14 at 3:38
• @110110 you mean something like this? (StringCount[#1, "0"] - StringCount[#2, "0"]) & @@@ EdgeList[g] – halmir Jan 22 '14 at 3:44
• That's all I need to know how to do it, terrific. – 110110 Jan 22 '14 at 3:47

Perhaps:

n = 2;
h = HypercubeGraph[n];
l = Length@IntegerDigits[n 2^(n - 1), 2];
b2[x_] := IntegerDigits[x, 2, l]
h1 = Fold[SetProperty[{#1, #2},
EdgeWeight -> HammingDistance[b2[#2[[1]]], b2[#2[[2]]]]] &, h,
EdgeList@h];

• @110110 It's assigning as edge weights for the graph the Hamming distance between the binary strings representing the vertex numbers. You can change the assigned weights by changing the EdgeWeight -> ... part to whatever you want – Dr. belisarius Jan 22 '14 at 3:30
• What I'm confused about is how we can have a Hamming distance $>1$? Shouldn't there only be an edge between Gray codes where the Hamming distance is strictly equal to one? – 110110 Jan 22 '14 at 3:35