networkX 中无向图的参数传递闭包
Parametric transitive closure of an undirected graph in networkX
我正在从现有边制作无向图。
G = nx.Graph()
edge_list = [(1,2),(2,3), (3,4), (4,5),(5,6)]
G.add_edges_from(edge_list)
现在我想执行由级别 k 参数化的传递闭包，这样 k=1 意味着将添加以下新边。
new_edge_list = [(1,3),(2,4),(3,5),(4,6)]
G.add_edges_from(new_edge_list)
而 k=2 意味着将添加以下新边。
new_edge_list = [(1,3),(1,4),(2,4),(2,5),(3,5), (3,6),(4,6)]
G.add_edges_from(new_edge_list)
这实质上意味着随着我们不断增加 k 的值，图 G 最终会变成一个团（即传递闭包）。但是，我想在 k 的特定级别上获得一个传递闭包。我能够使用 . But I am struggling with specific level of transitive closure. I am able to achieve k=1 transitive closure by using adjacency 表示法获得完整的传递闭包，但无法针对 k=2.
进行缩放
P.S：如果在参数传递闭包过程中像[(1,3),(3,1)]一样创建对称边也可以。
如果您有针对 k = 1 情况的有效算法，并且您提到的缩放比例问题不会因为您添加更多边时图形本身的增长而出现，那么您可以简单地使用它递归算法，因为将它应用于 k = 1-case 的输出将是你的 k = 2-case.
我正在从现有边制作无向图。
G = nx.Graph()
edge_list = [(1,2),(2,3), (3,4), (4,5),(5,6)]
G.add_edges_from(edge_list)
现在我想执行由级别 k 参数化的传递闭包，这样 k=1 意味着将添加以下新边。
new_edge_list = [(1,3),(2,4),(3,5),(4,6)]
G.add_edges_from(new_edge_list)
而 k=2 意味着将添加以下新边。
new_edge_list = [(1,3),(1,4),(2,4),(2,5),(3,5), (3,6),(4,6)]
G.add_edges_from(new_edge_list)
这实质上意味着随着我们不断增加 k 的值，图 G 最终会变成一个团（即传递闭包）。但是，我想在 k 的特定级别上获得一个传递闭包。我能够使用 k=1 transitive closure by using adjacency 表示法获得完整的传递闭包，但无法针对 k=2.
P.S：如果在参数传递闭包过程中像[(1,3),(3,1)]一样创建对称边也可以。
如果您有针对 k = 1 情况的有效算法，并且您提到的缩放比例问题不会因为您添加更多边时图形本身的增长而出现，那么您可以简单地使用它递归算法，因为将它应用于 k = 1-case 的输出将是你的 k = 2-case.