generate Hamming graph H(n, 2)

gistfile1.py

#!/usr/bin/env python
"""
Generate a Hamming Graph

"""
import networkx
import logging

def hamming_binary(chromosome_len):
    """Generate a binary Hamming Graph, where each genotype is composed by chromosome_len bases and each base can take only two values. H(chromosome_len, 2). 
    
    steps to generate an Hamming graph:
    
     * create 2^chromosome_len nodes, each for a different binary string
     * for each node, find the connected nodes by flipping one position at a time.
    """
    space = networkx.Graph()

    # create all nodes
    all_nodes = range(0, 2**chromosome_len)
    logging.debug(all_nodes)
    space.add_nodes_from(all_nodes) 
    
    # for each node, find neighbors
    for node in space.nodes():
        [space.add_edge(node, mutate_node(node, base)) for base in range(chromosome_len)]
    return space


def mutate_node(node, n):
    """Generate a mutational neighbor of a node. 
    
    Select the loci to be mutated by left-shifting a bit by n. Then do a bitwise
    XOR to do the mutation.
    
    Example:
    Node 26 =           11010
    n = 2: 00001 << 2 = 00100
                        -----
    XOR:                11110
    
    Example 2:
    Node 26 =           11010
    n = 1: 00001 << 1 = 00010
                        -----
    XOR:                11000
    """

    return node ^ (1 << n)


if __name__ == '__main__':
    logging.basicConfig(level=logging.DEBUG)
    space = hamming_binary(5)
    print len(space.edges())