view python/ppci/codegen/graph.py @ 312:2c9768114877

Added cool logging formatter
author Windel Bouwman
date Mon, 16 Dec 2013 17:58:15 +0100
parents 6753763d3bec
children e9fe6988497c
line wrap: on
line source


class Graph:
    """
       Generic graph base class.
       Can dump to graphiz dot format for example!
    """
    def __init__(self):
        self.nodes = set()
        self.edges = set()

    def addNode(self, n):
        self.nodes.add(n)

    def delNode(self, n):
        self.nodes.remove(n)

    def addEdge(self, n, m):
        """ Add an edge from n to m """
        self.edges.add((n, m))
        self.edges.add((m, n))

    def hasEdge(self, n, m):
        return (n, m) in self.edges

    def delEdge(self, n, m):
        self.edges.remove((n, m))
        self.edges.remove((m, n))

    def adjecent(self, n):
        """ Return all nodes with edges to n """
        # TODO: this can be optimized for speed:
        return set(m for m in self.nodes if self.hasEdge(n, m))

    def to_dot(self, f):
        """ Generate graphviz dot representation """
        for n in self.nodes:
            print('  {} [label="{}" shape=box3d];'.format(id(n), n), file=f)
        for n, m in self.edges:
            print('  {} -> {};'.format(id(n), id(m)), file=f)


class Node:
    """
       Node in a graph.
    """
    def __init__(self, g):
        self.g = g
        self.addDegree = 0    # Hack to increase degree

    @property
    def Adjecent(self):
        return self.g.adjecent(self)

    @property
    def Degree(self):
        return len(self.Adjecent) + self.addDegree


class DiGraph(Graph):
    """
        Directed graph.
    """
    def addEdge(self, n, m):
        """ Add an edge from n to m """
        self.edges.add((n, m))

    def hasEdge(self, n, m):
        return (n, m) in self.edges

    def successors(self, n):
        return set(m for m in self.nodes if self.hasEdge(n, m))

    def predecessors(self, n):
        return set(m for m in self.nodes if self.hasEdge(m, n))


class DiNode(Node):
    @property
    def Succ(self):
        return self.g.successors(self)

    @property
    def Pred(self):
        return self.g.predecessors(self)