Instantly share code, notes, and snippets.

Embed
What would you like to do?
generate Hamming graph H(n, 2)
#!/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)
@dalloliogm

This comment has been minimized.

Owner

dalloliogm commented Feb 20, 2012

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment