Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / ego.py @ 5cef0f13

History | View | Annotate | Download (2.24 KB)

1
"""
2
Ego graph.
3
"""
4
#    Copyright (C) 2010 by
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    Dan Schult <dschult@colgate.edu>
7
#    Pieter Swart <swart@lanl.gov>
8
#    All rights reserved.
9
#    BSD license.
10
__author__ = """\n""".join(['Drew Conway <drew.conway@nyu.edu>',
11
                            'Aric Hagberg <hagberg@lanl.gov>'])
12
__all__ = ['ego_graph']
13

    
14
import networkx as nx
15

    
16

    
17
def ego_graph(G, n, radius=1, center=True, undirected=False, distance=None):
18
    """Returns induced subgraph of neighbors centered at node n within
19
    a given radius.
20

21
    Parameters
22
    ----------
23
    G : graph
24
      A NetworkX Graph or DiGraph
25

26
    n : node
27
      A single node
28

29
    radius : number, optional
30
      Include all neighbors of distance<=radius from n.
31

32
    center : bool, optional
33
      If False, do not include center node in graph
34

35
    undirected : bool, optional
36
      If True use both in- and out-neighbors of directed graphs.
37

38
    distance : key, optional
39
      Use specified edge data key as distance.  For example, setting
40
      distance='weight' will use the edge weight to measure the
41
      distance from the node n.
42

43
    Notes
44
    -----
45
    For directed graphs D this produces the "out" neighborhood
46
    or successors.  If you want the neighborhood of predecessors
47
    first reverse the graph with D.reverse().  If you want both
48
    directions use the keyword argument undirected=True.
49

50
    Node, edge, and graph attributes are copied to the returned subgraph.
51
    """
52
    if undirected:
53
        if distance is not None:
54
            sp, _ = nx.single_source_dijkstra(G.to_undirected(),
55
                                              n, cutoff=radius,
56
                                              weight=distance)
57
        else:
58
            sp = dict(nx.single_source_shortest_path_length(G.to_undirected(),
59
                                                            n, cutoff=radius))
60
    else:
61
        if distance is not None:
62
            sp, _ = nx.single_source_dijkstra(G,
63
                                              n, cutoff=radius,
64
                                              weight=distance)
65
        else:
66
            sp = dict(nx.single_source_shortest_path_length(G, n, cutoff=radius))
67

    
68
    H = G.subgraph(sp).copy()
69
    if not center:
70
        H.remove_node(n)
71
    return H