dependency_graph.py

__author__    = 'Bojan Delic <bojan@delic.in.rs>'
__date__      = 'Jan 11, 2013'
__copyright__ = 'Copyright (c) 2013 Bojan Delic'


class DependencyGraphException(Exception): pass

class Node(object):
    ''' Represents single node in graph '''
    
    def __init__(self, project):
        if isinstance(project, dict):
            self.depends_on = project['depends_on']
            self.name       = project['name']
            self.group      = project['group']
        else:
            self.depends_on = project.depends_on
            self.name       = project.name
            self.group      = project.group
        self.dependant = set()
        self.requires  = set()
            
    def __str__(self):
        return "<Name: %s, NodeGroup: %s>" % (self.name, self.group)
    
    __repr__ = __str__
        
class NodeGroup(object):
    ''' Represents groupe of nodes that form single graph '''
    
    def __init__(self, name, projects):
        self.name  = name  
        self.nodes = {n.name:n for n in map(Node, projects)}
        self._resolve_dependencies()
        self.levels = self._populate_levels()
        
    def __iter__(self):
        return self.levels.__iter__()
    
    def __getitem__(self, key):
        return self.levels[key]
    
    def _populate_levels(self):
        levels = []
        nodes = self.nodes.values()
        while len(nodes) > 0:
            if len(levels) == 0:
                first_level = set(filter(lambda n: len(n.requires) == 0, nodes))
                if len(first_level) == 0:
                    raise DependencyGraphException('No root nodes - probably circular dependencies')
                levels.append(first_level)
            else:
                next_level = filter(lambda n: n.requires.issubset(reduce(set.union, levels)), nodes)
                levels.append(set(next_level))
            map(nodes.remove, levels[-1])
        return levels
    
    def _resolve_dependencies(self):
        for  node in self.nodes.values():
            for dep in node.depends_on:
                try:
                    node.requires.add(self.nodes[dep])
                    self.nodes[dep].dependant.add(node)
                except KeyError as e:
                    raise DependencyGraphException(e.message)
        
    def __str__(self):
        return '<Name: %s, Nodes: [%s]>' % (self.name, ', '.join(self.nodes))
    
    __repr__ = __str__
    
class DependencyGraph(object):
    ''' Dependency graph of nodes. '''
    
    def __init__(self, projects):
        nodes = map(Node, projects)
        group_names = set((n.group for n in nodes))
        self.groups = {}
        for group in group_names:
            self.groups[group] = NodeGroup(group, filter(lambda n: n.group == group, nodes))

        self.nodes = {n.name:n for n in map(Node, projects)}
        print self.groups
        
    def __getitem__(self, key):
        return self.groups[key]

    def __iter__(self):
        return self.groups.values().__iter__()
    
    
def main():
    projects = [
        {'name': 'p4', 'depends_on': ['p2', 'p3'], 'group': 'g1'},
        {'name': 'p1', 'depends_on': [], 'group': 'g1'},
        {'name': 'p2', 'depends_on': ['p1'], 'group': 'g1'},
        {'name': 'p3', 'depends_on': ['p1'], 'group': 'g1'},
        {'name': 'p2', 'depends_on': [], 'group': 'g2'},
    ]
    g = DependencyGraph(projects)
    print g['g1']
    for group in g:
        print group.name.upper()
        for levels in group:
            pprint.pprint(levels)
    
if __name__ == '__main__':
    main()