Python componenti collegati

Question

Sto scrivendo una funzione get_connected_components per una classe Graph:

def get_connected_components(self): 
    path=[] 
    for i in self.graph.keys(): 
     q=self.graph[i] 
     while q: 
      print(q) 
      v=q.pop(0) 
      if not v in path: 
       path=path+[v] 
    return path 

mio grafico è:

{0: [(0, 1), (0, 2), (0, 3)], 1: [], 2: [(2, 1)], 3: [(3, 4), (3, 5)], \ 
4: [(4, 3), (4, 5)], 5: [(5, 3), (5, 4), (5, 7)], 6: [(6, 8)], 7: [], \ 
8: [(8, 9)], 9: []} 

dove le chiavi sono i nodi ei valori sono il bordo. La mia funzione mi dà questo componente collegato:

[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), \ 
(5, 4), (5, 7), (6, 8), (8, 9)] 

ma avrei due diverse componenti connesse, quali:

[[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), \ 
(5, 3), (5, 4), (5, 7)],[(6, 8), (8, 9)]] 

non capisco dove ho fatto l'errore. Qualcuno può aiutarmi?

Answer 1

Diamo semplificare la rappresentazione grafica:

myGraph = {0: [1,2,3], 1: [], 2: [1], 3: [4,5],4: [3,5], 5: [3,4,7], 6: [8], 7: [],8: [9], 9: []} 

Qui abbiamo la funzione che restituisce un dizionario le cui chiavi sono le radici ei cui valori sono i componenti collegati:

def getRoots(aNeigh): 
    def findRoot(aNode,aRoot): 
     while aNode != aRoot[aNode][0]: 
      aNode = aRoot[aNode][0] 
     return (aNode,aRoot[aNode][1]) 
    myRoot = {} 
    for myNode in aNeigh.keys(): 
     myRoot[myNode] = (myNode,0) 
    for myI in aNeigh: 
     for myJ in aNeigh[myI]: 
      (myRoot_myI,myDepthMyI) = findRoot(myI,myRoot) 
      (myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot) 
      if myRoot_myI != myRoot_myJ: 
       myMin = myRoot_myI 
       myMax = myRoot_myJ 
       if myDepthMyI > myDepthMyJ: 
        myMin = myRoot_myJ 
        myMax = myRoot_myI 
       myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1])) 
       myRoot[myMin] = (myRoot[myMax][0],-1) 
    myToRet = {} 
    for myI in aNeigh: 
     if myRoot[myI][0] == myI: 
      myToRet[myI] = [] 
    for myI in aNeigh: 
     myToRet[findRoot(myI,myRoot)[0]].append(myI) 
    return myToRet 

proviamo:

print getRoots(myGraph) 

{8: [6, 8, 9], 1: [0, 1, 2, 3, 4, 5, 7]}

Answer 2

mi piace questo algoritmo:

def connected_components(neighbors): 
    seen = set() 
    def component(node): 
     nodes = set([node]) 
     while nodes: 
      node = nodes.pop() 
      seen.add(node) 
      nodes |= neighbors[node] - seen 
      yield node 
    for node in neighbors: 
     if node not in seen: 
      yield component(node) 

Non solo è breve ed elegante, ma anche veloce. Usalo in questo modo (Python 2.7):

old_graph = { 
    0: [(0, 1), (0, 2), (0, 3)], 
    1: [], 
    2: [(2, 1)], 
    3: [(3, 4), (3, 5)], 
    4: [(4, 3), (4, 5)], 
    5: [(5, 3), (5, 4), (5, 7)], 
    6: [(6, 8)], 
    7: [], 
    8: [(8, 9)], 
    9: []} 

new_graph = {node: set(each for edge in edges for each in edge) 
      for node, edges in old_graph.items()} 
components = [] 
for component in connected_components(new_graph): 
    c = set(component) 
    components.append([edge for edges in old_graph.values() 
          for edge in edges 
          if c.intersection(edge)]) 
print components 

Il risultato è:

[[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), (5, 4), (5, 7)], 
[(6, 8), (8, 9)]]