草庐IT

关于python：获取包含其间所有节点的networkx子图

codeneng 2023-03-28 原文

Get networkx subgraph containing all nodes in between

我有一个 networkx DiGraph，我想通过传入一个节点列表从中提取一个子图。然而，子图可以包含可能位于我通过的节点之间的所有节点。我检查了 nx.subgraph() 但它不像我打算的那样工作。举个小例子：

1
2
3
4
5
6
import networkx as nx

G = nx.DiGraph()
edges = [(7, 4), (3, 8), (3, 2), (3, 0), (3, 1), (7, 5), (7, 6), (7, 8)]
G.add_edges_from(edges)
H = get_subgraph(G, [0,6,7,8])

如何编写函数 get_subgraph() 以使 H 具有边 [(3, 8), (3, 0), (7, 6), (7, 8)]？
我需要的子图是这样的，它包含我在 get_subgraph() 函数中传递的节点之间的传出路径和传入路径中的所有节点。

一种方法可以是找到指定节点集之间的最长路径长度，然后找到包含路径中所有节点的相应诱导子图。但是，作为有向图，节点 3 和 7 之间将没有直接路径。所以我们需要在图的无向副本中找到路径。让我们设置问题：

1
2
3
4
5
6
7
8
9
10
G = nx.DiGraph()
edges = [(7, 4), (3, 8), (3, 2), (3, 0), (3, 1), (7, 5), (7, 6), (7, 8)]
G.add_edges_from(edges)

plt.figure(figsize=(10,6))
pos = nx.spring_layout(G, scale=20, k=3/np.sqrt(G.order()))
nx.draw(G, pos, node_color='lightblue',
        with_labels=True,
        node_size=1500,
        arrowsize=20)

现在我们可以使用 nx.to_undirected 获取图的无向副本，并找到指定节点的所有 nx.shortest_path_length：

1
2
3
4
5
6
7
8
9
10
11
from itertools import combinations

H = nx.to_undirected(G)

nodelist = [0,6,7,8]
paths = {}
for nodes in combinations(nodelist, r=2):
    paths[nodes] = nx.shortest_path_length(H, *nodes)

print(paths)
# {(0, 6): 4, (0, 7): 3, (0, 8): 2, (6, 7): 1, (6, 8): 2, (7, 8): 1}

我们可以在无向图中找到最长的路径：

1
2
max_path = max(paths.items(), key=lambda x: x[1])[0]
longest_induced_path = nx.shortest_path(H, *max_path)

而对应的诱导子图可以用Graph.subgraph得到：

1
2
3
4
5
6
7
sG = nx.subgraph(G, longest_induced_path)

pos = nx.spring_layout(sG, scale=20, k=3/np.sqrt(G.order()))
nx.draw(sG, pos, node_color='lightblue',
        with_labels=True,
        node_size=1500,
        arrowsize=20)

我从问题中理解这一点：
您需要路径中的所有节点，但提供该路径的一些节点，并且算法应该提供该路径的所有节点，然后您可以将这些节点传递给一个图并制作一个新图。
它应该是你想要的：
1.您必须使用此方法遍历所有节点对：

1
2
3
from itertools import combinations
b= combinations('ABCD', 2)
print(list(b))  --> [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

  • 你必须得到所有的路径：
    https://networkx.github.io/documentation/stable/reference/algorithms/simple_paths.html

  • 您必须选择具有最大节点的路径，这就是您的解决方案。

    • 明白了。谢谢您的意见。这类似于 yatus 答案

    有节其间spanclassbrgraphgraph-theorynetworkxpython

    有关关于python：获取包含其间所有节点的networkx子图的更多相关文章

    1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

      关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

    2. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

      为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

    3. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

      我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

    4. ruby - 简单获取法拉第超时 - 2

      有没有办法在这个简单的get方法中添加超时选项？我正在使用法拉第3.3。Faraday.get(url)四处寻找，我只能先发起连接后应用超时选项，然后应用超时选项。或者有什么简单的方法？这就是我现在正在做的:conn=Faraday.newresponse=conn.getdo|req|req.urlurlreq.options.timeout=2#2secondsend 最佳答案 试试这个:conn=Faraday.newdo|conn|conn.options.timeout=20endresponse=conn.get(url

    5. ruby - 从 Ruby 中的主机名获取 IP 地址 - 2

      我有一个存储主机名的Ruby数组server_names。如果我打印出来，它看起来像这样:["hostname.abc.com","hostname2.abc.com","hostname3.abc.com"]相当标准。我想要做的是获取这些服务器的IP(可能将它们存储在另一个变量中)。看起来IPSocket类可以做到这一点，但我不确定如何使用IPSocket类遍历它。如果它只是尝试像这样打印出IP:server_names.eachdo|name|IPSocket::getaddress(name)pnameend它提示我没有提供服务器名称。这是语法问题还是我没有正确使用类？输出:ge

    6. ruby - 获取模块中定义的所有常量的值 - 2

      我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？ 最佳答案 为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

    7. ruby-on-rails - 获取 inf-ruby 以使用 ruby​​ 版本管理器 (rvm) - 2

      我安装了ruby​​版本管理器，并将RVM安装的ruby​​实现设置为默认值，这样'哪个ruby'显示'~/.rvm/ruby-1.8.6-p383/bin/ruby'但是当我在emacs中打开inf-ruby缓冲区时，它使用安装在/usr/bin中的ruby​​。有没有办法让emacs像shell一样尊重ruby​​的路径？谢谢! 最佳答案 我创建了一个emacs扩展来将rvm集成到emacs中。如果您有兴趣，可以在这里获取:http://github.com/senny/rvm.el

    8. Ruby 从大范围中获取第 n 个项目 - 2

      假设我有这个范围:("aaaaa".."zzzzz")如何在不事先/每次生成整个项目的情况下从范围中获取第N个项目？ 最佳答案 一种快速简便的方法:("aaaaa".."zzzzz").first(42).last#==>"aaabp"如果出于某种原因你不得不一遍又一遍地这样做，或者如果你需要避免为前N个元素构建中间数组，你可以这样写:moduleEnumerabledefskip(n)returnto_enum:skip,nunlessblock_given?each_with_indexdo|item,index|yieldit

    9. ruby - Net::HTTP 获取源代码和状态 - 2

      我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

    10. Python 相当于 Perl/Ruby ||= - 2

      这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

    随机推荐