<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>networkx.algorithms.graphical — NetworkX 1.8.1 documentation</title>
<link rel="stylesheet" href="../../../_static/networkx.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../../../',
VERSION: '1.8.1',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: false
};
</script>
<script type="text/javascript" src="../../../_static/jquery.js"></script>
<script type="text/javascript" src="../../../_static/underscore.js"></script>
<script type="text/javascript" src="../../../_static/doctools.js"></script>
<link rel="search" type="application/opensearchdescription+xml"
title="Search within NetworkX 1.8.1 documentation"
href="../../../_static/opensearch.xml"/>
<link rel="top" title="NetworkX 1.8.1 documentation" href="../../../index.html" />
<link rel="up" title="networkx" href="../../networkx.html" />
</head>
<body>
<div style="color: black;background-color: white; font-size: 3.2em; text-align: left; padding: 15px 10px 10px 15px">
NetworkX
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../../../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="../../../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li><a href="http://networkx.github.com/">NetworkX Home </a> | </li>
<li><a href="http://networkx.github.com/documentation.html">Documentation </a>| </li>
<li><a href="http://networkx.github.com/download.html">Download </a> | </li>
<li><a href="http://github.com/networkx">Developer (Github)</a></li>
<li><a href="../../index.html" >Module code</a> »</li>
<li><a href="../../networkx.html" accesskey="U">networkx</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="../../../search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<h1>Source code for networkx.algorithms.graphical</h1><div class="highlight"><pre>
<span class="c"># -*- coding: utf-8 -*-</span>
<span class="sd">"""Test sequences for graphiness.</span>
<span class="sd">"""</span>
<span class="c"># Copyright (C) 2004-2013 by</span>
<span class="c"># Aric Hagberg <hagberg@lanl.gov></span>
<span class="c"># Dan Schult <dschult@colgate.edu></span>
<span class="c"># Pieter Swart <swart@lanl.gov></span>
<span class="c"># All rights reserved.</span>
<span class="c"># BSD license.</span>
<span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">defaultdict</span>
<span class="kn">import</span> <span class="nn">heapq</span>
<span class="kn">import</span> <span class="nn">networkx</span> <span class="kn">as</span> <span class="nn">nx</span>
<span class="n">__author__</span> <span class="o">=</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="o">.</span><span class="n">join</span><span class="p">([</span><span class="s">'Aric Hagberg (hagberg@lanl.gov)'</span><span class="p">,</span>
<span class="s">'Pieter Swart (swart@lanl.gov)'</span><span class="p">,</span>
<span class="s">'Dan Schult (dschult@colgate.edu)'</span>
<span class="s">'Joel Miller (joel.c.miller.research@gmail.com)'</span>
<span class="s">'Ben Edwards'</span>
<span class="s">'Brian Cloteaux <brian.cloteaux@nist.gov>'</span><span class="p">])</span>
<span class="n">__all__</span> <span class="o">=</span> <span class="p">[</span><span class="s">'is_graphical'</span><span class="p">,</span>
<span class="s">'is_multigraphical'</span><span class="p">,</span>
<span class="s">'is_pseudographical'</span><span class="p">,</span>
<span class="s">'is_digraphical'</span><span class="p">,</span>
<span class="s">'is_valid_degree_sequence_erdos_gallai'</span><span class="p">,</span>
<span class="s">'is_valid_degree_sequence_havel_hakimi'</span><span class="p">,</span>
<span class="s">'is_valid_degree_sequence'</span><span class="p">,</span> <span class="c"># deprecated</span>
<span class="p">]</span>
<div class="viewcode-block" id="is_graphical"><a class="viewcode-back" href="../../../reference/generated/networkx.algorithms.graphical.is_graphical.html#networkx.algorithms.graphical.is_graphical">[docs]</a><span class="k">def</span> <span class="nf">is_graphical</span><span class="p">(</span><span class="n">sequence</span><span class="p">,</span> <span class="n">method</span><span class="o">=</span><span class="s">'eg'</span><span class="p">):</span>
<span class="sd">"""Returns True if sequence is a valid degree sequence.</span>
<span class="sd"> A degree sequence is valid if some graph can realize it.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> sequence : list or iterable container</span>
<span class="sd"> A sequence of integer node degrees</span>
<span class="sd"> method : "eg" | "hh"</span>
<span class="sd"> The method used to validate the degree sequence.</span>
<span class="sd"> "eg" corresponds to the Erdős-Gallai algorithm, and</span>
<span class="sd"> "hh" to the Havel-Hakimi algorithm.</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> valid : bool</span>
<span class="sd"> True if the sequence is a valid degree sequence and False if not.</span>
<span class="sd"> Examples</span>
<span class="sd"> --------</span>
<span class="sd"> >>> G = nx.path_graph(4)</span>
<span class="sd"> >>> sequence = G.degree().values()</span>
<span class="sd"> >>> nx.is_valid_degree_sequence(sequence)</span>
<span class="sd"> True</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> Erdős-Gallai</span>
<span class="sd"> [EG1960]_, [choudum1986]_</span>
<span class="sd"> Havel-Hakimi</span>
<span class="sd"> [havel1955]_, [hakimi1962]_, [CL1996]_</span>
<span class="sd"> """</span>
<span class="k">if</span> <span class="n">method</span> <span class="o">==</span> <span class="s">'eg'</span><span class="p">:</span>
<span class="n">valid</span> <span class="o">=</span> <span class="n">is_valid_degree_sequence_erdos_gallai</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="n">sequence</span><span class="p">))</span>
<span class="k">elif</span> <span class="n">method</span> <span class="o">==</span> <span class="s">'hh'</span><span class="p">:</span>
<span class="n">valid</span> <span class="o">=</span> <span class="n">is_valid_degree_sequence_havel_hakimi</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="n">sequence</span><span class="p">))</span>
<span class="k">else</span><span class="p">:</span>
<span class="n">msg</span> <span class="o">=</span> <span class="s">"`method` must be 'eg' or 'hh'"</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXException</span><span class="p">(</span><span class="n">msg</span><span class="p">)</span>
<span class="k">return</span> <span class="n">valid</span>
</div>
<span class="n">is_valid_degree_sequence</span> <span class="o">=</span> <span class="n">is_graphical</span>
<span class="k">def</span> <span class="nf">_basic_graphical_tests</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">):</span>
<span class="c"># Sort and perform some simple tests on the sequence</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">nx</span><span class="o">.</span><span class="n">utils</span><span class="o">.</span><span class="n">is_list_of_ints</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">):</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXUnfeasible</span>
<span class="n">p</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">)</span>
<span class="n">num_degs</span> <span class="o">=</span> <span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="n">p</span>
<span class="n">dmax</span><span class="p">,</span> <span class="n">dmin</span><span class="p">,</span> <span class="n">dsum</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">p</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<span class="k">for</span> <span class="n">d</span> <span class="ow">in</span> <span class="n">deg_sequence</span><span class="p">:</span>
<span class="c"># Reject if degree is negative or larger than the sequence length</span>
<span class="k">if</span> <span class="n">d</span><span class="o"><</span><span class="mi">0</span> <span class="ow">or</span> <span class="n">d</span><span class="o">>=</span><span class="n">p</span><span class="p">:</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXUnfeasible</span>
<span class="c"># Process only the non-zero integers</span>
<span class="k">elif</span> <span class="n">d</span><span class="o">></span><span class="mi">0</span><span class="p">:</span>
<span class="n">dmax</span><span class="p">,</span> <span class="n">dmin</span><span class="p">,</span> <span class="n">dsum</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">dmax</span><span class="p">,</span><span class="n">d</span><span class="p">),</span> <span class="nb">min</span><span class="p">(</span><span class="n">dmin</span><span class="p">,</span><span class="n">d</span><span class="p">),</span> <span class="n">dsum</span><span class="o">+</span><span class="n">d</span><span class="p">,</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span>
<span class="n">num_degs</span><span class="p">[</span><span class="n">d</span><span class="p">]</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="c"># Reject sequence if it has odd sum or is oversaturated</span>
<span class="k">if</span> <span class="n">dsum</span><span class="o">%</span><span class="mi">2</span> <span class="ow">or</span> <span class="n">dsum</span><span class="o">></span><span class="n">n</span><span class="o">*</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">):</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXUnfeasible</span>
<span class="k">return</span> <span class="n">dmax</span><span class="p">,</span><span class="n">dmin</span><span class="p">,</span><span class="n">dsum</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">num_degs</span>
<div class="viewcode-block" id="is_valid_degree_sequence_havel_hakimi"><a class="viewcode-back" href="../../../reference/generated/networkx.algorithms.graphical.is_valid_degree_sequence_havel_hakimi.html#networkx.algorithms.graphical.is_valid_degree_sequence_havel_hakimi">[docs]</a><span class="k">def</span> <span class="nf">is_valid_degree_sequence_havel_hakimi</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">):</span>
<span class="sd">r"""Returns True if deg_sequence can be realized by a simple graph.</span>
<span class="sd"> The validation proceeds using the Havel-Hakimi theorem.</span>
<span class="sd"> Worst-case run time is: O(s) where s is the sum of the sequence.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> deg_sequence : list</span>
<span class="sd"> A list of integers where each element specifies the degree of a node</span>
<span class="sd"> in a graph.</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> valid : bool</span>
<span class="sd"> True if deg_sequence is graphical and False if not.</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> The ZZ condition says that for the sequence d if</span>
<span class="sd"> </span>
<span class="sd"> .. math::</span>
<span class="sd"> |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}</span>
<span class="sd"> then d is graphical. This was shown in Theorem 6 in [1]_.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory</span>
<span class="sd"> of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992).</span>
<span class="sd"> [havel1955]_, [hakimi1962]_, [CL1996]_</span>
<span class="sd"> """</span>
<span class="k">try</span><span class="p">:</span>
<span class="n">dmax</span><span class="p">,</span><span class="n">dmin</span><span class="p">,</span><span class="n">dsum</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">num_degs</span> <span class="o">=</span> <span class="n">_basic_graphical_tests</span><span class="p">(</span><span class="n">deg_sequence</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>
<span class="k">return</span> <span class="bp">False</span>
<span class="c"># Accept if sequence has no non-zero degrees or passes the ZZ condition</span>
<span class="k">if</span> <span class="n">n</span><span class="o">==</span><span class="mi">0</span> <span class="ow">or</span> <span class="mi">4</span><span class="o">*</span><span class="n">dmin</span><span class="o">*</span><span class="n">n</span> <span class="o">>=</span> <span class="p">(</span><span class="n">dmax</span><span class="o">+</span><span class="n">dmin</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o">*</span> <span class="p">(</span><span class="n">dmax</span><span class="o">+</span><span class="n">dmin</span><span class="o">+</span><span class="mi">1</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">True</span>
<span class="n">modstubs</span> <span class="o">=</span> <span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="p">(</span><span class="n">dmax</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span>
<span class="c"># Successively reduce degree sequence by removing the maximum degree</span>
<span class="k">while</span> <span class="n">n</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="c"># Retrieve the maximum degree in the sequence</span>
<span class="k">while</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">dmax</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
<span class="n">dmax</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">;</span>
<span class="c"># If there are not enough stubs to connect to, then the sequence is</span>
<span class="c"># not graphical</span>
<span class="k">if</span> <span class="n">dmax</span> <span class="o">></span> <span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="c"># Remove largest stub in list</span>
<span class="n">num_degs</span><span class="p">[</span><span class="n">dmax</span><span class="p">],</span> <span class="n">n</span> <span class="o">=</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">dmax</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="mi">1</span>
<span class="c"># Reduce the next dmax largest stubs</span>
<span class="n">mslen</span> <span class="o">=</span> <span class="mi">0</span>
<span class="n">k</span> <span class="o">=</span> <span class="n">dmax</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">dmax</span><span class="p">):</span>
<span class="k">while</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
<span class="n">k</span> <span class="o">-=</span> <span class="mi">1</span>
<span class="n">num_degs</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">n</span> <span class="o">=</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="mi">1</span>
<span class="k">if</span> <span class="n">k</span> <span class="o">></span> <span class="mi">1</span><span class="p">:</span>
<span class="n">modstubs</span><span class="p">[</span><span class="n">mslen</span><span class="p">]</span> <span class="o">=</span> <span class="n">k</span><span class="o">-</span><span class="mi">1</span>
<span class="n">mslen</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="c"># Add back to the list any non-zero stubs that were removed</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">mslen</span><span class="p">):</span>
<span class="n">stub</span> <span class="o">=</span> <span class="n">modstubs</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<span class="n">num_degs</span><span class="p">[</span><span class="n">stub</span><span class="p">],</span> <span class="n">n</span> <span class="o">=</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">stub</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span>
<span class="k">return</span> <span class="bp">True</span>
</div>
<div class="viewcode-block" id="is_valid_degree_sequence_erdos_gallai"><a class="viewcode-back" href="../../../reference/generated/networkx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai.html#networkx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai">[docs]</a><span class="k">def</span> <span class="nf">is_valid_degree_sequence_erdos_gallai</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">):</span>
<span class="sd">r"""Returns True if deg_sequence can be realized by a simple graph.</span>
<span class="sd"> The validation is done using the Erdős-Gallai theorem [EG1960]_.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> deg_sequence : list</span>
<span class="sd"> A list of integers</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> valid : bool</span>
<span class="sd"> True if deg_sequence is graphical and False if not.</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> This implementation uses an equivalent form of the Erdős-Gallai criterion.</span>
<span class="sd"> Worst-case run time is: O(n) where n is the length of the sequence.</span>
<span class="sd"> Specifically, a sequence d is graphical if and only if the</span>
<span class="sd"> sum of the sequence is even and for all strong indices k in the sequence,</span>
<span class="sd"> .. math::</span>
<span class="sd"> \sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{j=k+1}^{n} \min(d_i,k)</span>
<span class="sd"> = k(n-1) - ( k \sum_{j=0}^{k-1} n_j - \sum_{j=0}^{k-1} j n_j )</span>
<span class="sd"> A strong index k is any index where `d_k \geq k` and the value `n_j` is the</span>
<span class="sd"> number of occurrences of j in d. The maximal strong index is called the</span>
<span class="sd"> Durfee index.</span>
<span class="sd"> This particular rearrangement comes from the proof of Theorem 3 in [2]_.</span>
<span class="sd"> The ZZ condition says that for the sequence d if</span>
<span class="sd"> </span>
<span class="sd"> .. math::</span>
<span class="sd"> |d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}</span>
<span class="sd"> then d is graphical. This was shown in Theorem 6 in [2]_.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] A. Tripathi and S. Vijay. "A note on a theorem of Erdős & Gallai",</span>
<span class="sd"> Discrete Mathematics, 265, pp. 417-420 (2003).</span>
<span class="sd"> .. [2] I.E. Zverovich and V.E. Zverovich. "Contributions to the theory</span>
<span class="sd"> of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992).</span>
<span class="sd"> [EG1960]_, [choudum1986]_</span>
<span class="sd"> """</span>
<span class="k">try</span><span class="p">:</span>
<span class="n">dmax</span><span class="p">,</span><span class="n">dmin</span><span class="p">,</span><span class="n">dsum</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">num_degs</span> <span class="o">=</span> <span class="n">_basic_graphical_tests</span><span class="p">(</span><span class="n">deg_sequence</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>
<span class="k">return</span> <span class="bp">False</span>
<span class="c"># Accept if sequence has no non-zero degrees or passes the ZZ condition</span>
<span class="k">if</span> <span class="n">n</span><span class="o">==</span><span class="mi">0</span> <span class="ow">or</span> <span class="mi">4</span><span class="o">*</span><span class="n">dmin</span><span class="o">*</span><span class="n">n</span> <span class="o">>=</span> <span class="p">(</span><span class="n">dmax</span><span class="o">+</span><span class="n">dmin</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o">*</span> <span class="p">(</span><span class="n">dmax</span><span class="o">+</span><span class="n">dmin</span><span class="o">+</span><span class="mi">1</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">True</span>
<span class="c"># Perform the EG checks using the reformulation of Zverovich and Zverovich</span>
<span class="n">k</span><span class="p">,</span> <span class="n">sum_deg</span><span class="p">,</span> <span class="n">sum_nj</span><span class="p">,</span> <span class="n">sum_jnj</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<span class="k">for</span> <span class="n">dk</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">dmax</span><span class="p">,</span> <span class="n">dmin</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">):</span>
<span class="k">if</span> <span class="n">dk</span> <span class="o"><</span> <span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">:</span> <span class="c"># Check if already past Durfee index</span>
<span class="k">return</span> <span class="bp">True</span>
<span class="k">if</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">dk</span><span class="p">]</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="n">run_size</span> <span class="o">=</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">dk</span><span class="p">]</span> <span class="c"># Process a run of identical-valued degrees</span>
<span class="k">if</span> <span class="n">dk</span> <span class="o"><</span> <span class="n">k</span><span class="o">+</span><span class="n">run_size</span><span class="p">:</span> <span class="c"># Check if end of run is past Durfee index</span>
<span class="n">run_size</span> <span class="o">=</span> <span class="n">dk</span><span class="o">-</span><span class="n">k</span> <span class="c"># Adjust back to Durfee index</span>
<span class="n">sum_deg</span> <span class="o">+=</span> <span class="n">run_size</span> <span class="o">*</span> <span class="n">dk</span>
<span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">run_size</span><span class="p">):</span>
<span class="n">sum_nj</span> <span class="o">+=</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">k</span><span class="o">+</span><span class="n">v</span><span class="p">]</span>
<span class="n">sum_jnj</span> <span class="o">+=</span> <span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="n">v</span><span class="p">)</span> <span class="o">*</span> <span class="n">num_degs</span><span class="p">[</span><span class="n">k</span><span class="o">+</span><span class="n">v</span><span class="p">]</span>
<span class="n">k</span> <span class="o">+=</span> <span class="n">run_size</span>
<span class="k">if</span> <span class="n">sum_deg</span> <span class="o">></span> <span class="n">k</span><span class="o">*</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">-</span> <span class="n">k</span><span class="o">*</span><span class="n">sum_nj</span> <span class="o">+</span> <span class="n">sum_jnj</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="k">return</span> <span class="bp">True</span>
</div>
<div class="viewcode-block" id="is_multigraphical"><a class="viewcode-back" href="../../../reference/generated/networkx.algorithms.graphical.is_multigraphical.html#networkx.algorithms.graphical.is_multigraphical">[docs]</a><span class="k">def</span> <span class="nf">is_multigraphical</span><span class="p">(</span><span class="n">sequence</span><span class="p">):</span>
<span class="sd">"""Returns True if some multigraph can realize the sequence.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> deg_sequence : list</span>
<span class="sd"> A list of integers</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> valid : bool</span>
<span class="sd"> True if deg_sequence is a multigraphic degree sequence and False if not.</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> The worst-case run time is O(n) where n is the length of the sequence.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] S. L. Hakimi. "On the realizability of a set of integers as</span>
<span class="sd"> degrees of the vertices of a linear graph", J. SIAM, 10, pp. 496-506</span>
<span class="sd"> (1962).</span>
<span class="sd"> """</span>
<span class="n">deg_sequence</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">sequence</span><span class="p">)</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">nx</span><span class="o">.</span><span class="n">utils</span><span class="o">.</span><span class="n">is_list_of_ints</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="n">dsum</span><span class="p">,</span> <span class="n">dmax</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<span class="k">for</span> <span class="n">d</span> <span class="ow">in</span> <span class="n">deg_sequence</span><span class="p">:</span>
<span class="k">if</span> <span class="n">d</span><span class="o"><</span><span class="mi">0</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="n">dsum</span><span class="p">,</span> <span class="n">dmax</span> <span class="o">=</span> <span class="n">dsum</span><span class="o">+</span><span class="n">d</span><span class="p">,</span> <span class="nb">max</span><span class="p">(</span><span class="n">dmax</span><span class="p">,</span><span class="n">d</span><span class="p">)</span>
<span class="k">if</span> <span class="n">dsum</span><span class="o">%</span><span class="mi">2</span> <span class="ow">or</span> <span class="n">dsum</span><span class="o"><</span><span class="mi">2</span><span class="o">*</span><span class="n">dmax</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="k">return</span> <span class="bp">True</span>
</div>
<div class="viewcode-block" id="is_pseudographical"><a class="viewcode-back" href="../../../reference/generated/networkx.algorithms.graphical.is_pseudographical.html#networkx.algorithms.graphical.is_pseudographical">[docs]</a><span class="k">def</span> <span class="nf">is_pseudographical</span><span class="p">(</span><span class="n">sequence</span><span class="p">):</span>
<span class="sd">"""Returns True if some pseudograph can realize the sequence.</span>
<span class="sd"> Every nonnegative integer sequence with an even sum is pseudographical</span>
<span class="sd"> (see [1]_).</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> sequence : list or iterable container</span>
<span class="sd"> A sequence of integer node degrees</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> valid : bool</span>
<span class="sd"> True if the sequence is a pseudographic degree sequence and False if not.</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> The worst-case run time is O(n) where n is the length of the sequence.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] F. Boesch and F. Harary. "Line removal algorithms for graphs</span>
<span class="sd"> and their degree lists", IEEE Trans. Circuits and Systems, CAS-23(12),</span>
<span class="sd"> pp. 778-782 (1976).</span>
<span class="sd"> """</span>
<span class="n">s</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">sequence</span><span class="p">)</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">nx</span><span class="o">.</span><span class="n">utils</span><span class="o">.</span><span class="n">is_list_of_ints</span><span class="p">(</span><span class="n">s</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="k">return</span> <span class="nb">sum</span><span class="p">(</span><span class="n">s</span><span class="p">)</span><span class="o">%</span><span class="mi">2</span> <span class="o">==</span> <span class="mi">0</span> <span class="ow">and</span> <span class="nb">min</span><span class="p">(</span><span class="n">s</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">0</span>
</div>
<div class="viewcode-block" id="is_digraphical"><a class="viewcode-back" href="../../../reference/generated/networkx.algorithms.graphical.is_digraphical.html#networkx.algorithms.graphical.is_digraphical">[docs]</a><span class="k">def</span> <span class="nf">is_digraphical</span><span class="p">(</span><span class="n">in_sequence</span><span class="p">,</span> <span class="n">out_sequence</span><span class="p">):</span>
<span class="sd">r"""Returns True if some directed graph can realize the in- and out-degree </span>
<span class="sd"> sequences.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> in_sequence : list or iterable container</span>
<span class="sd"> A sequence of integer node in-degrees</span>
<span class="sd"> out_sequence : list or iterable container</span>
<span class="sd"> A sequence of integer node out-degrees</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> valid : bool</span>
<span class="sd"> True if in and out-sequences are digraphic False if not.</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> This algorithm is from Kleitman and Wang [1]_.</span>
<span class="sd"> The worst case runtime is O(s * log n) where s and n are the sum and length</span>
<span class="sd"> of the sequences respectively.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] D.J. Kleitman and D.L. Wang</span>
<span class="sd"> Algorithms for Constructing Graphs and Digraphs with Given Valences</span>
<span class="sd"> and Factors, Discrete Mathematics, 6(1), pp. 79-88 (1973)</span>
<span class="sd"> """</span>
<span class="n">in_deg_sequence</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">in_sequence</span><span class="p">)</span>
<span class="n">out_deg_sequence</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">out_sequence</span><span class="p">)</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">nx</span><span class="o">.</span><span class="n">utils</span><span class="o">.</span><span class="n">is_list_of_ints</span><span class="p">(</span><span class="n">in_deg_sequence</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">nx</span><span class="o">.</span><span class="n">utils</span><span class="o">.</span><span class="n">is_list_of_ints</span><span class="p">(</span><span class="n">out_deg_sequence</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="c"># Process the sequences and form two heaps to store degree pairs with</span>
<span class="c"># either zero or non-zero out degrees</span>
<span class="n">sumin</span><span class="p">,</span> <span class="n">sumout</span><span class="p">,</span> <span class="n">nin</span><span class="p">,</span> <span class="n">nout</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">in_deg_sequence</span><span class="p">),</span> <span class="nb">len</span><span class="p">(</span><span class="n">out_deg_sequence</span><span class="p">)</span>
<span class="n">maxn</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">nin</span><span class="p">,</span> <span class="n">nout</span><span class="p">)</span>
<span class="n">maxin</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">if</span> <span class="n">maxn</span><span class="o">==</span><span class="mi">0</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">True</span>
<span class="n">stubheap</span><span class="p">,</span> <span class="n">zeroheap</span> <span class="o">=</span> <span class="p">[</span> <span class="p">],</span> <span class="p">[</span> <span class="p">]</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">maxn</span><span class="p">):</span>
<span class="n">in_deg</span><span class="p">,</span> <span class="n">out_deg</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<span class="k">if</span> <span class="n">n</span><span class="o"><</span><span class="n">nout</span><span class="p">:</span>
<span class="n">out_deg</span> <span class="o">=</span> <span class="n">out_deg_sequence</span><span class="p">[</span><span class="n">n</span><span class="p">]</span>
<span class="k">if</span> <span class="n">n</span><span class="o"><</span><span class="n">nin</span><span class="p">:</span>
<span class="n">in_deg</span> <span class="o">=</span> <span class="n">in_deg_sequence</span><span class="p">[</span><span class="n">n</span><span class="p">]</span>
<span class="k">if</span> <span class="n">in_deg</span><span class="o"><</span><span class="mi">0</span> <span class="ow">or</span> <span class="n">out_deg</span><span class="o"><</span><span class="mi">0</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="n">sumin</span><span class="p">,</span> <span class="n">sumout</span><span class="p">,</span> <span class="n">maxin</span> <span class="o">=</span> <span class="n">sumin</span><span class="o">+</span><span class="n">in_deg</span><span class="p">,</span> <span class="n">sumout</span><span class="o">+</span><span class="n">out_deg</span><span class="p">,</span> <span class="nb">max</span><span class="p">(</span><span class="n">maxin</span><span class="p">,</span> <span class="n">in_deg</span><span class="p">)</span>
<span class="k">if</span> <span class="n">in_deg</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="n">stubheap</span><span class="o">.</span><span class="n">append</span><span class="p">((</span><span class="o">-</span><span class="mi">1</span><span class="o">*</span><span class="n">out_deg</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="o">*</span><span class="n">in_deg</span><span class="p">))</span>
<span class="k">elif</span> <span class="n">out_deg</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="n">zeroheap</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="o">-</span><span class="mi">1</span><span class="o">*</span><span class="n">out_deg</span><span class="p">)</span>
<span class="k">if</span> <span class="n">sumin</span> <span class="o">!=</span> <span class="n">sumout</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heapify</span><span class="p">(</span><span class="n">stubheap</span><span class="p">)</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heapify</span><span class="p">(</span><span class="n">zeroheap</span><span class="p">)</span>
<span class="n">modstubs</span> <span class="o">=</span> <span class="p">[(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">)]</span><span class="o">*</span><span class="p">(</span><span class="n">maxin</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span>
<span class="c"># Successively reduce degree sequence by removing the maximum out degree</span>
<span class="k">while</span> <span class="n">stubheap</span><span class="p">:</span>
<span class="c"># Take the first value in the sequence with non-zero in degree</span>
<span class="p">(</span><span class="n">freeout</span><span class="p">,</span> <span class="n">freein</span><span class="p">)</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span> <span class="n">stubheap</span> <span class="p">)</span>
<span class="n">freein</span> <span class="o">*=</span> <span class="o">-</span><span class="mi">1</span>
<span class="k">if</span> <span class="n">freein</span> <span class="o">></span> <span class="nb">len</span><span class="p">(</span><span class="n">stubheap</span><span class="p">)</span><span class="o">+</span><span class="nb">len</span><span class="p">(</span><span class="n">zeroheap</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="c"># Attach out stubs to the nodes with the most in stubs</span>
<span class="n">mslen</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">freein</span><span class="p">):</span>
<span class="k">if</span> <span class="n">zeroheap</span> <span class="ow">and</span> <span class="p">(</span><span class="ow">not</span> <span class="n">stubheap</span> <span class="ow">or</span> <span class="n">stubheap</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">></span> <span class="n">zeroheap</span><span class="p">[</span><span class="mi">0</span><span class="p">]):</span>
<span class="n">stubout</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">zeroheap</span><span class="p">)</span>
<span class="n">stubin</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">else</span><span class="p">:</span>
<span class="p">(</span><span class="n">stubout</span><span class="p">,</span> <span class="n">stubin</span><span class="p">)</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">stubheap</span><span class="p">)</span>
<span class="k">if</span> <span class="n">stubout</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="c"># Check if target is now totally connected</span>
<span class="k">if</span> <span class="n">stubout</span><span class="o">+</span><span class="mi">1</span><span class="o"><</span><span class="mi">0</span> <span class="ow">or</span> <span class="n">stubin</span><span class="o"><</span><span class="mi">0</span><span class="p">:</span>
<span class="n">modstubs</span><span class="p">[</span><span class="n">mslen</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">stubout</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">stubin</span><span class="p">)</span>
<span class="n">mslen</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="c"># Add back the nodes to the heap that still have available stubs</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">mslen</span><span class="p">):</span>
<span class="n">stub</span> <span class="o">=</span> <span class="n">modstubs</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<span class="k">if</span> <span class="n">stub</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o"><</span> <span class="mi">0</span><span class="p">:</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heappush</span><span class="p">(</span><span class="n">stubheap</span><span class="p">,</span> <span class="n">stub</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heappush</span><span class="p">(</span><span class="n">zeroheap</span><span class="p">,</span> <span class="n">stub</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
<span class="k">if</span> <span class="n">freeout</span><span class="o"><</span><span class="mi">0</span><span class="p">:</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heappush</span><span class="p">(</span><span class="n">zeroheap</span><span class="p">,</span> <span class="n">freeout</span><span class="p">)</span>
<span class="k">return</span> <span class="bp">True</span></div>
</pre></div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../../../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="../../../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li><a href="http://networkx.github.com/">NetworkX Home </a> | </li>
<li><a href="http://networkx.github.com/documentation.html">Documentation </a>| </li>
<li><a href="http://networkx.github.com/download.html">Download </a> | </li>
<li><a href="http://github.com/networkx">Developer (Github)</a></li>
<li><a href="../../index.html" >Module code</a> »</li>
<li><a href="../../networkx.html" >networkx</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright 2013, NetworkX Developers.
Last updated on Oct 23, 2013.
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.1.3.
</div>
</body>
</html>
