logo标签列表

NetworkX：从边生成诱导子图

pythongraphnetworkx
6

网络图(networkx)仅有一个名为

Graph.subgraph()

的函数用于创建由节点诱导出的子图。 但是如何从边列表构建子图呢？

谢谢！

你是否关心图实际上指向原始对象（使边缘携带对原始图的边缘的引用）？他们下面描述的方式是有效等效的（对于类型为nx.Graph G的原始图）G.subgraph(nbunch).copy()（请参见https://networkx.readthedocs.org/en/latest/reference/generated/networkx.Graph.subgraph.html#networkx.Graph.subgraph）。如果您想以保留引用的方式执行此操作，我认为您需要采用不同的方法。我可能需要这样做，如果我解决了它，我会发布一个答案。 - mpacer
2
我看到了一个Graph.edge_subgraph方法，但是在我的networkx版本（1.10）中似乎没有该方法。 - dbn
@dbw 这一定是最近实现的，我很喜欢它的实现方式。不确定是否喜欢你需要单独声明一个副本而不是传递参数，但这可能有助于API的一致性。 - mpacer
5个回答
5

如果您有一组边的列表，那么您已经拥有了子图。只需在该列表上调用nx.Graph，并可以选择添加原始图中未连接的节点。从文档中获取更多信息。

Graph.__init__(data=None, **attr)

用边、名称和图属性初始化一个图。用于初始化图的数据。如果数据为None（默认值），则创建一个空图。数据可以是边列表或任何NetworkX图对象。
希望你不介意，我通过添加文档链接和页面上的更多有用信息来改进了你的答案。 - Hooked
我已经有了一个图g，我想基于部分边创建一个子图。igraph包有相关的函数，但似乎networkx只能构建从节点引出的子图。 - user2281114
@user2281114：那是因为您不需要使用函数。您可以从边缘列表中构造一个新的图形，它将恰好是您想要的子图。 - Fred Foo
2
这会删除节点和边的属性。 - dbn
2
如果您想要一个具有Graph.subgraph()在从节点创建的子图中所具有的属性的函数，但是这个函数是在边缘迭代器上工作的，那么您需要保留对原始图形、边缘和节点的引用，以便能够传播图形、边缘或节点数据属性的更改。特别是从Graph.subgraph()的docstring中可以看出：

图形、边缘或节点属性只是指向原始图形。因此，对节点或边缘结构的更改不会反映在原始图形中，而对属性的更改则会。

要创建一个具有其自己的边/节点属性副本的子图，请使用: nx.Graph(G.subgraph(nbunch))

如果边缘属性是容器，则可以使用以下方式获得深度拷贝：G.subgraph(nbunch).copy()

目前提议的方法将不会反映其属性在原始图中的更改，因为它们将从头开始创建一个新的图形。
没有内置的函数/方法可以使用边缘列表完成这个任务。但是这个函数使用了节点.subgraph的基础设施，因此应该适用于Graph和DiGraph。它不适用于MultiGraph和MultiDiGraph，因为MultiGraph和MultiDiGraph可能需要引用边缘的键，而当前的方法忽略了第二个参数之后的参数，因此不考虑传递的边缘列表是否附带字典属性。即使它是在没有引用的情况下创建的（通过传递ref_back=False），它也不会使用nx.Graph或nx.DiGraph类初始化程序创建一个新图形，而是对原始图形进行深度拷贝。可以扩展它以涵盖其他情况...但是我现在不需要这样做，直到有人明确要求为止，我将假定没有其他人需要它（如果您想查看我在实践中使用的版本，请参见github）。
def subgraph_from_edges(G,edge_list,ref_back=True):
    """
    Creates a networkx graph that is a subgraph of G
    defined by the list of edges in edge_list.        

    Requires G to be a networkx Graph or DiGraph
    edge_list is a list of edges in either (u,v) or (u,v,d) form
    where u and v are nodes comprising an edge, 
    and d would be a dictionary of edge attributes

    ref_back determines whether the created subgraph refers to back
    to the original graph and therefore changes to the subgraph's 
    attributes also affect the original graph, or if it is to create a
    new copy of the original graph. 
    """

    sub_nodes = list({y for x in edge_list for y in x[0:2]})
    edge_list_no_data = [edge[0:2] for edge in edge_list]
    assert all([e in G.edges() for e in edge_list_no_data])

    if ref_back:
        G_sub = G.subgraph(sub_nodes)
        for edge in G_sub.edges():
            if edge not in edge_list_no_data:
                G_sub.remove_edge(*edge)
    else:
        G_sub = G.subgraph(sub_nodes).copy()
        for edge in G_sub.edges():
            if edge not in edge_list_no_data:
                G_sub.remove_edge(*edge)

    return G_sub

