You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 1 | #!/usr/bin/env python |
Jeremy Ronquillo | b27ce4c | 2017-07-17 12:41:28 -0700 | [diff] [blame] | 2 | |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 3 | """ |
| 4 | Copyright 2016 Open Networking Foundation ( ONF ) |
Jeremy Songster | ae01bba | 2016-07-11 15:39:17 -0700 | [diff] [blame] | 5 | |
| 6 | Please refer questions to either the onos test mailing list at <onos-test@onosproject.org>, |
| 7 | the System Testing Plans and Results wiki page at <https://wiki.onosproject.org/x/voMg>, |
| 8 | or the System Testing Guide page at <https://wiki.onosproject.org/x/WYQg> |
Jeremy Ronquillo | b27ce4c | 2017-07-17 12:41:28 -0700 | [diff] [blame] | 9 | |
| 10 | TestON is free software: you can redistribute it and/or modify |
| 11 | it under the terms of the GNU General Public License as published by |
| 12 | the Free Software Foundation, either version 2 of the License, or |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 13 | ( at your option ) any later version. |
Jeremy Ronquillo | b27ce4c | 2017-07-17 12:41:28 -0700 | [diff] [blame] | 14 | |
| 15 | TestON is distributed in the hope that it will be useful, |
| 16 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 17 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 18 | GNU General Public License for more details. |
| 19 | |
| 20 | You should have received a copy of the GNU General Public License |
| 21 | along with TestON. If not, see <http://www.gnu.org/licenses/>. |
| 22 | |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 23 | """ |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 24 | import time |
| 25 | import random |
| 26 | |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 27 | |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 28 | class Graph: |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 29 | |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 30 | """ |
| 31 | Graph class provides implementations of graph algorithms. |
| 32 | The functions currently supported include: |
| 33 | - Comparing two graphs with specified attributes for vertices and edges |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 34 | - Getting DFI ( Depth First Index ) and back edges during a DFS |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 35 | - Chain decomposition of a graph |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 36 | - Finding ( non- )cut-edges and vertices |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 37 | """ |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 38 | def __init__( self ): |
| 39 | # We use a dictionary to store all information about the graph |
| 40 | self.graphDict = {} |
| 41 | # Depth-first index of each vertex |
| 42 | self.DFI = {} |
| 43 | self.currentDFI = 0 |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 44 | # Parent vertex ( and edge to that vertex ) of each vertex in depth-first search tree |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 45 | self.parentVertexInDFS = {} |
| 46 | self.parentEdgeInDFS = {} |
| 47 | # Back edges of the graph generated during DFS |
| 48 | self.backEdges = {} |
| 49 | # All chains in chain decomposition algorithm |
| 50 | self.chains = [] |
| 51 | |
| 52 | def update( self, graphDict ): |
| 53 | """ |
| 54 | Update the graph data. The current graph dictionary will be replaced by the |
| 55 | new one. |
| 56 | graphDict is in a dictionary which maps each vertex to a list of attributes. |
| 57 | An example of graphDict: |
| 58 | { vertex1: { 'edges': ..., 'name': ..., 'protocol': ... }, |
| 59 | vertex2: { 'edges': ..., 'name': ..., 'protocol': ... } } |
| 60 | Each vertex should at least have an 'edges' attribute which describes the |
| 61 | adjacency information. The value of 'edges' attribute is also represented by |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 62 | a dictionary, which maps each edge ( identified by the neighbor vertex ) to a |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 63 | list of attributes. |
| 64 | An example of the edges dictionary: |
| 65 | 'edges': { vertex2: { 'port': ..., 'type': ... }, |
| 66 | vertex3: { 'port': ..., 'type': ... } } |
| 67 | """ |
| 68 | self.graphDict = graphDict |
| 69 | return main.TRUE |
| 70 | |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 71 | def compareGraphs( self, graphDictA, graphDictB, vertexAttributes=[ 'edges' ], edgeAttributes=[ 'port' ] ): |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 72 | """ |
| 73 | Compare two graphs. |
| 74 | By default only the adjacency relationship, i.e. 'port' attribute in |
| 75 | 'edges' attribute for each vertex, is compared, To get other attributes |
| 76 | included, attribute name needs to be specified in the args, e.g. |
| 77 | vertexAttributes=[ 'edges', 'protocol' ] or |
| 78 | edgeAttributes=[ 'port', 'type' ] |
| 79 | Return main.TRUE if two graphs are equal, otherwise main.FALSE |
| 80 | """ |
| 81 | try: |
| 82 | result = main.TRUE |
| 83 | for vertex in set( graphDictA ).difference( graphDictB ): |
| 84 | result = main.FALSE |
| 85 | main.log.warn( "Graph: graph B: vertex {} not found".format( vertex ) ) |
| 86 | for vertex in set( graphDictB ).difference( graphDictA ): |
| 87 | result = main.FALSE |
| 88 | main.log.warn( "Graph: graph A: vertex {} not found".format( vertex ) ) |
| 89 | for vertex in set( graphDictA ).intersection( graphDictB ): |
| 90 | for vertexAttribute in vertexAttributes: |
| 91 | attributeFound = True |
| 92 | if vertexAttribute not in graphDictA[ vertex ]: |
| 93 | main.log.warn( "Graph: graph A -> vertex {}: attribute {} not found".format( vertex, vertexAttribute ) ) |
| 94 | attributeFound = False |
| 95 | if vertexAttribute not in graphDictB[ vertex ]: |
| 96 | attributeFound = False |
| 97 | main.log.warn( "Graph: graph B -> vertex {}: attribute {} not found".format( vertex, vertexAttribute ) ) |
| 98 | if not attributeFound: |
| 99 | result = main.FALSE |
| 100 | continue |
| 101 | else: |
| 102 | # Compare two attributes |
| 103 | attributeValueA = graphDictA[ vertex ][ vertexAttribute ] |
| 104 | attributeValueB = graphDictB[ vertex ][ vertexAttribute ] |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 105 | # FIXME: the comparison may not work for ( sub )attribute values that are of list type |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 106 | # For attributes except for 'edges', we just rely on '==' for comparison |
| 107 | if not vertexAttribute == 'edges': |
| 108 | if not attributeValueA == attributeValueB: |
| 109 | result = main.FALSE |
| 110 | main.log.warn( "Graph: vertex {}: {} does not match: {} and {}".format( vertex, |
| 111 | vertexAttribute, |
| 112 | attributeValueA, |
| 113 | attributeValueB ) ) |
| 114 | # The structure of 'edges' is similar to that of graphs, so we use the same method for comparison |
| 115 | else: |
| 116 | edgeDictA = attributeValueA |
| 117 | edgeDictB = attributeValueB |
| 118 | for neighbor in set( edgeDictA ).difference( edgeDictB ): |
| 119 | result = main.FALSE |
| 120 | main.log.warn( "Graph: graph B -> vertex {}: neighbor {} not found".format( vertex, neighbor ) ) |
| 121 | for neighbor in set( edgeDictB ).difference( edgeDictA ): |
| 122 | result = main.FALSE |
| 123 | main.log.warn( "Graph: graph A -> vertex {}: neighbor {} not found".format( vertex, neighbor ) ) |
| 124 | for neighbor in set( edgeDictA ).intersection( edgeDictB ): |
| 125 | for edgeAttribute in edgeAttributes: |
| 126 | attributeFound = True |
| 127 | if edgeAttribute not in edgeDictA[ neighbor ]: |
| 128 | attributeFound = False |
| 129 | main.log.warn( "Graph: graph A -> vertex {} -> neighbor {}: attribute {} not found".format( vertex, |
| 130 | neighbor, |
| 131 | edgeAttribute ) ) |
| 132 | if edgeAttribute not in edgeDictB[ neighbor ]: |
| 133 | attributeFound = False |
| 134 | main.log.warn( "Graph: graph B -> vertex {} -> neighbor {}: attribute {} not found".format( vertex, |
| 135 | neighbor, |
| 136 | edgeAttribute ) ) |
| 137 | if not attributeFound: |
| 138 | result = main.FALSE |
| 139 | continue |
| 140 | else: |
| 141 | # Compare two attributes |
| 142 | attributeValueA = edgeDictA[ neighbor ][ edgeAttribute ] |
| 143 | attributeValueB = edgeDictB[ neighbor ][ edgeAttribute ] |
| 144 | if not attributeValueA == attributeValueB: |
| 145 | result = main.FALSE |
| 146 | main.log.warn( "Graph: vertex {} -> neighbor {}: {} does not match: {} and {}".format( vertex, |
| 147 | neighbor, |
| 148 | edgeAttribute, |
| 149 | attributeValueA, |
| 150 | attributeValueB ) ) |
| 151 | if not result: |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 152 | # main.log.debug( "Graph: graphDictA: {}".format( graphDictA ) ) |
| 153 | # main.log.debug( "Graph: graphDictB: {}".format( graphDictB ) ) |
You Wang | 9a589b9 | 2016-07-14 09:43:21 -0700 | [diff] [blame] | 154 | pass |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 155 | return result |
| 156 | except TypeError: |
| 157 | main.log.exception( "Graph: TypeError exception found" ) |
| 158 | return main.ERROR |
| 159 | except KeyError: |
| 160 | main.log.exception( "Graph: KeyError exception found" ) |
| 161 | return main.ERROR |
| 162 | except Exception: |
| 163 | main.log.exception( "Graph: Uncaught exception" ) |
| 164 | return main.ERROR |
| 165 | |
| 166 | def getNonCutEdges( self ): |
| 167 | """ |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 168 | Get a list of non-cut-edges ( non-bridges ). |
| 169 | The definition of a cut-edge ( bridge ) is: the deletion of a cut-edge will |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 170 | increase the number of connected component of a graph. |
| 171 | The function is realized by impelementing Schmidt's algorithm based on |
| 172 | chain decomposition. |
| 173 | Returns a list of edges, e.g. |
| 174 | [ [ vertex1, vertex2 ], [ vertex2, vertex3 ] ] |
| 175 | """ |
| 176 | try: |
| 177 | if not self.depthFirstSearch(): |
| 178 | return None |
| 179 | if not self.findChains(): |
| 180 | return None |
| 181 | nonCutEdges = [] |
| 182 | for chain in self.chains: |
| 183 | for edge in chain: |
| 184 | nonCutEdges.append( edge ) |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 185 | # main.log.debug( 'Non-cut-edges: {}'.format( nonCutEdges ) ) |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 186 | return nonCutEdges |
| 187 | except Exception: |
| 188 | main.log.exception( "Graph: Uncaught exception" ) |
| 189 | return None |
| 190 | |
| 191 | def getNonCutVertices( self ): |
| 192 | """ |
| 193 | Get a list of non-cut-vertices. |
| 194 | The definition of a cut-vertex is: the deletion of a cut-vertex will |
| 195 | increase the number of connected component of a graph. |
| 196 | The function is realized by impelementing Schmidt's algorithm based on |
| 197 | chain decomposition. |
| 198 | Returns a list of vertices, e.g. [ vertex1, vertex2, vertex3 ] |
| 199 | """ |
| 200 | try: |
| 201 | nonCutEdges = self.getNonCutEdges() |
| 202 | # find all cycle chains |
| 203 | cycleChains = [] |
| 204 | for chain in self.chains: |
| 205 | # if the source vertex of the first chain equals to the destination vertex of the last |
| 206 | # chain, the chain is a cycle chain |
| 207 | if chain[ 0 ][ 0 ] == chain[ -1 ][ 1 ]: |
| 208 | cycleChains.append( chain ) |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 209 | # main.log.debug( 'Cycle chains: {}'.format( cycleChains ) ) |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 210 | # Get a set of vertices which are the first vertices of a cycle chain (excluding the first |
| 211 | # cycle chain), and these vertices are a subset of all cut-vertices |
| 212 | subsetOfCutVertices = [] |
| 213 | if len( cycleChains ) > 1: |
| 214 | for cycleChain in cycleChains[ 1: ]: |
| 215 | subsetOfCutVertices.append( cycleChain[ 0 ][ 0 ] ) |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 216 | # main.log.debug( 'Subset of cut vertices: {}'.format( subsetOfCutVertices ) ) |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 217 | nonCutVertices = [] |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 218 | assert nonCutEdges is not None |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 219 | for vertex in self.graphDict.keys(): |
| 220 | if vertex in subsetOfCutVertices: |
| 221 | continue |
| 222 | vertexIsNonCut = True |
| 223 | for neighbor in self.graphDict[ vertex ][ 'edges' ].keys(): |
| 224 | edge = [ vertex, neighbor ] |
| 225 | backwardEdge = [ neighbor, vertex ] |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 226 | if edge not in nonCutEdges and backwardEdge not in nonCutEdges: |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 227 | vertexIsNonCut = False |
| 228 | break |
| 229 | if vertexIsNonCut: |
| 230 | nonCutVertices.append( vertex ) |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 231 | # main.log.debug( 'Non-cut-vertices: {}'.format( nonCutVertices ) ) |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 232 | return nonCutVertices |
| 233 | except KeyError: |
| 234 | main.log.exception( "Graph: KeyError exception found" ) |
| 235 | return None |
| 236 | except AssertionError: |
| 237 | main.log.exception( "Graph: AssertionError exception found" ) |
| 238 | return None |
| 239 | except Exception: |
| 240 | main.log.exception( "Graph: Uncaught exception" ) |
| 241 | return None |
| 242 | |
| 243 | def depthFirstSearch( self ): |
| 244 | """ |
| 245 | This function runs a depth-first search and gets DFI of each vertex as well |
| 246 | as generates the back edges |
| 247 | """ |
| 248 | try: |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 249 | assert self.graphDict is not None and len( self.graphDict ) != 0 |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 250 | for vertex in self.graphDict.keys(): |
| 251 | self.DFI[ vertex ] = -1 |
| 252 | self.parentVertexInDFS[ vertex ] = '' |
| 253 | self.parentEdgeInDFS[ vertex ] = None |
| 254 | firstVertex = self.graphDict.keys()[ 0 ] |
| 255 | self.currentDFI = 0 |
| 256 | self.backEdges = {} |
| 257 | if not self.depthFirstSearchRecursive( firstVertex ): |
| 258 | return main.ERROR |
| 259 | return main.TRUE |
| 260 | except KeyError: |
| 261 | main.log.exception( "Graph: KeyError exception found" ) |
| 262 | return main.ERROR |
| 263 | except AssertionError: |
| 264 | main.log.exception( "Graph: AssertionError exception found" ) |
| 265 | return main.ERROR |
| 266 | except Exception: |
| 267 | main.log.exception( "Graph: Uncaught exception" ) |
| 268 | return main.ERROR |
| 269 | |
| 270 | def depthFirstSearchRecursive( self, vertex ): |
| 271 | """ |
| 272 | Recursive function for depth-first search |
| 273 | """ |
| 274 | try: |
| 275 | self.DFI[ vertex ] = self.currentDFI |
| 276 | self.currentDFI += 1 |
| 277 | for neighbor in self.graphDict[ vertex ][ 'edges' ].keys(): |
| 278 | edge = [ vertex, neighbor ] |
| 279 | backwardEdge = [ neighbor, vertex ] |
| 280 | if neighbor == self.parentVertexInDFS[ vertex ]: |
| 281 | continue |
| 282 | elif self.DFI[ neighbor ] == -1: |
| 283 | self.parentVertexInDFS[ neighbor ] = vertex |
| 284 | self.parentEdgeInDFS[ neighbor ] = backwardEdge |
| 285 | if not self.depthFirstSearchRecursive( neighbor ): |
| 286 | return main.ERROR |
| 287 | else: |
| 288 | key = self.DFI[ neighbor ] |
| 289 | if key in self.backEdges.keys(): |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 290 | if edge not in self.backEdges[ key ] and\ |
| 291 | backwardEdge not in self.backEdges[ key ]: |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 292 | self.backEdges[ key ].append( backwardEdge ) |
| 293 | else: |
| 294 | tempKey = self.DFI[ vertex ] |
| 295 | if tempKey in self.backEdges.keys(): |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 296 | if edge not in self.backEdges[ tempKey ] and\ |
| 297 | backwardEdge not in self.backEdges[ tempKey ]: |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 298 | self.backEdges[ key ] = [ backwardEdge ] |
| 299 | else: |
| 300 | self.backEdges[ key ] = [ backwardEdge ] |
| 301 | return main.TRUE |
| 302 | except KeyError: |
| 303 | main.log.exception( "Graph: KeyError exception found" ) |
| 304 | return main.ERROR |
| 305 | except Exception: |
| 306 | main.log.exception( "Graph: Uncaught exception" ) |
| 307 | return main.ERROR |
| 308 | |
| 309 | def findChains( self ): |
| 310 | """ |
| 311 | This function finds all the chains in chain-decomposition algorithm |
| 312 | """ |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 313 | keyList = sorted( self.backEdges.keys() ) |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 314 | vertexIsVisited = {} |
| 315 | self.chains = [] |
| 316 | for vertex in self.graphDict.keys(): |
| 317 | vertexIsVisited[ vertex ] = False |
| 318 | try: |
| 319 | for key in keyList: |
| 320 | backEdgeList = self.backEdges[ key ] |
| 321 | for edge in backEdgeList: |
| 322 | chain = [] |
| 323 | currentEdge = edge |
| 324 | sourceVertex = edge[ 0 ] |
| 325 | while True: |
| 326 | currentVertex = currentEdge[ 0 ] |
| 327 | nextVertex = currentEdge[ 1 ] |
| 328 | vertexIsVisited[ currentVertex ] = True |
| 329 | chain.append( currentEdge ) |
Jeremy Ronquillo | 23fb216 | 2017-09-15 14:59:57 -0700 | [diff] [blame] | 330 | if nextVertex == sourceVertex or vertexIsVisited[ nextVertex ]: |
You Wang | b1a16c3 | 2016-05-23 15:30:52 -0700 | [diff] [blame] | 331 | break |
| 332 | currentEdge = self.parentEdgeInDFS[ nextVertex ] |
| 333 | self.chains.append( chain ) |
| 334 | return main.TRUE |
| 335 | except KeyError: |
| 336 | main.log.exception( "Graph: KeyError exception found" ) |
| 337 | return main.ERROR |
| 338 | except Exception: |
| 339 | main.log.exception( "Graph: Uncaught exception" ) |
| 340 | return main.ERROR |