1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
"""
Ego graph.
"""
# Copyright (C) 2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__author__ = """\n""".join(['Drew Conway <drew.conway@nyu.edu>',
'Aric Hagberg <hagberg@lanl.gov>'])
__all__ = ['ego_graph']
import networkx as nx
def ego_graph(G,n,radius=1,center=True,undirected=False,distance=None):
"""Returns induced subgraph of neighbors centered at node n within
a given radius.
Parameters
----------
G : graph
A NetworkX Graph or DiGraph
n : node
A single node
radius : number, optional
Include all neighbors of distance<=radius from n.
center : bool, optional
If False, do not include center node in graph
undirected : bool, optional
If True use both in- and out-neighbors of directed graphs.
distance : key, optional
Use specified edge data key as distance. For example, setting
distance='weight' will use the edge weight to measure the
distance from the node n.
Notes
-----
For directed graphs D this produces the "out" neighborhood
or successors. If you want the neighborhood of predecessors
first reverse the graph with D.reverse(). If you want both
directions use the keyword argument undirected=True.
Node, edge, and graph attributes are copied to the returned subgraph.
"""
if undirected:
if distance is not None:
sp,_=nx.single_source_dijkstra(G.to_undirected(),
n,cutoff=radius,
weight=distance)
else:
sp=nx.single_source_shortest_path_length(G.to_undirected(),
n,cutoff=radius)
else:
if distance is not None:
sp,_=nx.single_source_dijkstra(G,
n,cutoff=radius,
weight=distance)
else:
sp=nx.single_source_shortest_path_length(G,n,cutoff=radius)
H=G.subgraph(sp).copy()
if not center:
H.remove_node(n)
return H
|
