Modelling source file dependencies with a graph in Python

graph.py

# -*- coding: utf-8 -*-
"""A very basic general graph library."""

from __future__ import print_function

__all__ = ('Edge', 'Graph', 'Node')

import uuid


class Edge:
    def __init__(self, v, w, value):
        self.v = v
        self.w = w
        self.value = value

    def __repr__(self):
        return "Edge" + repr((self.v.label, self.w.label, self.value))


class Node(dict):
    def __init__(self, label, *args, **kwargs):
        self.label = label
        self.id = uuid.uuid4()
        super().__init__(*args, **kwargs)

    def __repr__(self):
        return 'Node(label={}, id={})'.format(self.label, self.id.hex)

    def __eq__(self, other):
        return self.id == other.id

    def __ne__(self, other):
        return self.id != other.id

    def __hash__(self):
        return self.id.int


class Graph(dict):
    def __init__(self, *args, **kwargs):
        self._edges = {}
        super().__init__(*args, **kwargs)

    def add_node(self, node):
        label = (node.label if isinstance(node, Node) else node)
        if label in self:
            return self[label]

        if not isinstance(node, Node):
            node = Node(node)

        self[node.label] = node
        return node

    def remove_node(self, node):
        if not isinstance(node, Node):
            node = self[node]

        for edge in list(self.get_edges(node)):
            self.remove_edge(edge)

        del self[node.label]

    def add_edge(self, v, w=None, value=None):
        if isinstance(v, Edge):
            edge = v
            v = edge.v
            w = edge.w
        else:
            assert isinstance(v, Node)
            assert isinstance(w, Node)
            edge = Edge(v, w, value)

        self._edges[(v.label, w.label)] = edge
        return edge

    def remove_edge(self, edge, w=None):
        if not isinstance(edge, Edge):
            assert w is not None
            edge = self.get_edge(edge, w)

        del self._edges[(edge.v.label, edge.w.label)]

    def nodes(self):
        return self.values()

    def edges(self):
        return self._edges.values()

    def get_edge(self, v, w):
        try:
            return self._edges[(v.label if isinstance(v, Node) else v,
                                w.label if isinstance(w, Node) else w)]
        except KeyError:
            return None

    def get_edges(self, node, value=None):
        label = node.label if isinstance(node, Node) else node
        return (edge for key, edge in self._edges.items()
                if label in key and (value is None or edge.value == value))


def main(args):
    from pprint import pformat

    v = Node('Berlin')
    print("New node:", v)
    w = Node('Muenchen')
    print("New node:", w)
    x = Node('Hamburg')
    print("New node:", x)
    e = Edge(v, w, 2)
    print("New edge:", e)
    g = Graph()
    g.add_node(v)
    g.add_node(w)
    g.add_node(x)
    g.add_edge(e)
    g.add_edge(w, x, 3)
    g.add_edge(v, x, 1)
    print("Graph:", pformat(g))
    print("Get edge Berlin-Muenchen:", g.get_edge(v, w))
    print("Remove edge Berlin-Muenchen.")
    g.remove_edge(e)
    print("Graph nodes:", pformat(g.nodes()))
    print("Graph edges:", pformat(g.edges()))
    print("Nodes connected to 'Hamburg':", pformat([e.v for e in g.get_edges('Hamburg')]))
    print("Remove node Muenchen.")
    g.remove_node('Muenchen')
    print("Graph:", pformat(g))


if __name__ == '__main__':
    import sys
    main(sys.argv[1:])

sass_graph.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import graph


DEPENDENCIES = [
    ("main.css", "layout.scss"),
    ("main.css", "colors.scss"),
    ("main.css", "fonts.scss"),
    ("main.css", "components.scss"),
    ("components.scss", "header.scss"),
    ("components.scss", "footer.scss"),
    ("frontpage.scss", "footer.scss"),
    ("frontpage.scss", "components.scss"),
]


class DependencyGraph(graph.Graph):
    def add_dependency(self, v, w):
        v = self.add_node(v)
        w = self.add_node(w)
        self.add_edge(v, w)

    def get_leaves(self, node, level=0):
        if not isinstance(node, graph.Node):
            node = self[node]

        deps = [edge for edge in self.get_edges(node) if edge.v is not node]

        if deps:
            for dep in deps:
                yield from self.get_leaves(dep.v, level + 1)
        elif level > 0:
            yield node


g = DependencyGraph()

for v, w in DEPENDENCIES:
    g.add_dependency(v, w)

print(set(g.get_leaves("footer.scss")))
print(set(g.get_leaves("components.scss")))
print(set(g.get_leaves("fonts.scss")))