使用python networkx modu查找图中的链

Question

我有一个带有节点和边列表的图

nodes=['a','b','c','d','e','f','g'] 
G.add_edges_from ([('a','f'),('a','d'),('a','b'),('a','e'),('b','g'),
                   ('b','e'),('b','c'),('c','b'),('c','d'),('d','a'),
                   ('d','c'),('e','b'),('e','a'),  ('f','a'),('g','b')]. 

我的问题是标识每个节点的邻居，我使用G.neighbors(node[i])标识这些邻居

我得到的结果是

^{pr2}$

现在我必须将链排序为f <=d <=b，另一个链排序为g<=c<=a，这意味着将它们作为另一个链的子集排序。f是d的一个子集，也是b的一个子集。在

e是连接这两条链的中心节点，我已经手工计算过了。问题是我得不到这条链条，如何循环它们？在

Answer 1

据我所知，您需要列出所有节点，这些节点都是相邻节点的子集。因此，对于示例图，链应该是：

f<；=d<；=b，g<；=c<；=a（你提到过）加上g<；=e，你没有提到。我假设您不希望有已经存在的链的子集；存储g<；=c<；=a而不是c<；=a

这就是我解决你的问题的方法（我评论了一下，让它尽可能清楚）：

tmp = [] # temporary storage for chains
chains = [] # stores all found chains
nodes = G.nodes() # save the labels of nodes
prev_node =  None # Holds the node which other nodes will be checked if they are a subset of.
for i in xrange(len(nodes)): # each node is considered as a superset and others will be compared to it
    tmp.append(nodes[i]) # append this node as the head of the chain
    prev_node = nodes[i] # store it to compare other nodes to it
    for j in xrange (i+1,len(nodes)): # looping the rest of the nodes
        if set(G.neighbors(nodes[j])).issubset(set(((G.neighbors(prev_node))))) : # if it is a subset
            tmp.append(nodes[j]) # append to the chain
            prev_node = nodes[j] # store to check if the rest of the nodes are subset of this one

    if not (is_subset(chains,tmp)): # After finishing the chain check it is not a subset of an already created chain
        chains.append(list(reversed(tmp))) # add it to the chains
    tmp =[] # reset
    prev_node = None
print chains

is_subset函数是一个简单的函数，如果tmp已经是链的子集（排除它），则返回true：

^{pr2}$