Re: [networkx-discuss] Subgraph from given root out to specific depth

[Aric Hagberg]

On Thu, Dec 13, 2012 at 9:54 PM, <se...@bromberger.com> wrote:
> Consider the following graph:
>>>> g = nx.Graph()
>>>> g.add_edges_from(((1,2),(2,3),(2,4),(3,5),(4,5),(4,6),(5,6)))
>
> "Graph to depth 3 from node 1" should include the following paths:
>
> depth 1: 1-2
> depth 2: 1-2-3, 1-2-4
> depth 3: 1-2-3-5, 1-2-4-5
>
> I can't get there from single_source_shortest_path, since it doesn't provide
> multiple equal-length paths for loops:
>>>> nx.single_source_shortest_path(g,1,cutoff=3)
> {1: [1],
> 2: [1, 2],
> 3: [1, 2, 3],
> 4: [1, 2, 4],
> 5: [1, 2, 3, 5],
> 6: [1, 2, 4, 6]}
>
> (note: I need 5: [1,2,4,5] in there as well)
>
>>>>nx.single_source_shortest_path_length(g,1,cutoff=3)
> {1: 0, 2: 1, 3: 2, 4: 2, 5: 3, 6: 3}
>
> I haven't yet found an elegant way to get a subgraph of a graph from an
> arbitrary node out to a given depth. I've done it with the following code,
> but I'm hoping I've overlooked something native to networkx:
>
> def graphtodepth(g,root,depth):
> neighbor_set = set()
> traversed = set()
> rootset = set([root])
> while (depth >= 0) and (rootset):
> newrootset = set()
> for d in rootset:
> traversed.add(d)
> neighbor_set.add(d)
> neighbors = g.neighbors(d)
> newrootset = newrootset.union(set(neighbors)) - traversed
> neighbor_set = neighbor_set.union(neighbors)
> rootset = newrootset
> depth -= 1
> return g.subgraph(list(neighbor_set))
>
> Is there a better/more elegant way of doing this?

Maybe you can use nx.ego_graph() with radius=3?


In [1]: import networkx as nx

In [2]: >>> g = nx.Graph()

In [3]: >>> g.add_edges_from(((1,2),(2,3),(2,4),(3,5),(4,5),(4,6),(5,6)))

In [4]: nx.ego_graph(g,1,radius=3).edges()
Out[4]: [(1, 2), (2, 3), (2, 4), (3, 5), (4, 5), (4, 6), (5, 6)]

In [5]: nx.ego_graph(g,1,radius=2).edges()
Out[5]: [(1, 2), (2, 3), (2, 4)]

Aric

[se...@bromberger.com]

Aric,

Thanks for the quick reply! But ego_graph isn't quite right, I don't think: at depth=3, there should be no edge (5,6). That happens at depth=4. 

[se...@bromberger.com]

Sorry to followup to my own post, but thanks to Aric, I found an error in my code above. Here's (my latest attempt at) code to get all nodes (and relevant edges) from a graph "g" centered at node "root", following paths out to depth "depth":

def graphtodepth(g,root,depth):

    link_set = set()

    traversed = set()

    rootset = set([root])

    while (depth >= 0) and (rootset):

        newrootset = set()

        for d in rootset:

            traversed.add(d)

            neighbors = g.neighbors(d)

            nextlinks = [(d,n) for n in neighbors]

            newrootset = newrootset.union(set(neighbors)) - traversed

            link_set = link_set.union(nextlinks)

        rootset = newrootset

        depth -= 1

    return nx.Graph(list(link_set)) 

As you can see, subgraph() won't work - when a node has multiple paths to it at different depths, subgraph() will include all of them if the nodes along the path are included, even if the depth exceeds the specified depth. I believe the code above handles this case properly.

[Dan Schult]

Doesn't ego_graph do this?  

You reply to Aric that 1-2-4-6 should not be in depth 3 but it looks like it should...

What is different between what you are doing and ego_graph?

Dan

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/nO_KYsqviy4J.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[se...@bromberger.com]

On Friday, December 14, 2012 5:03:04 AM UTC-8, Dan Schult wrote:

Doesn't ego_graph do this?  

You reply to Aric that 1-2-4-6 should not be in depth 3 but it looks like it should...

What is different between what you are doing and ego_graph?

Dan

Dan,

Thanks for your reply.

 ego_graph returns the edge (5,6) at radius three, which is not valid:

In [4]: g.edges()

Out[4]: [(1, 2), (2, 3), (2, 4), (3, 5), (4, 5), (4, 6), (5, 6)]

In [5]: nx.ego_graph(g,1,radius=3).edges() 

