Graph Canonicalization
by Brian Kelley

Listing One
for node in graph:
    # for every node in g traverse to their
    # adjacentNeighbors and edges
    for adjacentNode, traversalEdge in node.neighbors():
        print adjacentNode, traversalEdge

Listing Two
"""One of the best ways to store graphs in python is with a dictionary object.
g = {}

Nodes in a graph are the keys in a dictionary and the edges are the values.
To traverse through the nodes in a graph
for n in g:
   # do something with the node

to traverse through key and edge values
for n,e in g.items()

to traverse through edge values
for n in g.values()

"""
from types import DictType
class Graph(DictType):
    def nodes(self):
        return self.keys()
    def edges(self):
        _edges = {}
        for neighbor in self.values():
            for edge in neighbor.values():
                _edges[edge] = 1
        return _edges.keys()
    def iternodes(self):
        """iterate through the nodes"""
        return self.iterkeys()
    def neighbors(self, node):
        """(node) -> return the (node, edge) pairs for a given
        node"""
        return self[node].items()
    def iterneighbors(self):
        """iterate through the neighbors of a node"""
        return self.iteritems()
    def addNode(self, node):
        self[node] = self.get(node, {})
        node.setParent(self)
    def addEdge(self, n1, n2, edge):
        # assumes n1 and n2 are already in a node
        try:
            assert not self[n1].has_key(n2)
            assert not self[n2].has_key(n1)
            self[n1][n2] = edge
            self[n2][n1] = edge
        except KeyError:
            raise GraphError("One of the edge nodes is not in the graph")
from weakref import proxy

class Base:
    def __init__(self, label):
        self.label = label
        self.equiv_class = -1
        self.symorder = -1
        self.symclass = -1
        self.parent = None
    def setParent(self, parent):
        self.parent = proxy(parent)
    def __hash__(self):
        return id(self)
    def __cmp__(self, other):
        return cmp(self.label, other.label)
    def __str__(self):
        return self.label
    def __repr__(self):
        return "%s(%s)"%(self.__class__.__name__, `self.label`)
class Node(Base):
    def neighbors(self):
        return self.parent.neighbors(self)
class Edge(Base):
    pass

Listing Three

"""computes equivalence classes for atoms
GenerateEquivClasses(graph)
"""
def GenerateEquivClasses(graph):
    """(graph) -> given a graph, generate the equivalence classes for the 
    nodes and edges of the graph by assigning a unique number to uniquely 
    labeled nodes and edges.  The nodes and edges must be sortable"""
        # sort and rank the Nodes and Edges
    for labeledObject in [graph.nodes(), graph.edges()]:
        # sort the objects based on their label attribute
        labeledObject.sort(lambda x,y: cmp(x.label, y.label))
        last = None
        rank = -1
        for ob in labeledObject:
            if ob.label != last:
                # increment the rank
                rank = rank + 1
            ob.equiv_class = rank
            last = ob.label


Listing Four
"""Recursively traverse a graph building up a canonical representation.
Each vertex of a Molecule or Graph must have a attribute 'symorder' which
is a unique number. This number guarantees only one traversal for
the graph. Additionally each edge must have an attribute equiv_class which is
a unique value for each different type of bond. This guarantees
proper canonicalization of edges as well as vertices.
usage
generateSymmetryOrders(graph)
"""

def _traverse(node, prevNode, visitedNodes, visitedEdges, nodes, edges):
    visitedNodes[node] = 1
    nodes.append(node)
    edgeIndex = 0
    edgesToTraverse = []

    for onode, edge in node.neighbors():        
        if prevNode is not None and onode is prevNode:
            # we are traversing back the way we came! so don't...
            pass
        elif visitedNodes.has_key(onode):
            # a closure!
            # traverse.addClosure(node, onode, edge)
            edges.append(edge)
            visitedEdges[edge] = 1
        else:
            edgesToTraverse.append((onode.symorder, edge.equiv_class,
                                              edgeIndex, onode, edge))
        edgeIndex += 1
    if not edgesToTraverse:
        # dead end, return
        return
    edgesToTraverse.sort()
    for symorder, edgeEclass, index, onode, oedge in edgesToTraverse:
        if visitedNodes.has_key(onode):
            # somehow, we've seen this node so skip it
            continue
        edges.append(oedge)
        visitedEdges[oedge] = 1
        _traverse(onode, node, visitedNodes, visitedEdges, nodes, edges)
def _get_lowest_symorder(nodes):
    best = nodes[0]
    for node in nodes[1:]:
        if node.symorder < best.symorder:
            best = node
    return best
def generateSymmetryOrders(graph):
    """(graph) -> traverse the symmetry classes in order of the
    smallest edge equiv_classes to generate symmetry orders"""
    node = _get_lowest_symorder(graph.nodes())
    visitedNodes = {}
    visitedEdges = {}
    nodesUsed = []
    edgesUsed = []
    _traverse(node, None, visitedNodes, visitedEdges, nodesUsed, edgesUsed)
    i = 0
    # set the symmetry orders of the nodes and edges
    for n in nodesUsed:
        n.symorder = i
        i += 1
    i = 0
    for edge in edgesUsed:
        edge.symorder = i
        i += 1
        





3


