Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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"]

enter image description here

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}]

enter image description here

share|improve this answer
    
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 at 3:38
    
@110110 you mean something like this? (StringCount[#1, "0"] - StringCount[#2, "0"]) & @@@ EdgeList[g] –  halmir Jan 22 at 3:44
    
That's all I need to know how to do it, terrific. –  110110 Jan 22 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];
WeightedAdjacencyMatrix@h1 // MatrixForm

Mathematica graphics

share|improve this answer
    
I'm a little confused as to what this is doing? I'm trying to specify arbitrary edge weights to an edge between two specific Gray codes for all such pairs of Gray codes? –  110110 Jan 22 at 3:12
    
@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 –  belisarius Jan 22 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 at 3:35
    
    
I think maybe we're talking past each other, and if so, I apologize. For a hypercube representation of a Gray code, we only have edges between strings with Hamming distance 1. So how can we have edges corresponding to the Hamming distance between the two vertices being connected with weights >1? –  110110 Jan 22 at 4:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.