TestON/tests/CHOTestMonkey/dependencies/GraphHelper.py

"""
Graph algorithm implementations for CHOTestMonkey
Author: you@onlab.us
"""
class GraphHelper:
    """
    This class implements graph algorithms for CHOTestMonkey.
    It reads main.devices and main.links as vertices and edges.
    Currently it offers functions for finding (non-)cut-edges and vertices,
    which is realized based on chain-decomposition algorithm
    """
    def __init__( self ):
        # Depth-first index of each node
        self.DFI = []
        # Parent vertex and egde of each node in depth-first search tree
        self.parentDeviceInDFS = []
        self.parentLinkInDFS = []
        # Data structures for chain-decomposition algorithm
        self.backEdges = {}
        self.chains = []
        self.currentDFI = 0
        self.upDevices = []
        for device in main.devices:
            if device.isUp():
                self.upDevices.append( device )
        for i in range( len( main.devices ) ):
            self.DFI.append( -1 )
            self.parentDeviceInDFS.append( None )
            self.parentLinkInDFS.append( None )

    def genDFIandBackEdge( self, device ):
        """
        This function runs a depth-first search and get DFI of each node
        as well as collect the back edges
        """
        self.DFI[ device.index ] = self.currentDFI
        self.currentDFI += 1
        for link in device.outgoingLinks:
            if not link.isUp():
                continue
            backwardLink = link.backwardLink
            neighbor = link.deviceB
            if neighbor == self.parentDeviceInDFS[ device.index ]:
                continue
            elif self.DFI[ neighbor.index ] == -1:
                self.parentDeviceInDFS[ neighbor.index ] = device
                self.parentLinkInDFS[ neighbor.index ] = backwardLink
                self.genDFIandBackEdge( neighbor )
            else:
                key = self.DFI[ neighbor.index ]
                if key in self.backEdges.keys():
                    if not link in self.backEdges[ key ] and\
                    not backwardLink in self.backEdges[ key ]:
                        self.backEdges[ key ].append( backwardLink )
                else:
                    tempKey = self.DFI[ device.index ]
                    if tempKey in self.backEdges.keys():
                        if not link in self.backEdges[ tempKey ] and\
                        not backwardLink in self.backEdges[ tempKey ]:
                            self.backEdges[ key ] = [ backwardLink ]
                    else:
                        self.backEdges[ key ] = [ backwardLink ]

    def findChains( self ):
        """
        This function finds all the 'chains' for chain-decomposition algorithm
        """
        keyList = self.backEdges.keys()
        keyList.sort()
        deviceIsVisited = []
        for i in range( len( main.devices ) ):
            deviceIsVisited.append( 0 )
        for key in keyList:
            backEdgeList = self.backEdges[ key ]
            for link in backEdgeList:
                chain = []
                currentLink = link
                sourceDevice = link.deviceA
                while True:
                    currentDevice = currentLink.deviceA
                    nextDevice = currentLink.deviceB
                    deviceIsVisited[ currentDevice.index ] = 1
                    chain.append( currentLink )
                    if nextDevice == sourceDevice or deviceIsVisited[ nextDevice.index ] == 1:
                        break
                    currentLink = self.parentLinkInDFS[ nextDevice.index ]
                self.chains.append( chain )

    def getNonCutEdges( self ):
        """
        This function returns all non-cut-edges of a graph
        """
        assert len( self.upDevices ) != 0
        self.genDFIandBackEdge( self.upDevices[ 0 ] )
        self.findChains()
        nonCutEdges = []
        for chain in self.chains:
            for link in chain:
                nonCutEdges.append( link )
        return nonCutEdges

    def getNonCutVertices( self ):
        """
        This function returns all non-cut-vertices of a graph
        """
        nonCutEdges = self.getNonCutEdges()
        nonCutVertices = []
        for device in self.upDevices:
            deviceIsNonCut = True
            for link in device.outgoingLinks:
                if link.isUp() and not ( link in nonCutEdges or link.backwardLink in nonCutEdges ):
                    deviceIsNonCut = False
                    break
            if deviceIsNonCut:
                nonCutVertices.append( device )
        return nonCutVertices

    def printDFI( self ):
        print self.DFI

    def printParentInDFS( self ):
        print self.parentInDFS

    def printBackEdges( self ):
        print self.backEdges

    def printChains( self ):
        chainIndex = 0
        for chain in self.chains:
            print chainIndex
            for link in chain:
                print link
            chainIndex += 1