Skip to content

Instantly share code, notes, and snippets.

Created February 17, 2012 16:48
Show Gist options
  • Save dalloliogm/1854319 to your computer and use it in GitHub Desktop.
Save dalloliogm/1854319 to your computer and use it in GitHub Desktop.
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]
# 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'
newbase = '0'
new_node = node[0:n] + newbase + node[n+1:]
return new_node
if __name__ == '__main__':
space = hamming_binary(5)
Copy link

note the forked version by Brandon Invergo, which uses binary operators

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