diff options
| author | jarrodmillman <jarrod.millman@gmail.com> | 2022-12-14 17:21:13 +0000 |
|---|---|---|
| committer | jarrodmillman <jarrod.millman@gmail.com> | 2022-12-14 17:21:13 +0000 |
| commit | 832c558e3507e5cb667a622b5372f91384ab026f (patch) | |
| tree | 74481f14ab9cfb5c6984ab59b378cdc857a8180d /reference/algorithms/approximation.html | |
| parent | 71985f91c82bf85657dce6a74669e93ec8d29e11 (diff) | |
| download | networkx-832c558e3507e5cb667a622b5372f91384ab026f.tar.gz | |
Deploying to gh-pages from @ networkx/networkx@6be702047b1bb596a8010cf80911bb6ea939b1d1 🚀
Diffstat (limited to 'reference/algorithms/approximation.html')
| -rw-r--r-- | reference/algorithms/approximation.html | 985 |
1 files changed, 985 insertions, 0 deletions
diff --git a/reference/algorithms/approximation.html b/reference/algorithms/approximation.html new file mode 100644 index 00000000..9d5a534f --- /dev/null +++ b/reference/algorithms/approximation.html @@ -0,0 +1,985 @@ + +<!DOCTYPE html> + +<html lang="en"> + <head> + <meta charset="utf-8" /> + <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.19: https://docutils.sourceforge.io/" /> + + <title>Approximations and Heuristics — NetworkX 3.0rc2.dev0 documentation</title> + + + + <script data-cfasync="false"> + document.documentElement.dataset.mode = localStorage.getItem("mode") || "light"; + document.documentElement.dataset.theme = localStorage.getItem("theme") || "light"; + </script> + + <!-- Loaded before other Sphinx assets --> + <link href="../../_static/styles/theme.css?digest=796348d33e8b1d947c94" rel="stylesheet"> +<link href="../../_static/styles/bootstrap.css?digest=796348d33e8b1d947c94" rel="stylesheet"> +<link href="../../_static/styles/pydata-sphinx-theme.css?digest=796348d33e8b1d947c94" rel="stylesheet"> + + + <link href="../../_static/vendor/fontawesome/6.1.2/css/all.min.css?digest=796348d33e8b1d947c94" rel="stylesheet"> + <link rel="preload" as="font" type="font/woff2" crossorigin href="../../_static/vendor/fontawesome/6.1.2/webfonts/fa-solid-900.woff2"> +<link rel="preload" as="font" type="font/woff2" crossorigin href="../../_static/vendor/fontawesome/6.1.2/webfonts/fa-brands-400.woff2"> +<link rel="preload" as="font" type="font/woff2" crossorigin href="../../_static/vendor/fontawesome/6.1.2/webfonts/fa-regular-400.woff2"> + + <link rel="stylesheet" type="text/css" href="../../_static/pygments.css" /> + <link rel="stylesheet" type="text/css" href="../../_static/custom.css" /> + <link rel="stylesheet" type="text/css" href="../../_static/sg_gallery.css" /> + <link rel="stylesheet" type="text/css" href="../../_static/sg_gallery-binder.css" /> + <link rel="stylesheet" type="text/css" href="../../_static/sg_gallery-dataframe.css" /> + <link rel="stylesheet" type="text/css" href="../../_static/sg_gallery-rendered-html.css" /> + + <!-- Pre-loaded scripts that we'll load fully later --> + <link rel="preload" as="script" href="../../_static/scripts/bootstrap.js?digest=796348d33e8b1d947c94"> +<link rel="preload" as="script" href="../../_static/scripts/pydata-sphinx-theme.js?digest=796348d33e8b1d947c94"> + + <script data-url_root="../../" id="documentation_options" src="../../_static/documentation_options.js"></script> + <script src="../../_static/jquery.js"></script> + <script src="../../_static/underscore.js"></script> + <script src="../../_static/_sphinx_javascript_frameworks_compat.js"></script> + <script src="../../_static/doctools.js"></script> + <script src="../../_static/sphinx_highlight.js"></script> + <script src="../../_static/copybutton.js"></script> + <script>DOCUMENTATION_OPTIONS.pagename = 'reference/algorithms/approximation';</script> + <link rel="canonical" href="https://networkx.org/documentation/stable/reference/algorithms/approximation.html" /> + <link rel="search" type="application/opensearchdescription+xml" + title="Search within NetworkX 3.0rc2.dev0 documentation" + href="../../_static/opensearch.xml"/> + <link rel="index" title="Index" href="../../genindex.html" /> + <link rel="search" title="Search" href="../../search.html" /> + <link rel="next" title="all_pairs_node_connectivity" href="generated/networkx.algorithms.approximation.connectivity.all_pairs_node_connectivity.html" /> + <link rel="prev" title="Algorithms" href="index.html" /> + <meta name="viewport" content="width=device-width, initial-scale=1" /> + <meta name="docsearch:language" content="en"> + </head> + + + <body data-spy="scroll" data-target="#bd-toc-nav" data-offset="180" data-default-mode="light"> + + + + <a class="skip-link" href="#main-content">Skip to main content</a> +<div class="container-fluid version-alert devbar"> + <div class="row no-gutters"> + <div class="col-12 text-center"> + This page is documentation for a DEVELOPMENT / PRE-RELEASE version. + <a + class="btn version-stable font-weight-bold ml-3 my-3 align-baseline" + href="https://networkx.org/documentation/stable/" + >Switch to stable version</a + > + </div> + </div> +</div> + + + + <input type="checkbox" class="sidebar-toggle" name="__primary" id="__primary"> + <label class="overlay overlay-primary" for="__primary"></label> + + + <input type="checkbox" class="sidebar-toggle" name="__secondary" id="__secondary"> + <label class="overlay overlay-secondary" for="__secondary"></label> + + + <div class="search-button__wrapper"> + <div class="search-button__overlay"></div> + <div class="search-button__search-container"> + +<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> + + + <nav class="bd-header navbar navbar-expand-lg bd-navbar" id="navbar-main"><div class="bd-header__inner bd-page-width"> + <label class="sidebar-toggle primary-toggle" for="__primary"> + <span class="fa-solid fa-bars"></span> + </label> + <div id="navbar-start"> + + + + + +<a class="navbar-brand logo" href="../../index.html"> + + + + + + + + + + + <img src="../../_static/networkx_banner.svg" class="logo__image only-light" alt="Logo image"> + <img src="../../_static/networkx_banner.svg" class="logo__image only-dark" alt="Logo image"> + + +</a> + + </div> + + + <div class="col-lg-9 navbar-header-items"> + <div id="navbar-center" class="mr-auto"> + + <div class="navbar-center-item"> + <nav class="navbar-nav"> + <p class="sidebar-header-items__title" role="heading" aria-level="1" aria-label="Site Navigation"> + Site Navigation + </p> + <ul id="navbar-main-elements" class="navbar-nav"> + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../install.html"> + Install + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../tutorial.html"> + Tutorial + </a> + </li> + + + <li class="nav-item current active"> + <a class="nav-link nav-internal" href="../index.html"> + Reference + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../auto_examples/index.html"> + Gallery + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../developer/index.html"> + Developer + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../release/index.html"> + Releases + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-external" href="https://networkx.org/nx-guides/"> + Guides + </a> + </li> + + </ul> +</nav> + </div> + + </div> + + <div id="navbar-end"> + + <div class="navbar-end-item navbar-persistent--container"> + +<button class="btn btn-sm navbar-btn search-button search-button__button" title="Search" aria-label="Search" data-toggle="tooltip"> + <i class="fa-solid fa-magnifying-glass"></i> +</button> + </div> + + + <div class="navbar-end-item"> + <button class="theme-switch-button btn btn-sm btn-outline-primary navbar-btn rounded-circle" title="light/dark" aria-label="light/dark" data-toggle="tooltip"> + <span class="theme-switch" data-mode="light"><i class="fa-solid fa-sun"></i></span> + <span class="theme-switch" data-mode="dark"><i class="fa-solid fa-moon"></i></span> + <span class="theme-switch" data-mode="auto"><i class="fa-solid fa-circle-half-stroke"></i></span> +</button> + </div> + + <div class="navbar-end-item"> + <ul id="navbar-icon-links" class="navbar-nav" aria-label="Icon Links"> + <li class="nav-item"> + + + + + + + + <a href="https://networkx.org" title="Home Page" class="nav-link" rel="noopener" target="_blank" data-toggle="tooltip"><span><i class="fas fa-home"></i></span> + <label class="sr-only">Home Page</label></a> + </li> + <li class="nav-item"> + + + + + + + + <a href="https://github.com/networkx/networkx" title="GitHub" class="nav-link" rel="noopener" target="_blank" data-toggle="tooltip"><span><i class="fab fa-github-square"></i></span> + <label class="sr-only">GitHub</label></a> + </li> + </ul> + </div> + + <div class="navbar-end-item"> + <ul class="navbar-nav"> + <li class="mr-2 dropdown"> + <button + type="button" + class="btn btn-version btn-sm navbar-btn dropdown-toggle" + id="dLabelMore" + data-toggle="dropdown" + > + v3.0rc2.dev0 + <span class="caret"></span> + </button> + <ul class="dropdown-menu" aria-labelledby="dLabelMore"> + <li> + <a href="https://networkx.org/documentation/latest/index.html" + >devel (latest)</a + > + </li> + <li> + <a href="https://networkx.org/documentation/stable/index.html" + >current (stable)</a + > + </li> + </ul> + </li> +</ul> + </div> + + </div> + </div> + + + + + <div class="navbar-persistent--mobile"> +<button class="btn btn-sm navbar-btn search-button search-button__button" title="Search" aria-label="Search" data-toggle="tooltip"> + <i class="fa-solid fa-magnifying-glass"></i> +</button> + </div> + + + + <label class="sidebar-toggle secondary-toggle" for="__secondary"> + <span class="fa-solid fa-outdent"></span> + </label> + + +</div> + </nav> + + + <div class="bd-container"> + <div class="bd-container__inner bd-page-width"> + + <div class="bd-sidebar-primary bd-sidebar"> + + + <div class="sidebar-header-items sidebar-primary__section"> + + + <div class="sidebar-header-items__center"> + + <div class="navbar-center-item"> + <nav class="navbar-nav"> + <p class="sidebar-header-items__title" role="heading" aria-level="1" aria-label="Site Navigation"> + Site Navigation + </p> + <ul id="navbar-main-elements" class="navbar-nav"> + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../install.html"> + Install + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../tutorial.html"> + Tutorial + </a> + </li> + + + <li class="nav-item current active"> + <a class="nav-link nav-internal" href="../index.html"> + Reference + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../auto_examples/index.html"> + Gallery + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../developer/index.html"> + Developer + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-internal" href="../../release/index.html"> + Releases + </a> + </li> + + + <li class="nav-item"> + <a class="nav-link nav-external" href="https://networkx.org/nx-guides/"> + Guides + </a> + </li> + + </ul> +</nav> + </div> + + </div> + + + + + <div class="sidebar-header-items__end"> + + <div class="navbar-end-item"> + <button class="theme-switch-button btn btn-sm btn-outline-primary navbar-btn rounded-circle" title="light/dark" aria-label="light/dark" data-toggle="tooltip"> + <span class="theme-switch" data-mode="light"><i class="fa-solid fa-sun"></i></span> + <span class="theme-switch" data-mode="dark"><i class="fa-solid fa-moon"></i></span> + <span class="theme-switch" data-mode="auto"><i class="fa-solid fa-circle-half-stroke"></i></span> +</button> + </div> + + <div class="navbar-end-item"> + <ul id="navbar-icon-links" class="navbar-nav" aria-label="Icon Links"> + <li class="nav-item"> + + + + + + + + <a href="https://networkx.org" title="Home Page" class="nav-link" rel="noopener" target="_blank" data-toggle="tooltip"><span><i class="fas fa-home"></i></span> + <label class="sr-only">Home Page</label></a> + </li> + <li class="nav-item"> + + + + + + + + <a href="https://github.com/networkx/networkx" title="GitHub" class="nav-link" rel="noopener" target="_blank" data-toggle="tooltip"><span><i class="fab fa-github-square"></i></span> + <label class="sr-only">GitHub</label></a> + </li> + </ul> + </div> + + <div class="navbar-end-item"> + <ul class="navbar-nav"> + <li class="mr-2 dropdown"> + <button + type="button" + class="btn btn-version btn-sm navbar-btn dropdown-toggle" + id="dLabelMore" + data-toggle="dropdown" + > + v3.0rc2.dev0 + <span class="caret"></span> + </button> + <ul class="dropdown-menu" aria-labelledby="dLabelMore"> + <li> + <a href="https://networkx.org/documentation/latest/index.html" + >devel (latest)</a + > + </li> + <li> + <a href="https://networkx.org/documentation/stable/index.html" + >current (stable)</a + > + </li> + </ul> + </li> +</ul> + </div> + + </div> + + </div> + + + <div class="sidebar-start-items sidebar-primary__section"> + <div class="sidebar-start-items__item"><nav class="bd-links" id="bd-docs-nav" aria-label="Section navigation"> + <p class="bd-links__title" role="heading" aria-level="1"> + Section Navigation + </p> + <div class="bd-toc-item navbar-nav"> + <ul class="current nav bd-sidenav"> +<li class="toctree-l1"><a class="reference internal" href="../introduction.html">Introduction</a></li> +<li class="toctree-l1"><a class="reference internal" href="../classes/index.html">Graph types</a></li> +<li class="toctree-l1 current active has-children"><a class="reference internal" href="index.html">Algorithms</a><input checked="" class="toctree-checkbox" id="toctree-checkbox-1" name="toctree-checkbox-1" type="checkbox"/><label class="toctree-toggle" for="toctree-checkbox-1"><i class="fa-solid fa-chevron-down"></i></label><ul class="current"> +<li class="toctree-l2 current active"><a class="current reference internal" href="#">Approximations and Heuristics</a></li> +<li class="toctree-l2"><a class="reference internal" href="assortativity.html">Assortativity</a></li> +<li class="toctree-l2"><a class="reference internal" href="asteroidal.html">Asteroidal</a></li> +<li class="toctree-l2"><a class="reference internal" href="bipartite.html">Bipartite</a></li> +<li class="toctree-l2"><a class="reference internal" href="boundary.html">Boundary</a></li> +<li class="toctree-l2"><a class="reference internal" href="bridges.html">Bridges</a></li> +<li class="toctree-l2"><a class="reference internal" href="centrality.html">Centrality</a></li> +<li class="toctree-l2"><a class="reference internal" href="chains.html">Chains</a></li> +<li class="toctree-l2"><a class="reference internal" href="chordal.html">Chordal</a></li> +<li class="toctree-l2"><a class="reference internal" href="clique.html">Clique</a></li> +<li class="toctree-l2"><a class="reference internal" href="clustering.html">Clustering</a></li> +<li class="toctree-l2"><a class="reference internal" href="coloring.html">Coloring</a></li> +<li class="toctree-l2"><a class="reference internal" href="communicability_alg.html">Communicability</a></li> +<li class="toctree-l2"><a class="reference internal" href="community.html">Communities</a></li> +<li class="toctree-l2"><a class="reference internal" href="component.html">Components</a></li> +<li class="toctree-l2"><a class="reference internal" href="connectivity.html">Connectivity</a></li> +<li class="toctree-l2"><a class="reference internal" href="core.html">Cores</a></li> +<li class="toctree-l2"><a class="reference internal" href="covering.html">Covering</a></li> +<li class="toctree-l2"><a class="reference internal" href="cycles.html">Cycles</a></li> +<li class="toctree-l2"><a class="reference internal" href="cuts.html">Cuts</a></li> +<li class="toctree-l2"><a class="reference internal" href="d_separation.html">D-Separation</a></li> +<li class="toctree-l2"><a class="reference internal" href="dag.html">Directed Acyclic Graphs</a></li> +<li class="toctree-l2"><a class="reference internal" href="distance_measures.html">Distance Measures</a></li> +<li class="toctree-l2"><a class="reference internal" href="distance_regular.html">Distance-Regular Graphs</a></li> +<li class="toctree-l2"><a class="reference internal" href="dominance.html">Dominance</a></li> +<li class="toctree-l2"><a class="reference internal" href="dominating.html">Dominating Sets</a></li> +<li class="toctree-l2"><a class="reference internal" href="efficiency_measures.html">Efficiency</a></li> +<li class="toctree-l2"><a class="reference internal" href="euler.html">Eulerian</a></li> +<li class="toctree-l2"><a class="reference internal" href="flow.html">Flows</a></li> +<li class="toctree-l2"><a class="reference internal" href="graph_hashing.html">Graph Hashing</a></li> +<li class="toctree-l2"><a class="reference internal" href="graphical.html">Graphical degree sequence</a></li> +<li class="toctree-l2"><a class="reference internal" href="hierarchy.html">Hierarchy</a></li> +<li class="toctree-l2"><a class="reference internal" href="hybrid.html">Hybrid</a></li> +<li class="toctree-l2"><a class="reference internal" href="isolates.html">Isolates</a></li> +<li class="toctree-l2"><a class="reference internal" href="isomorphism.html">Isomorphism</a></li> +<li class="toctree-l2"><a class="reference internal" href="link_analysis.html">Link Analysis</a></li> +<li class="toctree-l2"><a class="reference internal" href="link_prediction.html">Link Prediction</a></li> +<li class="toctree-l2"><a class="reference internal" href="lowest_common_ancestors.html">Lowest Common Ancestor</a></li> +<li class="toctree-l2"><a class="reference internal" href="matching.html">Matching</a></li> +<li class="toctree-l2"><a class="reference internal" href="minors.html">Minors</a></li> +<li class="toctree-l2"><a class="reference internal" href="mis.html">Maximal independent set</a></li> +<li class="toctree-l2"><a class="reference internal" href="non_randomness.html">non-randomness</a></li> +<li class="toctree-l2"><a class="reference internal" href="moral.html">Moral</a></li> +<li class="toctree-l2"><a class="reference internal" href="node_classification.html">Node Classification</a></li> +<li class="toctree-l2"><a class="reference internal" href="operators.html">Operators</a></li> +<li class="toctree-l2"><a class="reference internal" href="planarity.html">Planarity</a></li> +<li class="toctree-l2"><a class="reference internal" href="planar_drawing.html">Planar Drawing</a></li> +<li class="toctree-l2"><a class="reference internal" href="polynomials.html">Graph Polynomials</a></li> +<li class="toctree-l2"><a class="reference internal" href="reciprocity.html">Reciprocity</a></li> +<li class="toctree-l2"><a class="reference internal" href="regular.html">Regular</a></li> +<li class="toctree-l2"><a class="reference internal" href="rich_club.html">Rich Club</a></li> +<li class="toctree-l2"><a class="reference internal" href="shortest_paths.html">Shortest Paths</a></li> +<li class="toctree-l2"><a class="reference internal" href="similarity.html">Similarity Measures</a></li> +<li class="toctree-l2"><a class="reference internal" href="simple_paths.html">Simple Paths</a></li> +<li class="toctree-l2"><a class="reference internal" href="smallworld.html">Small-world</a></li> +<li class="toctree-l2"><a class="reference internal" href="smetric.html">s metric</a></li> +<li class="toctree-l2"><a class="reference internal" href="sparsifiers.html">Sparsifiers</a></li> +<li class="toctree-l2"><a class="reference internal" href="structuralholes.html">Structural holes</a></li> +<li class="toctree-l2"><a class="reference internal" href="summarization.html">Summarization</a></li> +<li class="toctree-l2"><a class="reference internal" href="swap.html">Swap</a></li> +<li class="toctree-l2"><a class="reference internal" href="threshold.html">Threshold Graphs</a></li> +<li class="toctree-l2"><a class="reference internal" href="tournament.html">Tournament</a></li> +<li class="toctree-l2"><a class="reference internal" href="traversal.html">Traversal</a></li> +<li class="toctree-l2"><a class="reference internal" href="tree.html">Tree</a></li> +<li class="toctree-l2"><a class="reference internal" href="triads.html">Triads</a></li> +<li class="toctree-l2"><a class="reference internal" href="vitality.html">Vitality</a></li> +<li class="toctree-l2"><a class="reference internal" href="voronoi.html">Voronoi cells</a></li> +<li class="toctree-l2"><a class="reference internal" href="wiener.html">Wiener index</a></li> +</ul> +</li> +<li class="toctree-l1"><a class="reference internal" href="../functions.html">Functions</a></li> +<li class="toctree-l1"><a class="reference internal" href="../generators.html">Graph generators</a></li> +<li class="toctree-l1"><a class="reference internal" href="../linalg.html">Linear algebra</a></li> +<li class="toctree-l1"><a class="reference internal" href="../convert.html">Converting to and from other data formats</a></li> +<li class="toctree-l1"><a class="reference internal" href="../relabel.html">Relabeling nodes</a></li> +<li class="toctree-l1"><a class="reference internal" href="../readwrite/index.html">Reading and writing graphs</a></li> +<li class="toctree-l1"><a class="reference internal" href="../drawing.html">Drawing</a></li> +<li class="toctree-l1"><a class="reference internal" href="../randomness.html">Randomness</a></li> +<li class="toctree-l1"><a class="reference internal" href="../exceptions.html">Exceptions</a></li> +<li class="toctree-l1"><a class="reference internal" href="../utils.html">Utilities</a></li> +<li class="toctree-l1"><a class="reference internal" href="../glossary.html">Glossary</a></li> +</ul> + + </div> +</nav> + </div> + <div class="sidebar-start-items__item"> + </div> + </div> + + + + <div class="sidebar-end-items sidebar-primary__section"> + <div class="sidebar-end-items__item"> + </div> + </div> + + + <div id="rtd-footer-container"></div> + + </div> + <main id="main-content" class="bd-main"> + + + <div class="bd-content"> + <div class="bd-article-container"> + + <div class="bd-header-article"> + + </div> + + + <article class="bd-article" role="main"> + + <section id="module-networkx.algorithms.approximation"> +<span id="approximations-and-heuristics"></span><h1>Approximations and Heuristics<a class="headerlink" href="#module-networkx.algorithms.approximation" title="Permalink to this heading">#</a></h1> +<p>Approximations of graph properties and Heuristic methods for optimization.</p> +<div class="admonition warning"> +<p class="admonition-title">Warning</p> +<p>These functions are not imported in the top-level of <code class="docutils literal notranslate"><span class="pre">networkx</span></code></p> +</div> +<p>These functions can be accessed using +<code class="docutils literal notranslate"><span class="pre">networkx.approximation.function_name</span></code></p> +<p>They can be imported using <code class="docutils literal notranslate"><span class="pre">from</span> <span class="pre">networkx.algorithms</span> <span class="pre">import</span> <span class="pre">approximation</span></code> +or <code class="docutils literal notranslate"><span class="pre">from</span> <span class="pre">networkx.algorithms.approximation</span> <span class="pre">import</span> <span class="pre">function_name</span></code></p> +<section id="module-networkx.algorithms.approximation.connectivity"> +<span id="connectivity"></span><h2>Connectivity<a class="headerlink" href="#module-networkx.algorithms.approximation.connectivity" title="Permalink to this heading">#</a></h2> +<p>Fast approximation for node connectivity</p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.connectivity.all_pairs_node_connectivity.html#networkx.algorithms.approximation.connectivity.all_pairs_node_connectivity" title="networkx.algorithms.approximation.connectivity.all_pairs_node_connectivity"><code class="xref py py-obj docutils literal notranslate"><span class="pre">all_pairs_node_connectivity</span></code></a>(G[, nbunch, cutoff])</p></td> +<td><p>Compute node connectivity between all pairs of nodes.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.connectivity.local_node_connectivity.html#networkx.algorithms.approximation.connectivity.local_node_connectivity" title="networkx.algorithms.approximation.connectivity.local_node_connectivity"><code class="xref py py-obj docutils literal notranslate"><span class="pre">local_node_connectivity</span></code></a>(G, source, target[, ...])</p></td> +<td><p>Compute node connectivity between source and target.</p></td> +</tr> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.connectivity.node_connectivity.html#networkx.algorithms.approximation.connectivity.node_connectivity" title="networkx.algorithms.approximation.connectivity.node_connectivity"><code class="xref py py-obj docutils literal notranslate"><span class="pre">node_connectivity</span></code></a>(G[, s, t])</p></td> +<td><p>Returns an approximation for node connectivity for a graph or digraph G.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.kcomponents"> +<span id="k-components"></span><h2>K-components<a class="headerlink" href="#module-networkx.algorithms.approximation.kcomponents" title="Permalink to this heading">#</a></h2> +<p>Fast approximation for k-component structure</p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.kcomponents.k_components.html#networkx.algorithms.approximation.kcomponents.k_components" title="networkx.algorithms.approximation.kcomponents.k_components"><code class="xref py py-obj docutils literal notranslate"><span class="pre">k_components</span></code></a>(G[, min_density])</p></td> +<td><p>Returns the approximate k-component structure of a graph G.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.clique"> +<span id="clique"></span><h2>Clique<a class="headerlink" href="#module-networkx.algorithms.approximation.clique" title="Permalink to this heading">#</a></h2> +<p>Functions for computing large cliques and maximum independent sets.</p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.clique.maximum_independent_set.html#networkx.algorithms.approximation.clique.maximum_independent_set" title="networkx.algorithms.approximation.clique.maximum_independent_set"><code class="xref py py-obj docutils literal notranslate"><span class="pre">maximum_independent_set</span></code></a>(G)</p></td> +<td><p>Returns an approximate maximum independent set.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.clique.max_clique.html#networkx.algorithms.approximation.clique.max_clique" title="networkx.algorithms.approximation.clique.max_clique"><code class="xref py py-obj docutils literal notranslate"><span class="pre">max_clique</span></code></a>(G)</p></td> +<td><p>Find the Maximum Clique</p></td> +</tr> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.clique.clique_removal.html#networkx.algorithms.approximation.clique.clique_removal" title="networkx.algorithms.approximation.clique.clique_removal"><code class="xref py py-obj docutils literal notranslate"><span class="pre">clique_removal</span></code></a>(G)</p></td> +<td><p>Repeatedly remove cliques from the graph.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.clique.large_clique_size.html#networkx.algorithms.approximation.clique.large_clique_size" title="networkx.algorithms.approximation.clique.large_clique_size"><code class="xref py py-obj docutils literal notranslate"><span class="pre">large_clique_size</span></code></a>(G)</p></td> +<td><p>Find the size of a large clique in a graph.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.clustering_coefficient"> +<span id="clustering"></span><h2>Clustering<a class="headerlink" href="#module-networkx.algorithms.approximation.clustering_coefficient" title="Permalink to this heading">#</a></h2> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.clustering_coefficient.average_clustering.html#networkx.algorithms.approximation.clustering_coefficient.average_clustering" title="networkx.algorithms.approximation.clustering_coefficient.average_clustering"><code class="xref py py-obj docutils literal notranslate"><span class="pre">average_clustering</span></code></a>(G[, trials, seed])</p></td> +<td><p>Estimates the average clustering coefficient of G.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.distance_measures"> +<span id="distance-measures"></span><h2>Distance Measures<a class="headerlink" href="#module-networkx.algorithms.approximation.distance_measures" title="Permalink to this heading">#</a></h2> +<p>Distance measures approximated metrics.</p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.distance_measures.diameter.html#networkx.algorithms.approximation.distance_measures.diameter" title="networkx.algorithms.approximation.distance_measures.diameter"><code class="xref py py-obj docutils literal notranslate"><span class="pre">diameter</span></code></a>(G[, seed])</p></td> +<td><p>Returns a lower bound on the diameter of the graph G.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.dominating_set"> +<span id="dominating-set"></span><h2>Dominating Set<a class="headerlink" href="#module-networkx.algorithms.approximation.dominating_set" title="Permalink to this heading">#</a></h2> +<p>Functions for finding node and edge dominating sets.</p> +<p>A <a class="reference external" href="https://en.wikipedia.org/wiki/Dominating_set">dominating set</a> for an undirected graph <em>G</em> with vertex set <em>V</em> +and edge set <em>E</em> is a subset <em>D</em> of <em>V</em> such that every vertex not in +<em>D</em> is adjacent to at least one member of <em>D</em>. An <a class="reference external" href="https://en.wikipedia.org/wiki/Edge_dominating_set">edge dominating set</a> +is a subset <em>F</em> of <em>E</em> such that every edge not in <em>F</em> is +incident to an endpoint of at least one edge in <em>F</em>.</p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.dominating_set.min_weighted_dominating_set.html#networkx.algorithms.approximation.dominating_set.min_weighted_dominating_set" title="networkx.algorithms.approximation.dominating_set.min_weighted_dominating_set"><code class="xref py py-obj docutils literal notranslate"><span class="pre">min_weighted_dominating_set</span></code></a>(G[, weight])</p></td> +<td><p>Returns a dominating set that approximates the minimum weight node dominating set.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.dominating_set.min_edge_dominating_set.html#networkx.algorithms.approximation.dominating_set.min_edge_dominating_set" title="networkx.algorithms.approximation.dominating_set.min_edge_dominating_set"><code class="xref py py-obj docutils literal notranslate"><span class="pre">min_edge_dominating_set</span></code></a>(G)</p></td> +<td><p>Returns minimum cardinality edge dominating set.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.matching"> +<span id="matching"></span><h2>Matching<a class="headerlink" href="#module-networkx.algorithms.approximation.matching" title="Permalink to this heading">#</a></h2> +<p>Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent +edges; that is, no two edges share a common vertex.</p> +<p><a class="reference external" href="https://en.wikipedia.org/wiki/Matching_(graph_theory)">Wikipedia: Matching</a></p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.matching.min_maximal_matching.html#networkx.algorithms.approximation.matching.min_maximal_matching" title="networkx.algorithms.approximation.matching.min_maximal_matching"><code class="xref py py-obj docutils literal notranslate"><span class="pre">min_maximal_matching</span></code></a>(G)</p></td> +<td><p>Returns the minimum maximal matching of G.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.ramsey"> +<span id="ramsey"></span><h2>Ramsey<a class="headerlink" href="#module-networkx.algorithms.approximation.ramsey" title="Permalink to this heading">#</a></h2> +<p>Ramsey numbers.</p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.ramsey.ramsey_R2.html#networkx.algorithms.approximation.ramsey.ramsey_R2" title="networkx.algorithms.approximation.ramsey.ramsey_R2"><code class="xref py py-obj docutils literal notranslate"><span class="pre">ramsey_R2</span></code></a>(G)</p></td> +<td><p>Compute the largest clique and largest independent set in <code class="xref py py-obj docutils literal notranslate"><span class="pre">G</span></code>.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.steinertree"> +<span id="steiner-tree"></span><h2>Steiner Tree<a class="headerlink" href="#module-networkx.algorithms.approximation.steinertree" title="Permalink to this heading">#</a></h2> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.steinertree.metric_closure.html#networkx.algorithms.approximation.steinertree.metric_closure" title="networkx.algorithms.approximation.steinertree.metric_closure"><code class="xref py py-obj docutils literal notranslate"><span class="pre">metric_closure</span></code></a>(G[, weight])</p></td> +<td><p>Return the metric closure of a graph.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.steinertree.steiner_tree.html#networkx.algorithms.approximation.steinertree.steiner_tree" title="networkx.algorithms.approximation.steinertree.steiner_tree"><code class="xref py py-obj docutils literal notranslate"><span class="pre">steiner_tree</span></code></a>(G, terminal_nodes[, weight, method])</p></td> +<td><p>Return an approximation to the minimum Steiner tree of a graph.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.traveling_salesman"> +<span id="traveling-salesman"></span><h2>Traveling Salesman<a class="headerlink" href="#module-networkx.algorithms.approximation.traveling_salesman" title="Permalink to this heading">#</a></h2> +<section id="travelling-salesman-problem-tsp"> +<h3>Travelling Salesman Problem (TSP)<a class="headerlink" href="#travelling-salesman-problem-tsp" title="Permalink to this heading">#</a></h3> +<p>Implementation of approximate algorithms +for solving and approximating the TSP problem.</p> +<p>Categories of algorithms which are implemented:</p> +<ul class="simple"> +<li><p>Christofides (provides a 3/2-approximation of TSP)</p></li> +<li><p>Greedy</p></li> +<li><p>Simulated Annealing (SA)</p></li> +<li><p>Threshold Accepting (TA)</p></li> +<li><p>Asadpour Asymmetric Traveling Salesman Algorithm</p></li> +</ul> +<p>The Travelling Salesman Problem tries to find, given the weight +(distance) between all points where a salesman has to visit, the +route so that:</p> +<ul class="simple"> +<li><p>The total distance (cost) which the salesman travels is minimized.</p></li> +<li><p>The salesman returns to the starting point.</p></li> +<li><p>Note that for a complete graph, the salesman visits each point once.</p></li> +</ul> +<p>The function <code class="xref py py-obj docutils literal notranslate"><span class="pre">travelling_salesman_problem</span></code> allows for incomplete +graphs by finding all-pairs shortest paths, effectively converting +the problem to a complete graph problem. It calls one of the +approximate methods on that problem and then converts the result +back to the original graph using the previously found shortest paths.</p> +<p>TSP is an NP-hard problem in combinatorial optimization, +important in operations research and theoretical computer science.</p> +<p><a class="reference external" href="http://en.wikipedia.org/wiki/Travelling_salesman_problem">http://en.wikipedia.org/wiki/Travelling_salesman_problem</a></p> +</section> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.traveling_salesman.christofides.html#networkx.algorithms.approximation.traveling_salesman.christofides" title="networkx.algorithms.approximation.traveling_salesman.christofides"><code class="xref py py-obj docutils literal notranslate"><span class="pre">christofides</span></code></a>(G[, weight, tree])</p></td> +<td><p>Approximate a solution of the traveling salesman problem</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem.html#networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem" title="networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem"><code class="xref py py-obj docutils literal notranslate"><span class="pre">traveling_salesman_problem</span></code></a>(G[, weight, ...])</p></td> +<td><p>Find the shortest path in <code class="xref py py-obj docutils literal notranslate"><span class="pre">G</span></code> connecting specified nodes</p></td> +</tr> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.traveling_salesman.greedy_tsp.html#networkx.algorithms.approximation.traveling_salesman.greedy_tsp" title="networkx.algorithms.approximation.traveling_salesman.greedy_tsp"><code class="xref py py-obj docutils literal notranslate"><span class="pre">greedy_tsp</span></code></a>(G[, weight, source])</p></td> +<td><p>Return a low cost cycle starting at <code class="xref py py-obj docutils literal notranslate"><span class="pre">source</span></code> and its cost.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.traveling_salesman.simulated_annealing_tsp.html#networkx.algorithms.approximation.traveling_salesman.simulated_annealing_tsp" title="networkx.algorithms.approximation.traveling_salesman.simulated_annealing_tsp"><code class="xref py py-obj docutils literal notranslate"><span class="pre">simulated_annealing_tsp</span></code></a>(G, init_cycle[, ...])</p></td> +<td><p>Returns an approximate solution to the traveling salesman problem.</p></td> +</tr> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.traveling_salesman.threshold_accepting_tsp.html#networkx.algorithms.approximation.traveling_salesman.threshold_accepting_tsp" title="networkx.algorithms.approximation.traveling_salesman.threshold_accepting_tsp"><code class="xref py py-obj docutils literal notranslate"><span class="pre">threshold_accepting_tsp</span></code></a>(G, init_cycle[, ...])</p></td> +<td><p>Returns an approximate solution to the traveling salesman problem.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.traveling_salesman.asadpour_atsp.html#networkx.algorithms.approximation.traveling_salesman.asadpour_atsp" title="networkx.algorithms.approximation.traveling_salesman.asadpour_atsp"><code class="xref py py-obj docutils literal notranslate"><span class="pre">asadpour_atsp</span></code></a>(G[, weight, seed, source])</p></td> +<td><p>Returns an approximate solution to the traveling salesman problem.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.treewidth"> +<span id="treewidth"></span><h2>Treewidth<a class="headerlink" href="#module-networkx.algorithms.approximation.treewidth" title="Permalink to this heading">#</a></h2> +<p>Functions for computing treewidth decomposition.</p> +<p>Treewidth of an undirected graph is a number associated with the graph. +It can be defined as the size of the largest vertex set (bag) in a tree +decomposition of the graph minus one.</p> +<p><a class="reference external" href="https://en.wikipedia.org/wiki/Treewidth">Wikipedia: Treewidth</a></p> +<p>The notions of treewidth and tree decomposition have gained their +attractiveness partly because many graph and network problems that are +intractable (e.g., NP-hard) on arbitrary graphs become efficiently +solvable (e.g., with a linear time algorithm) when the treewidth of the +input graphs is bounded by a constant <a class="reference internal" href="#rfd2b568a4a59-1" id="id2">[1]</a> <a class="reference internal" href="#rfd2b568a4a59-2" id="id3">[2]</a>.</p> +<p>There are two different functions for computing a tree decomposition: +<a class="reference internal" href="generated/networkx.algorithms.approximation.treewidth.treewidth_min_degree.html#networkx.algorithms.approximation.treewidth.treewidth_min_degree" title="networkx.algorithms.approximation.treewidth.treewidth_min_degree"><code class="xref py py-func docutils literal notranslate"><span class="pre">treewidth_min_degree()</span></code></a> and <a class="reference internal" href="generated/networkx.algorithms.approximation.treewidth.treewidth_min_fill_in.html#networkx.algorithms.approximation.treewidth.treewidth_min_fill_in" title="networkx.algorithms.approximation.treewidth.treewidth_min_fill_in"><code class="xref py py-func docutils literal notranslate"><span class="pre">treewidth_min_fill_in()</span></code></a>.</p> +<div role="list" class="citation-list"> +<div class="citation" id="rfd2b568a4a59-1" role="doc-biblioentry"> +<span class="label"><span class="fn-bracket">[</span><a role="doc-backlink" href="#id2">1</a><span class="fn-bracket">]</span></span> +<p>Hans L. Bodlaender and Arie M. C. A. Koster. 2010. “Treewidth +computations I.Upper bounds”. Inf. Comput. 208, 3 (March 2010),259-275. +<a class="reference external" href="http://dx.doi.org/10.1016/j.ic.2009.03.008">http://dx.doi.org/10.1016/j.ic.2009.03.008</a></p> +</div> +<div class="citation" id="rfd2b568a4a59-2" role="doc-biblioentry"> +<span class="label"><span class="fn-bracket">[</span><a role="doc-backlink" href="#id3">2</a><span class="fn-bracket">]</span></span> +<p>Hans L. Bodlaender. “Discovering Treewidth”. Institute of Information +and Computing Sciences, Utrecht University. +Technical Report UU-CS-2005-018. +<a class="reference external" href="http://www.cs.uu.nl">http://www.cs.uu.nl</a></p> +</div> +<div class="citation" id="rfd2b568a4a59-3" role="doc-biblioentry"> +<span class="label"><span class="fn-bracket">[</span>3<span class="fn-bracket">]</span></span> +<p>K. Wang, Z. Lu, and J. Hicks <em>Treewidth</em>. +<a class="reference external" href="https://web.archive.org/web/20210507025929/http://web.eecs.utk.edu/~cphill25/cs594_spring2015_projects/treewidth.pdf">https://web.archive.org/web/20210507025929/http://web.eecs.utk.edu/~cphill25/cs594_spring2015_projects/treewidth.pdf</a></p> +</div> +</div> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.treewidth.treewidth_min_degree.html#networkx.algorithms.approximation.treewidth.treewidth_min_degree" title="networkx.algorithms.approximation.treewidth.treewidth_min_degree"><code class="xref py py-obj docutils literal notranslate"><span class="pre">treewidth_min_degree</span></code></a>(G)</p></td> +<td><p>Returns a treewidth decomposition using the Minimum Degree heuristic.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.treewidth.treewidth_min_fill_in.html#networkx.algorithms.approximation.treewidth.treewidth_min_fill_in" title="networkx.algorithms.approximation.treewidth.treewidth_min_fill_in"><code class="xref py py-obj docutils literal notranslate"><span class="pre">treewidth_min_fill_in</span></code></a>(G)</p></td> +<td><p>Returns a treewidth decomposition using the Minimum Fill-in heuristic.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.vertex_cover"> +<span id="vertex-cover"></span><h2>Vertex Cover<a class="headerlink" href="#module-networkx.algorithms.approximation.vertex_cover" title="Permalink to this heading">#</a></h2> +<p>Functions for computing an approximate minimum weight vertex cover.</p> +<p>A <a class="reference external" href="https://en.wikipedia.org/wiki/Vertex_cover"><em>vertex cover</em></a> is a subset of nodes such that each edge in the graph +is incident to at least one node in the subset.</p> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.vertex_cover.min_weighted_vertex_cover.html#networkx.algorithms.approximation.vertex_cover.min_weighted_vertex_cover" title="networkx.algorithms.approximation.vertex_cover.min_weighted_vertex_cover"><code class="xref py py-obj docutils literal notranslate"><span class="pre">min_weighted_vertex_cover</span></code></a>(G[, weight])</p></td> +<td><p>Returns an approximate minimum weighted vertex cover.</p></td> +</tr> +</tbody> +</table> +</section> +<section id="module-networkx.algorithms.approximation.maxcut"> +<span id="max-cut"></span><h2>Max Cut<a class="headerlink" href="#module-networkx.algorithms.approximation.maxcut" title="Permalink to this heading">#</a></h2> +<table class="autosummary longtable table autosummary"> +<tbody> +<tr class="row-odd"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.maxcut.randomized_partitioning.html#networkx.algorithms.approximation.maxcut.randomized_partitioning" title="networkx.algorithms.approximation.maxcut.randomized_partitioning"><code class="xref py py-obj docutils literal notranslate"><span class="pre">randomized_partitioning</span></code></a>(G[, seed, p, weight])</p></td> +<td><p>Compute a random partitioning of the graph nodes and its cut value.</p></td> +</tr> +<tr class="row-even"><td><p><a class="reference internal" href="generated/networkx.algorithms.approximation.maxcut.one_exchange.html#networkx.algorithms.approximation.maxcut.one_exchange" title="networkx.algorithms.approximation.maxcut.one_exchange"><code class="xref py py-obj docutils literal notranslate"><span class="pre">one_exchange</span></code></a>(G[, initial_cut, seed, weight])</p></td> +<td><p>Compute a partitioning of the graphs nodes and the corresponding cut value.</p></td> +</tr> +</tbody> +</table> +</section> +</section> + + + </article> + + + + </div> + + + + <div class="bd-sidebar-secondary bd-toc"> + +<div class="toc-item"> + +<div class="tocsection onthispage"> + <i class="fa-solid fa-list"></i> On this page +</div> +<nav id="bd-toc-nav" class="page-toc"> + <ul class="visible nav section-nav flex-column"> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.connectivity"> + Connectivity + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.kcomponents"> + K-components + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.clique"> + Clique + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.clustering_coefficient"> + Clustering + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.distance_measures"> + Distance Measures + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.dominating_set"> + Dominating Set + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.matching"> + Matching + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.ramsey"> + Ramsey + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.steinertree"> + Steiner Tree + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.traveling_salesman"> + Traveling Salesman + </a> + <ul class="nav section-nav flex-column"> + <li class="toc-h3 nav-item toc-entry"> + <a class="reference internal nav-link" href="#travelling-salesman-problem-tsp"> + Travelling Salesman Problem (TSP) + </a> + </li> + </ul> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.treewidth"> + Treewidth + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.vertex_cover"> + Vertex Cover + </a> + </li> + <li class="toc-h2 nav-item toc-entry"> + <a class="reference internal nav-link" href="#module-networkx.algorithms.approximation.maxcut"> + Max Cut + </a> + </li> +</ul> + +</nav> +</div> + +<div class="toc-item"> + +<div id="searchbox"></div> +</div> + +<div class="toc-item"> + +</div> + +<div class="toc-item"> + +</div> + + </div> + + + </div> + <footer class="bd-footer-content"> + <div class="bd-footer-content__inner"> + + </div> + </footer> + + </main> + </div> + </div> + + + + <!-- Scripts loaded after <body> so the DOM is not blocked --> + <script src="../../_static/scripts/bootstrap.js?digest=796348d33e8b1d947c94"></script> +<script src="../../_static/scripts/pydata-sphinx-theme.js?digest=796348d33e8b1d947c94"></script> + + <footer class="bd-footer"><div class="bd-footer__inner container"> + + <div class="footer-item"> + +<p class="copyright"> + + © Copyright 2004-2022, NetworkX Developers.<br> + +</p> + + </div> + + <div class="footer-item"> + <p class="theme-version"> + Built with the + <a href="https://pydata-sphinx-theme.readthedocs.io/en/stable/index.html"> + PyData Sphinx Theme + </a> + 0.12.0. +</p> + </div> + + <div class="footer-item"> + +<p class="sphinx-version"> +Created using <a href="http://sphinx-doc.org/">Sphinx</a> 5.2.3.<br> +</p> + + </div> + +</div> + </footer> + </body> +</html>
\ No newline at end of file |