Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / utils / rcm.py @ 5cef0f13

History | View | Annotate | Download (4.79 KB)

1
"""
2
Cuthill-McKee ordering of graph nodes to produce sparse matrices
3
"""
4
#    Copyright (C) 2011-2014 by
5
#    Aric Hagberg <aric.hagberg@gmail.com>
6
#    All rights reserved.
7
#    BSD license.
8
from collections import deque
9
from operator import itemgetter
10

    
11
import networkx as nx
12
from ..utils import arbitrary_element
13

    
14
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>'])
15
__all__ = ['cuthill_mckee_ordering',
16
           'reverse_cuthill_mckee_ordering']
17

    
18

    
19
def cuthill_mckee_ordering(G, heuristic=None):
20
    """Generate an ordering (permutation) of the graph nodes to make
21
    a sparse matrix.
22

23
    Uses the Cuthill-McKee heuristic (based on breadth-first search) [1]_.
24

25
    Parameters
26
    ----------
27
    G : graph
28
      A NetworkX graph
29

30
    heuristic : function, optional
31
      Function to choose starting node for RCM algorithm.  If None
32
      a node from a pseudo-peripheral pair is used.  A user-defined function
33
      can be supplied that takes a graph object and returns a single node.
34

35
    Returns
36
    -------
37
    nodes : generator
38
       Generator of nodes in Cuthill-McKee ordering.
39

40
    Examples
41
    --------
42
    >>> from networkx.utils import cuthill_mckee_ordering
43
    >>> G = nx.path_graph(4)
44
    >>> rcm = list(cuthill_mckee_ordering(G))
45
    >>> A = nx.adjacency_matrix(G, nodelist=rcm) # doctest: +SKIP
46

47
    Smallest degree node as heuristic function:
48

49
    >>> def smallest_degree(G):
50
    ...     return min(G, key=G.degree)
51
    >>> rcm = list(cuthill_mckee_ordering(G, heuristic=smallest_degree))
52

53

54
    See Also
55
    --------
56
    reverse_cuthill_mckee_ordering
57

58
    Notes
59
    -----
60
    The optimal solution the the bandwidth reduction is NP-complete [2]_.
61

62

63
    References
64
    ----------
65
    .. [1] E. Cuthill and J. McKee.
66
       Reducing the bandwidth of sparse symmetric matrices,
67
       In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969.
68
       http://doi.acm.org/10.1145/800195.805928
69
    .. [2]  Steven S. Skiena. 1997. The Algorithm Design Manual.
70
       Springer-Verlag New York, Inc., New York, NY, USA.
71
    """
72
    for c in nx.connected_components(G):
73
        for n in connected_cuthill_mckee_ordering(G.subgraph(c), heuristic):
74
            yield n
75

    
76

    
77
def reverse_cuthill_mckee_ordering(G, heuristic=None):
78
    """Generate an ordering (permutation) of the graph nodes to make
79
    a sparse matrix.
80

81
    Uses the reverse Cuthill-McKee heuristic (based on breadth-first search)
82
    [1]_.
83

84
    Parameters
85
    ----------
86
    G : graph
87
      A NetworkX graph
88

89
    heuristic : function, optional
90
      Function to choose starting node for RCM algorithm.  If None
91
      a node from a pseudo-peripheral pair is used.  A user-defined function
92
      can be supplied that takes a graph object and returns a single node.
93

94
    Returns
95
    -------
96
    nodes : generator
97
       Generator of nodes in reverse Cuthill-McKee ordering.
98

99
    Examples
100
    --------
101
    >>> from networkx.utils import reverse_cuthill_mckee_ordering
102
    >>> G = nx.path_graph(4)
103
    >>> rcm = list(reverse_cuthill_mckee_ordering(G))
104
    >>> A = nx.adjacency_matrix(G, nodelist=rcm) # doctest: +SKIP
105

106
    Smallest degree node as heuristic function:
107

108
    >>> def smallest_degree(G):
109
    ...     return min(G, key=G.degree)
110
    >>> rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree))
111

112

113
    See Also
114
    --------
115
    cuthill_mckee_ordering
116

117
    Notes
118
    -----
119
    The optimal solution the the bandwidth reduction is NP-complete [2]_.
120

121
    References
122
    ----------
123
    .. [1] E. Cuthill and J. McKee.
124
       Reducing the bandwidth of sparse symmetric matrices,
125
       In Proc. 24th Nat. Conf. ACM, pages 157-72, 1969.
126
       http://doi.acm.org/10.1145/800195.805928
127
    .. [2]  Steven S. Skiena. 1997. The Algorithm Design Manual.
128
       Springer-Verlag New York, Inc., New York, NY, USA.
129
    """
130
    return reversed(list(cuthill_mckee_ordering(G, heuristic=heuristic)))
131

    
132

    
133
def connected_cuthill_mckee_ordering(G, heuristic=None):
134
    # the cuthill mckee algorithm for connected graphs
135
    if heuristic is None:
136
        start = pseudo_peripheral_node(G)
137
    else:
138
        start = heuristic(G)
139
    visited = {start}
140
    queue = deque([start])
141
    while queue:
142
        parent = queue.popleft()
143
        yield parent
144
        nd = sorted(list(G.degree(set(G[parent]) - visited)),
145
                    key=itemgetter(1))
146
        children = [n for n, d in nd]
147
        visited.update(children)
148
        queue.extend(children)
149

    
150

    
151
def pseudo_peripheral_node(G):
152
    # helper for cuthill-mckee to find a node in a "pseudo peripheral pair"
153
    # to use as good starting node
154
    u = arbitrary_element(G)
155
    lp = 0
156
    v = u
157
    while True:
158
        spl = dict(nx.shortest_path_length(G, v))
159
        l = max(spl.values())
160
        if l <= lp:
161
            break
162
        lp = l
163
        farthest = (n for n, dist in spl.items() if dist == l)
164
        v, deg = min(G.degree(farthest), key=itemgetter(1))
165
    return v