技巧在于，任何未出现在边缘中的节点都可以从图中安全地删除（给我们我们的节点子集），然后您可以删除任何剩余但不在您的边缘列表中的边缘。
注意：我意识到这现在是一个相当古老的问题，但是提供的答案实际上没有回答如果将询问者想要直接引用原始图形、边缘和节点（特别是包括它们的数据属性）的情况。我需要那个解决方案，所以我认为我会发布它。
虽然这是一篇旧帖子，但我正在寻找具有MultiDiGraph功能的实现。 - Erotemic
1
相比我试图恢复的一些旧代码，这个还不算太老 :）。而且我现在无法为MultiDiGraph编写代码，但是关键是要存储您想保留的每个边的键。可能需要删除的行是edge_list_no_data = [edge[0:2] for edge in edge_list]，并且for edge in G_sub.edges():需要更改为类似于for edge in G_sub.edges(keys=True):的内容，但是然后您需要确保edge_list_no_data确实具有其他行所需的键。 - mpacer
虽然有些老旧，但我在这里贴出一些建议，以防有人需要。对于非双向图，“edge in edge_list_no_data”最好改为“(u,v) in edge_list_no_data or (v,u) in edge_list_no_data”或“G.has_edge(u,v)”，因为节点顺序可能会引起问题。如果我们只需要边缘的属性，那么函数可以很容易地编写为“G_sub = networkx.Graph([(u, v, d) for u, v, d in G.edges(data=True) if ((u, v) in edge_list) or ((v, u) in edge_list)])”。 - Young
@Young 我假设你正在处理的是非双向图，并且你正在小心地选择要保留哪些边。而非双向图实际上正是我编写这个程序的使用情况。有些情况下，你可能会遇到一个包含2个节点循环的图，并且只想返回没有循环的图。在这种情况下，你的一行代码将无法删除边的一个方向同时保留另一个方向。此外，它要么无法引用原始图形，要么无法创建新副本。我认为是前者，但我不确定。 - mpacer
2

@larsmans的答案是正确的。这里是一个简单的例子：

In [1]: import networkx as nx

In [2]: G = nx.path_graph(6)

In [3]: G.edges()
Out[3]: [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]

In [4]: subgraph_edges = [(1,2), (3,4)]

In [5]: S = nx.Graph(subgraph_edges)

In [6]: S.edges()
Out[6]: [(1, 2), (3, 4)]
这在networkx上运行良好，谢谢！但igraph需要连续编号，所以我混淆了两个问题。 - user2281114
2
根据dbn的评论，networkx现在包括一个名为nx.edge_subgraph的函数来实现此功能。它保留了原始图形的属性，但对这些属性的更改将反映在原始图形中。
G = nx.path_graph(5)
S = G.edge_subgraph([(0, 1), (3, 4)])
list(S.nodes) # [0, 1, 3, 4]
list(H.edges) # [(0, 1), (3, 4)]
0
基于之前的回答，一个保留原始图形及其所有属性的非常简单的解决方法可能是：
FG = nx.Graph(fedges)
G = G.subgraph(FG.nodes())

这里，fedges 是构建子图的筛选边的列表。首先，使用筛选后的边创建一个新的临时图(FG)。然后使用节点列表(FG.nodes())从原图中获取一个子图。由于你实际上是在原始图对象上使用 subgraph 函数，因此不会失去任何属性。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接