实践中经常遇到这样一个小问题。有一套图数据，所有节点间并不是全部连通的（任意点间均有通路）。这必然导致出现相互隔离的子图，这时我们可能希望将所有分离的子图找出来，单独处理。这里给出解决这个问题的一小段程序。
The problem is, given a set of edges(node, node), seperate all subgraphs that are isolated from each other. Isolation of two graphs Gx and Gy is defined as every node Xi in Gx has no edge(or path) to every node Yi in Gy.
data = [[1,2],[2,3],[3,4],[5,6],[6,7]]
# expect output 2 subgraph of {1,2,3,4} and {5,6,7}naive idea, construct a set of nodes of a subgraph, a new node is added to the set if it can connect to any node in the set
def getSubgraphs(data):
rstList = []
for row in data:
connect = False
for s in rstList:
if row[0] in s or row[1] in s:
s.update(row)
connect = True
break
if not connect:
rstList.append(set(row))
return rstList
rstList = getSubgraphs(data)
print rstList
[set([1, 2, 3, 4]), set([5, 6, 7])]
data.append([4,5])
# this edge should connect two subgraph
rstList = getSubgraphs(data)
print rstList
[set([1, 2, 3, 4, 5]), set([5, 6, 7])]Not as expected, something must be wrong!
Later added edges may connect preview added sets together, check every pair of sets to see if they have any intersection
import itertools
def combineSet(rstList):
for a,b in itertools.product(rstList, repeat=2):
if a<>b and len(a&b) > 0:
rstList.remove(a)
rstList.remove(b)
rstList.append(a|b)
breakiterate to combine sets till length of list don’t change
while True:
length = len(rstList)
combineSet(rstList)
if length==len(rstList):
break
print rstList
[set([1, 2, 3, 4, 5, 6, 7])]If you are familiar with Leetcode, you may feel like it is a real world practice of Merge Intervals.
comments powered by Disqus