generate Hamming graph H(n, 2)

gistfile1.py

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

"""
import networkx
import itertools
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
    l = ["01"] * chromosome_len 
    all_nodes = itertools.product(*l)
    all_nodes = [''.join(x) for x in all_nodes]
    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):
    # wonder if there is some binary utils package for python
    if node[n] == '0':
        newbase = '1'
    else:
        newbase = '0'
    new_node = node[0:n] + newbase + node[n+1:]
    return new_node


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

note the forked version by Brandon Invergo, which uses binary operators
https://gist.github.com/1854574