Framework of the new CHOtest
Change-Id: Ie5b58bfa2ed487386443692cbea0d469d7419c24
diff --git a/TestON/tests/CHOTestMonkey/dependencies/GraphHelper.py b/TestON/tests/CHOTestMonkey/dependencies/GraphHelper.py
new file mode 100644
index 0000000..13f110b
--- /dev/null
+++ b/TestON/tests/CHOTestMonkey/dependencies/GraphHelper.py
@@ -0,0 +1,133 @@
+"""
+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