Module Expr Str ImportFrom alias ImportFrom alias Import alias identifier ImportFrom alias Assign NameStore Call AttributeLoad Str attr ListLoad Str Assign NameStore ListLoad Str Str FunctionDef arguments args NameParam NameParam defaults NameLoad body Expr Str For NameStore Call AttributeLoad NameLoad attr NameLoad body For NameStore Call NameLoad Call AttributeLoad NameLoad attr NameLoad NameLoad body Expr Yield NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults NameLoad body Expr Str Return Call NameLoad Call NameLoad Call NameLoad NameLoad keyword NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults NameLoad body If CompareIs NameLoad NameLoad body Assign NameStore Call NameLoad NameLoad orelse Assign NameStore Call NameLoad NameLoad Assign NameStore Set NameLoad Assign NameStore Call NameLoad ListLoad NameLoad While NameLoad body Assign NameStore Call AttributeLoad NameLoad attr Expr Yield NameLoad Assign NameStore Call NameLoad Call NameLoad Call AttributeLoad NameLoad attr BinOpSub Call NameLoad SubscriptLoad NameLoad Index NameLoad NameLoad keyword Call NameLoad Num Assign NameStore ListComp NameLoad comprehension TupleStore NameStore NameStore NameLoad Expr Call AttributeLoad NameLoad attr NameLoad Expr Call AttributeLoad NameLoad attr NameLoad decorator_list FunctionDef arguments args NameParam defaults body Assign NameStore Call NameLoad NameLoad Assign NameStore Num Assign NameStore NameLoad While NameLoad body Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr NameLoad NameLoad Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr If CompareLtE NameLoad NameLoad body Break Assign NameStore NameLoad Assign NameStore GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr CompareEq NameLoad NameLoad Assign TupleStore NameStore NameStore Call NameLoad Call AttributeLoad NameLoad attr NameLoad keyword Call NameLoad Num Return NameLoad decorator_list
N/A N/A 
Cuthill-McKee ordering of graph nodes to produce sparse matrices
 collections deque operator itemgetter N/A networkx nx utils arbitrary_element N/A __author__ N/A N/A join N/A Aric Hagberg <aric.hagberg@gmail.com> N/A __all__ N/A cuthill_mckee_ordering reverse_cuthill_mckee_ordering cuthill_mckee_ordering N/A N/A G heuristic N/A None N/A N/A Generate an ordering (permutation) of the graph nodes to make
    a sparse matrix.

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

    Parameters
    ----------
    G : graph
      A NetworkX graph

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

    Returns
    -------
    nodes : generator
       Generator of nodes in Cuthill-McKee ordering.

    Examples
    --------
    >>> from networkx.utils import cuthill_mckee_ordering
    >>> G = nx.path_graph(4)
    >>> rcm = list(cuthill_mckee_ordering(G))
    >>> A = nx.adjacency_matrix(G, nodelist=rcm) # doctest: +SKIP

    Smallest degree node as heuristic function:

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


    See Also
    --------
    reverse_cuthill_mckee_ordering

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


    References
    ----------
    .. [1] E. Cuthill and J. McKee.
       Reducing the bandwidth of sparse symmetric matrices,
       In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969.
       http://doi.acm.org/10.1145/800195.805928
    .. [2]  Steven S. Skiena. 1997. The Algorithm Design Manual.
       Springer-Verlag New York, Inc., New York, NY, USA.
     N/A c N/A N/A nx connected_components G N/A N/A n N/A connected_cuthill_mckee_ordering N/A N/A G subgraph c heuristic N/A N/A N/A n N/A reverse_cuthill_mckee_ordering N/A N/A G heuristic N/A None N/A N/A Generate an ordering (permutation) of the graph nodes to make
    a sparse matrix.

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

    Parameters
    ----------
    G : graph
      A NetworkX graph

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

    Returns
    -------
    nodes : generator
       Generator of nodes in reverse Cuthill-McKee ordering.

    Examples
    --------
    >>> from networkx.utils import reverse_cuthill_mckee_ordering
    >>> G = nx.path_graph(4)
    >>> rcm = list(reverse_cuthill_mckee_ordering(G))
    >>> A = nx.adjacency_matrix(G, nodelist=rcm) # doctest: +SKIP

    Smallest degree node as heuristic function:

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


    See Also
    --------
    cuthill_mckee_ordering

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

    References
    ----------
    .. [1] E. Cuthill and J. McKee.
       Reducing the bandwidth of sparse symmetric matrices,
       In Proc. 24th Nat. Conf. ACM, pages 157-72, 1969.
       http://doi.acm.org/10.1145/800195.805928
    .. [2]  Steven S. Skiena. 1997. The Algorithm Design Manual.
       Springer-Verlag New York, Inc., New York, NY, USA.
     N/A N/A reversed N/A list N/A cuthill_mckee_ordering G heuristic heuristic N/A connected_cuthill_mckee_ordering N/A N/A G heuristic N/A None N/A N/A N/A heuristic None N/A N/A start N/A pseudo_peripheral_node G N/A N/A start N/A heuristic G N/A visited N/A start N/A queue N/A deque N/A start N/A queue N/A N/A parent N/A N/A queue popleft N/A N/A parent N/A nd N/A sorted N/A list N/A N/A G degree N/A N/A set N/A G N/A parent visited key N/A itemgetter 1 N/A children N/A n N/A N/A n d nd N/A N/A N/A visited update children N/A N/A N/A queue extend children N/A pseudo_peripheral_node N/A N/A G N/A N/A N/A u N/A arbitrary_element G N/A lp 0 N/A v u N/A True N/A N/A spl N/A dict N/A N/A nx shortest_path_length G v N/A l N/A max N/A N/A spl values N/A N/A l lp N/A N/A N/A lp l N/A farthest N/A n N/A N/A n dist N/A N/A spl items N/A dist l N/A N/A v deg N/A min N/A N/A G degree farthest key N/A itemgetter 1 N/A v N/A