A General Algorithm for Performing Graph Reductions

P. Boothe
Computer Science Dept.
University of Oregon
peter@cs.uoregon.edu
http://soy.dyndns.org/~peter/projects/research/reduction/

1 Introduction

Graph theory and testing graph properties have proven to be fertile grounds for algorithms research, with applications to networks, digital design, and even analysis of social hierarchies. Graphs with a particular property are often essential to guarantee a correct design, and some algorithms that are exponential time in the general case can be run in polynomial time on certain classes of graphs. Many properties are very easy to test for - whether a graph is connected can be solved with a simple depth first search, for example - but testing for other properties, such as Hamiltonian Path, has been shown to be NP-Hard.

The ideal algorithm would take a description of the desired property in some formal language, and a graph. Then it would quickly respond with true or false based on whether the graph has the desired property. Unfortunately, since testing for many properties is NP-Hard, this algorithm is currently unknown and possibly nonexistant. One way to get around this is to restrict the language so that it cannot describe an NP-Hard property. One such restriction is monadic second order logic, which is a restriction of second order logic to quantifiers over functions of arity at most one. It was shown in [1] that any property with bounded treewidth described in this language was necessarily testable in linear time with respect to the size of the input graph. Despite this surprising time bound, the language still has quite a bit of expressive power. Many properties, including outerplanarity, 3-connectedness, partial 3-tree, planar partial 3-tree, and planar partial 2-tree can be expressed.

The existence of a time-efficient algorithm was then proven by showing (non-constructively) that any property describable in monadic second order logic necessarily has a corresponding graph reduction system and then showing (non-constructively again) that each reduction system necessarily has a linear time algorithm for testing whether a graph has the property corresponding to the original property. A graph reduction system is a set of reduction rules, which are pairs of labeled graphs, each vertex of which is also tagged as restricted or unrestricted, and a set of base graphs which we refer to as reducts. Whenever an instance of the left graph of any of the reduction rules is found as a subgraph of our tested graph, subject to the constraint that the restricted vertices have the same degree in the original graph as they do in the reduction rule, we apply the corresponding reduction rule by replacing the subgraph with the other graph in the rule. Once we can no longer apply any reduction rules we test whether the reduced graph is isomorphic to any of our reducts. If our graph is isomorphic to a reduct, then the graph has the desired property. Otherwise it does not. A sample graph reduction system is shown in Figure 1, with the restricted nodes colored solid, and the unrestricted ones hollow. The labeling of the graph is implied by the positions of each node. The definition of a graph reduction system does not imply an ordering on reduction rules, thus any graph with the the desired property will reduce to a valid reduct, no matter the order in which the reduction rules are applied.

Figure 1: A sample graph reduction system for partial 3-trees. Solid black vertices are restricted, solid white ones are unrestricted, and the only reduct (not shown) is the empty graph

More formally, a graph reduction system $S$ consists of a set of reduction rules $S_U$, and a set of irreducible reducts $S_I$. A reduction rule $U \in S_U$ is two graphs $G_{left} = (V_{left},E_{left})$ and $G_{right} = (V_{right},E_{right})$ such that the size of $G_{right}$ is strictly less than the size of $G_{left}$ for some measure of graph size.¹Furthermore, for each $V_{left}$ we have a set $E \subseteq V_{left}$ that we label restricted. Whenever we see a subgraph of our input graph $G = (V,E)$, that is isomorphic to a $G_{left}$ in rule $L$ via some mapping $m$, and $\forall v$ such that $m(v) \in E$ it is true that $d_G(v) = d_{G_{left}}(m(v))$ where $d_G$ is the degree function for $G$, we can reduce our graph by reduction rule $U$ by setting

$$V' = (V \setminus \{ v \vert m(v) \in E \}) \cup \{v \vert m(v) \in V_{right}\}$$ (1)

$$E' = (E \setminus \{(u,v) \vert (m(u), m(v)) \in E_{left}) \cup \{(u,v) \vert (m(u), m(v) \in E_{right} \}.$$ (2)

We then repeat our search on $G' = (V', E')$ until no chances to apply a reduction rule can be found. We then accept the graph it is isomorphic to some element of $S_I$ and reject it otherwise.

Several things are surprising about these systems. The first is that the order in which rules are applied does not matter! In a graph reduction system, it does not matter what order you apply the rules in - if a graph has the property under test, it will be reduced to some reduct in $S_I$ no matter what the rule order is. The second is that these systems have enough power to test any MSOL bounded treewidth property. The power of these systems should not be too surprising, however, as there is a very deep connection between graph reduction systems and graph grammars.

