btj dZddlZddlmZgdZejdZedejdZededejd d d d Z dS)z5Functions for computing and verifying regular graphs.N)not_implemented_for) is_regular is_k_regulark_factorct|dkrtjdtj|}|s5||tfd|jDS||fd|jD}| |fd|j D}t|ot|S)aDetermines whether a graph is regular. A regular graph is a graph where all nodes have the same degree. A regular digraph is a graph where all nodes have the same indegree and all nodes have the same outdegree. Parameters ---------- G : NetworkX graph Returns ------- bool Whether the given graph or digraph is regular. Examples -------- >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 1)]) >>> nx.is_regular(G) True rzGraph has no nodes.c3*K|] \}}|kVdSN).0_dd1s Y/var/www/html/CA-Chatbot/venv/lib/python3.11/site-packages/networkx/algorithms/regular.py zis_regular..&s+00tq!27000000c3*K|] \}}|kVdSr r )r r r d_ins rrzis_regular..)s+88DAqdai888888rc3*K|] \}}|kVdSr r )r r r d_outs rrzis_regular..+s+;;dauz;;;;;;r) lennxNetworkXPointlessConceptutilsarbitrary_element is_directeddegreeall in_degree out_degree)Gn1 in_regular out_regularrrrs @@@rrr s0 1vv{{)*?@@@  # #A & &B ==??4 XXb\\0000qx000000{{28888AK888  R  ;;;;al;;; :33{#3#33rdirectedcDtfd|jDS)aDetermines whether the graph ``G`` is a k-regular graph. A k-regular graph is a graph where each vertex has degree k. Parameters ---------- G : NetworkX graph Returns ------- bool Whether the given graph is k-regular. Examples -------- >>> G = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)]) >>> nx.is_k_regular(G, k=3) False c3*K|] \}}|kVdSr r )r nr ks rrzis_k_regular..Fs+++$!QqAv++++++r)rr)r r(s `rrr/s*. ++++!(+++ + ++r multigraphT)preserve_edge_attrs returns_graphweightc& tfd|jDrtjd|}g}|jD]I\}|dz k fdt |D r%fdt |d|zz D}g nDfdt d|zd|zzD}fdt |d|zD |t t|D]\}\}} |j ||fi| | fd |D| | | fKtj |d |  tj | stjd | fd |jD|D]\} |t#|} D]<}|j|D]\}} || vr|j |fi| n=||z z|S)u<Compute a `k`-factor of a graph. A `k`-factor of a graph is a spanning `k`-regular subgraph. A spanning `k`-regular subgraph of `G` is a subgraph that contains each node of `G` and a subset of the edges of `G` such that each node has degree `k`. Parameters ---------- G : NetworkX graph An undirected graph. k : int The degree of the `k`-factor. matching_weight: string, optional (default="weight") Edge attribute name corresponding to the edge weight. If not present, the edge is assumed to have weight 1. Used for finding the max-weighted perfect matching. Returns ------- NetworkX graph A `k`-factor of `G`. Examples -------- >>> G = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)]) >>> KF = nx.k_factor(G, k=1) >>> KF.edges() EdgeView([(1, 2), (3, 4)]) References ---------- .. [1] "An algorithm for computing simple k-factors.", Meijer, Henk, Yurai Núñez-Rodríguez, and David Rappaport, Information processing letters, 2009. c3*K|] \}}|kVdSr r )r r r r(s rrzk_factor..ts+ & &TQ1q5 & & & & & &rz/Graph contains a vertex with degree less than kg@cg|]}|fSr r r inodes r zk_factor..s222q$222rcg|]}|fSr r r0s rr3zk_factor..sEEE!T1IEEErcg|]}|fSr r r0s rr3zk_factor..sIII!T1IIIIrcg|]}|fSr r r0s rr3zk_factor..sBBB1dAYBBBrc32K|]}rnD]}||fV dSr r )r uvinneris_largeouters rrzk_factor..s=VVA8TuVV!!QVVVVVVVrT)maxcardinalityr,z7Cannot find k-factor because no perfect matching existsc3>K|]}|v|dddv|VdS)Nr )r ems rrzk_factor..s?NNaaqjjQtttWA=M=M=M=M=M=MNNr)anyrrNetworkXUnfeasiblecopyrangeadd_edges_fromzipitemsadd_edge remove_nodeappendmax_weight_matchingis_perfect_matchingremove_edges_fromedgesadd_nodeset_adjremove_nodes_from)r r(matching_weightggadgetsrcoreouter_nneighborattrscore_setr;r<rBr2r=s ` @@@@@rrrIs4V & & & &QX & & &&&W#$UVVV AG33 f $3222E&MM222  CEEEEuVQZ!^'D'DEEEDEEIIIIuQZVa'H'HIIIDBBBBfa&j(A(ABBBE UE**+++*-eQtW]]__*E*E 3 3 &G&h AJw 2 2E 2 2 2 2 VVVVVVVVVVVV deT512222 qoNNNA !!Q ' ' # E   NNNN17NNNNNN%,22 eT5 4t99  G#$6'?#8#8#:#:  %8++AJtX77777E, EDL501111 Hr)r,) __doc__networkxrnetworkx.utilsr__all__ _dispatchablerrrr rrrbs;;...... 4 4 4"4"4"4JZ  ,,! ,0Z  \""d$???[ [ [ @?#"! [ [ [ r