Recipes/Topology: topology.py

"""This is a database simple pattern for topology data structure, 
It bases on Elixir and SQLAlchemy

The main propose of this module is just for topological sorting now.
I said "now" imply that it can be extend in future.

There are two tables in this pattern :

TraceNode contains nodes of topology
TraceLink contains relationship between two nodes

You can inherit them just like this:

class Task(TraceNode):
    using_options(inheritance='multi')
    # priority of this task
    priority = Field(Float, default=1.0)
    # name of this task
    name = Field(Unicode(32), nullable=False)
    # brief of this task
    brief = Field(Unicode(128))
    # description of this task
    description = Field(Unicode)
            
    def __repr__(self):
        pattern = '<Task %s, priority: %s, changed: %s>'
        return pattern % (self.name, self.priority, self.changed)
        
    def __cmp__(self, other):
        if self.priority < other.priority:
            return -1
        elif self.priority > other.priority:
            return 1
        return TraceNode.__cmp__(self, other)
        
class Dependency(TraceLink):
    using_options(inheritance='multi')

Wow! How easy it is! you just finish a task topological sorting system
based on database! That's the power of the ORM.

We will have a task topology as example like this:

    A
  /  \
 B   C
  \ /
   D
   
B -> A
C -> A (priority 10)
D -> B
D -> C
 
Now let's see how to create this topology.

c = Task(name=u'C', brief=u'Hi, mom!', priority=-10.0) # this is very important!
a = Task(name=u'A', brief=u'This is a important task!')
d = Task(name=u'D', brief=u'Get every thing done')
b = Task(name=u'B', brief=u'Well..It is not so imporant')

ba = Dependency(fromNode=b, toNode=a)
ca = Dependency(fromNode=c, toNode=a)
db = Dependency(fromNode=d, toNode=b)
dc = Dependency(fromNode=d, toNode=c)

session.commit()

tasks = Task.query.all()
# here you are! topological-sorted tasks
print '\n'.join(map(repr, sortNodes(tasks)))

As you see, every thing is just there! What's more, change tracing!
That's what I write this pattern for. You never like change do you?
But you have to face it! Sometimes that will be a big problem
if there is something depends on other, once the depended one has
been changed, you can just update everything, but it is not a good idea
if you have a million rows in database. The best way is just update
part that is affected by this change.

Here shows how to use it.

def handleNode(node):
    print 'handle', node

# Why all task is changed? Because created is considered as changed
# You have to handle just-created task as well.
print '# 1 change: All task'
tracer = ChangeTracer()
tracer.traceChange(handleNode)

print '# 2 change: A'
# make some change here
a.changed = True
tracer.traceChange(handleNode)

print '# 3 change: B'
# make some change here
b.changed = True
tracer.traceChange(handleNode)

print '# 4 change: C'
# make some change here
c.changed = True
tracer.traceChange(handleNode)

print '# 5 change: D'
# make some change here
d.changed = True
tracer.traceChange(handleNode)
    
By Victor Lin ( bornstub@gmail.com ).
http://victorlin.serveftp.org/programming

"""

__email__ = 'bornstub@gmail.com'
__author__ = 'Victor Lin'

from elixir import *

class TraceNode(Entity):
    using_options(tablename='trace_node')
    # is this node changed
    changed = Field(Boolean, nullable=False, index=True)
    # links that connect to other nodes
    outLinks = OneToMany('TraceLink')
    # links that connected to this node
    inLinks= OneToMany('TraceLink')
    
    def __init__(self, changed=True, *args, **kwargs):
        Entity.__init__(self, *args, **kwargs)
        self.changed = changed
        
    def __repr__(self):
        return '<TraceNode id: %s, changed: %s>' % (self.id, self.changed)
    
    def __cmp__(self, other):
        if self.id < other.id:
            return -1
        elif self.id > other.id:
            return 1
        return 0 if self is other else -1
    
class TraceLink(Entity):
    using_options(tablename='trace_link')
    # link from which node
    fromNode = ManyToOne('TraceNode', inverse='outLinks', primary_key=True)
    # connect to which node
    toNode = ManyToOne('TraceNode', inverse='inLinks', primary_key=True)
        
    def __repr__(self):
        return '<TraceLink from %s to %s>' % (self.fromNode.id, self.toNode.id)

