diff options
Diffstat (limited to '_modules/networkx/algorithms/connectivity/edge_augmentation.html')
| -rw-r--r-- | _modules/networkx/algorithms/connectivity/edge_augmentation.html | 44 |
1 files changed, 28 insertions, 16 deletions
diff --git a/_modules/networkx/algorithms/connectivity/edge_augmentation.html b/_modules/networkx/algorithms/connectivity/edge_augmentation.html index 84d8553c..20630df2 100644 --- a/_modules/networkx/algorithms/connectivity/edge_augmentation.html +++ b/_modules/networkx/algorithms/connectivity/edge_augmentation.html @@ -5,7 +5,7 @@ <head> <meta charset="utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1.0" /> - <title>networkx.algorithms.connectivity.edge_augmentation — NetworkX 3.0rc2.dev0 documentation</title> + <title>networkx.algorithms.connectivity.edge_augmentation — NetworkX 3.1rc1.dev0 documentation</title> @@ -46,12 +46,18 @@ <script>DOCUMENTATION_OPTIONS.pagename = '_modules/networkx/algorithms/connectivity/edge_augmentation';</script> <link rel="canonical" href="https://networkx.org/documentation/stable/_modules/networkx/algorithms/connectivity/edge_augmentation.html" /> <link rel="search" type="application/opensearchdescription+xml" - title="Search within NetworkX 3.0rc2.dev0 documentation" + title="Search within NetworkX 3.1rc1.dev0 documentation" href="../../../../_static/opensearch.xml"/> <link rel="index" title="Index" href="../../../../genindex.html" /> <link rel="search" title="Search" href="../../../../search.html" /> +<script + defer + data-domain="networkx.org" + src="https://views.scientific-python.org/js/script.js" +></script> + <meta name="viewport" content="width=device-width, initial-scale=1" /> - <meta name="docsearch:language" content="en"> + <meta name="docsearch:language" content="en"> </head> @@ -93,6 +99,12 @@ <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd>K</kbd></span> </form> </div> + </div><div class="bd-header-announcement container-fluid" id="header-announcement"> + + + +<div class="bd-header-announcement__content"><p><a href='https://forms.gle/NUGcBxyjx5onbAgc8'> NetworkX User Survey 2023</a> 🎉 Fill out the survey to tell us about your ideas, complaints, praises of NetworkX!</p></div> + </div> @@ -244,7 +256,7 @@ id="dLabelMore" data-toggle="dropdown" > - v3.0rc2.dev0 + v3.1rc1.dev0 <span class="caret"></span> </button> <ul class="dropdown-menu" aria-labelledby="dLabelMore"> @@ -407,7 +419,7 @@ id="dLabelMore" data-toggle="dropdown" > - v3.0rc2.dev0 + v3.1rc1.dev0 <span class="caret"></span> </button> <ul class="dropdown-menu" aria-labelledby="dLabelMore"> @@ -725,7 +737,7 @@ <span class="n">aug_edges</span> <span class="o">=</span> <span class="n">greedy_k_edge_augmentation</span><span class="p">(</span> <span class="n">G</span><span class="p">,</span> <span class="n">k</span><span class="o">=</span><span class="n">k</span><span class="p">,</span> <span class="n">avail</span><span class="o">=</span><span class="n">avail</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="n">weight</span><span class="p">,</span> <span class="n">seed</span><span class="o">=</span><span class="mi">0</span> <span class="p">)</span> - <span class="c1"># Do eager evaulation so we can catch any exceptions</span> + <span class="c1"># Do eager evaluation so we can catch any exceptions</span> <span class="c1"># Before executing partial code.</span> <span class="k">yield from</span> <span class="nb">list</span><span class="p">(</span><span class="n">aug_edges</span><span class="p">)</span> <span class="k">except</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXUnfeasible</span><span class="p">:</span> @@ -831,13 +843,13 @@ <span class="p">}</span> <span class="c1"># Remove potential augmenting edges</span> <span class="n">C</span><span class="o">.</span><span class="n">remove_edges_from</span><span class="p">(</span><span class="n">sub_avail</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span> - <span class="c1"># Find a subset of these edges that makes the compoment</span> + <span class="c1"># Find a subset of these edges that makes the component</span> <span class="c1"># k-edge-connected and ignore the rest</span> <span class="k">yield from</span> <span class="n">nx</span><span class="o">.</span><span class="n">k_edge_augmentation</span><span class="p">(</span><span class="n">C</span><span class="p">,</span> <span class="n">k</span><span class="o">=</span><span class="n">k</span><span class="p">,</span> <span class="n">avail</span><span class="o">=</span><span class="n">sub_avail</span><span class="p">)</span> <span class="c1"># Generate all edges between CCs that could not be k-edge-connected</span> <span class="k">for</span> <span class="n">cc1</span><span class="p">,</span> <span class="n">cc2</span> <span class="ow">in</span> <span class="n">it</span><span class="o">.</span><span class="n">combinations</span><span class="p">(</span><span class="n">k_edge_subgraphs</span><span class="p">,</span> <span class="mi">2</span><span class="p">):</span> - <span class="k">for</span> <span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span> <span class="ow">in</span> <span class="n">_edges_between_disjoint</span><span class="p">(</span><span class="n">H</span><span class="p">,</span> <span class="n">cc1</span><span class="p">,</span> <span class="n">cc2</span><span class="p">):</span> + <span class="k">for</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">_edges_between_disjoint</span><span class="p">(</span><span class="n">H</span><span class="p">,</span> <span class="n">cc1</span><span class="p">,</span> <span class="n">cc2</span><span class="p">):</span> <span class="n">d</span> <span class="o">=</span> <span class="n">H</span><span class="o">.</span><span class="n">get_edge_data</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span> <span class="n">edge</span> <span class="o">=</span> <span class="n">d</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s2">"generator"</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span> <span class="k">if</span> <span class="n">edge</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span> @@ -1005,7 +1017,7 @@ <span class="sd"> -----</span> <span class="sd"> Each node in the metagraph is a k-edge-connected component in the original</span> <span class="sd"> graph. We don't care about any edge within the same k-edge-connected</span> -<span class="sd"> component, so we ignore self edges. We also are only intereseted in the</span> +<span class="sd"> component, so we ignore self edges. We also are only interested in the</span> <span class="sd"> minimum weight edge bridging each k-edge-connected component so, we group</span> <span class="sd"> the edges by meta-edge and take the lightest in each group.</span> @@ -1686,7 +1698,7 @@ <span class="c1"># Incrementally add edges in until we are k-connected</span> <span class="n">H</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span> - <span class="k">for</span> <span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span> <span class="ow">in</span> <span class="n">avail_uv</span><span class="p">:</span> + <span class="k">for</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">avail_uv</span><span class="p">:</span> <span class="n">done</span> <span class="o">=</span> <span class="kc">False</span> <span class="k">if</span> <span class="ow">not</span> <span class="n">is_locally_k_edge_connected</span><span class="p">(</span><span class="n">H</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">k</span><span class="o">=</span><span class="n">k</span><span class="p">):</span> <span class="c1"># Only add edges in parts that are not yet locally k-edge-connected</span> @@ -1704,7 +1716,7 @@ <span class="c1"># Randomized attempt to reduce the size of the solution</span> <span class="n">_compat_shuffle</span><span class="p">(</span><span class="n">seed</span><span class="p">,</span> <span class="n">aug_edges</span><span class="p">)</span> - <span class="k">for</span> <span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span> <span class="ow">in</span> <span class="nb">list</span><span class="p">(</span><span class="n">aug_edges</span><span class="p">):</span> + <span class="k">for</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="nb">list</span><span class="p">(</span><span class="n">aug_edges</span><span class="p">):</span> <span class="c1"># Don't remove if we know it would break connectivity</span> <span class="k">if</span> <span class="n">H</span><span class="o">.</span><span class="n">degree</span><span class="p">(</span><span class="n">u</span><span class="p">)</span> <span class="o"><=</span> <span class="n">k</span> <span class="ow">or</span> <span class="n">H</span><span class="o">.</span><span class="n">degree</span><span class="p">(</span><span class="n">v</span><span class="p">)</span> <span class="o"><=</span> <span class="n">k</span><span class="p">:</span> <span class="k">continue</span> @@ -1731,11 +1743,11 @@ <div class="toc-item"> -<div id="searchbox"></div> -</div> - -<div class="toc-item"> - +<form class="bd-search d-flex align-items-center" action="../../../../search.html" method="get"> + <i class="fa-solid fa-magnifying-glass"></i> + <input type="search" class="form-control" name="q" id="search-input" placeholder="Search the docs ..." aria-label="Search the docs ..." autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"> + <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd>K</kbd></span> +</form> </div> <div class="toc-item"> |