Graph grammars are tools used to create graphs that have a particular property, and graph reduction systems can be analogized to tools that parse graphs to check for a property. Further extending the analogy, it is sometimes useful to think of the restricted vertices as the terminal symbols of a production grammar, and the reducts as start expressions for the production of graphs. Graph grammars have been written about extensively, and their relation to graph reduction systems can be found many places, including [3].

2 Algorithm

The goal of Algorithm 1 is to take each vertex with a degree no larger than the largest degree of any restricted vertex, and attempt to place that vertex in each restricted place in each reduction rule. Since it does not matter what order we apply reductions in, we apply them greedily. Every time it is possible to reduce the graph, we do so. Our prof of correctness will then follow from the fact that we never stop trying to reduce the graph until there are no reductions possible.

For the purposes of the algorithm, it will be necessary to talk about the border nodes of a restricted vertex. These are exactly the unrestricted vertices surrounding the subgraph of restricted nodes containing that restricted vertex.

The running time of our algorithm is initially hard to see for two reasons. Partially because it hinges upon the time it takes to perform the operations SET and ACCESS on an associative array, and partially because when we talk about the runtime of our algorithm, we talk about its parameterized complexity[2], which has the expressiveness to deal with the two inputs separately.

Abstracting away issues of SET and ACCESS time, and simply referring to $\max(t_{SET}, t_{ACCESS})$ as $t_M$, we will prove the following theorem:

Theorem 1 (Running Time of Algorithm 1)   Algorithm 1 runs in $O(n*t_M)$ time with respect to the size of the graph under test.

Proof. We begin by noting that the initial $n$ time is created by the act of reading in the graph. Then, we put in the queue all vertices of degree no larger than the largest restricted vertex, which takes $O(\vert V\vert)$ time. Then, inside the while() loop, we note that the number of iterations of every for() loop is bounded above by a constant with respect to the input graph. Therefore, we execute SET and ACCESS on $M$ at most a constant number of times each iteration of our main loop.

Every iteration of that main loop either applies a reduction or it does not. If the vertex under test does not complete a reduction rule, then we simply record any rules that it matched part of, and never look at it again unless its degree changes. If it does complete a reduction rule, then that reduction rule is applied to the graph, making it smaller. At the same time the rule is applied, all vertices whose degree has changed and is sufficiently small are put into the search queue if they were not there already. To get our $O(n)$ bound on the number of while() loop iterations, we count the maximum number of iterations that a problematic graph could force us to go through.

Since every increase in queue size is accompanied by a corresponding decrease in graph size, we can have at most $n$ queue size increases before the graph has been reduced to nothing. These increases in queue size never increase the queue by more than a constant (again, with respect to the input graph) because the rules are constant size with respect to the graph. Calling the maximum size increase $k$, we can see that the greatest number of iterations we could be forced to do is $O(n*k) = O(n)$. Thus, we will run through the main loop $O(n)$ times, and each iteration takes $O(1 + t_M)$ time, for a total time bound of $O(n*t_M)$. $\qedsymbol$

