<!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.generators.degree_seq — 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.generators.degree_seq</h1><div class="highlight"><pre>
<span class="c"># -*- coding: utf-8 -*-</span>
<span class="sd">"""Generate graphs with a given degree sequence or expected degree sequence.</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">import</span> <span class="nn">heapq</span>
<span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> <span class="n">combinations</span><span class="p">,</span> <span class="n">permutations</span>
<span class="kn">import</span> <span class="nn">math</span>
<span class="kn">from</span> <span class="nn">operator</span> <span class="kn">import</span> <span class="n">itemgetter</span>
<span class="kn">import</span> <span class="nn">random</span>
<span class="kn">import</span> <span class="nn">networkx</span> <span class="kn">as</span> <span class="nn">nx</span>
<span class="kn">from</span> <span class="nn">networkx.utils</span> <span class="kn">import</span> <span class="n">random_weighted_sample</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 <aric.hagberg@gmail.com>'</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="p">,</span>
<span class="s">'Nathan Lemons <nlemons@gmail.com>'</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">'configuration_model'</span><span class="p">,</span>
<span class="s">'directed_configuration_model'</span><span class="p">,</span>
<span class="s">'expected_degree_graph'</span><span class="p">,</span>
<span class="s">'havel_hakimi_graph'</span><span class="p">,</span>
<span class="s">'directed_havel_hakimi_graph'</span><span class="p">,</span>
<span class="s">'degree_sequence_tree'</span><span class="p">,</span>
<span class="s">'random_degree_sequence_graph'</span><span class="p">]</span>
<div class="viewcode-block" id="configuration_model"><a class="viewcode-back" href="../../../reference/generated/networkx.generators.degree_seq.configuration_model.html#networkx.generators.degree_seq.configuration_model">[docs]</a><span class="k">def</span> <span class="nf">configuration_model</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">,</span><span class="n">create_using</span><span class="o">=</span><span class="bp">None</span><span class="p">,</span><span class="n">seed</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="sd">"""Return a random graph with the given degree sequence.</span>
<span class="sd"> The configuration model generates a random pseudograph (graph with</span>
<span class="sd"> parallel edges and self loops) by randomly assigning edges to</span>
<span class="sd"> match the given degree sequence.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> deg_sequence : list of integers</span>
<span class="sd"> Each list entry corresponds to the degree of a node.</span>
<span class="sd"> create_using : graph, optional (default MultiGraph)</span>
<span class="sd"> Return graph of this type. The instance will be cleared.</span>
<span class="sd"> seed : hashable object, optional</span>
<span class="sd"> Seed for random number generator.</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> G : MultiGraph</span>
<span class="sd"> A graph with the specified degree sequence.</span>
<span class="sd"> Nodes are labeled starting at 0 with an index</span>
<span class="sd"> corresponding to the position in deg_sequence.</span>
<span class="sd"> Raises</span>
<span class="sd"> ------</span>
<span class="sd"> NetworkXError</span>
<span class="sd"> If the degree sequence does not have an even sum.</span>
<span class="sd"> See Also</span>
<span class="sd"> --------</span>
<span class="sd"> is_valid_degree_sequence</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> As described by Newman [1]_.</span>
<span class="sd"> A non-graphical degree sequence (not realizable by some simple</span>
<span class="sd"> graph) is allowed since this function returns graphs with self</span>
<span class="sd"> loops and parallel edges. An exception is raised if the degree</span>
<span class="sd"> sequence does not have an even sum.</span>
<span class="sd"> This configuration model construction process can lead to</span>
<span class="sd"> duplicate edges and loops. You can remove the self-loops and</span>
<span class="sd"> parallel edges (see below) which will likely result in a graph</span>
<span class="sd"> that doesn't have the exact degree sequence specified. This</span>
<span class="sd"> "finite-size effect" decreases as the size of the graph increases.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] M.E.J. Newman, "The structure and function of complex networks",</span>
<span class="sd"> SIAM REVIEW 45-2, pp 167-256, 2003.</span>
<span class="sd"> Examples</span>
<span class="sd"> --------</span>
<span class="sd"> >>> from networkx.utils import powerlaw_sequence</span>
<span class="sd"> >>> z=nx.utils.create_degree_sequence(100,powerlaw_sequence)</span>
<span class="sd"> >>> G=nx.configuration_model(z)</span>
<span class="sd"> To remove parallel edges:</span>
<span class="sd"> >>> G=nx.Graph(G)</span>
<span class="sd"> To remove self loops:</span>
<span class="sd"> >>> G.remove_edges_from(G.selfloop_edges())</span>
<span class="sd"> """</span>
<span class="k">if</span> <span class="ow">not</span> <span class="nb">sum</span><span class="p">(</span><span class="n">deg_sequence</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="p">:</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">'Invalid degree sequence'</span><span class="p">)</span>
<span class="k">if</span> <span class="n">create_using</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">create_using</span> <span class="o">=</span> <span class="n">nx</span><span class="o">.</span><span class="n">MultiGraph</span><span class="p">()</span>
<span class="k">elif</span> <span class="n">create_using</span><span class="o">.</span><span class="n">is_directed</span><span class="p">():</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">"Directed Graph not supported"</span><span class="p">)</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">seed</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="n">seed</span><span class="p">)</span>
<span class="c"># start with empty N-node graph</span>
<span class="n">N</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="c"># allow multiedges and selfloops</span>
<span class="n">G</span><span class="o">=</span><span class="n">nx</span><span class="o">.</span><span class="n">empty_graph</span><span class="p">(</span><span class="n">N</span><span class="p">,</span><span class="n">create_using</span><span class="p">)</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="nb">max</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">)</span><span class="o">==</span><span class="mi">0</span><span class="p">:</span> <span class="c"># done if no edges</span>
<span class="k">return</span> <span class="n">G</span>
<span class="c"># build stublist, a list of available degree-repeated stubs</span>
<span class="c"># e.g. for deg_sequence=[3,2,1,1,1]</span>
<span class="c"># initially, stublist=[1,1,1,2,2,3,4,5]</span>
<span class="c"># i.e., node 1 has degree=3 and is repeated 3 times, etc.</span>
<span class="n">stublist</span><span class="o">=</span><span class="p">[]</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="n">G</span><span class="p">:</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">deg_sequence</span><span class="p">[</span><span class="n">n</span><span class="p">]):</span>
<span class="n">stublist</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
<span class="c"># shuffle stublist and assign pairs by removing 2 elements at a time</span>
<span class="n">random</span><span class="o">.</span><span class="n">shuffle</span><span class="p">(</span><span class="n">stublist</span><span class="p">)</span>
<span class="k">while</span> <span class="n">stublist</span><span class="p">:</span>
<span class="n">n1</span> <span class="o">=</span> <span class="n">stublist</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<span class="n">n2</span> <span class="o">=</span> <span class="n">stublist</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">n1</span><span class="p">,</span><span class="n">n2</span><span class="p">)</span>
<span class="n">G</span><span class="o">.</span><span class="n">name</span><span class="o">=</span><span class="s">"configuration_model </span><span class="si">%d</span><span class="s"> nodes </span><span class="si">%d</span><span class="s"> edges"</span><span class="o">%</span><span class="p">(</span><span class="n">G</span><span class="o">.</span><span class="n">order</span><span class="p">(),</span><span class="n">G</span><span class="o">.</span><span class="n">size</span><span class="p">())</span>
<span class="k">return</span> <span class="n">G</span>
</div>
<div class="viewcode-block" id="directed_configuration_model"><a class="viewcode-back" href="../../../reference/generated/networkx.generators.degree_seq.directed_configuration_model.html#networkx.generators.degree_seq.directed_configuration_model">[docs]</a><span class="k">def</span> <span class="nf">directed_configuration_model</span><span class="p">(</span><span class="n">in_degree_sequence</span><span class="p">,</span>
<span class="n">out_degree_sequence</span><span class="p">,</span>
<span class="n">create_using</span><span class="o">=</span><span class="bp">None</span><span class="p">,</span><span class="n">seed</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="sd">"""Return a directed_random graph with the given degree sequences.</span>
<span class="sd"> The configuration model generates a random directed pseudograph</span>
<span class="sd"> (graph with parallel edges and self loops) by randomly assigning</span>
<span class="sd"> edges to match the given degree sequences.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> in_degree_sequence : list of integers</span>
<span class="sd"> Each list entry corresponds to the in-degree of a node.</span>
<span class="sd"> out_degree_sequence : list of integers</span>
<span class="sd"> Each list entry corresponds to the out-degree of a node.</span>
<span class="sd"> create_using : graph, optional (default MultiDiGraph)</span>
<span class="sd"> Return graph of this type. The instance will be cleared.</span>
<span class="sd"> seed : hashable object, optional</span>
<span class="sd"> Seed for random number generator.</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> G : MultiDiGraph</span>
<span class="sd"> A graph with the specified degree sequences.</span>
<span class="sd"> Nodes are labeled starting at 0 with an index</span>
<span class="sd"> corresponding to the position in deg_sequence.</span>
<span class="sd"> Raises</span>
<span class="sd"> ------</span>
<span class="sd"> NetworkXError</span>
<span class="sd"> If the degree sequences do not have the same sum.</span>
<span class="sd"> See Also</span>
<span class="sd"> --------</span>
<span class="sd"> configuration_model</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> Algorithm as described by Newman [1]_.</span>
<span class="sd"> A non-graphical degree sequence (not realizable by some simple</span>
<span class="sd"> graph) is allowed since this function returns graphs with self</span>
<span class="sd"> loops and parallel edges. An exception is raised if the degree</span>
<span class="sd"> sequences does not have the same sum.</span>
<span class="sd"> This configuration model construction process can lead to</span>
<span class="sd"> duplicate edges and loops. You can remove the self-loops and</span>
<span class="sd"> parallel edges (see below) which will likely result in a graph</span>
<span class="sd"> that doesn't have the exact degree sequence specified. This</span>
<span class="sd"> "finite-size effect" decreases as the size of the graph increases.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] Newman, M. E. J. and Strogatz, S. H. and Watts, D. J.</span>
<span class="sd"> Random graphs with arbitrary degree distributions and their applications</span>
<span class="sd"> Phys. Rev. E, 64, 026118 (2001)</span>
<span class="sd"> Examples</span>
<span class="sd"> --------</span>
<span class="sd"> >>> D=nx.DiGraph([(0,1),(1,2),(2,3)]) # directed path graph</span>
<span class="sd"> >>> din=list(D.in_degree().values())</span>
<span class="sd"> >>> dout=list(D.out_degree().values())</span>
<span class="sd"> >>> din.append(1)</span>
<span class="sd"> >>> dout[0]=2</span>
<span class="sd"> >>> D=nx.directed_configuration_model(din,dout)</span>
<span class="sd"> To remove parallel edges:</span>
<span class="sd"> >>> D=nx.DiGraph(D)</span>
<span class="sd"> To remove self loops:</span>
<span class="sd"> >>> D.remove_edges_from(D.selfloop_edges())</span>
<span class="sd"> """</span>
<span class="k">if</span> <span class="ow">not</span> <span class="nb">sum</span><span class="p">(</span><span class="n">in_degree_sequence</span><span class="p">)</span> <span class="o">==</span> <span class="nb">sum</span><span class="p">(</span><span class="n">out_degree_sequence</span><span class="p">):</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">'Invalid degree sequences. '</span>
<span class="s">'Sequences must have equal sums.'</span><span class="p">)</span>
<span class="k">if</span> <span class="n">create_using</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">create_using</span> <span class="o">=</span> <span class="n">nx</span><span class="o">.</span><span class="n">MultiDiGraph</span><span class="p">()</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">seed</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="n">seed</span><span class="p">)</span>
<span class="n">nin</span><span class="o">=</span><span class="nb">len</span><span class="p">(</span><span class="n">in_degree_sequence</span><span class="p">)</span>
<span class="n">nout</span><span class="o">=</span><span class="nb">len</span><span class="p">(</span><span class="n">out_degree_sequence</span><span class="p">)</span>
<span class="c"># pad in- or out-degree sequence with zeros to match lengths</span>
<span class="k">if</span> <span class="n">nin</span><span class="o">></span><span class="n">nout</span><span class="p">:</span>
<span class="n">out_degree_sequence</span><span class="o">.</span><span class="n">extend</span><span class="p">((</span><span class="n">nin</span><span class="o">-</span><span class="n">nout</span><span class="p">)</span><span class="o">*</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
<span class="k">else</span><span class="p">:</span>
<span class="n">in_degree_sequence</span><span class="o">.</span><span class="n">extend</span><span class="p">((</span><span class="n">nout</span><span class="o">-</span><span class="n">nin</span><span class="p">)</span><span class="o">*</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
<span class="c"># start with empty N-node graph</span>
<span class="n">N</span><span class="o">=</span><span class="nb">len</span><span class="p">(</span><span class="n">in_degree_sequence</span><span class="p">)</span>
<span class="c"># allow multiedges and selfloops</span>
<span class="n">G</span><span class="o">=</span><span class="n">nx</span><span class="o">.</span><span class="n">empty_graph</span><span class="p">(</span><span class="n">N</span><span class="p">,</span><span class="n">create_using</span><span class="p">)</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="nb">max</span><span class="p">(</span><span class="n">in_degree_sequence</span><span class="p">)</span><span class="o">==</span><span class="mi">0</span><span class="p">:</span> <span class="c"># done if no edges</span>
<span class="k">return</span> <span class="n">G</span>
<span class="c"># build stublists of available degree-repeated stubs</span>
<span class="c"># e.g. for degree_sequence=[3,2,1,1,1]</span>
<span class="c"># initially, stublist=[1,1,1,2,2,3,4,5]</span>
<span class="c"># i.e., node 1 has degree=3 and is repeated 3 times, etc.</span>
<span class="n">in_stublist</span><span class="o">=</span><span class="p">[]</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="n">G</span><span class="p">:</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">in_degree_sequence</span><span class="p">[</span><span class="n">n</span><span class="p">]):</span>
<span class="n">in_stublist</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
<span class="n">out_stublist</span><span class="o">=</span><span class="p">[]</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="n">G</span><span class="p">:</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">out_degree_sequence</span><span class="p">[</span><span class="n">n</span><span class="p">]):</span>
<span class="n">out_stublist</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
<span class="c"># shuffle stublists and assign pairs by removing 2 elements at a time</span>
<span class="n">random</span><span class="o">.</span><span class="n">shuffle</span><span class="p">(</span><span class="n">in_stublist</span><span class="p">)</span>
<span class="n">random</span><span class="o">.</span><span class="n">shuffle</span><span class="p">(</span><span class="n">out_stublist</span><span class="p">)</span>
<span class="k">while</span> <span class="n">in_stublist</span> <span class="ow">and</span> <span class="n">out_stublist</span><span class="p">:</span>
<span class="n">source</span> <span class="o">=</span> <span class="n">out_stublist</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<span class="n">target</span> <span class="o">=</span> <span class="n">in_stublist</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">source</span><span class="p">,</span><span class="n">target</span><span class="p">)</span>
<span class="n">G</span><span class="o">.</span><span class="n">name</span><span class="o">=</span><span class="s">"directed configuration_model </span><span class="si">%d</span><span class="s"> nodes </span><span class="si">%d</span><span class="s"> edges"</span><span class="o">%</span><span class="p">(</span><span class="n">G</span><span class="o">.</span><span class="n">order</span><span class="p">(),</span><span class="n">G</span><span class="o">.</span><span class="n">size</span><span class="p">())</span>
<span class="k">return</span> <span class="n">G</span>
</div>
<div class="viewcode-block" id="expected_degree_graph"><a class="viewcode-back" href="../../../reference/generated/networkx.generators.degree_seq.expected_degree_graph.html#networkx.generators.degree_seq.expected_degree_graph">[docs]</a><span class="k">def</span> <span class="nf">expected_degree_graph</span><span class="p">(</span><span class="n">w</span><span class="p">,</span> <span class="n">seed</span><span class="o">=</span><span class="bp">None</span><span class="p">,</span> <span class="n">selfloops</span><span class="o">=</span><span class="bp">True</span><span class="p">):</span>
<span class="sd">r"""Return a random graph with given expected degrees.</span>
<span class="sd"> Given a sequence of expected degrees `W=(w_0,w_1,\ldots,w_{n-1}`)</span>
<span class="sd"> of length `n` this algorithm assigns an edge between node `u` and</span>
<span class="sd"> node `v` with probability</span>
<span class="sd"> .. math::</span>
<span class="sd"> p_{uv} = \frac{w_u w_v}{\sum_k w_k} .</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> w : list</span>
<span class="sd"> The list of expected degrees.</span>
<span class="sd"> selfloops: bool (default=True)</span>
<span class="sd"> Set to False to remove the possibility of self-loop edges.</span>
<span class="sd"> seed : hashable object, optional</span>
<span class="sd"> The seed for the random number generator.</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> Graph</span>
<span class="sd"> Examples</span>
<span class="sd"> --------</span>
<span class="sd"> >>> z=[10 for i in range(100)]</span>
<span class="sd"> >>> G=nx.expected_degree_graph(z)</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> The nodes have integer labels corresponding to index of expected degrees</span>
<span class="sd"> input sequence.</span>
<span class="sd"> The complexity of this algorithm is `\mathcal{O}(n+m)` where `n` is the</span>
<span class="sd"> number of nodes and `m` is the expected number of edges.</span>
<span class="sd"> The model in [1]_ includes the possibility of self-loop edges.</span>
<span class="sd"> Set selfloops=False to produce a graph without self loops.</span>
<span class="sd"> For finite graphs this model doesn't produce exactly the given</span>
<span class="sd"> expected degree sequence. Instead the expected degrees are as</span>
<span class="sd"> follows.</span>
<span class="sd"> For the case without self loops (selfloops=False),</span>
<span class="sd"> .. math::</span>
<span class="sd"> E[deg(u)] = \sum_{v \ne u} p_{uv}</span>
<span class="sd"> = w_u \left( 1 - \frac{w_u}{\sum_k w_k} \right) .</span>
<span class="sd"> NetworkX uses the standard convention that a self-loop edge counts 2</span>
<span class="sd"> in the degree of a node, so with self loops (selfloops=True),</span>
<span class="sd"> .. math::</span>
<span class="sd"> E[deg(u)] = \sum_{v \ne u} p_{uv} + 2 p_{uu}</span>
<span class="sd"> = w_u \left( 1 + \frac{w_u}{\sum_k w_k} \right) .</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] Fan Chung and L. Lu, Connected components in random graphs with</span>
<span class="sd"> given expected degree sequences, Ann. Combinatorics, 6,</span>
<span class="sd"> pp. 125-145, 2002.</span>
<span class="sd"> .. [2] Joel Miller and Aric Hagberg,</span>
<span class="sd"> Efficient generation of networks with given expected degrees,</span>
<span class="sd"> in Algorithms and Models for the Web-Graph (WAW 2011),</span>
<span class="sd"> Alan Frieze, Paul Horn, and Paweł Prałat (Eds), LNCS 6732,</span>
<span class="sd"> pp. 115-126, 2011.</span>
<span class="sd"> """</span>
<span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">w</span><span class="p">)</span>
<span class="n">G</span><span class="o">=</span><span class="n">nx</span><span class="o">.</span><span class="n">empty_graph</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="mi">0</span> <span class="ow">or</span> <span class="nb">max</span><span class="p">(</span><span class="n">w</span><span class="p">)</span><span class="o">==</span><span class="mi">0</span><span class="p">:</span> <span class="c"># done if no edges</span>
<span class="k">return</span> <span class="n">G</span>
<span class="k">if</span> <span class="n">seed</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="n">seed</span><span class="p">)</span>
<span class="n">rho</span> <span class="o">=</span> <span class="mi">1</span><span class="o">/</span><span class="nb">float</span><span class="p">(</span><span class="nb">sum</span><span class="p">(</span><span class="n">w</span><span class="p">))</span>
<span class="c"># sort weights, largest first</span>
<span class="c"># preserve order of weights for integer node label mapping</span>
<span class="n">order</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">enumerate</span><span class="p">(</span><span class="n">w</span><span class="p">),</span><span class="n">key</span><span class="o">=</span><span class="n">itemgetter</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span><span class="n">reverse</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span>
<span class="n">mapping</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">((</span><span class="n">c</span><span class="p">,</span><span class="n">uv</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="k">for</span> <span class="n">c</span><span class="p">,</span><span class="n">uv</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">order</span><span class="p">))</span>
<span class="n">seq</span> <span class="o">=</span> <span class="p">[</span><span class="n">v</span> <span class="k">for</span> <span class="n">u</span><span class="p">,</span><span class="n">v</span> <span class="ow">in</span> <span class="n">order</span><span class="p">]</span>
<span class="n">last</span><span class="o">=</span><span class="n">n</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">selfloops</span><span class="p">:</span>
<span class="n">last</span><span class="o">-=</span><span class="mi">1</span>
<span class="k">for</span> <span class="n">u</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">last</span><span class="p">):</span>
<span class="n">v</span> <span class="o">=</span> <span class="n">u</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">selfloops</span><span class="p">:</span>
<span class="n">v</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="n">factor</span> <span class="o">=</span> <span class="n">seq</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">*</span> <span class="n">rho</span>
<span class="n">p</span> <span class="o">=</span> <span class="n">seq</span><span class="p">[</span><span class="n">v</span><span class="p">]</span><span class="o">*</span><span class="n">factor</span>
<span class="k">if</span> <span class="n">p</span><span class="o">></span><span class="mi">1</span><span class="p">:</span>
<span class="n">p</span> <span class="o">=</span> <span class="mi">1</span>
<span class="k">while</span> <span class="n">v</span><span class="o"><</span><span class="n">n</span> <span class="ow">and</span> <span class="n">p</span><span class="o">></span><span class="mi">0</span><span class="p">:</span>
<span class="k">if</span> <span class="n">p</span> <span class="o">!=</span> <span class="mi">1</span><span class="p">:</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">random</span><span class="o">.</span><span class="n">random</span><span class="p">()</span>
<span class="n">v</span> <span class="o">+=</span> <span class="nb">int</span><span class="p">(</span><span class="n">math</span><span class="o">.</span><span class="n">floor</span><span class="p">(</span><span class="n">math</span><span class="o">.</span><span class="n">log</span><span class="p">(</span><span class="n">r</span><span class="p">)</span><span class="o">/</span><span class="n">math</span><span class="o">.</span><span class="n">log</span><span class="p">(</span><span class="mi">1</span><span class="o">-</span><span class="n">p</span><span class="p">)))</span>
<span class="k">if</span> <span class="n">v</span> <span class="o"><</span> <span class="n">n</span><span class="p">:</span>
<span class="n">q</span> <span class="o">=</span> <span class="n">seq</span><span class="p">[</span><span class="n">v</span><span class="p">]</span><span class="o">*</span><span class="n">factor</span>
<span class="k">if</span> <span class="n">q</span><span class="o">></span><span class="mi">1</span><span class="p">:</span>
<span class="n">q</span> <span class="o">=</span> <span class="mi">1</span>
<span class="k">if</span> <span class="n">random</span><span class="o">.</span><span class="n">random</span><span class="p">()</span> <span class="o"><</span> <span class="n">q</span><span class="o">/</span><span class="n">p</span><span class="p">:</span>
<span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">mapping</span><span class="p">[</span><span class="n">u</span><span class="p">],</span><span class="n">mapping</span><span class="p">[</span><span class="n">v</span><span class="p">])</span>
<span class="n">v</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="n">p</span> <span class="o">=</span> <span class="n">q</span>
<span class="k">return</span> <span class="n">G</span>
</div>
<div class="viewcode-block" id="havel_hakimi_graph"><a class="viewcode-back" href="../../../reference/generated/networkx.generators.degree_seq.havel_hakimi_graph.html#networkx.generators.degree_seq.havel_hakimi_graph">[docs]</a><span class="k">def</span> <span class="nf">havel_hakimi_graph</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">,</span><span class="n">create_using</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="sd">"""Return a simple graph with given degree sequence constructed</span>
<span class="sd"> using the Havel-Hakimi algorithm.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> deg_sequence: list of integers</span>
<span class="sd"> Each integer corresponds to the degree of a node (need not be sorted).</span>
<span class="sd"> create_using : graph, optional (default Graph)</span>
<span class="sd"> Return graph of this type. The instance will be cleared.</span>
<span class="sd"> Directed graphs are not allowed.</span>
<span class="sd"> Raises</span>
<span class="sd"> ------</span>
<span class="sd"> NetworkXException</span>
<span class="sd"> For a non-graphical degree sequence (i.e. one</span>
<span class="sd"> not realizable by some simple graph).</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> The Havel-Hakimi algorithm constructs a simple graph by</span>
<span class="sd"> successively connecting the node of highest degree to other nodes</span>
<span class="sd"> of highest degree, resorting remaining nodes by degree, and</span>
<span class="sd"> repeating the process. The resulting graph has a high</span>
<span class="sd"> degree-associativity. Nodes are labeled 1,.., len(deg_sequence),</span>
<span class="sd"> corresponding to their position in deg_sequence.</span>
<span class="sd"> The basic algorithm is from Hakimi [1]_ and was generalized by</span>
<span class="sd"> Kleitman and Wang [2]_.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] Hakimi S., On Realizability of a Set of Integers as </span>
<span class="sd"> Degrees of the Vertices of a Linear Graph. I,</span>
<span class="sd"> Journal of SIAM, 10(3), pp. 496-506 (1962)</span>
<span class="sd"> .. [2] Kleitman D.J. and Wang D.L.</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="k">if</span> <span class="ow">not</span> <span class="n">nx</span><span class="o">.</span><span class="n">is_valid_degree_sequence</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">NetworkXError</span><span class="p">(</span><span class="s">'Invalid degree sequence'</span><span class="p">)</span>
<span class="k">if</span> <span class="n">create_using</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="k">if</span> <span class="n">create_using</span><span class="o">.</span><span class="n">is_directed</span><span class="p">():</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">"Directed graphs are not supported"</span><span class="p">)</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">G</span><span class="o">=</span><span class="n">nx</span><span class="o">.</span><span class="n">empty_graph</span><span class="p">(</span><span class="n">p</span><span class="p">,</span><span class="n">create_using</span><span class="p">)</span>
<span class="n">num_degs</span> <span class="o">=</span> <span class="p">[]</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">p</span><span class="p">):</span>
<span class="n">num_degs</span><span class="o">.</span><span class="n">append</span><span class="p">([])</span>
<span class="n">dmax</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="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"># Process only the non-zero integers</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="n">num_degs</span><span class="p">[</span><span class="n">d</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
<span class="n">dmax</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="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="c"># Return graph if no edges</span>
<span class="k">if</span> <span class="n">n</span><span class="o">==</span><span class="mi">0</span><span class="p">:</span>
<span class="k">return</span> <span class="n">G</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">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="nb">len</span><span class="p">(</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">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">'Non-graphical integer sequence'</span><span class="p">)</span>
<span class="c"># Remove largest stub in list</span>
<span class="n">source</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="n">pop</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="nb">len</span><span class="p">(</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">target</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="n">pop</span><span class="p">()</span>
<span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">source</span><span class="p">,</span> <span class="n">target</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="p">(</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="n">target</span><span class="p">)</span>
<span class="n">mslen</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="c"># Add back to the list any nonzero 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="p">(</span><span class="n">stubval</span><span class="p">,</span> <span class="n">stubtarget</span><span class="p">)</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">stubval</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">stubtarget</span><span class="p">)</span>
<span class="n">n</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="n">G</span><span class="o">.</span><span class="n">name</span><span class="o">=</span><span class="s">"havel_hakimi_graph </span><span class="si">%d</span><span class="s"> nodes </span><span class="si">%d</span><span class="s"> edges"</span><span class="o">%</span><span class="p">(</span><span class="n">G</span><span class="o">.</span><span class="n">order</span><span class="p">(),</span><span class="n">G</span><span class="o">.</span><span class="n">size</span><span class="p">())</span>
<span class="k">return</span> <span class="n">G</span>
</div>
<div class="viewcode-block" id="directed_havel_hakimi_graph"><a class="viewcode-back" href="../../../reference/generated/networkx.generators.degree_seq.directed_havel_hakimi_graph.html#networkx.generators.degree_seq.directed_havel_hakimi_graph">[docs]</a><span class="k">def</span> <span class="nf">directed_havel_hakimi_graph</span><span class="p">(</span><span class="n">in_deg_sequence</span><span class="p">,</span>
<span class="n">out_deg_sequence</span><span class="p">,</span>
<span class="n">create_using</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="sd">"""Return a directed graph with the given degree sequences.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> in_deg_sequence : list of integers </span>
<span class="sd"> Each list entry corresponds to the in-degree of a node.</span>
<span class="sd"> out_deg_sequence : list of integers </span>
<span class="sd"> Each list entry corresponds to the out-degree of a node.</span>
<span class="sd"> create_using : graph, optional (default DiGraph)</span>
<span class="sd"> Return graph of this type. The instance will be cleared.</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> G : DiGraph</span>
<span class="sd"> A graph with the specified degree sequences.</span>
<span class="sd"> Nodes are labeled starting at 0 with an index</span>
<span class="sd"> corresponding to the position in deg_sequence</span>
<span class="sd"> Raises</span>
<span class="sd"> ------</span>
<span class="sd"> NetworkXError</span>
<span class="sd"> If the degree sequences are not digraphical.</span>
<span class="sd"> See Also</span>
<span class="sd"> --------</span>
<span class="sd"> configuration_model</span>
<span class="sd"> </span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> Algorithm as described by Kleitman and Wang [1]_.</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="k">assert</span><span class="p">(</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">assert</span><span class="p">(</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">if</span> <span class="n">create_using</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">create_using</span> <span class="o">=</span> <span class="n">nx</span><span class="o">.</span><span class="n">DiGraph</span><span class="p">()</span>
<span class="c"># Process the sequences and form two heaps to store degree pairs with</span>
<span class="c"># either zero or nonzero 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">G</span> <span class="o">=</span> <span class="n">nx</span><span class="o">.</span><span class="n">empty_graph</span><span class="p">(</span><span class="n">maxn</span><span class="p">,</span><span class="n">create_using</span><span class="p">)</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="n">G</span>
<span class="n">maxin</span> <span class="o">=</span> <span class="mi">0</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">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span>
<span class="s">'Invalid degree sequences. Sequence values must be positive.'</span><span class="p">)</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="n">n</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="n">n</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">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span>
<span class="s">'Invalid degree sequences. Sequences must have equal sums.'</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">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="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 </span>
<span class="k">while</span> <span class="n">stubheap</span><span class="p">:</span>
<span class="c"># Remove first value in the sequence with a 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="n">target</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">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">'Non-digraphical integer sequence'</span><span class="p">)</span>
<span class="c"># Attach arcs from the nodes with the most 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="mi">0</span><span class="p">]):</span>
<span class="p">(</span><span class="n">stubout</span><span class="p">,</span> <span class="n">stubsource</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">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="n">stubsource</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">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">'Non-digraphical integer sequence'</span><span class="p">)</span>
<span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">stubsource</span><span class="p">,</span> <span class="n">target</span><span class="p">)</span>
<span class="c"># Check if source 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">stubsource</span><span class="p">)</span>
<span class="n">mslen</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="c"># Add the nodes back to the heaps 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="p">(</span><span class="n">stub</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">stub</span><span class="p">[</span><span class="mi">2</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="p">(</span><span class="n">freeout</span><span class="p">,</span> <span class="n">target</span><span class="p">))</span>
<span class="n">G</span><span class="o">.</span><span class="n">name</span><span class="o">=</span><span class="s">"directed_havel_hakimi_graph </span><span class="si">%d</span><span class="s"> nodes </span><span class="si">%d</span><span class="s"> edges"</span><span class="o">%</span><span class="p">(</span><span class="n">G</span><span class="o">.</span><span class="n">order</span><span class="p">(),</span><span class="n">G</span><span class="o">.</span><span class="n">size</span><span class="p">())</span>
<span class="k">return</span> <span class="n">G</span>
</div>
<div class="viewcode-block" id="degree_sequence_tree"><a class="viewcode-back" href="../../../reference/generated/networkx.generators.degree_seq.degree_sequence_tree.html#networkx.generators.degree_seq.degree_sequence_tree">[docs]</a><span class="k">def</span> <span class="nf">degree_sequence_tree</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">,</span><span class="n">create_using</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="sd">"""Make a tree for the given degree sequence.</span>
<span class="sd"> A tree has #nodes-#edges=1 so</span>
<span class="sd"> the degree sequence must have</span>
<span class="sd"> len(deg_sequence)-sum(deg_sequence)/2=1</span>
<span class="sd"> """</span>
<span class="k">if</span> <span class="ow">not</span> <span class="nb">len</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">)</span><span class="o">-</span><span class="nb">sum</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">)</span><span class="o">/</span><span class="mf">2.0</span> <span class="o">==</span> <span class="mf">1.0</span><span class="p">:</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">"Degree sequence invalid"</span><span class="p">)</span>
<span class="k">if</span> <span class="n">create_using</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span> <span class="ow">and</span> <span class="n">create_using</span><span class="o">.</span><span class="n">is_directed</span><span class="p">():</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">"Directed Graph not supported"</span><span class="p">)</span>
<span class="c"># single node tree</span>
<span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">deg_sequence</span><span class="p">)</span><span class="o">==</span><span class="mi">1</span><span class="p">:</span>
<span class="n">G</span><span class="o">=</span><span class="n">nx</span><span class="o">.</span><span class="n">empty_graph</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="n">create_using</span><span class="p">)</span>
<span class="k">return</span> <span class="n">G</span>
<span class="c"># all degrees greater than 1</span>
<span class="n">deg</span><span class="o">=</span><span class="p">[</span><span class="n">s</span> <span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="n">deg_sequence</span> <span class="k">if</span> <span class="n">s</span><span class="o">></span><span class="mi">1</span><span class="p">]</span>
<span class="n">deg</span><span class="o">.</span><span class="n">sort</span><span class="p">(</span><span class="n">reverse</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span>
<span class="c"># make path graph as backbone</span>
<span class="n">n</span><span class="o">=</span><span class="nb">len</span><span class="p">(</span><span class="n">deg</span><span class="p">)</span><span class="o">+</span><span class="mi">2</span>
<span class="n">G</span><span class="o">=</span><span class="n">nx</span><span class="o">.</span><span class="n">path_graph</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">create_using</span><span class="p">)</span>
<span class="n">last</span><span class="o">=</span><span class="n">n</span>
<span class="c"># add the leaves</span>
<span class="k">for</span> <span class="n">source</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</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="p">):</span>
<span class="n">nedges</span><span class="o">=</span><span class="n">deg</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span><span class="o">-</span><span class="mi">2</span>
<span class="k">for</span> <span class="n">target</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">last</span><span class="p">,</span><span class="n">last</span><span class="o">+</span><span class="n">nedges</span><span class="p">):</span>
<span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="p">)</span>
<span class="n">last</span><span class="o">+=</span><span class="n">nedges</span>
<span class="c"># in case we added one too many</span>
<span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">G</span><span class="o">.</span><span class="n">degree</span><span class="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">G</span><span class="o">.</span><span class="n">remove_node</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="k">return</span> <span class="n">G</span>
</div>
<div class="viewcode-block" id="random_degree_sequence_graph"><a class="viewcode-back" href="../../../reference/generated/networkx.generators.degree_seq.random_degree_sequence_graph.html#networkx.generators.degree_seq.random_degree_sequence_graph">[docs]</a><span class="k">def</span> <span class="nf">random_degree_sequence_graph</span><span class="p">(</span><span class="n">sequence</span><span class="p">,</span> <span class="n">seed</span><span class="o">=</span><span class="bp">None</span><span class="p">,</span> <span class="n">tries</span><span class="o">=</span><span class="mi">10</span><span class="p">):</span>
<span class="sd">r"""Return a simple random graph with the given degree sequence.</span>
<span class="sd"> If the maximum degree `d_m` in the sequence is `O(m^{1/4})` then the</span>
<span class="sd"> algorithm produces almost uniform random graphs in `O(m d_m)` time</span>
<span class="sd"> where `m` is the number of edges.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> sequence : list of integers</span>
<span class="sd"> Sequence of degrees</span>
<span class="sd"> seed : hashable object, optional</span>
<span class="sd"> Seed for random number generator</span>
<span class="sd"> tries : int, optional</span>
<span class="sd"> Maximum number of tries to create a graph</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> G : Graph</span>
<span class="sd"> A graph with the specified degree sequence.</span>
<span class="sd"> Nodes are labeled starting at 0 with an index</span>
<span class="sd"> corresponding to the position in the sequence.</span>
<span class="sd"> Raises</span>
<span class="sd"> ------</span>
<span class="sd"> NetworkXUnfeasible</span>
<span class="sd"> If the degree sequence is not graphical.</span>
<span class="sd"> NetworkXError</span>
<span class="sd"> If a graph is not produced in specified number of tries</span>
<span class="sd"> See Also</span>
<span class="sd"> --------</span>
<span class="sd"> is_valid_degree_sequence, configuration_model</span>
<span class="sd"> Notes</span>
<span class="sd"> -----</span>
<span class="sd"> The generator algorithm [1]_ is not guaranteed to produce a graph.</span>
<span class="sd"> References</span>
<span class="sd"> ----------</span>
<span class="sd"> .. [1] Moshen Bayati, Jeong Han Kim, and Amin Saberi,</span>
<span class="sd"> A sequential algorithm for generating random graphs.</span>
<span class="sd"> Algorithmica, Volume 58, Number 4, 860-910,</span>
<span class="sd"> DOI: 10.1007/s00453-009-9340-1</span>
<span class="sd"> Examples</span>
<span class="sd"> --------</span>
<span class="sd"> >>> sequence = [1, 2, 2, 3]</span>
<span class="sd"> >>> G = nx.random_degree_sequence_graph(sequence)</span>
<span class="sd"> >>> sorted(G.degree().values())</span>
<span class="sd"> [1, 2, 2, 3]</span>
<span class="sd"> """</span>
<span class="n">DSRG</span> <span class="o">=</span> <span class="n">DegreeSequenceRandomGraph</span><span class="p">(</span><span class="n">sequence</span><span class="p">,</span> <span class="n">seed</span><span class="o">=</span><span class="n">seed</span><span class="p">)</span>
<span class="k">for</span> <span class="n">try_n</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">tries</span><span class="p">):</span>
<span class="k">try</span><span class="p">:</span>
<span class="k">return</span> <span class="n">DSRG</span><span class="o">.</span><span class="n">generate</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">pass</span>
<span class="k">raise</span> <span class="n">nx</span><span class="o">.</span><span class="n">NetworkXError</span><span class="p">(</span><span class="s">'failed to generate graph in </span><span class="si">%d</span><span class="s"> tries'</span><span class="o">%</span><span class="n">tries</span><span class="p">)</span>
</div>
<span class="k">class</span> <span class="nc">DegreeSequenceRandomGraph</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
<span class="c"># class to generate random graphs with a given degree sequence</span>
<span class="c"># use random_degree_sequence_graph()</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">degree</span><span class="p">,</span> <span class="n">seed</span><span class="o">=</span><span class="bp">None</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">is_valid_degree_sequence</span><span class="p">(</span><span class="n">degree</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="p">(</span><span class="s">'degree sequence is not graphical'</span><span class="p">)</span>
<span class="k">if</span> <span class="n">seed</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="n">seed</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">degree</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">degree</span><span class="p">)</span>
<span class="c"># node labels are integers 0,...,n-1</span>
<span class="bp">self</span><span class="o">.</span><span class="n">m</span> <span class="o">=</span> <span class="nb">sum</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">degree</span><span class="p">)</span><span class="o">/</span><span class="mf">2.0</span> <span class="c"># number of edges</span>
<span class="k">try</span><span class="p">:</span>
<span class="bp">self</span><span class="o">.</span><span class="n">dmax</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">degree</span><span class="p">)</span> <span class="c"># maximum degree</span>
<span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
<span class="bp">self</span><span class="o">.</span><span class="n">dmax</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">def</span> <span class="nf">generate</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="c"># remaining_degree is mapping from int->remaining degree</span>
<span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span><span class="nb">enumerate</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">degree</span><span class="p">))</span>
<span class="c"># add all nodes to make sure we get isolated nodes</span>
<span class="bp">self</span><span class="o">.</span><span class="n">graph</span> <span class="o">=</span> <span class="n">nx</span><span class="o">.</span><span class="n">Graph</span><span class="p">()</span>
<span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">add_nodes_from</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">)</span>
<span class="c"># remove zero degree nodes</span>
<span class="k">for</span> <span class="n">n</span><span class="p">,</span><span class="n">d</span> <span class="ow">in</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="o">.</span><span class="n">items</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">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">n</span><span class="p">]</span>
<span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">)</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="c"># build graph in three phases according to how many unmatched edges</span>
<span class="bp">self</span><span class="o">.</span><span class="n">phase1</span><span class="p">()</span>
<span class="bp">self</span><span class="o">.</span><span class="n">phase2</span><span class="p">()</span>
<span class="bp">self</span><span class="o">.</span><span class="n">phase3</span><span class="p">()</span>
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">graph</span>
<span class="k">def</span> <span class="nf">update_remaining</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">aux_graph</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="c"># decrement remaining nodes, modify auxilliary graph if in phase3</span>
<span class="k">if</span> <span class="n">aux_graph</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="c"># remove edges from auxilliary graph</span>
<span class="n">aux_graph</span><span class="o">.</span><span class="n">remove_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
<span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">u</span><span class="p">]</span>
<span class="k">if</span> <span class="n">aux_graph</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">aux_graph</span><span class="o">.</span><span class="n">remove_node</span><span class="p">(</span><span class="n">u</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span>
<span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">-=</span> <span class="mi">1</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
<span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">v</span><span class="p">]</span>
<span class="k">if</span> <span class="n">aux_graph</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">aux_graph</span><span class="o">.</span><span class="n">remove_node</span><span class="p">(</span><span class="n">v</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span>
<span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">-=</span> <span class="mi">1</span>
<span class="k">def</span> <span class="nf">p</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span>
<span class="c"># degree probability</span>
<span class="k">return</span> <span class="mi">1</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">degree</span><span class="p">[</span><span class="n">u</span><span class="p">]</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">degree</span><span class="p">[</span><span class="n">v</span><span class="p">]</span><span class="o">/</span><span class="p">(</span><span class="mf">4.0</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">m</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">q</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span>
<span class="c"># remaining degree probability</span>
<span class="n">norm</span> <span class="o">=</span> <span class="nb">float</span><span class="p">(</span><span class="nb">max</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="o">.</span><span class="n">values</span><span class="p">()))</span><span class="o">**</span><span class="mi">2</span>
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">u</span><span class="p">]</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">[</span><span class="n">v</span><span class="p">]</span><span class="o">/</span><span class="n">norm</span>
<span class="k">def</span> <span class="nf">suitable_edge</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="c"># Check if there is a suitable edge that is not in the graph</span>
<span class="c"># True if an (arbitrary) remaining node has at least one possible </span>
<span class="c"># connection to another remaining node</span>
<span class="n">nodes</span> <span class="o">=</span> <span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">)</span>
<span class="n">u</span> <span class="o">=</span> <span class="nb">next</span><span class="p">(</span><span class="n">nodes</span><span class="p">)</span> <span class="c"># one arbitrary node</span>
<span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">nodes</span><span class="p">:</span> <span class="c"># loop over all other remaining nodes</span>
<span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">True</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="k">def</span> <span class="nf">phase1</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="c"># choose node pairs from (degree) weighted distribution</span>
<span class="k">while</span> <span class="nb">sum</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="o">.</span><span class="n">values</span><span class="p">())</span> <span class="o">>=</span> <span class="mi">2</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">dmax</span><span class="o">**</span><span class="mi">2</span><span class="p">:</span>
<span class="n">u</span><span class="p">,</span><span class="n">v</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="n">random_weighted_sample</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">,</span> <span class="mi">2</span><span class="p">))</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span>
<span class="k">continue</span>
<span class="k">if</span> <span class="n">random</span><span class="o">.</span><span class="n">random</span><span class="p">()</span> <span class="o"><</span> <span class="bp">self</span><span class="o">.</span><span class="n">p</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span> <span class="c"># accept edge</span>
<span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">update_remaining</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">phase2</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="c"># choose remaining nodes uniformly at random and use rejection sampling</span>
<span class="k">while</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">2</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">dmax</span><span class="p">:</span>
<span class="n">norm</span> <span class="o">=</span> <span class="nb">float</span><span class="p">(</span><span class="nb">max</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="o">.</span><span class="n">values</span><span class="p">()))</span><span class="o">**</span><span class="mi">2</span>
<span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
<span class="n">u</span><span class="p">,</span><span class="n">v</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="n">random</span><span class="o">.</span><span class="n">sample</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="o">.</span><span class="n">keys</span><span class="p">(),</span> <span class="mi">2</span><span class="p">))</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span>
<span class="k">continue</span>
<span class="k">if</span> <span class="n">random</span><span class="o">.</span><span class="n">random</span><span class="p">()</span> <span class="o"><</span> <span class="bp">self</span><span class="o">.</span><span class="n">q</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span>
<span class="k">break</span>
<span class="k">if</span> <span class="n">random</span><span class="o">.</span><span class="n">random</span><span class="p">()</span> <span class="o"><</span> <span class="bp">self</span><span class="o">.</span><span class="n">p</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span> <span class="c"># accept edge</span>
<span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">update_remaining</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">phase3</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="c"># build potential remaining edges and choose with rejection sampling</span>
<span class="n">potential_edges</span> <span class="o">=</span> <span class="n">combinations</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
<span class="c"># build auxilliary graph of potential edges not already in graph</span>
<span class="n">H</span> <span class="o">=</span> <span class="n">nx</span><span class="o">.</span><span class="n">Graph</span><span class="p">([(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span> <span class="k">for</span> <span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span> <span class="ow">in</span> <span class="n">potential_edges</span>
<span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">has_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)])</span>
<span class="k">while</span> <span class="bp">self</span><span class="o">.</span><span class="n">remaining_degree</span><span class="p">:</span>
<span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">suitable_edge</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="p">(</span><span class="s">'no suitable edges left'</span><span class="p">)</span>
<span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
<span class="n">u</span><span class="p">,</span><span class="n">v</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="n">random</span><span class="o">.</span><span class="n">choice</span><span class="p">(</span><span class="n">H</span><span class="o">.</span><span class="n">edges</span><span class="p">()))</span>
<span class="k">if</span> <span class="n">random</span><span class="o">.</span><span class="n">random</span><span class="p">()</span> <span class="o"><</span> <span class="bp">self</span><span class="o">.</span><span class="n">q</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span>
<span class="k">break</span>
<span class="k">if</span> <span class="n">random</span><span class="o">.</span><span class="n">random</span><span class="p">()</span> <span class="o"><</span> <span class="bp">self</span><span class="o">.</span><span class="n">p</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">):</span> <span class="c"># accept edge</span>
<span class="bp">self</span><span class="o">.</span><span class="n">graph</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span><span class="n">update_remaining</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">,</span> <span class="n">aux_graph</span><span class="o">=</span><span class="n">H</span><span class="p">)</span>
</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>