Out[5]: [(1, 2), (2, 3), (2, 4), (3, 5), (4, 5), (4, 6), (5, 6)]

The (5,6) edge should only be included in paths that have length greater than three:

1-2-3-5-6 and 1-2-4-5-6.

Nodes 5 and 6 should be included in the graph at radius 3 (node 5 via 1-2-3-5 and 1-2-4-5; node 6 via 1-2-4-6), but they should not be connected at that radius.

This may not be a failing of ego_graph; it does, however, suggest that ego_graph isn't what I need for following paths in a graph from a root out to all nodes within a particular path radius.

[se...@bromberger.com]

It's been a few days with no followup, so I'm just wondering whether there'd be any interest in including this type of graph generator in the package, and if so, what it should be named. 

The algorithm differs from ego_graph in that ego_graph does not limit edges within a specific radius - it just includes nodes out to a certain radius and returns a subgraph with any edges within that set of nodes regardless of the radius at which the edge is created.

The code I posted above takes radius into account when determining which edges / adjacencies to include, so that the example above would not include the (5,6) adjacency since it happens at a radius greater than the cutoff. This has the effect of creating a subgraph of nodes with all, and only, paths included out to the radius/cutoff. The maximum path depth is therefore equal to the cutoff.

If this code is useful just for me, then so be it - I won't bother submitting it via a pull request :)

[Dan Schult]

On Dec 18, 2012, at 11:59 AM, se...@bromberger.com wrote:
>
> It's been a few days with no followup, so I'm just wondering whether there'd be any interest in including this type of graph generator in the package, and if so, what it should be named.
>
> The algorithm differs from ego_graph in that ego_graph does not limit edges within a specific radius - it just includes nodes out to a certain radius and returns a subgraph with any edges within that set of nodes regardless of the radius at which the edge is created.
>
> The code I posted above takes radius into account when determining which edges / adjacencies to include, so that the example above would not include the (5,6) adjacency since it happens at a radius greater than the cutoff. This has the effect of creating a subgraph of nodes with all, and only, paths included out to the radius/cutoff. The maximum path depth is therefore equal to the cutoff.
>
> If this code is useful just for me, then so be it - I won't bother submitting it via a pull request :)

What is your use case? Is it an area lots of others work with? Could you see it needing weighted edge capability?

It seems there are an endless supply of useful shortest-path functions. This one could be called ego_edge_graph(G,source,cutoff). Even better would be to find a name for it in the literature somewhere and call it that. We've got ego_graph.py located in the repository with the graph generators, but it certainly uses functions from the algorithms area. I'm thinking that would be a good home. If you want to match what was done with ego_graph you could create a routine to generate the edges similar to bfs_edges(). Then the ego_edge_graph could take that edge generator and build a graph with it.
Dan

[se...@bromberger.com]

My specific use case has to do with answering the question, "Show me all nodes from a root out to a given radius with the set of edges that made up each path." It's for a specific network-related application; I don't know how many others would benefit from it but I suspect that the original author of https://groups.google.com/d/topic/networkx-discuss/EOFmAh901SI/discussion was looking for something similar.

It could handle different edge weights, I guess - but right now, if you assume each edge has a weight of 1, the algorithm is designed to include all paths from (G, root)  that have a total weight <= "radius".

I tried implementing this using all_simple_paths() but it was much less efficient than the set() method I wound up using in the first place.

Let me look at bfs_edges() and see if I can create an edge generator in /traversal (and some graph generator using it in /generators). I like the name ego_edge_graph; the issue is that I'm not a graph theorist by any stretch of the imagination so I'm not up on the current literature. My original post was an inquiry as to whether such functionality already existed (and I've determined it doesn't yet, at least in networkx).

Thanks for the feedback!

Seth.

[Seth Bromberger]

Hi Paul,

Let me know whether the code I posted works for you. Happy to discuss any improvements you might suggest. I think it should work with a list of root nodes with very little modification. 

Cheers,

Seth. 

On Dec 30, 2012, at 18:47, Polo <paul.an...@gmail.com> wrote:

+1

I am also looking for something like extracting a subgraph from a root node (rather : from **several** identified nodes / vertices)  following more or less specific paths until a defined maximal depth is achieved.

For now, I am trying to deal with Neo4jj/Gremlin/Bulbs, and I am giving a try to the De Wilde solution (at https://groups.google.com/forum/?fromgroups=#!topic/gremlin-users/02CSSaJzXS8), but I would really welcome a more systematic way of dealing with subgraphs.

Happy New Year !

Paul

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/rH2GkxB_CLEJ.