Module Expr Str Import alias Import alias Import alias identifier ImportFrom alias ImportFrom alias ImportFrom alias ImportFrom alias identifier ImportFrom alias ImportFrom alias Assign NameStore Call AttributeLoad Str attr ListLoad Str Assign NameStore ListLoad Str Expr Call NameLoad Str FunctionDef arguments args NameParam NameParam defaults Num body Expr Str Assign NameStore Call AttributeLoad NameLoad attr NameLoad Assign NameStore NameLoad Assign NameStore AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr For NameStore Call AttributeLoad NameLoad attr NameLoad body Assign NameStore Call NameLoad NameLoad If CompareGt Call NameLoad NameLoad Num body Expr Call AttributeLoad SubscriptLoad NameLoad Index Num attr NameLoad For NameStore Call AttributeLoad NameLoad attr NameLoad body Assign NameStore Call NameLoad NameLoad If CompareGt Call NameLoad NameLoad Num body Expr Call AttributeLoad SubscriptLoad NameLoad Index Num attr NameLoad Assign NameStore Call NameLoad NameLoad Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr For NameStore Call NameLoad Num BinOpAdd NameLoad Num body Assign NameStore Call NameLoad NameLoad NameLoad keyword NameLoad For NameStore Call NameLoad NameLoad body If CompareLt Call NameLoad NameLoad NameLoad body Continue Assign NameStore Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call NameLoad Expr Call AttributeLoad NameLoad attr Call AttributeLoad NameLoad attr For TupleStore NameStore NameStore Call NameLoad NameLoad Num body Assign NameStore Call NameLoad NameLoad NameLoad NameLoad keyword NameLoad If CompareGt NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr NameLoad NameLoad For NameStore Call NameLoad NameLoad body If CompareLtE Call NameLoad NameLoad NameLoad body Continue Assign NameStore Call AttributeLoad NameLoad attr NameLoad For NameStore Call NameLoad NameLoad NameLoad NameLoad NameLoad body For NameStore Call NameLoad NameLoad body Assign NameStore Call AttributeLoad NameLoad attr Call AttributeLoad NameLoad attr NameLoad NameLoad If CompareLtE Call NameLoad NameLoad NameLoad body Continue Expr Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr Call NameLoad NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam defaults body Assign NameStore Call AttributeLoad NameLoad attr NameLoad For TupleStore NameStore NameStore Call NameLoad Call NameLoad Call NameLoad Call AttributeLoad NameLoad attr keyword NameLoad body Assign NameStore Call NameLoad GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr CompareEq NameLoad NameLoad If CompareEq NameLoad Num body Assign NameStore NameLoad orelse Assign NameStore Call AttributeLoad NameLoad attr ListComp Call NameLoad GeneratorExp NameLoad comprehension NameStore SubscriptLoad NameLoad Index NameLoad CompareNotIn NameLoad NameLoad comprehension NameStore NameLoad If BoolOpAnd NameLoad CompareLt Call NameLoad NameLoad NameLoad body Assign NameStore Call AttributeLoad NameLoad attr BinOpBitOr NameLoad NameLoad orelse Assign NameStore Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call AttributeLoad NameLoad attr NameLoad NameLoad While UnaryOpNot BoolOpAnd Call NameLoad NameLoad CompareGtE Call AttributeLoad NameLoad attr NameLoad NameLoad body Assign NameStore Call AttributeLoad NameLoad attr NameLoad If CompareLtE Call NameLoad NameLoad NameLoad body Break Assign NameStore Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr Expr Call AttributeLoad NameLoad attr GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr CompareEq NameLoad NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call AttributeLoad NameLoad attr NameLoad NameLoad orelse Expr Yield NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults Num body Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr If CompareLtE BinOpSub Call NameLoad NameLoad Call NameLoad NameLoad NameLoad body Return NameLoad Return NameLoad decorator_list ClassDef bases AttributeLoad NameLoad attr body Expr Str Assign NameStore Dict Str Num FunctionDef arguments args NameParam defaults body Return AttributeLoad NameLoad attr decorator_list Assign NameStore NameLoad FunctionDef arguments args NameParam NameParam defaults body Expr Str Assign NameStore AttributeLoad NameLoad attr Return Call NameLoad GeneratorExp TupleLoad NameLoad NameLoad comprehension NameStore BinOpSub BinOpSub Call NameLoad AttributeLoad NameLoad attr Call NameLoad SubscriptLoad AttributeLoad NameLoad attr Index NameLoad Call NameLoad ListLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str TryExcept body Return Call NameLoad BinOpSub BinOpSub Call NameLoad AttributeLoad NameLoad attr Call NameLoad SubscriptLoad AttributeLoad NameLoad attr Index NameLoad Call NameLoad ListLoad NameLoad handlers ExceptHandler type NameLoad body Raise Call NameLoad BinOpMod Str TupleLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults NameLoad NameLoad body Expr Str If CompareIn NameLoad NameLoad body Assign NameStore DictComp NameLoad AttributeLoad NameLoad attr comprehension NameStore BinOpSub BinOpSub Call NameLoad AttributeLoad NameLoad attr Call NameLoad SubscriptLoad AttributeLoad NameLoad attr Index NameLoad Call NameLoad ListLoad NameLoad If CompareIs NameLoad NameLoad body Return BinOpAdd Call NameLoad NameLoad CompareIn NameLoad NameLoad Return BinOpAdd Call NameLoad GeneratorExp Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr NameLoad Num comprehension NameStore NameLoad BoolOpAnd CompareIn NameLoad NameLoad Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr NameLoad Num If CompareIs NameLoad NameLoad body Assign NameStore GeneratorExp TupleLoad NameLoad DictComp NameLoad AttributeLoad NameLoad attr comprehension NameStore BinOpSub BinOpSub Call NameLoad AttributeLoad NameLoad attr Call NameLoad SubscriptLoad AttributeLoad NameLoad attr Index NameLoad Call NameLoad ListLoad NameLoad comprehension NameStore Call AttributeLoad NameLoad attr orelse Assign NameStore GeneratorExp TupleLoad NameLoad DictComp NameLoad AttributeLoad NameLoad attr comprehension NameStore BinOpSub BinOpSub Call NameLoad Call AttributeLoad NameLoad attr Call NameLoad SubscriptLoad AttributeLoad NameLoad attr Index NameLoad Call NameLoad ListLoad NameLoad comprehension NameStore Call AttributeLoad NameLoad attr NameLoad If CompareIs NameLoad NameLoad body FunctionDef arguments args defaults body For TupleStore NameStore NameStore NameLoad body Expr Yield TupleLoad NameLoad BinOpAdd Call NameLoad NameLoad CompareIn NameLoad NameLoad decorator_list orelse FunctionDef arguments args defaults body For TupleStore NameStore NameStore NameLoad body Expr Yield TupleLoad NameLoad BinOpAdd Call NameLoad GeneratorExp Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr NameLoad Num comprehension NameStore NameLoad BoolOpAnd CompareIn NameLoad NameLoad Call AttributeLoad SubscriptLoad NameLoad Index NameLoad attr NameLoad Num decorator_list Return Call NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str For NameStore AttributeLoad NameLoad attr body Expr Yield TupleLoad NameLoad BinOpSub BinOpSub Call NameLoad AttributeLoad NameLoad attr Call NameLoad SubscriptLoad AttributeLoad NameLoad attr Index NameLoad Call NameLoad ListLoad NameLoad decorator_list decorator_list
N/A N/A  Fast approximation for k-component structure
 N/A itertools N/A collections N/A networkx nx networkx.exception NetworkXError networkx.utils not_implemented_for networkx.algorithms.approximation local_node_connectivity networkx.algorithms.connectivity local_node_connectivity exact_local_node_connectivity networkx.algorithms.connectivity build_auxiliary_node_connectivity networkx.algorithms.flow build_residual_network N/A __author__ N/A N/A join N/A Jordi Torrents <jtorrents@milnou.net> N/A __all__ N/A k_components N/A N/A not_implemented_for directed k_components N/A N/A G min_density N/A 0.95 N/A N/A Returns the approximate k-component structure of a graph G.
    
    A `k`-component is a maximal subgraph of a graph G that has, at least, 
    node connectivity `k`: we need to remove at least `k` nodes to break it
    into more components. `k`-components have an inherent hierarchical
    structure because they are nested in terms of connectivity: a connected 
    graph can contain several 2-components, each of which can contain 
    one or more 3-components, and so forth.

    This implementation is based on the fast heuristics to approximate
    the `k`-component sturcture of a graph [1]_. Which, in turn, it is based on
    a fast approximation algorithm for finding good lower bounds of the number 
    of node independent paths between two nodes [2]_.
  
    Parameters
    ----------
    G : NetworkX graph
        Undirected graph

    min_density : Float
        Density relaxation treshold. Default value 0.95

    Returns
    -------
    k_components : dict
        Dictionary with connectivity level `k` as key and a list of
        sets of nodes that form a k-component of level `k` as values.
        

    Examples
    --------
    >>> # Petersen graph has 10 nodes and it is triconnected, thus all 
    >>> # nodes are in a single component on all three connectivity levels
    >>> from networkx.algorithms import approximation as apxa
    >>> G = nx.petersen_graph()
    >>> k_components = apxa.k_components(G)
    
    Notes
    -----
    The logic of the approximation algorithm for computing the `k`-component 
    structure [1]_ is based on repeatedly applying simple and fast algorithms 
    for `k`-cores and biconnected components in order to narrow down the 
    number of pairs of nodes over which we have to compute White and Newman's
    approximation algorithm for finding node independent paths [2]_. More
    formally, this algorithm is based on Whitney's theorem, which states 
    an inclusion relation among node connectivity, edge connectivity, and 
    minimum degree for any graph G. This theorem implies that every 
    `k`-component is nested inside a `k`-edge-component, which in turn, 
    is contained in a `k`-core. Thus, this algorithm computes node independent
    paths among pairs of nodes in each biconnected part of each `k`-core,
    and repeats this procedure for each `k` from 3 to the maximal core number 
    of a node in the input graph.

    Because, in practice, many nodes of the core of level `k` inside a 
    bicomponent actually are part of a component of level k, the auxiliary 
    graph needed for the algorithm is likely to be very dense. Thus, we use 
    a complement graph data structure (see `AntiGraph`) to save memory. 
    AntiGraph only stores information of the edges that are *not* present 
    in the actual auxiliary graph. When applying algorithms to this 
    complement graph data structure, it behaves as if it were the dense 
    version.

    See also
    --------
    k_components

    References
    ----------
    .. [1]  Torrents, J. and F. Ferraro (2015) Structural Cohesion: 
            Visualization and Heuristics for Fast Computation.
            http://arxiv.org/pdf/1503.04476v1

    .. [2]  White, Douglas R., and Mark Newman (2001) A Fast Algorithm for 
            Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
            http://eclectic.ss.uci.edu/~drwhite/working.pdf

    .. [3]  Moody, J. and D. White (2003). Social cohesion and embeddedness: 
            A hierarchical conception of social groups. 
            American Sociological Review 68(1), 103--28.
            http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf

     N/A k_components N/A N/A collections defaultdict list N/A node_connectivity local_node_connectivity N/A k_core N/A nx k_core N/A core_number N/A nx core_number N/A biconnected_components N/A nx biconnected_components N/A density N/A nx density N/A combinations N/A itertools combinations N/A component N/A N/A nx connected_components G N/A N/A comp N/A set component N/A N/A N/A len comp 1 N/A N/A N/A N/A N/A k_components N/A 1 append comp N/A bicomponent N/A N/A nx biconnected_components G N/A N/A bicomp N/A set bicomponent N/A N/A N/A len bicomp 2 N/A N/A N/A N/A N/A k_components N/A 2 append bicomp N/A g_cnumber N/A core_number G N/A max_core N/A max N/A N/A g_cnumber values N/A k N/A range 3 N/A max_core 1 N/A N/A C N/A k_core G k core_number g_cnumber N/A nodes N/A biconnected_components C N/A N/A N/A N/A len nodes k N/A N/A N/A SG N/A N/A G subgraph nodes N/A H N/A _AntiGraph N/A N/A N/A H add_nodes_from N/A N/A SG nodes N/A N/A u v N/A combinations SG 2 N/A N/A K N/A node_connectivity SG u v cutoff k N/A N/A k K N/A N/A N/A N/A H add_edge u v N/A h_nodes N/A biconnected_components H N/A N/A N/A N/A len h_nodes k N/A N/A N/A SH N/A N/A H subgraph h_nodes N/A Gc N/A _cliques_heuristic SG SH k min_density N/A N/A k_nodes N/A biconnected_components Gc N/A N/A Gk N/A N/A nx k_core N/A N/A SG subgraph k_nodes k N/A N/A N/A len Gk k N/A N/A N/A N/A N/A N/A k_components N/A k append N/A set Gk N/A k_components N/A _cliques_heuristic N/A N/A G H k min_density N/A N/A N/A h_cnumber N/A N/A nx core_number H N/A N/A i c_value N/A enumerate N/A sorted N/A set N/A N/A h_cnumber values reverse True N/A N/A cands N/A set N/A n N/A N/A n c N/A N/A h_cnumber items N/A c c_value N/A N/A i 0 N/A N/A overlap False N/A N/A overlap N/A N/A set intersection N/A N/A set N/A x N/A x N/A H N/A n N/A x cands N/A n cands N/A N/A overlap N/A N/A len overlap k N/A N/A SH N/A N/A H subgraph N/A cands overlap N/A N/A SH N/A N/A H subgraph cands N/A sh_cnumber N/A N/A nx core_number SH N/A SG N/A N/A nx k_core N/A N/A G subgraph SH k N/A N/A N/A N/A _same sh_cnumber N/A N/A N/A nx density SH min_density N/A N/A SH N/A N/A H subgraph SG N/A N/A N/A len SH k N/A N/A N/A sh_cnumber N/A N/A nx core_number SH N/A sh_deg N/A dict N/A N/A SH degree N/A min_deg N/A min N/A N/A sh_deg values N/A N/A N/A SH remove_nodes_from N/A n N/A N/A n d N/A N/A sh_deg items N/A d min_deg N/A SG N/A N/A nx k_core N/A N/A G subgraph SH k N/A N/A N/A SG N/A _same N/A N/A measure tol N/A 0 N/A N/A vals N/A set N/A N/A measure values N/A N/A N/A N/A max vals N/A min vals tol N/A N/A True N/A False N/A _AntiGraph N/A N/A nx Graph N/A N/A 
    Class for complement graphs.

    The main goal is to be able to work with big and dense graphs with
    a low memory foodprint.

    In this class you add the edges that *do not exist* in the dense graph,
    the report methods of the class return the neighbors, the edges and 
    the degree as if it was the dense graph. Thus it's possible to use
    an instance of this class with some of NetworkX functions. In this
    case we only use k-core, connected_components, and biconnected_components.
     N/A all_edge_dict N/A weight 1 single_edge_dict N/A N/A self N/A N/A N/A N/A self all_edge_dict N/A N/A edge_attr_dict_factory single_edge_dict __getitem__ N/A N/A self n N/A N/A N/A Return a dict of neighbors of node n in the dense graph.

        Parameters
        ----------
        n : node
           A node in the graph.

        Returns
        -------
        adj_dict : dictionary
           The adjacency dictionary for nodes connected to n.

         N/A all_edge_dict N/A self all_edge_dict N/A N/A dict N/A N/A node all_edge_dict N/A node N/A N/A N/A set N/A self adj N/A set N/A N/A self adj N/A n N/A set N/A n N/A neighbors N/A N/A self n N/A N/A N/A Return an iterator over all neighbors of node n in the 
           dense graph.

         N/A N/A N/A N/A iter N/A N/A N/A set N/A self adj N/A set N/A N/A self adj N/A n N/A set N/A n N/A N/A N/A KeyError N/A N/A N/A NetworkXError N/A The node %s is not in the graph. N/A n N/A degree N/A N/A self nbunch weight N/A None None N/A N/A Return an iterator for (node, degree) and degree for single node.

        The node degree is the number of edges adjacent to the node.

        Parameters
        ----------
        nbunch : iterable container, optional (default=all nodes)
            A container of nodes.  The container will be iterated
            through once.

        weight : string or None, optional (default=None)
           The edge attribute that holds the numerical value used 
           as a weight.  If None, then each edge has weight 1.
           The degree is the sum of the edge weights adjacent to the node.

        Returns
        -------
        deg:
            Degree of the node, if a single node is passed as argument.
        nd_iter : an iterator
            The iterator returns two-tuples of (node, degree).

        See Also
        --------
        degree

        Examples
        --------
        >>> G = nx.path_graph(4)
        >>> G.degree(0) # node 0 with degree 1
        1
        >>> list(G.degree([0,1]))
        [(0, 1), (1, 2)]

         N/A N/A nbunch self N/A N/A nbrs N/A v N/A self all_edge_dict N/A v N/A N/A N/A set N/A self adj N/A set N/A N/A self adj N/A nbunch N/A set N/A nbunch N/A N/A weight None N/A N/A N/A N/A len nbrs N/A nbunch nbrs N/A N/A N/A sum N/A N/A N/A N/A nbrs N/A nbr get weight 1 N/A nbr nbrs N/A N/A nbunch nbrs N/A N/A N/A nbrs N/A nbunch get weight 1 N/A N/A nbunch None N/A N/A nodes_nbrs N/A N/A n N/A v N/A self all_edge_dict N/A v N/A N/A N/A set N/A self adj N/A set N/A N/A self adj N/A n N/A set N/A n N/A n N/A N/A self nodes N/A N/A nodes_nbrs N/A N/A n N/A v N/A self all_edge_dict N/A v N/A N/A N/A set N/A N/A self nodes N/A set N/A N/A self adj N/A n N/A set N/A n N/A n N/A N/A self nbunch_iter nbunch N/A N/A weight None N/A d_iter N/A N/A N/A N/A N/A N/A n nbrs nodes_nbrs N/A N/A N/A N/A n N/A N/A len nbrs N/A n nbrs N/A N/A d_iter N/A N/A N/A N/A N/A N/A n nbrs nodes_nbrs N/A N/A N/A N/A n N/A N/A sum N/A N/A N/A N/A nbrs N/A nbr get weight 1 N/A nbr nbrs N/A N/A n nbrs N/A N/A N/A nbrs N/A n get weight 1 N/A N/A N/A d_iter N/A adjacency N/A N/A self N/A N/A N/A Return an iterator of (node, adjacency set) tuples for all nodes
           in the dense graph.

        This is the fastest way to look at every edge.
        For directed graphs, only outgoing adjacencies are included.

        Returns
        -------
        adj_iter : iterator
           An iterator of (node, adjacency set) for all nodes in
           the graph.

         N/A n N/A self adj N/A N/A N/A N/A n N/A N/A N/A set N/A self adj N/A set N/A N/A self adj N/A n N/A set N/A n N/A N/A