networkx:creating a subgraph induced from edges

Question

networkx only has a function

Graph.subgraph()

to create a subgraph induced from nodes. but how to construct a subgraph from edge list ?

thanks !

Answer 1

If you have a list of edges, then you already have the subgraph. Just call nx.Graph on the list, and optionally add the (unconnected) nodes from the original graph. From the docs

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

Initialize a graph with edges, name, graph attributes.
Data to initialize graph. If data=None (default) an empty graph is created. The data can be an edge list, or any NetworkX graph object.

Answer 2

The answer by @larsmans is correct. Here is a simple example:

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)]

Answer 3

If you want to have a function that has the properties that Graph.subgraph() has for subgraphs created from nodes but instead this function works on iterators of edges, you need to keep references to the original graph, edges and nodes to be able to propagate changes in the graph, edge or node data attributes. Notably from the docstring of Graph.subgraph():

The graph, edge or node attributes just point to the original graph. So changes to the node or edge structure will not be reflected in the original graph while changes to the attributes will.

To create a subgraph with its own copy of the edge/node attributes use: nx.Graph(G.subgraph(nbunch))

If edge attributes are containers, a deep copy can be obtained using: G.subgraph(nbunch).copy()

The currently proposed methods will not reflect changes in their attributes back in the original graph, as they will create a new graph from scratch.

There is no built in function/method for accomplishing this with a list of edges. But this function uses the infrastructure of the node .subgraph and thus should work for Graph and DiGraph. It will not work for not MultiGraph and MultiDiGraph. This is because MultiGraph and MultiDiGraph may need you to refer to the key of the edge and the current approach ignores arguments after the second so as to be insensitive to whether the passed in list of edges has attributes attached as a dictionary or not. Also, even when it is created without reference (by passing ref_back=False), it does not create a new graph using the nx.Graph or nx.DiGraph class initializers, but a deepcopy of the original graph. It would be possible to extend it to cover other cases… but I don't need that for now, and until someone explicitly asks for it I'm going to assume that no one else does (see github if you want to see the version that I've used in practice).

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

The trick is that any nodes not present in the edges can be safely excised from the graph (giving us our node subset), and then you can remove any edges that remain but aren't in your edge list.

Note: I realize that this is now a fairly ancient question, but the answers provided don't actually answer the question if interpreted as a case where the asker wanted a graph that directly referenced the original graph, edges and nodes (notably including their data attributes). I needed that solution, so I figured I'd post it regardless.

Answer 4

As per dbn's comment, networkx now includes a function nx.edge_subgraph to do this. It preserves the attributes from the original graph, however changes to these attributes will be reflected in the original graph.

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)]