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