Various implementations of $M$ have different effects on our runtime, with the more obvious balanced tree or hashtable approaches leading to $O(n \lg nP$ and $O(n)$ expected time and $O(n^2)$ worst case, respectively. Tarjan describes in [4] a method of implementing an associative array with $O(1)$ access time, which leads to our best case linear time bound, but it is unlikely that this would be used in practice due to its extremely large space requirements.

All this time, however, we have been ignoring the effects of our reduction system on the runtime. If we hold our input graph fixed, and only look at the reduction system's affect on the runtime, then simply counting up the maximum bounds of each internal for() loop we get a runtime of $O(r*p*s^d*t_{gi}(s)$, where $r$ is the number of reduction rules, $p$ is the maximum number of subgraphs of restricted components in a rule, $s$ is the maximum size of these subgraphs, $d$ is the maximum degree of a restricted vertex, and $t_{gi}$ is the time it takes to perform graph isomorphism on a graph of the given size. To get a runtime in terms of only two factors, we concentrate on the maximum subgraph size and call it $k$. The best known graph isomorphism solutions have a running time of $O(2^k)$ where $k$ is the size of the graph being tested. On an intuitive level, graph reduction systems have many rules, but it is only when the rules get big that the problem becomes really hard. Choosing subgraph size as our parameter allows us to do several things. First of all, we can ignore $r$ and $p$, then we can note that the largest $s$ or $d$ can be is $k$. Which makes the runtime of the algorithm $O(2^k*k^k*n*t_M)$. Which, as described earlier, we can make as low as $O(n)$, but will probably be $O(n \lg n)$ in most implementations.

3 Conclusion

We have described and proven correct algorithm that will work for any reduction system. In addition, we also have an implementation that works in $O(\vert V\vert+\vert E\vert)$ expected time that can be downloaded from http://soy.dyndns.org/~peter/projects/research/reduction/linear. The algorithm works and, despite an intimidating looking runtime, is useful for testing many properties.

4 Further Work

Automatic discovery of reduction rules from a monadic second order logic description remains an open problem, as does the automatic generation of heuristics that might help with subgraph isomorphism. Also, figuring out whether or not an MSOL property has bounded treewidth is not always easy, and it would be useful if that was automated as well.

Bibliography

1

Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese.
An algebraic theory of graph reduction.
Journal of the ACM (JACM), 40(5):1134-1164, 1993.

2

R. G. Downey and M. R. Fellows.
Parameterized Complexity.
Springer, 1999.

3

H Ehrig, G Engels, H-J Kreowski, and G Rozenberg.
Handbook of Graph Grammand and Computing by Graph Transformation.
World Scientific, 1997.

4

R. E. Tarjan.
Data Structures and Network Algorithms.
SIAM, 1983.

5 combo.py

#!/usr/bin/env python2.2

from __future__ import generators

def getAllPermutations(seq):
    """ Erlich's Swap Method - from TAOCP Book 4 pre-facile 2
    http://www-cs-staff.stanford.edu/~knuth/taocp.html """
    seq = seq[:]  # Work on a copy of what we are given
    n = len(seq)

    b = [i for i in range(n)]
    c = [0 for i in range(n+1)]

    while 1:
        yield seq

        k = 1
        if c[k] == k:
            while not c[k] < k:
                c[k] = 0
                k = k+1

        if n == k:
            return
        else:
            c[k] = c[k] + 1

        seq[b[k]], seq[0] = seq[0], seq[b[k]]

        j = 1
        k = k-1
        while j < k:
            b[j], b[k] = b[k], b[j]
            j = j+1
            k = k-1


def getAllSubsets(seq, size):
    "Generate all subsets of a particular size"
    assert size <= len(seq)
    seq = seq[:]

    # This algorithm comes from Knuth's third pre-facile for volume 4
    # It is very dense.
    c = [ 0 ] + range(size) + [ len(seq), 0 ]
    while 1:
        yield map(lambda x: seq[x], c[1:size+1])

        j = 1
        while c[j]+1 == c[j+1]:
            c[j] = j-1
            j = j+1
        if j > size:
            return

        c[j] = c[j]+1



def getAllSubsetPermutations(seq, size):
    "Generate all permutations of all subsets of the indicated size."
    assert size <= len(seq)
    for s in getAllSubsets(seq, size):
        for c in getAllPermutations(s):
            yield c
    

if __name__ == '__main__':
    count = 0
    for c in getAllPermutations(range(5)):
        count = count + 1
    assert count == 5*4*3*2*1

    count = 0
    for s in getAllSubsets(range(7), 5):
        count = count + 1
    assert count == (7*6)/(2*1)

    count = 0
    for sp in getAllSubsetPermutations(range(7), 5):
        count = count + 1
    assert count == (7*6*5*4*3)

    print "All tests passed!"

6 graphs.py

#!/usr/bin/env python2.2

debug = 0
def p(*s):
    "Print stuff if we are in debug mode.  Don't otherwise"
    if debug:
        import sys
        sys.stderr.write(reduce(lambda x,y: x+' '+str(y), s, "")[1:] + "\n")

from combo import getAllPermutations

class Edge:
    "An edge in a graph"
    def __init__(self, v1,v2):
        self.v1 = v1
        self.v2 = v2

    def __str__(self):
        return( str(self.v1)+' -- '+str(self.v2))

class Graph:
    def __init__(self, vertices, edges):
        """Creates an undirected graph with vertices and edges.  All vertex
        objects must be hashable (and therefore immutable) objects, but they
        don't have to be strings.
        
        Make sure that every vertex in the edge list is also in the vertex
        list, otherwise an exception will be thrown.
        """
        for e in edges:
            assert e.v1 in vertices
            assert e.v2 in vertices
            
        self.degrees = {}
        self.adjacent = {}

        self.e_cache = edges
        self.v_cache = vertices

        for v in vertices:
            self.degrees[v] = 0
            self.adjacent[v] = {}

        for e in edges:
            self.degrees[e.v1] = self.degrees[e.v1] + 1
            self.adjacent[e.v1][e.v2] = None

            self.degrees[e.v2] = self.degrees[e.v2] + 1
            self.adjacent[e.v2][e.v1] = None

    def remove_edge(self, v1, v2):
        assert self.are_adjacent(v1,v2), \
                "Can't remove non-existent edge: " + str(v1) + " -- " + str(v2)

        self.degrees[v1] = self.degrees[v1] - 1
        self.degrees[v2] = self.degrees[v2] - 1
        del self.adjacent[v1][v2]
        del self.adjacent[v2][v1]
        self.e_cache = []
        
    def remove_vertex(self, vertex):
        for v in self.adjacent[vertex]:
            del self.adjacent[v][vertex]
        del self.adjacent[vertex]
        del self.degrees[vertex]

    def add_edge(self, v1, v2):
        if not self.are_adjacent(v1,v2):
            self.e_cache.append(Edge(v1,v2))
            self.adjacent[v1][v2] = None
            self.adjacent[v2][v1] = None
            self.degrees[v1] += 1
            self.degrees[v2] += 1
        else:
            p(v1, "and", v2, "are already adjacent!")
            p(self.adjacent)
    
    def are_adjacent(self, v1, v2):
        "Return the number of connections between v1 and v2"
        assert self.adjacent[v1].has_key(v2) == self.adjacent[v2].has_key(v1)
        return self.adjacent[v1].has_key(v2)

    def isIsomorphic(self, other):
        """A combinatorial approach to graph isomorphism.  This is really slow,
        but that's okay because it is only used on graphs of bounded size."""

        if len(self.getVertices()) != len(other.getVertices()):
            return 0
        if len(self.getEdges()) != len(other.getEdges()):
            return 0

        for ordering in getAllPermutations(self.getVertices().keys()):
            mapping = {}
            other_vlist = other.getVertices().keys()
            for i in range(len(ordering)):
                mapping[ordering[i]] = other_vlist[i]

            error = 0
            for v in self.getVertices():
                if self.degrees[v] != other.degrees[mapping[v]]:
                    error = 1
                    break

                for n in self.adjacent[v]:
                    if mapping[n] not in other.adjacent[mapping[v]]:
                        error = 1
                        break

            #If we didn't find anything wrong
            if not error:
                return 1
        return 0
            

    def getEdges(self):
        #if not self.e_cache:
        if 1:
            self.e_cache = []
            dealt_with = {}
            for fr in self.getVertices():
                dealt_with[fr] = None
                for to in filter(lambda x: not dealt_with.has_key(x), \
                        self.adjacent[fr]):
                    self.e_cache.append(Edge(fr, to))
        return self.e_cache
            

    def getVertices(self):
        return self.adjacent

    def __str__(self):
        """Returns a string with the title of %s and the label %s.  Use the %
        operator to either further flesh the string out, or just print it out
        as-is.
        """

        p(self.adjacent)
        p(map(str, self.getEdges()))
        s = "graph \"%s\" {\n"

        for node in self.getVertices():
            s = s + "\t" + str(node) + " ;\n"

        for edge in self.getEdges():
            s = s + "\t" + str(edge) + " ;\n"

        s = s + """
    label = "%s";
}
"""
        return s


def readGraph(file):
    """Read a graph from the passed in open file"""
    lines = file.readlines()
    vertices = lines[0].split()
    edges = []
    for edge in lines[1:]:
        edge = edge.split()
        if len(edge) == 3:
            edges.append(Edge(edge[0], edge[2]))

    return Graph(vertices, edges)



def printGraph(graph, title):
    """Prints out a graph in a form suitable for input into graphviz stuff"""
    print str(graph) % (title, title)

7 membership.py

#!/usr/bin/env python2.2
import sys

debug = 0
def p(*s):
    "Print stuff if we are in debug mode.  Don't otherwise"
    if debug:
        import sys
        sys.stderr.write(reduce(lambda x,y: x+' '+str(y), s, "")[1:] + "\n")

# argument parsing - you must tell us what file to get the reduction from
assert len(sys.argv) > 1 and len(sys.argv[1]) >  0, """
Error - did not supply an argument.

usage:
    %s [-P] reductionFileWithoutDotPy < file.graph | neato -Tps > file.ps
""" % (sys.argv[0],)
shouldPrint = 0
if sys.argv[1] == '-P' or (len(sys.argv) == 3 and sys.argv[2] == '-P'):
    shouldPrint = 1
if sys.argv[1] == '-P':
    del sys.argv[1]

exec "from "+sys.argv[1]+" import reductions, propertyName, representatives"

import reduction
from graphs import readGraph, printGraph

graph = readGraph(sys.stdin)
maxSmallDegree = max(map(lambda x: x.getMaxBlackDegree(), reductions))
for r in reductions:
    r.maxdegree = maxSmallDegree
list = filter(lambda x: graph.degrees[x] <= maxSmallDegree, graph.getVertices())

titleString = "Original graph"
count = 0

printGraph(graph, titleString)

while list:
    v = list.pop()
    if v not in graph.getVertices():
        continue

    p(v)
    
    for reduction in reductions:
        p(reduction.name)
        small = reduction.process(v, graph)
        if small != None:
            for s in small:
                if s not in list:
                    list.append(s)

            count = count + 1
            if shouldPrint:
                printGraph(graph, \
                        "After applying %s -- %d" % (reduction.name, count))
            break

inSet = 0
for rep in representatives:
    if rep.isIsomorphic(graph):
        #printGraph(rep, "Representative")
        inSet = 1
        break

if inSet:
    sys.stderr.write("It was a " + propertyName + "\n")
else:
    sys.stderr.write("It wasn't a " + propertyName + "\n")

8 outerplanar.py

#!/usr/bin/env python2.2

from graphs import Graph
from graphs import Edge as E

from reduction import Reduction

# some convenience variables to save typing lots of quotes:
a="a"; b="b"; c="c"; d="d"; e="e"; f="f"; g="g"; h="h"; i="i"; j="j"; k="k";
l="l"; m="m"; n="n"; o="o"; p="p"; q="q"; r="r"; s="s"; t="t"; u="u"; v="v";
w="w"; x="x"; y="y"; z="z";

p_2_1_2 = Reduction(
    "p_2(1,2)",
    Graph("lrm", [E(l,r), E(l,m), E(m,r)]),
    "m",
    Graph("lrm",[E(l,m), E(m,r)])
)

s_2_1_2 = Reduction(
    "s_2(1,2)", 
    Graph("labr", [E(l,a), E(a,b), E(b,r)]),
    "ab",
    Graph("lbr", [E(l,b), E(b,r)])
)

s_2_1_3a = Reduction(
    "s_2(1,3)a", 
    Graph("ltbmar", [E(l,t), E(l,b), E(t,m), E(b,m), E(m,a), E(a,r)]),
    "tbma",
    Graph("ltbmr", [E(l,t), E(l,b), E(t,m), E(b,m), E(m,r)])
)

s_2_1_3b = Reduction(
    "s_2(1,3)b", 
    Graph("cdlrtb", [E(c,l), E(l,t), E(l,b), E(t,r), E(b,r), E(r,d)]),
    "lrtb",
    Graph("ctbrd", [E(c,t), E(c,b), E(t,r), E(b,r), E(r,d)])
)

s_2_3_3 = Reduction(
    "s_2(3,3)",
    Graph("lmrabcd", \
          [E(l,a), E(l,b), E(a,m), E(b,m), E(m,c), E(m,d), E(c,r), E(d,r)] ),
    "mabcd",
    Graph("lrabm", [E(l,a), E(l,b), E(b,m), E(a,m), E(m,r)])
)

pendant = Reduction(
    "pendant",
    Graph("lr", [E(l,r)]),
    "l",
    Graph("r", [])
)

singleton = Reduction(
    "singleton",
    Graph("a", []),
    "a",
    Graph([], [])
)


propertyName = "Outerplanar Graph"
reductions = [ p_2_1_2 , s_2_1_2, s_2_1_3a, s_2_1_3b, s_2_3_3, pendant, \
               singleton ]
representatives = [ Graph([],[]) ]

9 partial3tree.py

#!/usr/bin/env python2.2

from graphs import Graph
from graphs import Edge as E

from reduction import Reduction

# some convenience variables to save typing lots of quotes:
a="a"; b="b"; c="c"; d="d"; e="e"; f="f"; g="g"; h="h"; i="i"; j="j"; k="k";
l="l"; m="m"; n="n"; o="o"; p="p"; q="q"; r="r"; s="s"; t="t"; u="u"; v="v";
w="w"; x="x"; y="y"; z="z";

isolated = Reduction(
    "isolated",
    Graph(["point"], []),
    ["point"],
    Graph([],[])
)

pendant = Reduction(
    "pendant", 
    Graph(["body", "leaf"], [E("body", "leaf")]),
    ["leaf"],
    Graph(["body"], [])
)

series = Reduction(
    "series", 
    Graph("lmr", [E(l, m), E(m, r)]),
    "m",
    Graph("lr", [E(l, r)])
)

triangle = Reduction(
    "triangle",
    Graph("tmlr", [E(t,m), E(m,l), E(l,r), E(r,m)]),
    "m",
    Graph("tlr", [E(t,l), E(t,r), E(l,r)])
)

buddy = Reduction(
    "buddy",
    Graph("tmlrb", [E(t,m), E(m,l), E(m,r), E(t,b), E(l,b), E(r,b)]),
    "mb",
    Graph("tlr", [E(t,l), E(t,r), E(l,r)])
)

cube = Reduction(
    "cube",
    Graph("tlrabcd", 
        [E(a,t),E(t,b),E(b,r),E(r,c),E(c,l),E(l,a),E(a,d),E(b,d),E(c,d)]
    ),
    "abcd",
    Graph("tlr", [E(t,l), E(t,r), E(l,r)])
)


propertyName = "Partial 3-Tree"
reductions = [isolated, pendant, series, triangle, buddy, cube]
representatives = [ Graph([],[]) ]

10 planar3Tree.py

#!/usr/bin/env python2.2

from graphs import Graph
from graphs import Edge as E

from reduction import Reduction

# some convenience variables to save typing lots of quotes:
a="a"; b="b"; c="c"; d="d"; e="e"; f="f"; g="g"; h="h"; i="i"; j="j"; k="k";
l="l"; m="m"; n="n"; o="o"; p="p"; q="q"; r="r"; s="s"; t="t"; u="u"; v="v";
w="w"; x="x"; y="y"; z="z";

r2 = Reduction(
    "r_2", 
    Graph(["body", "leaf"], [E("body", "leaf")]),
    ["leaf"],
    Graph(["body"], [])
)

s2 = Reduction(
    "s_2", 
    Graph("lmr", [E(l, m), E(m, r)]),
    "m",
    Graph("lr", [E(l, r)])
)

slash32 = Reduction(
    "//_3,2",
    Graph("tbrm", [E(t,b), E(t,r), E(t,m), E(b,m), E(r,m)]),
    "m",
    Graph("tbrm", [E(t,r), E(t,m), E(b,m), E(r,m)])
)

s33 = Reduction(
    "s_3,3",
    Graph("lrmnb", [E(l,m), E(m,b), E(m,n), E(b,n), E(n,r)]),
    "mn",
    Graph("lbrm", [E(l,r), E(l,m), E(b,m), E(r,m)])
)

s33alt = Reduction(
    "s_3,3 (alternate)",
    Graph("lrbmnt", 
          [E(l,t), E(t,r), E(l,m), E(r,n), E(m,t), E(n,t), E(m,b), E(n,b)]
    ),
    "mnt",
    Graph("lbrm", [E(l,r), E(l,m), E(b,m), E(r,m)])
)

s3 = Reduction(
    "s_3",
    Graph("lrbmnot", 
          [ E(l,t), E(t,r), E(r,n), E(n,b), E(b,m), E(m,l),
            E(m,o), E(n,o), E(o,t) ]
    ),
    "mnot",
    Graph("lbrm", [E(l,r), E(l,m), E(b,m), E(r,m)])
)

s3alt = Reduction(
    "s_3 (alternate)",
    Graph("lrbmnot", 
         [ E(l,t), E(t,r), E(r,n), E(n,b), E(b,m), E(m,l),
           E(m,o), E(n,o), E(o,t), E(o,b) ]
    ),
    "mnot",
    Graph("lbrm", [E(l,r), E(l,m), E(b,m), E(r,m)])
)

propertyName = "Planar 3-Tree"
reductionRules = [r2, s2, slash2, slash32, s33, s33alt, s3, s3alt ]
representatives = [ Graph([],[]), Graph([a],[]) ]

11 reduction.py

#!/usr/bin/env python2.2

from __future__ import generators
from combo import getAllSubsetPermutations

debug = 0
def p(*s):
    "Print stuff if we are in debug mode.  Don't otherwise"
    if debug:
        import sys
        sys.stderr.write(reduce(lambda x,y: x+' '+str(y), s, "")[1:] + "\n")

from graphs import Graph, Edge

verticesToMatches = {}

class Reduction:
    """A reduction is two graphs, the second one of which is smaller, which has
    some vertices whose degree is fully specified, and other vertices whose
    degree is only given a lower bound.
    """

    def __init__(self, name, fromgraph, restrictedNodes, tograph):
        """Initialize a new reduction.  Give the nodes in fromgraph and tograph
        the same names.  In particular, all names in tograph have to be in
        fromgraph.  Also, You need at least some restricted nodes.
        
        The big idea here is to break the graph up into contiguous black
        regions, rather than single nodes.
        """

        self.name = name
        self.fr = fromgraph
        self.restrict = restrictedNodes
        self.to = tograph
        self.matches = {}
        self.maxBlackDegree = -1
        self.maxdegree = self.getMaxBlackDegree()
        self.vToM = {}
        verticesToMatches[self] = self.vToM

        # Find the contiguous black node regions
        self.regions = []
        for node in self.restrict:
            if node in reduce(lambda x,y: x+list(y), self.regions, []):
                continue

            region = [ node ]
            i = 0
            while i < len(region):
                if region[i] not in self.restrict:
                    i = i+1
                    continue
                newNodes = filter(lambda x: x not in region, \
                        self.fr.adjacent[region[i]])
                if newNodes:
                    region = region + newNodes
                i = i+1

            self.regions.append(tuple(region))

        # Make sure of some properties
        assert self.restrict, "You need to have some black nodes"
        for v in self.restrict:
            assert v in self.fr.getVertices(), "Bad restricted node: "+str(v)

        for v in self.to.getVertices():
            assert v in self.fr.getVertices(), "Bad mapping :"+str(v)


    def getMaxBlackDegree(self):
        """Return the maximum degree of a black vertex in this rule"""
        if self.maxBlackDegree == -1:
            self.maxBlackDegree = \
                    max(map(lambda x: self.fr.degrees[x], self.restrict) + [0])
        return self.maxBlackDegree


    def getRegionDepth(self, region):
        """What is the maximum depth of a BFS required to search the entire
        region in question?
        """

        queue = [(region[0], 0)]
        bucket = []
        max = 0
        while queue:
            v, d = queue[0]
            del queue[0]
            bucket.append(v)
            if d > max:
                max = d
            if self.fr.degrees[v] <= self.getMaxBlackDegree():
                for n in filter(lambda x: x not in bucket, \
                                self.fr.adjacent[v].keys()):
                    queue.append((n, d+1))
        return max

    
    def whiteBorderedSearch(self, start, graph, region):
        """Do a breadth first search (that does not cross any white vertices)
        down depth levels.
        """

        depth = self.getRegionDepth(region)
        
        bucket=[]
        queue = [(start, 0)]
        while queue:
            v, d = queue[0]
            del queue[0]

            bucket.append(v)
            p("Reading", v)
            if d < depth and graph.degrees[v] <= self.getMaxBlackDegree():
                for n in filter(lambda x: x not in bucket, \
                                graph.adjacent[v].keys()):
                    queue.append((n, d+1))
        return bucket
                

    def getAllPossibleMatches(self, start, graph, region):
        """Get all possible matches.  Note that this number is bounded, and so
        can be thrown away, despite its potential hugeosity.
        """

        p(start, graph)
        nodes = self.whiteBorderedSearch(start, graph, region)
        if len(nodes) < len(region):
            return
        else:
            mapping = {}
            for n_permute in getAllSubsetPermutations(nodes, len(region)):
                for i in range(len(region)):
                    mapping[region[i]] = n_permute[i]
                yield mapping
                
        

    def verifyMatch(self, match, region, graph):
        "Verify that a particular match does not violate any properties"

        region = list(region)
        for v in match.keys():
            # Make sure it has the right number of connections
            if v in self.restrict:
                if self.fr.degrees[v] != graph.degrees[match[v]]:
                    return 0
            else:
                if self.fr.degrees[v] > graph.degrees[match[v]]:
                    return 0

            # Make sure the connections are to the right place
            for n in filter(lambda x: x in region, self.fr.adjacent[v].keys()):
                if not graph.are_adjacent(match[v], match[n]):
                    return 0
        return 1

    
    def findIndex(self, region):
        "Get the canonical ordering for the external nodes of a region"
        index = []
        for r in self.regions:
            if r == tuple(region):
                continue
            index.extend(filter(lambda x: x in region and x not in index, r))
        index.sort()
        return tuple(index)
    
    def addMatch(self, match, region):
        """Add a match into the database, combine it with any matches it can be
        combined with, and if it can be applied to the graph at hand, then
        return the appropriate mapping"""

        region_l = list(region)
        index = self.findIndex(region)
        m_index = tuple([ match[i] for i in index ])

        external_node_map = (tuple(index), tuple(m_index))

        if self.matches.has_key(external_node_map):
            self.matches[external_node_map].append(match)
        else:
            self.matches[external_node_map] = [ match ]

        for n in match.keys():
            if not self.vToM.has_key(n):
                self.vToM[n] = []
            self.vToM[n].append(match)

        for ext_hc, ext_dyn in self.matches.keys():
            ext_hc_l = list(ext_hc)
            ext_dyn_l = list(ext_dyn)

            all_ok = 1
            for i in range(len(index)):
                if ext_dyn[ext_hc_l.index(range[i])] != m_index[i]:
                    all_ok = 0
                    break
            if not all_ok:
                continue

            for partial_match in self.matches[(ext_hc, ext_dyn)]:
                intersection = filter( \
                        lambda x: (x in match) and (x not in ext_dyn_l), \
                        partial_match.values())
                
                if intersection:
                    continue

                partial_match = partial_match.copy()
                for i in match.keys():
                    partial_match[i] = match[i]

                remaining = filter(lambda x: x not in partial_match.keys(),\
                        self.fr.getVertices())

                if not remaining:
                    return partial_match
                else:
                    remaining = tuple(remaining)
                    if self.matches.has_key(remaining):
                        self.matches[remaining].append(partial_match)
                    else:
                        self.matches[remaining] = [ partial_match ]

        # If we made it to here, nothing matched
        return None


    def apply(self, mapping, graph):
        "Apply this reduction to the graph in a specific place"

        for e in self.fr.getEdges():
            graph.remove_edge(mapping[e.v1], mapping[e.v2])

        # For every black edge that doesn't appear in the final graph
        for v in filter(lambda x: x not in self.to.getVertices(), \
                self.restrict):
            p("Removing", mapping[v])
            graph.remove_vertex(mapping[v])
            for reduction in verticesToMatches.keys():
                if reduction.vToM.has_key(mapping[v]):
                    for m in reduction.vToM[mapping[v]]:
                        del reduction.matches[m]
                    del reduction.vToM[mapping[v]]
            

        for e in self.to.getEdges():
            p("Adding an edge from", mapping[e.v1], "to", mapping[e.v2])
            graph.add_edge(mapping[e.v1], mapping[e.v2])

        return filter(lambda x: graph.degrees[x] <= self.maxdegree, \
                map(mapping.__getitem__, self.to.getVertices()))


    def process(self, v, graph):
        "Take one 'small vertex' from graph and try and place it in each region"

        for region in self.regions:
            # For every possible match (exponential in the size of region)
            for match in self.getAllPossibleMatches(v, graph, region):
                if self.verifyMatch(match, region, graph):
                    mapping = self.addMatch(match, region)
                    if mapping:
                        return self.apply(mapping, graph)

12 tree.py

#!/usr/bin/env python

from graphs import Graph, Edge
from reduction import Reduction

trimLeaf = Reduction("Leaf Trimmer",
        Graph(["tree","leaf"], [Edge("tree","leaf")]), 
        ["leaf"], 
        Graph(["tree"], []))

propertyName = "Tree"
reductions = [ trimLeaf ]

singlePoint = Graph(["single point"], [])

representatives = [ singlePoint ]

About this document ...

A General Algorithm for Performing Graph Reductions

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -html_version 4.0 -numbered_footnotes -no_white -split 0 drp.tex

The translation was initiated by Peter Boothe on 2004-05-25

Footnotes

... size.¹

Most systems have $V_{right} \subset V_{left}$, but that is not required.