Repetitivity.py

"""Repetitivity.py

Repetitivity analysis in graphs: algorithms for taking as input an
edge-labeled graph and finding paths or cycles in which no two
consecutive edges have the same label.

D. Eppstein, July 2005.
"""

from StrongConnectivity import StronglyConnectedComponents
import DFS

class NonrepetitiveGraph:
    """
    Data structure for finding nonrepetitive paths in graphs.
    If G is a digraph, with G[v][w] = a collection of labels
    of the edge from v to w, then NonrepetitiveGraph(G) allows
    us to find paths in G, with a choice of label per edge of
    the path, such that no two consecutive labels are equal.
    
    If NR is a NonrepetitiveGraph instance, then
    - iter(NR) lists the vertices in NR
    - NR[v] lists the labels incident to vertex v
    - cyclic() generates a sequence of triples (v,w,label)
      that can be part of nonrepetitive cycles in NR
    - reachable(v,label) generates a sequence of pairs
      (w,label) that can be reached by nonrepetitive
      paths starting from v with the given label.
    - shortest(v,label,w,label) finds a shortest path between
      the given vertex,label pairs.
    """
    
    def __init__(self,G):
        """
        Initialize from a given graph instance.  The graph G
        should have G[v][w] equal to a collection (list, set, etc)
        of the labels on edges from v to w; this allows us to
        represent multigraphs with differing labels on their
        multiedges.
        
        Data stored in fields of this instance:
        - self.nrg is a transformed unlabeled graph in which paths
          represent nonrepetitive paths in G
        - self.labels is a dictionary mapping vertices to their
          label sets
        """
        self.labels = {}
        for v in G:
            self.labels[v] = set()
            for w in G[v]:
                self.labels[w] = set()
        for v in G:
            for w in G[v]:
                self.labels[v].update(G[v][w])
                self.labels[w].update(G[v][w])
        self.nrg = {}
        for v in self:
            self._gadget(v,self.labels[v])
        for v in G:
            for w in G[v]:
                for L in G[v][w]:
                    self.nrg[v,L,False].add((w,L,True))
    
    def __getitem__(self,v):
        """x.__getitem__(y) <==> x[y]"""
        return self.labels[v]

    def __contains__(self,v):
        """x.__contains__(y) <==> y in x"""
        return v in self.labels

    def __iter__(self):
        """x.__iter__() <==> iter(x)"""
        return iter(self.labels)

    def _gadget(self,v,labels):
        """Create nonrepetitivity gadget for vertex v and given label set."""
        labels = list(labels)
        for L in labels:
            self.nrg.setdefault((v,L,True),set())
            self.nrg.setdefault((v,L,False),set())
        if len(labels) == 1:
            return
        groups = []
        n = len(labels)
        while n > 0:
            if n % 3 == 0:
                grouplen = 3
            else:
                grouplen = 2
            group = labels[n-grouplen:n]
            for L1 in group:
                for L2 in group:
                    if L1 != L2:
                        self.nrg[v,L1,True].add((v,L2,False))
            if len(labels) > 3:
                groups.append(object())
                self.nrg[v,groups[-1],False] = {(v,L,False) for L in group}
                for L in group:
                    self.nrg[v,L,True].add((v,groups[-1],True))
            n -= grouplen
        if len(groups) > 1:
            self._gadget(v,groups)

    def cyclic(self):
        """Yield triples (v,w,label) belonging to all nonrepetitive cycles."""
        components = {}
        for C in StronglyConnectedComponents(self.nrg):
            for v in C:
                components[v] = C
        for v in self:
            for L in self[v]:
                for w,LL,bit in self.nrg[v,L,False]:
                    if components[v,L,False] == components[w,L,True]:
                        yield v,w,L

    def reachable(self,v,L):
        """Yield pairs (w,label) on nonrepetitive paths from v,L."""
        if v not in self or L not in self[v]:
            return
        for w,LL,bit in DFS.preorder(self.nrg,(v,L,False)):
            if bit and LL in self[w]:
                yield w,LL

    def _flattenpath(self,path):
        """Helper routine for shortest: convert output from internal format."""
        output = []
        while path:
            output.append(path[0])
            path = path[1]
        output.reverse()
        return output

    def shortest(self,v,L,w,LL):
        """
        Breadth first search for shortest path from (v,L) to (w,LL).
        The path is returned as a list of vertices.
        """
        start = (v,L,False)
        visited = {start}
        thislevel = [(start,(v,None))]
        nextlevel = []
        levelindex = 0
        while levelindex < len(thislevel) or nextlevel:
            if levelindex >= len(thislevel):
                thislevel = nextlevel
                nextlevel = []
                levelindex = 0
            current,path = thislevel[levelindex]
            levelindex += 1
            for nrgnode in self.nrg[current]:
                if nrgnode not in visited:
                    if nrgnode[2] and not current[2]:   # non-gadget edge?
                        newpath = (nrgnode[0],path)
                        if nrgnode[:2] == (w,LL):
                            return self._flattenpath(newpath)
                        nextlevel.append((nrgnode,newpath))
                    else:
                        thislevel.append((nrgnode,path))
                    visited.add(nrgnode)
        raise ValueError("No such path exists")