Add graph utility for TestON
Change-Id: I87fcb9bfa61e5778b66281609ed98b0dd3f54df0
diff --git a/TestON/core/graph.py b/TestON/core/graph.py
new file mode 100644
index 0000000..c893adc
--- /dev/null
+++ b/TestON/core/graph.py
@@ -0,0 +1,317 @@
+#!/usr/bin/env python
+import time
+import random
+
+class Graph:
+ """
+ Graph class provides implementations of graph algorithms.
+ The functions currently supported include:
+ - Comparing two graphs with specified attributes for vertices and edges
+ - Getting DFI (Depth First Index) and back edges during a DFS
+ - Chain decomposition of a graph
+ - Finding (non-)cut-edges and vertices
+ """
+
+ def __init__( self ):
+ # We use a dictionary to store all information about the graph
+ self.graphDict = {}
+ # Depth-first index of each vertex
+ self.DFI = {}
+ self.currentDFI = 0
+ # Parent vertex (and edge to that vertex) of each vertex in depth-first search tree
+ self.parentVertexInDFS = {}
+ self.parentEdgeInDFS = {}
+ # Back edges of the graph generated during DFS
+ self.backEdges = {}
+ # All chains in chain decomposition algorithm
+ self.chains = []
+
+ def update( self, graphDict ):
+ """
+ Update the graph data. The current graph dictionary will be replaced by the
+ new one.
+ graphDict is in a dictionary which maps each vertex to a list of attributes.
+ An example of graphDict:
+ { vertex1: { 'edges': ..., 'name': ..., 'protocol': ... },
+ vertex2: { 'edges': ..., 'name': ..., 'protocol': ... } }
+ Each vertex should at least have an 'edges' attribute which describes the
+ adjacency information. The value of 'edges' attribute is also represented by
+ a dictionary, which maps each edge (identified by the neighbor vertex) to a
+ list of attributes.
+ An example of the edges dictionary:
+ 'edges': { vertex2: { 'port': ..., 'type': ... },
+ vertex3: { 'port': ..., 'type': ... } }
+ """
+ self.graphDict = graphDict
+ return main.TRUE
+
+ def compareGraphs( self, graphDictA, graphDictB, vertexAttributes=['edges'], edgeAttributes=['port'] ):
+ """
+ Compare two graphs.
+ By default only the adjacency relationship, i.e. 'port' attribute in
+ 'edges' attribute for each vertex, is compared, To get other attributes
+ included, attribute name needs to be specified in the args, e.g.
+ vertexAttributes=[ 'edges', 'protocol' ] or
+ edgeAttributes=[ 'port', 'type' ]
+ Return main.TRUE if two graphs are equal, otherwise main.FALSE
+ """
+ try:
+ result = main.TRUE
+ for vertex in set( graphDictA ).difference( graphDictB ):
+ result = main.FALSE
+ main.log.warn( "Graph: graph B: vertex {} not found".format( vertex ) )
+ for vertex in set( graphDictB ).difference( graphDictA ):
+ result = main.FALSE
+ main.log.warn( "Graph: graph A: vertex {} not found".format( vertex ) )
+ for vertex in set( graphDictA ).intersection( graphDictB ):
+ for vertexAttribute in vertexAttributes:
+ attributeFound = True
+ if vertexAttribute not in graphDictA[ vertex ]:
+ main.log.warn( "Graph: graph A -> vertex {}: attribute {} not found".format( vertex, vertexAttribute ) )
+ attributeFound = False
+ if vertexAttribute not in graphDictB[ vertex ]:
+ attributeFound = False
+ main.log.warn( "Graph: graph B -> vertex {}: attribute {} not found".format( vertex, vertexAttribute ) )
+ if not attributeFound:
+ result = main.FALSE
+ continue
+ else:
+ # Compare two attributes
+ attributeValueA = graphDictA[ vertex ][ vertexAttribute ]
+ attributeValueB = graphDictB[ vertex ][ vertexAttribute ]
+ # FIXME: the comparison may not work for (sub)attribute values that are of list type
+ # For attributes except for 'edges', we just rely on '==' for comparison
+ if not vertexAttribute == 'edges':
+ if not attributeValueA == attributeValueB:
+ result = main.FALSE
+ main.log.warn( "Graph: vertex {}: {} does not match: {} and {}".format( vertex,
+ vertexAttribute,
+ attributeValueA,
+ attributeValueB ) )
+ # The structure of 'edges' is similar to that of graphs, so we use the same method for comparison
+ else:
+ edgeDictA = attributeValueA
+ edgeDictB = attributeValueB
+ for neighbor in set( edgeDictA ).difference( edgeDictB ):
+ result = main.FALSE
+ main.log.warn( "Graph: graph B -> vertex {}: neighbor {} not found".format( vertex, neighbor ) )
+ for neighbor in set( edgeDictB ).difference( edgeDictA ):
+ result = main.FALSE
+ main.log.warn( "Graph: graph A -> vertex {}: neighbor {} not found".format( vertex, neighbor ) )
+ for neighbor in set( edgeDictA ).intersection( edgeDictB ):
+ for edgeAttribute in edgeAttributes:
+ attributeFound = True
+ if edgeAttribute not in edgeDictA[ neighbor ]:
+ attributeFound = False
+ main.log.warn( "Graph: graph A -> vertex {} -> neighbor {}: attribute {} not found".format( vertex,
+ neighbor,
+ edgeAttribute ) )
+ if edgeAttribute not in edgeDictB[ neighbor ]:
+ attributeFound = False
+ main.log.warn( "Graph: graph B -> vertex {} -> neighbor {}: attribute {} not found".format( vertex,
+ neighbor,
+ edgeAttribute ) )
+ if not attributeFound:
+ result = main.FALSE
+ continue
+ else:
+ # Compare two attributes
+ attributeValueA = edgeDictA[ neighbor ][ edgeAttribute ]
+ attributeValueB = edgeDictB[ neighbor ][ edgeAttribute ]
+ if not attributeValueA == attributeValueB:
+ result = main.FALSE
+ main.log.warn( "Graph: vertex {} -> neighbor {}: {} does not match: {} and {}".format( vertex,
+ neighbor,
+ edgeAttribute,
+ attributeValueA,
+ attributeValueB ) )
+ if not result:
+ main.log.debug( "Graph: graphDictA: {}".format( graphDictA ) )
+ main.log.debug( "Graph: graphDictB: {}".format( graphDictB ) )
+ return result
+ except TypeError:
+ main.log.exception( "Graph: TypeError exception found" )
+ return main.ERROR
+ except KeyError:
+ main.log.exception( "Graph: KeyError exception found" )
+ return main.ERROR
+ except Exception:
+ main.log.exception( "Graph: Uncaught exception" )
+ return main.ERROR
+
+ def getNonCutEdges( self ):
+ """
+ Get a list of non-cut-edges (non-bridges).
+ The definition of a cut-edge (bridge) is: the deletion of a cut-edge will
+ increase the number of connected component of a graph.
+ The function is realized by impelementing Schmidt's algorithm based on
+ chain decomposition.
+ Returns a list of edges, e.g.
+ [ [ vertex1, vertex2 ], [ vertex2, vertex3 ] ]
+ """
+ try:
+ if not self.depthFirstSearch():
+ return None
+ if not self.findChains():
+ return None
+ nonCutEdges = []
+ for chain in self.chains:
+ for edge in chain:
+ nonCutEdges.append( edge )
+ main.log.debug( 'Non-cut-edges: {}'.format( nonCutEdges ) )
+ return nonCutEdges
+ except Exception:
+ main.log.exception( "Graph: Uncaught exception" )
+ return None
+
+ def getNonCutVertices( self ):
+ """
+ Get a list of non-cut-vertices.
+ The definition of a cut-vertex is: the deletion of a cut-vertex will
+ increase the number of connected component of a graph.
+ The function is realized by impelementing Schmidt's algorithm based on
+ chain decomposition.
+ Returns a list of vertices, e.g. [ vertex1, vertex2, vertex3 ]
+ """
+ try:
+ nonCutEdges = self.getNonCutEdges()
+ # find all cycle chains
+ cycleChains = []
+ for chain in self.chains:
+ # if the source vertex of the first chain equals to the destination vertex of the last
+ # chain, the chain is a cycle chain
+ if chain[ 0 ][ 0 ] == chain[ -1 ][ 1 ]:
+ cycleChains.append( chain )
+ main.log.debug( 'Cycle chains: {}'.format( cycleChains ) )
+ # Get a set of vertices which are the first vertices of a cycle chain (excluding the first
+ # cycle chain), and these vertices are a subset of all cut-vertices
+ subsetOfCutVertices = []
+ if len( cycleChains ) > 1:
+ for cycleChain in cycleChains[ 1: ]:
+ subsetOfCutVertices.append( cycleChain[ 0 ][ 0 ] )
+ main.log.debug( 'Subset of cut vertices: {}'.format( subsetOfCutVertices ) )
+ nonCutVertices = []
+ assert nonCutEdges != None
+ for vertex in self.graphDict.keys():
+ if vertex in subsetOfCutVertices:
+ continue
+ vertexIsNonCut = True
+ for neighbor in self.graphDict[ vertex ][ 'edges' ].keys():
+ edge = [ vertex, neighbor ]
+ backwardEdge = [ neighbor, vertex ]
+ if not edge in nonCutEdges and not backwardEdge in nonCutEdges:
+ vertexIsNonCut = False
+ break
+ if vertexIsNonCut:
+ nonCutVertices.append( vertex )
+ main.log.debug( 'Non-cut-vertices: {}'.format( nonCutVertices ) )
+ return nonCutVertices
+ except KeyError:
+ main.log.exception( "Graph: KeyError exception found" )
+ return None
+ except AssertionError:
+ main.log.exception( "Graph: AssertionError exception found" )
+ return None
+ except Exception:
+ main.log.exception( "Graph: Uncaught exception" )
+ return None
+
+ def depthFirstSearch( self ):
+ """
+ This function runs a depth-first search and gets DFI of each vertex as well
+ as generates the back edges
+ """
+ try:
+ assert self.graphDict != None and len( self.graphDict ) != 0
+ for vertex in self.graphDict.keys():
+ self.DFI[ vertex ] = -1
+ self.parentVertexInDFS[ vertex ] = ''
+ self.parentEdgeInDFS[ vertex ] = None
+ firstVertex = self.graphDict.keys()[ 0 ]
+ self.currentDFI = 0
+ self.backEdges = {}
+ if not self.depthFirstSearchRecursive( firstVertex ):
+ return main.ERROR
+ return main.TRUE
+ except KeyError:
+ main.log.exception( "Graph: KeyError exception found" )
+ return main.ERROR
+ except AssertionError:
+ main.log.exception( "Graph: AssertionError exception found" )
+ return main.ERROR
+ except Exception:
+ main.log.exception( "Graph: Uncaught exception" )
+ return main.ERROR
+
+ def depthFirstSearchRecursive( self, vertex ):
+ """
+ Recursive function for depth-first search
+ """
+ try:
+ self.DFI[ vertex ] = self.currentDFI
+ self.currentDFI += 1
+ for neighbor in self.graphDict[ vertex ][ 'edges' ].keys():
+ edge = [ vertex, neighbor ]
+ backwardEdge = [ neighbor, vertex ]
+ if neighbor == self.parentVertexInDFS[ vertex ]:
+ continue
+ elif self.DFI[ neighbor ] == -1:
+ self.parentVertexInDFS[ neighbor ] = vertex
+ self.parentEdgeInDFS[ neighbor ] = backwardEdge
+ if not self.depthFirstSearchRecursive( neighbor ):
+ return main.ERROR
+ else:
+ key = self.DFI[ neighbor ]
+ if key in self.backEdges.keys():
+ if not edge in self.backEdges[ key ] and\
+ not backwardEdge in self.backEdges[ key ]:
+ self.backEdges[ key ].append( backwardEdge )
+ else:
+ tempKey = self.DFI[ vertex ]
+ if tempKey in self.backEdges.keys():
+ if not edge in self.backEdges[ tempKey ] and\
+ not backwardEdge in self.backEdges[ tempKey ]:
+ self.backEdges[ key ] = [ backwardEdge ]
+ else:
+ self.backEdges[ key ] = [ backwardEdge ]
+ return main.TRUE
+ except KeyError:
+ main.log.exception( "Graph: KeyError exception found" )
+ return main.ERROR
+ except Exception:
+ main.log.exception( "Graph: Uncaught exception" )
+ return main.ERROR
+
+ def findChains( self ):
+ """
+ This function finds all the chains in chain-decomposition algorithm
+ """
+ keyList = self.backEdges.keys()
+ keyList.sort()
+ vertexIsVisited = {}
+ self.chains = []
+ for vertex in self.graphDict.keys():
+ vertexIsVisited[ vertex ] = False
+ try:
+ for key in keyList:
+ backEdgeList = self.backEdges[ key ]
+ for edge in backEdgeList:
+ chain = []
+ currentEdge = edge
+ sourceVertex = edge[ 0 ]
+ while True:
+ currentVertex = currentEdge[ 0 ]
+ nextVertex = currentEdge[ 1 ]
+ vertexIsVisited[ currentVertex ] = True
+ chain.append( currentEdge )
+ if nextVertex == sourceVertex or vertexIsVisited[ nextVertex ] == True:
+ break
+ currentEdge = self.parentEdgeInDFS[ nextVertex ]
+ self.chains.append( chain )
+ return main.TRUE
+ except KeyError:
+ main.log.exception( "Graph: KeyError exception found" )
+ return main.ERROR
+ except Exception:
+ main.log.exception( "Graph: Uncaught exception" )
+ return main.ERROR