def sortNodes(nodes, cmp=None, *args, **kwargs):
    """Performance topological sorting
    
    example :
    Node A
    Node B
    Node C
    B depends on A
    C depends on A
    C depends on B
    
    B depends on A, indicate that B is bigger than A
    C depends on A, indicate that C is bigger than A
    C depends on B, indicate that C is bigger than B
    
    so that the order after sort is [A, B, C]
    
    If there is no way to compare two nodes, just sort by id
    
    @param cmp: cmp function to decide nodes in same level
    @return: a new sorted list of nodes
    """
    # get a copy of nodes
    nodes = nodes[:]
    # stored sorted nodes
    sortedNodes = []
    def getNoDependNodes():
        resultList = []
        for node in nodes:
            inNodes = False
            for link in node.outLinks:
                if link.toNode in nodes:
                    inNodes = True
                    break
            if inNodes:
                continue
            resultList.append(node)
        return resultList
    # nodes that have no incoming links that comes from one of nodes
    noIncomingNodes = getNoDependNodes()
    while len(noIncomingNodes):
        # sort these nodes, make sure they are in right order
        noIncomingNodes.sort(cmp)
        # extend them to sorted nodes
        sortedNodes.extend(noIncomingNodes)
        # remove all sorted nodes from nodes
        [nodes.remove(node) for node in noIncomingNodes]
        # nodes that have no incoming links that comes from one of nodes
        noIncomingNodes = getNoDependNodes()
    return sortedNodes

def getDependedNodes(nodes):
    """Get depended nodes
    
    @param nodes: nodes to get depended nodes
    @return: list of depended nodes, included nodes of arg
    """
    # list of result nodes
    resultList = nodes[:]
    # first level to walk through
    level = nodes
    while len(level):
        nextLevel = []
        for item in level:
            # find all nodes that is linked to this node
            for link in item.inLinks:
                if link.fromNode not in nextLevel and link.fromNode not in resultList:
                     nextLevel.append(link.fromNode)
        level = nextLevel
        resultList.extend(nextLevel)
    return resultList

def detectCycle(nodes):
    """Find is there cycle exist in topology of this nodes
    
    Oops! I have no idea what is the name of algorithm.
    Because I just think it by myself.
    
    This is what I think:
    
    Every node of a cycle should like this
    
    A -> B -> C -> A -> B -> ....

    What my algorithm is going to do, to delete nodes that are not cycle-nodes
    In other word, it have no both in and out links.

    No matter how many nodes I delete, cycle-nodes can't ever be delete.
    Because they always have some one point to it, and it always point to some one.
    They can not be broke.
    
    Once length of remaining nodes is same with last round.
    It's time to see, if the length is zero, indicate there is no cycle.
    Otherwise, there should be more than once cycle in these nodes.
    
    step 1. delete all nodes that have no both in and out links
    step 2. 
        
    @param nodes: nodes to check
    @return: True if there is loop, otherwise False
    """
    nodes = nodes[:]
    lastLen = len(nodes)
    while 1:
        for node in nodes[:]:
            # find links it have
            inLinks = [link for link in node.inLinks if link.fromNode in nodes]
            outLinks = [link for link in node.outLinks if link.toNode in nodes]
            # this can't be a cycle-node, just delete it
            if not len(inLinks) or not len(outLinks):
                nodes.remove(node)
        # we have same length of nodes as last round
        if len(nodes) == lastLen:
            break
        lastLen = len(nodes)
    if len(nodes):
        return True
    return False

class ChangeTracer(object):
    """Algorithm for tracing change nodes and dependency topology
    
    """
    
    def __init__(self, nodeTable=TraceNode, linkTable=TraceLink):
        self.nodeTable = nodeTable
        self.linkTable = linkTable

    def traceChange(self, handleNode):
        """Algorithm for tracing change nodes and dependency topology
        
        @param handleNode: function to handle changed node
        """
        # step 1. find changed nodes
        changedNodes = self.findChangedNodes()
        # step 2. find all depended nodes
        depenedNodes = self.findDepenedNodes(changedNodes)
        # check there is no cycle
        assert not detectCycle(depenedNodes)
        # step 3. set all depended nodes as changed
        self.setDepenedNodesToChanged(depenedNodes)
        # step 4. sort changed nodes
        sortedNodes = self.sortChagedNodes(depenedNodes)
        # step 5. update changed nodes in correct order, set changed to false
        self.updateChangedNodes(sortedNodes, handleNode)

    def findChangedNodes(self):
        return self.nodeTable.query.filter_by(changed=True).all()
     
    def findDepenedNodes(self, nodes):
        return getDependedNodes(nodes)
    
    def setDepenedNodesToChanged(self, nodes):
        try:
            #session.begin_nested()
            for node in nodes:
                node.changed = True
            session.commit()
        except:
            session.rollback()
            raise
    
    def sortChagedNodes(self, nodes):
        return sortNodes(nodes)
        
    def updateChangedNodes(self, nodes, handleNode):
        for node in nodes:
            handleNode(node)
            try:
                #session.begin_nested()
                node.changed = False
                session.commit()
            except:
                session.rollback()
                raise
        
__all__ = [
    'TraceNode',
    'TraceLink',
    'sortNodes',
    'detectCycle',
    'ChangeTracer'
]