o ]Zh@sdZddlmZddlmZddlmZddlZddl m Z ddl m Z e Z dgZe d ejdd dZd d Zd dZddZddZdS)z, Moody and White algorithm for k-components ) defaultdict) combinations) itemgetterN) edmonds_karp)not_implemented_for k_componentsZdirectedc stt}|dur t}tD]}t|}t|dkr"|d|qfddtD}|D]}t|}t|dkrD|d|q1|D]}t|dkrPqGtj ||d} | dkrd|| t|ttj || |d} | t || | fg} | r| d\} } z:t | }| |}tj ||d}|| kr|dkr||t|ttj |||d} | r| |t || |fWn ty| Ynw| syqGt|S) a7 Returns the 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. Parameters ---------- G : NetworkX graph flow_func : function Function to perform the underlying flow computations. Default value :meth:`edmonds_karp`. This function performs better in sparse graphs with right tailed degree distributions. :meth:`shortest_augmenting_path` will perform better in denser graphs. Returns ------- k_components : dict Dictionary with all connectivity levels `k` in the input Graph as keys and a list of sets of nodes that form a k-component of level `k` as values. Raises ------ NetworkXNotImplemented If the input graph is directed. Examples -------- >>> # Petersen graph has 10 nodes and it is triconnected, thus all >>> # nodes are in a single component on all three connectivity levels >>> G = nx.petersen_graph() >>> k_components = nx.k_components(G) Notes ----- Moody and White [1]_ (appendix A) provide an algorithm for identifying k-components in a graph, which is based on Kanevsky's algorithm [2]_ for finding all minimum-size node cut-sets of a graph (implemented in :meth:`all_node_cuts` function): 1. Compute node connectivity, k, of the input graph G. 2. Identify all k-cutsets at the current level of connectivity using Kanevsky's algorithm. 3. Generate new graph components based on the removal of these cutsets. Nodes in a cutset belong to both sides of the induced cut. 4. If the graph is neither complete nor trivial, return to 1; else end. This implementation also uses some heuristics (see [3]_ for details) to speed up the computation. See also -------- node_connectivity all_node_cuts biconnected_components : special case of this function when k=2 k_edge_components : similar to this function, but uses edge-connectivity instead of node-connectivity References ---------- .. [1] 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 .. [2] Kanevsky, A. (1993). Finding all minimum-size separating vertex sets in a graph. Networks 23(6), 533--541. http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract .. [3] Torrents, J. and F. Ferraro (2015). Structural Cohesion: Visualization and Heuristics for Fast Computation. https://arxiv.org/pdf/1503.04476v1 Ncsg|]}|qS)subgraph.0cGr [/var/www/auris/lib/python3.10/site-packages/networkx/algorithms/connectivity/kcomponents.py xsz k_components..) flow_func)kr)rlistdefault_flow_funcnxconnected_componentssetlenappendZbiconnected_componentsZnode_connectivityZ all_node_cuts_generate_partitionnextr StopIterationpop_reconstruct_k_components)rrr componentcompZ bicomponentsZ bicomponentZbicompBrcutsstackZparent_k partitionnodesCZthis_kr rrrsPZ       c#snt}tt|||fddtdDt|D]}tj fdd|DVq%dS)asMerge sets that share k or more elements. See: http://rosettacode.org/wiki/Set_consolidation The iterative python implementation posted there is faster than this because of the overhead of building a Graph and calling nx.connected_components, but it's not clear for us if we can use it in NetworkX because there is no licence for the code. c3s4|]\}}t||@kr||fVqdSN)r)r uvrr(r r s*z_consolidate..rcsg|]}|qSr r r n)r(r rrsz _consolidate..N) rZGraphdict enumerateZadd_nodes_fromZadd_edges_fromrrrunion)Zsetsrrr"r r-r _consolidates  r4c #sdd}g}fdd|Ddd|D}||}t|D](}t|}|D]} | D] } ||| |r<|| q/q+t||krK||q#t |dEdHdS)Ncstfdd||DS)Nc3s|]}|vVqdSr*r r/r'r rr.zE_generate_partition..has_nbrs_in_partition..any)rnoder'r r5rhas_nbrs_in_partitionsz2_generate_partition..has_nbrs_in_partitioncsh|] \}}|kr|qSr r )r r0drr r sz&_generate_partition..cSsh|] }|D]}|qqSr r )r cutr0r r rr=sr) Zdegreer rrraddrorderrr4) rr%rr: componentsr(Hccr"r>r9r r<rrs"$    rcsi}t|}ttd|dD]S}||kr!tt|||||<q||vr3tt||d|||<qtj||fdd||dD}|rWtt||||||<qtt|||||<q|S)Nrcs&g|]}tfdd|Dr|qS)c3s|]}|vVqdSr*r r/Z nodes_at_kr rr.r6z7_reconstruct_k_components...r7r rDr rrs&z-_reconstruct_k_components..)maxreversedrangerr4rr3)Zk_compsresultZmax_krZto_addr rDrr!sr!cCsBi}t|tddD]\}}|D] }|D]}|||<qqq |S)Nr)key)sorteditemsr)ZkcompsrHrcompsr#r9r r rbuild_k_number_dicts rMr*)__doc__ collectionsr itertoolsroperatorrZnetworkxrZnetworkx.algorithms.flowrZnetworkx.utilsrr__all__Z _dispatchablerr4rr!rMr r r rs"