I'm writing a function get_connected_components
for a class 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
My graph is:
{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: []}
where the keys are the nodes and the values are the edge. My function gives me this connected component:
[(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)]
But I would have two different connected components, like:
[[(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)]]
I don't understand where I made the mistake. Can anyone help me?
Let's simplify the graph representation:
myGraph = {0: [1,2,3], 1: [], 2: [1], 3: [4,5],4: [3,5], 5: [3,4,7], 6: [8], 7: [],8: [9], 9: []}
Here we have the function returning a dictionary whose keys are the roots and whose values are the connected components:
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
Let's try it:
print getRoots(myGraph)
{8: [6, 8, 9], 1: [0, 1, 2, 3, 4, 5, 7]}