Python:找到连接到N(元组)的所有节点

Question

我想找出是否可以从某个节点传达所有节点。我对路径不感兴趣，如果我不能或不能输出是或否。假设我有以下图 - 作为约束，我需要表示我的节点为元组(i，j(：

graph={
    (1,1): [(1,2),(2,2)]
    (1,2): [(1,3)]
    (1,3): [(1,2),(2,3)]
    (2,2): [(3,3)]
    (2,3): []
    (3,3): [(2,2)]
}

现在，我需要证明是否可以从(1,1(，(2,2(或(3,3(中到达，即(i，j(i = j，所有其他节点，i！= = =j。如果是，请打印(是( - 如果否，请打印(否(。上面提到的示例将输出节点(1,1(，因为我可以通过节点(1,1(达到(1,2(，(1,3(和(2,3(。

我尝试使用以下

G = nx.DiGraph()
G.add_edges_from(graph)
for reachable_node in nx.dfs_postorder_nodes(G, source=None):
    print reachable_node

但是，如果我声明(1,1(，(2,2(或(3,3(为nx.dfs_postorder.nodes((中的源，1(

我应该使用哪个函数或库(库越好！(来指示我是否可以从任何(i，i(节点接触到所有节点？

感谢所有澄清！我是一个新成员，因此，如果我的问题不遵循Stackoverflow指南，请随时告诉我如何改善下一个问题！

Answer 1

此程序应完成工作，并且仅使用标准库(基本上为您提供了可以在给定起点访问的所有可能的状态(：

graph={
    (1,1): [(1,2), (2,2)],
    (1,2): [(1,3)],
    (1,3): [(1,2), (2,3)],
    (2,2): [(3,3)],
    (2,3): [],
    (3,3): [(2,2)]
}
node0 = (1,1) #choose the starting node
node0_connections = [node0] #this list will contain all the possible states that can be visited from node0
for node in node0_connections: 
     for node_to in graph[node]:
         if  node0_connections.count(node_to) == 0:
             node0_connections.append(node_to)                
print 'All possible states to be visted from node', node0,':', node0_connections,'.'
count = node0_connections.count((1,2)) + node0_connections.count((1,3)) + node0_connections.count((2,2))
if count == 3:
    print 'YES'
else:
    print 'NO'

Answer 2

我想我理解您的问题。您可以使用try/except块使用nx.shortest_path尝试详尽的方法：

import networkx as nx
graph={
    (1,1): [(1,2),(2,2)],
    (1,2): [(1,3)],
    (1,3): [(1,2),(2,3)],
    (2,2): [(3,3)],
    (3,3): [(2,2)],
    (4,4): [(1,3)],
    (5,5): []
}
G = nx.Graph(graph)
nodes = G.nodes()
balanced_nodes = [node for node in G.nodes() if node[0] == node[1]]
unbalanced_nodes = [node for node in G.nodes() if node[0] != node[1]]
for balanced_node in balanced_nodes:
    for unbalanced_node in unbalanced_nodes:
        connected = True
        try:
            path = nx.shortest_path(G,balanced_node, unbalanced_node)
        except:
            connected = False
            break
    print(balanced_node, ": ", connected)

这将导致：

(1, 1) :  True
(2, 2) :  True
(3, 3) :  True
(4, 4) :  True
(5, 5) :  False