Abdelrahman Said
5473 lines
209 KiB
HTML
5473 lines
209 KiB
HTML
<html>
|
||
<head>
|
||
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
|
||
<title>Chapter 11. Deterministic graph generators</title>
|
||
<meta name="generator" content="DocBook XSL Stylesheets Vsnapshot">
|
||
<link rel="home" href="index.html" title="igraph Reference Manual">
|
||
<link rel="up" href="index.html" title="igraph Reference Manual">
|
||
<link rel="prev" href="igraph-Attributes.html" title="Chapter 10. Graph, vertex and edge attributes">
|
||
<link rel="next" href="igraph-Games.html" title='Chapter 12. Stochastic graph generators ("games")'>
|
||
<script type="text/javascript" src="toggle.js"></script><link rel="stylesheet" href="style.css" type="text/css">
|
||
<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css" type="text/css">
|
||
<link rel="chapter" href="igraph-Introduction.html" title="Chapter 1. Introduction">
|
||
<link rel="chapter" href="igraph-Installation.html" title="Chapter 2. Installation">
|
||
<link rel="chapter" href="igraph-Tutorial.html" title="Chapter 3. Tutorial">
|
||
<link rel="chapter" href="igraph-Basic.html" title="Chapter 4. Basic data types and interface">
|
||
<link rel="chapter" href="igraph-Error.html" title="Chapter 5. Error handling">
|
||
<link rel="chapter" href="igraph-Memory.html" title="Chapter 6. Memory (de)allocation">
|
||
<link rel="chapter" href="igraph-Data-structures.html" title="Chapter 7. Data structure library: vector, matrix, other data types">
|
||
<link rel="chapter" href="igraph-Random.html" title="Chapter 8. Random numbers">
|
||
<link rel="chapter" href="igraph-Iterators.html" title="Chapter 9. Vertex and edge selectors and sequences, iterators">
|
||
<link rel="chapter" href="igraph-Attributes.html" title="Chapter 10. Graph, vertex and edge attributes">
|
||
<link rel="chapter" href="igraph-Generators.html" title="Chapter 11. Deterministic graph generators">
|
||
<link rel="chapter" href="igraph-Games.html" title='Chapter 12. Stochastic graph generators ("games")'>
|
||
<link rel="chapter" href="igraph-Bipartite.html" title="Chapter 13. Bipartite, i.e. two-mode graphs">
|
||
<link rel="chapter" href="igraph-Spatial.html" title="Chapter 14. Spatial graphs">
|
||
<link rel="chapter" href="igraph-Operators.html" title="Chapter 15. Graph operators">
|
||
<link rel="chapter" href="igraph-Visitors.html" title="Chapter 16. Graph visitors">
|
||
<link rel="chapter" href="igraph-Structural.html" title="Chapter 17. Structural properties of graphs">
|
||
<link rel="chapter" href="igraph-Cycles.html" title="Chapter 18. Graph cycles">
|
||
<link rel="chapter" href="igraph-Cliques.html" title="Chapter 19. Cliques and independent vertex sets">
|
||
<link rel="chapter" href="igraph-Motifs.html" title="Chapter 20. Graph motifs, dyad census and triad census">
|
||
<link rel="chapter" href="igraph-Isomorphism.html" title="Chapter 21. Graph isomorphism">
|
||
<link rel="chapter" href="igraph-Coloring.html" title="Chapter 22. Graph coloring">
|
||
<link rel="chapter" href="igraph-Flows.html" title="Chapter 23. Maximum flows, minimum cuts and related measures">
|
||
<link rel="chapter" href="igraph-Separators.html" title="Chapter 24. Vertex separators">
|
||
<link rel="chapter" href="igraph-Community.html" title="Chapter 25. Detecting community structure">
|
||
<link rel="chapter" href="igraph-Graphlets.html" title="Chapter 26. Graphlets">
|
||
<link rel="chapter" href="igraph-HRG.html" title="Chapter 27. Hierarchical random graphs">
|
||
<link rel="chapter" href="igraph-Embedding.html" title="Chapter 28. Embedding of graphs">
|
||
<link rel="chapter" href="igraph-Layout.html" title="Chapter 29. Generating layouts for graph drawing">
|
||
<link rel="chapter" href="igraph-Processes.html" title="Chapter 30. Processes on graphs">
|
||
<link rel="chapter" href="igraph-Foreign.html" title="Chapter 31. Reading and writing graphs from and to files">
|
||
<link rel="chapter" href="igraph-Linalg.html" title="Chapter 32. Using BLAS, LAPACK and ARPACK for igraph matrices and graphs">
|
||
<link rel="chapter" href="igraph-Nongraph.html" title="Chapter 33. Non-graph related functions">
|
||
<link rel="chapter" href="igraph-Advanced.html" title="Chapter 34. Advanced igraph programming">
|
||
<link rel="chapter" href="igraph-Glossary.html" title="Chapter 35. Glossary">
|
||
<link rel="chapter" href="igraph-Licenses.html" title="Chapter 36. Licenses for igraph and this manual">
|
||
<link rel="index" href="ix01.html" title="Index">
|
||
</head>
|
||
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
|
||
<div class="navigation-header mb-4" width="100%" summary="Navigation header"><div class="btn-group">
|
||
<a accesskey="p" class="btn btn-light" href="igraph-Attributes.html"><i class="fa fa-chevron-left"></i>
|
||
Previous
|
||
</a><a accesskey="h" class="btn btn-light" href="index.html"><i class="fa fa-home"></i>
|
||
Home
|
||
</a><a accesskey="n" class="btn btn-light" href="igraph-Games.html"><i class="fa fa-chevron-right"></i>
|
||
Next
|
||
</a>
|
||
</div></div>
|
||
<div class="chapter">
|
||
<div class="titlepage"><div><div><h1 class="title">
|
||
<a name="igraph-Generators"></a>Chapter 11. Deterministic graph generators</h1></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#about-generators">1. About generators</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#id-1.12.3">2. Basic graph creation</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#adjacency-generators">3. Graphs from adjacency matrices and adjacency lists</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#regular-structre-generators">4. Regular structures</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#tree-generators">5. Tree generators</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#degree-graph-generators">6. Graphs with given degrees</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#complete-graph-generators">7. Complete graphs</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#pre-defined-generators">8. Pre-defined graphs</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#other-generators">9. Other well-known graphs from graph theory</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="about-generators"></a>1. About generators</h2></div></div></div>
|
||
<p>
|
||
Most functions that create graphs in a deterministic manner are documented here. See also
|
||
<a class="link" href="igraph-Games.html" title='Chapter 12. Stochastic graph generators ("games")'>stochastic generators</a>,
|
||
<a class="link" href="igraph-Spatial.html#spatial-generators" title="2. Spatial graph generators">spatial graph generators</a>,
|
||
<a class="link" href="igraph-Bipartite.html#create-two-mode-networks" title="2. Create two-mode networks">bipartite graph generators</a>,
|
||
and <a class="link" href="igraph-Operators.html" title="Chapter 15. Graph operators">operators that transform graphs</a>.
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="id-1.12.3"></a>2. Basic graph creation</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_create">2.1. <code class="function">igraph_create</code> — Creates a graph with the specified edges.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_small">2.2. <code class="function">igraph_small</code> — Shorthand to create a small graph, giving the edges as arguments.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_create"></a>2.1. <code class="function">igraph_create</code> — Creates a graph with the specified edges.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.3.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_create(igraph_t *graph, const igraph_vector_int_t *edges,
|
||
igraph_int_t n, igraph_bool_t directed);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
An uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>edges</code></em>:</span></p></td>
|
||
<td><p>
|
||
The edges to add, the first two elements are the first
|
||
edge, etc.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of vertices in the graph, if smaller or equal
|
||
to the highest vertex ID in the <em class="parameter"><code>edges</code></em> vector it
|
||
will be increased automatically. So it is safe to give 0
|
||
here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, whether to create a directed graph or
|
||
not. If yes, then the first edge points from the first
|
||
vertex ID in <em class="parameter"><code>edges</code></em> to the second, etc.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_EINVAL</code>: invalid edges vector (odd number of vertices).
|
||
<code class="constant">IGRAPH_EINVVID</code>: invalid (negative) vertex ID.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|),
|
||
|V| is the number of vertices,
|
||
|E| the number of edges in the
|
||
graph.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.3.2.8.1"></a><p class="title"><b>Example 11.1. File <code class="code">examples/simple/igraph_create.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
|
||
igraph_t g;
|
||
igraph_vector_int_t v1, v2;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* simple use */</em></span>
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&v1, 8);
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[0] = 0;
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[1] = 1;
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[2] = 1;
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[3] = 2;
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[4] = 2;
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[5] = 3;
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[6] = 2;
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v1)[7] = 2;
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_create" title="2.1. igraph_create — Creates a graph with the specified edges.">igraph_create</a></strong></span>(&g, &v1, 0, 0);
|
||
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&g) != 4) {
|
||
<span class="strong"><strong>return</strong></span> 1;
|
||
}
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&v2, 0);
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_get_edgelist" title="26.11. igraph_get_edgelist — The list of edges in a graph.">igraph_get_edgelist</a></strong></span>(&g, &v2, 0);
|
||
<span class="strong"><strong>igraph_vector_int_sort</strong></span>(&v1);
|
||
<span class="strong"><strong>igraph_vector_int_sort</strong></span>(&v2);
|
||
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong>igraph_vector_int_all_e</strong></span>(&v1, &v2)) {
|
||
<span class="strong"><strong>return</strong></span> 2;
|
||
}
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g);
|
||
|
||
<span class="emphasis"><em>/* higher number of vertices */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_create" title="2.1. igraph_create — Creates a graph with the specified edges.">igraph_create</a></strong></span>(&g, &v1, 10, 0);
|
||
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&g) != 10) {
|
||
<span class="strong"><strong>return</strong></span> 1;
|
||
}
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_get_edgelist" title="26.11. igraph_get_edgelist — The list of edges in a graph.">igraph_get_edgelist</a></strong></span>(&g, &v2, 0);
|
||
<span class="strong"><strong>igraph_vector_int_sort</strong></span>(&v1);
|
||
<span class="strong"><strong>igraph_vector_int_sort</strong></span>(&v2);
|
||
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong>igraph_vector_int_all_e</strong></span>(&v1, &v2)) {
|
||
<span class="strong"><strong>return</strong></span> 3;
|
||
}
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&v1);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&v2);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_small"></a>2.2. <code class="function">igraph_small</code> — Shorthand to create a small graph, giving the edges as arguments.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.3.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_small(igraph_t *graph, igraph_int_t n, igraph_bool_t directed,
|
||
int first, ...);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function is handy when a relatively small graph needs to be created.
|
||
Instead of giving the edges as a vector, they are given simply as
|
||
arguments and a <code class="literal">-1</code> needs to be given after the last meaningful
|
||
edge argument.
|
||
|
||
</p>
|
||
<p>
|
||
This function is intended to be used with vertex IDs that are entered as
|
||
literal integers. If you use a variable instead of a literal, make sure
|
||
that it is of type <span class="type">int</span>, as this is the type that this function
|
||
assumes for all variadic arguments. Using a different integer type is
|
||
undefined behaviour and likely to cause platform-specific issues.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object. The result
|
||
will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of vertices in the graph; a non-negative integer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Boolean constant; gives whether the graph should be
|
||
directed. Supported values are:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_DIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
The graph to be created will be <span class="emphasis"><em>directed.</em></span>
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
The graph to be created will be <span class="emphasis"><em>undirected.</em></span>
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>...</code></em>:</span></p></td>
|
||
<td><p>
|
||
The additional arguments giving the edges of the graph,
|
||
and <span class="emphasis"><em>must</em></span> be of type <span class="type">int</span>. Don't forget to supply an
|
||
additional <code class="literal">-1</code> after the last (meaningful) argument. The
|
||
<em class="parameter"><code>first</code></em> parameter is present for technical reasons and represents
|
||
the first variadic argument.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the number of vertices plus the number
|
||
of edges in the graph to create.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.3.3.9.1"></a><p class="title"><b>Example 11.2. File <code class="code">examples/simple/igraph_small.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
|
||
igraph_t g;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_small" title="2.2. igraph_small — Shorthand to create a small graph, giving the edges as arguments.">igraph_small</a></strong></span>(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, 6, 1, -1);
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_write_graph_edgelist" title="1.2. igraph_write_graph_edgelist — Writes the edge list of a graph to a file.">igraph_write_graph_edgelist</a></strong></span>(&g, stdout);
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="adjacency-generators"></a>3. Graphs from adjacency matrices and adjacency lists</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_adjacency">3.1. <code class="function">igraph_adjacency</code> — Creates a graph from an adjacency matrix.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_weighted_adjacency">3.2. <code class="function">igraph_weighted_adjacency</code> — Creates a graph from a weighted adjacency matrix.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_sparse_adjacency">3.3. <code class="function">igraph_sparse_adjacency</code> — Creates a graph from a sparse adjacency matrix.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_sparse_weighted_adjacency">3.4. <code class="function">igraph_sparse_weighted_adjacency</code> — Creates a graph from a weighted sparse adjacency matrix.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_adjlist">3.5. <code class="function">igraph_adjlist</code> — Creates a graph from an adjacency list.</a></span></dt>
|
||
</dl></div>
|
||
<p>These functions create graphs from weighted or unweighted adjacency matrices, or an adjacency list.</p>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_adjacency"></a>3.1. <code class="function">igraph_adjacency</code> — Creates a graph from an adjacency matrix.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.4.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_adjacency(
|
||
igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode,
|
||
igraph_loops_t loops
|
||
);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
The order of the vertices in the matrix is preserved, i.e. the vertex
|
||
corresponding to the first row/column will be vertex with id 0, the
|
||
next row is for vertex 1, etc. No guarantees are given about the ordering
|
||
of edges.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>adjmatrix</code></em>:</span></p></td>
|
||
<td><p>
|
||
The adjacency matrix. How it is interpreted
|
||
depends on the <em class="parameter"><code>mode</code></em> argument.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant to specify how the given matrix is interpreted
|
||
as an adjacency matrix. Possible values (A(i,j) is the element in
|
||
row i and column j in the adjacency matrix <em class="parameter"><code>adjmatrix</code></em>):
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_DIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
The graph will be directed and an element gives the number of edges
|
||
between two vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
The graph will be undirected and an element gives the number of
|
||
edges between two vertices. If the input matrix is not symmetric,
|
||
an error is thrown.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_MAX</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created and the number of edges between
|
||
vertices i and j is max(A(i,j), A(j,i)).
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_MIN</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created with min(A(i,j), A(j,i)) edges
|
||
between vertices i and j.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_PLUS</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created with A(i,j)+A(j,i) edges
|
||
between vertices i and j.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_UPPER</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created. Only the upper right triangle
|
||
(including the diagonal) is used for the number of edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_LOWER</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created. Only the lower left triangle
|
||
(including the diagonal) is used for the number of edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant of type <a class="link" href="igraph-Structural.html#igraph_loops_t" title="27.1. igraph_loops_t — How to interpret self-loops in undirected graphs?"><code class="function">igraph_loops_t</code></a> to specify how the diagonal
|
||
of the matrix should be treated when creating loop edges. Ignored for
|
||
modes <code class="constant">IGRAPH_ADJ_DIRECTED</code>, <code class="constant">IGRAPH_ADJ_UPPER</code> and <code class="constant">IGRAPH_ADJ_LOWER</code>.
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_NO_LOOPS</code></span></p></td>
|
||
<td><p>
|
||
|
||
Ignore the diagonal of the input matrix and do not create loops.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_ONCE</code></span></p></td>
|
||
<td><p>
|
||
|
||
Treat the diagonal entries as the number of loop edges incident on
|
||
the corresponding vertex.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_TWICE</code></span></p></td>
|
||
<td><p>
|
||
|
||
Treat the diagonal entries as <span class="emphasis"><em>twice</em></span> the number of loop edges
|
||
incident on the corresponding vertex. Odd numbers in the diagonal
|
||
will return an error code.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code,
|
||
<code class="constant">IGRAPH_EINVAL</code>: Non-square adjacency matrix, negative entry in
|
||
adjacency matrix, or an odd number was found in the diagonal with
|
||
<code class="constant">IGRAPH_LOOPS_TWICE</code>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V||V|),
|
||
|V| is the number of vertices in the graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_weighted_adjacency"></a>3.2. <code class="function">igraph_weighted_adjacency</code> — Creates a graph from a weighted adjacency matrix.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.4.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_weighted_adjacency(
|
||
igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode,
|
||
igraph_vector_t *weights, igraph_loops_t loops
|
||
);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
The order of the vertices in the matrix is preserved, i.e. the vertex
|
||
corresponding to the first row/column will be vertex with id 0, the
|
||
next row is for vertex 1, etc. No guarantees are given for the ordering
|
||
of edges.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>adjmatrix</code></em>:</span></p></td>
|
||
<td><p>
|
||
The weighted adjacency matrix. How it is interpreted
|
||
depends on the <em class="parameter"><code>mode</code></em> argument. The common feature is that
|
||
edges with zero weights are considered nonexistent (however,
|
||
negative weights are permitted).
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant to specify how the given matrix is interpreted
|
||
as an adjacency matrix. Possible values (A(i,j) is the element in row
|
||
i and column j in the adjacency matrix <em class="parameter"><code>adjmatrix</code></em>):
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_DIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
The graph will be directed and an element specifies the weight of the
|
||
edge between two vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
This is the same as <code class="constant">IGRAPH_ADJ_MAX</code>, for convenience.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_MAX</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created and the weight of the edge between
|
||
vertices i and j is max(A(i,j), A(j,i)).
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_MIN</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created and the weight of the edge between
|
||
vertices i and j is min(A(i,j), A(j,i)).
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_PLUS</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created and the weight of the edge between
|
||
vertices i and j is A(i,j)+A(j,i).
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_UPPER</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created. Only the upper right triangle
|
||
(including the diagonal) is used for the edge weights.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ADJ_LOWER</code></span></p></td>
|
||
<td><p>
|
||
|
||
An undirected graph will be created. Only the lower left triangle
|
||
(including the diagonal) is used for the edge weights.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>weights</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector, the weights will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant to specify how the diagonal of the matrix should be
|
||
treated when creating loop edges. Ignored for modes
|
||
<code class="constant">IGRAPH_ADJ_DIRECTED</code>, <code class="constant">IGRAPH_ADJ_UPPER</code> and <code class="constant">IGRAPH_ADJ_LOWER</code>.
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_NO_LOOPS</code></span></p></td>
|
||
<td><p>
|
||
|
||
Ignore the diagonal of the input matrix and do not create loops.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_ONCE</code></span></p></td>
|
||
<td><p>
|
||
|
||
Treat the diagonal entries as the weight of the loop edge incident
|
||
on the corresponding vertex.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_TWICE</code></span></p></td>
|
||
<td><p>
|
||
|
||
Treat the diagonal entries as <span class="emphasis"><em>twice</em></span> the weight of the loop edge
|
||
incident on the corresponding vertex.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code,
|
||
<code class="constant">IGRAPH_EINVAL</code>: non-square matrix.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V||V|),
|
||
|V| is the number of vertices in the graph.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.4.4.8.1"></a><p class="title"><b>Example 11.3. File <code class="code">examples/simple/igraph_weighted_adjacency.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
igraph_t graph;
|
||
igraph_real_t data[4][4] = { { 0, 1.2, 2.3, 0 },
|
||
{ 2.0, 0, 0, 1.0 },
|
||
{ 0, 0, 1.5, 0 },
|
||
{ 0, 1.0, 0, 0 } };
|
||
|
||
<span class="emphasis"><em>/* C arrays use row-major storage, while igraph's matrix uses column-major.</em></span>
|
||
<span class="emphasis"><em> * The matrix 'mat' will be the transpose of 'data'. */</em></span>
|
||
<span class="strong"><strong>const</strong></span> igraph_matrix_t mat =
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_matrix_view" title="3.5.1. igraph_matrix_view — Creates a matrix view into an existing array.">igraph_matrix_view</a></strong></span>(*data, <span class="strong"><strong>sizeof</strong></span>(data[0]) / <span class="strong"><strong>sizeof</strong></span>(data[0][0]),
|
||
<span class="strong"><strong>sizeof</strong></span>(data) / <span class="strong"><strong>sizeof</strong></span>(data[0]));
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> weights;
|
||
igraph_vector_int_t edges;
|
||
igraph_int_t n;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* Initialize vector into which weights will be written. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_init" title="2.2.1. igraph_vector_init — Initializes a vector object (constructor).">igraph_vector_init</a></strong></span>(&weights, 0);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_weighted_adjacency" title="3.2. igraph_weighted_adjacency — Creates a graph from a weighted adjacency matrix.">igraph_weighted_adjacency</a></strong></span>(&graph, &mat, IGRAPH_ADJ_DIRECTED, &weights, IGRAPH_LOOPS_ONCE);
|
||
|
||
<span class="emphasis"><em>/* When igraph_weighted_adjacency() returns, 'weights' will typically have</em></span>
|
||
<span class="emphasis"><em> * more capacity allocated than what it uses. We may optionally free any</em></span>
|
||
<span class="emphasis"><em> * unused capacity to save memory, although in most applications this</em></span>
|
||
<span class="emphasis"><em> * is not necessary. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_resize_min" title="2.13.4. igraph_vector_resize_min — Deallocate the unused memory of a vector.">igraph_vector_resize_min</a></strong></span>(&weights);
|
||
|
||
<span class="emphasis"><em>/* Get the edge list of the graph and output it, along with the weights. */</em></span>
|
||
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&edges, 0);
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_get_edgelist" title="26.11. igraph_get_edgelist — The list of edges in a graph.">igraph_get_edgelist</a></strong></span>(&graph, &edges, 0);
|
||
n = <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&graph);
|
||
|
||
<span class="strong"><strong>for</strong></span> (igraph_int_t i = 0; i < n; i++) {
|
||
<span class="strong"><strong>printf</strong></span>("%" IGRAPH_PRId " --> %" IGRAPH_PRId ": %g\n",
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(edges)[2*i], <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(edges)[2*i + 1], <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(weights)[i]);
|
||
}
|
||
|
||
<span class="emphasis"><em>/* Free all allocated storage. */</em></span>
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&edges);
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_destroy" title="2.2.5. igraph_vector_destroy — Destroys a vector object.">igraph_vector_destroy</a></strong></span>(&weights);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_sparse_adjacency"></a>3.3. <code class="function">igraph_sparse_adjacency</code> — Creates a graph from a sparse adjacency matrix.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.4.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_sparse_adjacency(igraph_t *graph, igraph_sparsemat_t *adjmatrix,
|
||
igraph_adjacency_t mode, igraph_loops_t loops);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
This has the same functionality as <a class="link" href="igraph-Generators.html#igraph_adjacency" title="3.1. igraph_adjacency — Creates a graph from an adjacency matrix."><code class="function">igraph_adjacency()</code></a>, but uses
|
||
a column-compressed adjacency matrix.
|
||
|
||
</p>
|
||
<p>
|
||
Time complexity: O(|E|),
|
||
where |E| is the number of edges in the graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_sparse_weighted_adjacency"></a>3.4. <code class="function">igraph_sparse_weighted_adjacency</code> — Creates a graph from a weighted sparse adjacency matrix.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.4.6.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_sparse_weighted_adjacency(
|
||
igraph_t *graph, igraph_sparsemat_t *adjmatrix, igraph_adjacency_t mode,
|
||
igraph_vector_t *weights, igraph_loops_t loops
|
||
);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
This has the same functionality as <a class="link" href="igraph-Generators.html#igraph_weighted_adjacency" title="3.2. igraph_weighted_adjacency — Creates a graph from a weighted adjacency matrix."><code class="function">igraph_weighted_adjacency()</code></a>, but uses
|
||
a column-compressed adjacency matrix.
|
||
|
||
</p>
|
||
<p>
|
||
Time complexity: O(|E|),
|
||
where |E| is the number of edges in the graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_adjlist"></a>3.5. <code class="function">igraph_adjlist</code> — Creates a graph from an adjacency list.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.4.7.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_adjlist(igraph_t *graph, const igraph_adjlist_t *adjlist,
|
||
igraph_neimode_t mode, igraph_bool_t duplicate);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
An adjacency list is a list of vectors, containing the neighbors
|
||
of all vertices. For operations that involve many changes to the
|
||
graph structure, it is recommended that you convert the graph into
|
||
an adjacency list via <a class="link" href="igraph-Data-structures.html#igraph_adjlist_init" title="10.1.1. igraph_adjlist_init — Constructs an adjacency list of vertices from a given graph."><code class="function">igraph_adjlist_init()</code></a>, perform the
|
||
modifications (these are cheap for an adjacency list) and then
|
||
recreate the igraph graph via this function.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>adjlist</code></em>:</span></p></td>
|
||
<td><p>
|
||
The adjacency list.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether or not to create a directed graph. <code class="constant">IGRAPH_ALL</code>
|
||
means an undirected graph, <code class="constant">IGRAPH_OUT</code> means a
|
||
directed graph from an out-adjacency list (i.e. each
|
||
list contains the successors of the corresponding
|
||
vertices), <code class="constant">IGRAPH_IN</code> means a directed graph from an
|
||
in-adjacency list
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>duplicate</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean constant. For undirected graphs this specifies
|
||
whether each edge is included twice, in the vectors of
|
||
both adjacent vertices. If this is <code class="constant">false</code>, then it is
|
||
assumed that every edge is included only once. This argument
|
||
is ignored for directed graphs.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Data-structures.html#igraph_adjlist_init" title="10.1.1. igraph_adjlist_init — Constructs an adjacency list of vertices from a given graph."><code class="function">igraph_adjlist_init()</code></a> for the opposite operation.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|).
|
||
|
||
|
||
</p>
|
||
</div>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="regular-structre-generators"></a>4. Regular structures</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_star">4.1. <code class="function">igraph_star</code> — Creates a <span class="emphasis"><em>star</em></span> graph, every vertex connects only to the center.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_wheel">4.2. <code class="function">igraph_wheel</code> — Creates a <span class="emphasis"><em>wheel</em></span> graph, a union of a star and a cycle graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_hypercube">4.3. <code class="function">igraph_hypercube</code> — The n-dimensional hypercube graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_square_lattice">4.4. <code class="function">igraph_square_lattice</code> — Arbitrary dimensional square lattices.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_triangular_lattice">4.5. <code class="function">igraph_triangular_lattice</code> — A triangular lattice with the given shape.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_hexagonal_lattice">4.6. <code class="function">igraph_hexagonal_lattice</code> — A hexagonal lattice with the given shape.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_ring">4.7. <code class="function">igraph_ring</code> — Creates a <span class="emphasis"><em>cycle</em></span> graph or a <span class="emphasis"><em>path</em></span> graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_path_graph">4.8. <code class="function">igraph_path_graph</code> — A path graph <code class="constant">P_n</code>.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_cycle_graph">4.9. <code class="function">igraph_cycle_graph</code> — A cycle graph <code class="constant">C_n</code>.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_lcf">4.10. <code class="function">igraph_lcf</code> — Creates a graph from LCF notation.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_lcf_small">4.11. <code class="function">igraph_lcf_small</code> — Shorthand to create a graph from LCF notation, giving shifts as the arguments.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_circulant">4.12. <code class="function">igraph_circulant</code> — Creates a circulant graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_extended_chordal_ring">4.13. <code class="function">igraph_extended_chordal_ring</code> — Create an extended chordal ring.</a></span></dt>
|
||
</dl></div>
|
||
<p>These functions produce various basic regular graph structures, such as paths, cycles or lattices.</p>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_star"></a>4.1. <code class="function">igraph_star</code> — Creates a <span class="emphasis"><em>star</em></span> graph, every vertex connects only to the center.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_star(igraph_t *graph, igraph_int_t n, igraph_star_mode_t mode,
|
||
igraph_int_t center);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, this will
|
||
be the result.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer constant, the number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant, gives the type of the star graph to
|
||
create. Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_STAR_OUT</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed star graph, edges point
|
||
<span class="emphasis"><em>from</em></span> the center to the other vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_STAR_IN</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed star graph, edges point
|
||
<span class="emphasis"><em>to</em></span> the center from the other vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_STAR_MUTUAL</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed star graph with mutual edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_STAR_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
an undirected star graph is
|
||
created.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>center</code></em>:</span></p></td>
|
||
<td><p>
|
||
Id of the vertex which will be the center of the
|
||
graph.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td>
|
||
<p>
|
||
Error code:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVVID</code></span></p></td>
|
||
<td><p>
|
||
|
||
invalid number of vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVAL</code></span></p></td>
|
||
<td><p>
|
||
|
||
invalid center vertex.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVMODE</code></span></p></td>
|
||
<td><p>
|
||
|
||
invalid mode argument.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), the
|
||
number of vertices in the graph.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_wheel" title="4.2. igraph_wheel — Creates a wheel graph, a union of a star and a cycle graph."><code class="function">igraph_wheel()</code></a>, <a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a>, <a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>, <a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a>
|
||
for creating other regular structures.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.5.3.10.1"></a><p class="title"><b>Example 11.4. File <code class="code">examples/simple/igraph_star.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
<span class="strong"><strong>#include</strong></span> <stdio.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
igraph_t graph;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* Create an undirected 6-star, with the 0th node as the centre. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_star" title="4.1. igraph_star — Creates a star graph, every vertex connects only to the center.">igraph_star</a></strong></span>(&graph, 7, IGRAPH_STAR_UNDIRECTED, 0);
|
||
|
||
<span class="emphasis"><em>/* Output the edge list of the graph. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_write_graph_edgelist" title="1.2. igraph_write_graph_edgelist — Writes the edge list of a graph to a file.">igraph_write_graph_edgelist</a></strong></span>(&graph, stdout);
|
||
|
||
<span class="emphasis"><em>/* Destroy the graph when we are done using it. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_wheel"></a>4.2. <code class="function">igraph_wheel</code> — Creates a <span class="emphasis"><em>wheel</em></span> graph, a union of a star and a cycle graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_wheel(igraph_t *graph, igraph_int_t n, igraph_wheel_mode_t mode,
|
||
igraph_int_t center);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
A wheel graph on <em class="parameter"><code>n</code></em> vertices can be thought of as a wheel with
|
||
<code class="literal">n - 1</code> spokes. The cycle graph part makes up the rim,
|
||
while the star graph part adds the spokes.
|
||
|
||
</p>
|
||
<p>
|
||
Note that the two and three-vertex wheel graphs are non-simple:
|
||
The two-vertex wheel graph contains a self-loop, while the three-vertex
|
||
wheel graph contains parallel edges (a 1-cycle and a 2-cycle, respectively).
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, this will
|
||
be the result.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer constant, the number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant, gives the type of the star graph to
|
||
create. Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_WHEEL_OUT</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed wheel graph, edges point
|
||
<span class="emphasis"><em>from</em></span> the center to the other vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_WHEEL_IN</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed wheel graph, edges point
|
||
<span class="emphasis"><em>to</em></span> the center from the other vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_WHEEL_MUTUAL</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed wheel graph with mutual edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_WHEEL_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
an undirected wheel graph is
|
||
created.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>center</code></em>:</span></p></td>
|
||
<td><p>
|
||
Id of the vertex which will be the center of the
|
||
graph.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td>
|
||
<p>
|
||
Error code:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVVID</code></span></p></td>
|
||
<td><p>
|
||
|
||
invalid number of vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVAL</code></span></p></td>
|
||
<td><p>
|
||
|
||
invalid center vertex.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVMODE</code></span></p></td>
|
||
<td><p>
|
||
|
||
invalid mode argument.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), the
|
||
number of vertices in the graph.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a>, <a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>, <a class="link" href="igraph-Generators.html#igraph_star" title="4.1. igraph_star — Creates a star graph, every vertex connects only to the center."><code class="function">igraph_star()</code></a>,
|
||
<a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a> for creating other regular structures.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_hypercube"></a>4.3. <code class="function">igraph_hypercube</code> — The n-dimensional hypercube graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_hypercube(igraph_t *graph,
|
||
igraph_int_t n, igraph_bool_t directed);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
The hypercube graph <code class="constant">Q_n</code> has <code class="literal">2^n</code> vertices and
|
||
<code class="literal">2^(n-1) n</code> edges. Two vertices are connected when the binary
|
||
representations of their zero-based vertex IDs differs in precisely one bit.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
An uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
The dimension of the hypercube graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether the graph should be directed. Edges will point
|
||
from lower index vertices towards higher index ones.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(2^n)
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_square_lattice"></a>4.4. <code class="function">igraph_square_lattice</code> — Arbitrary dimensional square lattices.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.6.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_square_lattice(
|
||
igraph_t *graph, const igraph_vector_int_t *dimvector, igraph_int_t nei,
|
||
igraph_bool_t directed, igraph_bool_t mutual, const igraph_vector_bool_t *periodic
|
||
);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
Creates d-dimensional square lattices of the given size. Optionally,
|
||
the lattice can be made periodic, and the neighbors within a given
|
||
graph distance can be connected.
|
||
|
||
</p>
|
||
<p>
|
||
In the zero-dimensional case, the singleton graph is returned.
|
||
|
||
</p>
|
||
<p>
|
||
The vertices of the resulting graph are ordered such that the
|
||
index of the vertex at position <code class="literal">(i_1, i_2, i_3, ..., i_d)</code>
|
||
in a lattice of size <code class="literal">(n_1, n_2, ..., n_d)</code> will be
|
||
<code class="literal">i_1 + n_1 * i_2 + n_1 * n_2 * i_3 + ...</code>.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
An uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>dimvector</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector giving the sizes of the lattice in each of
|
||
its dimensions. The dimension of the lattice will be the
|
||
same as the length of this vector.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>nei</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer value giving the distance (number of steps)
|
||
within which two vertices will be connected.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, whether to create a directed graph.
|
||
If the <code class="constant">mutual</code> and <code class="constant">circular</code> arguments are not set to true,
|
||
edges will be directed from lower-index vertices towards
|
||
higher-index ones.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mutual</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, if the graph is directed this gives whether
|
||
to create all connections as mutual.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>periodic</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean vector, defines whether the generated lattice is
|
||
periodic along each dimension. The length of this vector must match
|
||
the length of <em class="parameter"><code>dimvector</code></em>. This parameter may also be <code class="constant">NULL</code>, which
|
||
implies that the lattice will not be periodic.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_EINVAL</code>: invalid (negative) dimension vector or mismatch
|
||
between the length of the dimension vector and the periodicity vector.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_hypercube" title="4.3. igraph_hypercube — The n-dimensional hypercube graph."><code class="function">igraph_hypercube()</code></a> to create a hypercube graph; <a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>
|
||
to create a cycle graph or path graph; <a class="link" href="igraph-Generators.html#igraph_triangular_lattice" title="4.5. igraph_triangular_lattice — A triangular lattice with the given shape."><code class="function">igraph_triangular_lattice()</code></a>
|
||
and <a class="link" href="igraph-Generators.html#igraph_hexagonal_lattice" title="4.6. igraph_hexagonal_lattice — A hexagonal lattice with the given shape."><code class="function">igraph_hexagonal_lattice()</code></a> to create other types of lattices;
|
||
<a class="link" href="igraph-Generators.html#igraph_regular_tree" title="5.3. igraph_regular_tree — Creates a regular tree."><code class="function">igraph_regular_tree()</code></a> to create a Bethe lattice.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: If <em class="parameter"><code>nei</code></em> is less than two then it is O(|V|+|E|) (as
|
||
far as I remember), |V| and |E| are the number of vertices
|
||
and edges in the generated graph. Otherwise it is O(|V|*d^k+|E|), d
|
||
is the average degree of the graph, k is the <em class="parameter"><code>nei</code></em> argument.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_triangular_lattice"></a>4.5. <code class="function">igraph_triangular_lattice</code> — A triangular lattice with the given shape.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.7.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_triangular_lattice(
|
||
igraph_t *graph, const igraph_vector_int_t *dims,
|
||
igraph_bool_t directed, igraph_bool_t mutual);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Creates a triangular lattice whose vertices have the form (i, j) for non-negative
|
||
integers i and j and (i, j) is generally connected with (i + 1, j), (i, j + 1),
|
||
and (i - 1, j + 1). The function constructs a planar dual of the graph
|
||
constructed by <a class="link" href="igraph-Generators.html#igraph_hexagonal_lattice" title="4.6. igraph_hexagonal_lattice — A hexagonal lattice with the given shape."><code class="function">igraph_hexagonal_lattice()</code></a>. In particular, there a one-to-one
|
||
correspondence between the vertices in the constructed graph and the cycles of
|
||
length 6 in the graph constructed by <a class="link" href="igraph-Generators.html#igraph_hexagonal_lattice" title="4.6. igraph_hexagonal_lattice — A hexagonal lattice with the given shape."><code class="function">igraph_hexagonal_lattice()</code></a>
|
||
with the same <em class="parameter"><code>dims</code></em> parameter.
|
||
|
||
</p>
|
||
<p>
|
||
The vertices of the resulting graph are ordered lexicographically with the 2nd
|
||
coordinate being more significant, e.g., (i, j) < (i + 1, j) and
|
||
(i + 1, j) < (i, j + 1)
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
An uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>dims</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer vector, defines the shape of the lattice.
|
||
If <em class="parameter"><code>dims</code></em> is of length 1, the resulting lattice has a triangular shape
|
||
where each side of the triangle contains <code class="literal">dims[0]</code> vertices.
|
||
If <em class="parameter"><code>dims</code></em> is of length 2, the resulting lattice has a
|
||
"quasi rectangular" shape with the sides containing <code class="literal">dims[0]</code> and
|
||
<code class="literal">dims[1]</code> vertices, respectively.
|
||
If <em class="parameter"><code>dims</code></em> is of length 3, the resulting lattice has a hexagonal shape
|
||
where the sides of the hexagon contain <code class="literal">dims[0]</code>, <code class="literal">dims[1]</code>
|
||
and <code class="literal">dims[2]</code> vertices. All dimensions must be non-negative.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, whether to create a directed graph.
|
||
If the <code class="constant">mutual</code> argument is not set to true, edges will be directed from
|
||
lower-index vertices towards higher-index ones.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mutual</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, if the graph is directed this gives whether
|
||
to create all connections as mutual.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_EINVAL</code>: The size of <em class="parameter"><code>dims</code></em> must be either 1, 2, or 3 with all
|
||
the components at least 1.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_hexagonal_lattice" title="4.6. igraph_hexagonal_lattice — A hexagonal lattice with the given shape."><code class="function">igraph_hexagonal_lattice()</code></a> and <a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a> for creating
|
||
other types of lattices; <a class="link" href="igraph-Generators.html#igraph_regular_tree" title="5.3. igraph_regular_tree — Creates a regular tree."><code class="function">igraph_regular_tree()</code></a> to create a Bethe lattice.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), where |V| is the number of vertices in the generated graph.
|
||
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_hexagonal_lattice"></a>4.6. <code class="function">igraph_hexagonal_lattice</code> — A hexagonal lattice with the given shape.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.8.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_hexagonal_lattice(
|
||
igraph_t *graph, const igraph_vector_int_t *dims,
|
||
igraph_bool_t directed, igraph_bool_t mutual);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Creates a hexagonal lattice whose vertices have the form (i, j) for non-negative
|
||
integers i and j and (i, j) is generally connected with (i + 1, j), and if i is
|
||
odd also with (i - 1, j + 1). The function constructs a planar dual of the graph
|
||
constructed by <a class="link" href="igraph-Generators.html#igraph_triangular_lattice" title="4.5. igraph_triangular_lattice — A triangular lattice with the given shape."><code class="function">igraph_triangular_lattice()</code></a>. In particular, there a one-to-one
|
||
correspondence between the cycles of length 6 in the constructed graph and the
|
||
vertices of the graph constructed by <a class="link" href="igraph-Generators.html#igraph_triangular_lattice" title="4.5. igraph_triangular_lattice — A triangular lattice with the given shape."><code class="function">igraph_triangular_lattice()</code></a> function
|
||
with the same <em class="parameter"><code>dims</code></em> parameter.
|
||
|
||
</p>
|
||
<p>
|
||
The vertices of the resulting graph are ordered lexicographically with the 2nd
|
||
coordinate being more significant, e.g., (i, j) < (i + 1, j) and
|
||
(i + 1, j) < (i, j + 1)
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
An uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>dims</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer vector, defines the shape of the lattice.
|
||
If <em class="parameter"><code>dims</code></em> is of length 1, the resulting lattice has a triangular shape
|
||
where each side of the triangle contains <code class="literal">dims[0]</code> vertices.
|
||
If <em class="parameter"><code>dims</code></em> is of length 2, the resulting lattice has a "quasi rectangular"
|
||
shape with the sides containing <code class="literal">dims[0]</code> and <code class="literal">dims[1]</code>
|
||
vertices, respectively. If <em class="parameter"><code>dims</code></em> is of length 3, the resulting lattice has
|
||
a hexagonal shape where the sides of the hexagon contain <code class="literal">dims[0]</code>,
|
||
<code class="literal">dims[1]</code> and <code class="literal">dims[2]</code> vertices. All coordinates must
|
||
be non-negative.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, whether to create a directed graph.
|
||
If the <code class="constant">mutual</code> argument is not set to true, edges will be directed from
|
||
lower-index vertices towards higher-index ones.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mutual</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, if the graph is directed this gives whether to create
|
||
all connections as mutual.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_EINVAL</code>: The size of <em class="parameter"><code>dims</code></em> must be either 1, 2, or 3 with all
|
||
the components at least 1.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_triangular_lattice" title="4.5. igraph_triangular_lattice — A triangular lattice with the given shape."><code class="function">igraph_triangular_lattice()</code></a> and <a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a> for creating
|
||
other types of lattices; ; <a class="link" href="igraph-Generators.html#igraph_regular_tree" title="5.3. igraph_regular_tree — Creates a regular tree."><code class="function">igraph_regular_tree()</code></a> to create a Bethe lattice.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), where |V| is the number of vertices in the generated graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_ring"></a>4.7. <code class="function">igraph_ring</code> — Creates a <span class="emphasis"><em>cycle</em></span> graph or a <span class="emphasis"><em>path</em></span> graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.9.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_ring(igraph_t *graph, igraph_int_t n, igraph_bool_t directed,
|
||
igraph_bool_t mutual, igraph_bool_t circular);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
A circular ring on <code class="constant">n</code> vertices is commonly known in graph
|
||
theory as the cycle graph, and often denoted by <code class="literal">C_n</code>.
|
||
Removing a single edge from the cycle graph <code class="literal">C_n</code> results
|
||
in the path graph <code class="literal">P_n</code>. This function can generate both.
|
||
|
||
</p>
|
||
<p>
|
||
When <em class="parameter"><code>n</code></em> is 1 or 2, the result may not be a simple graph:
|
||
the one-cycle contains a self-loop and the undirected or reciprocally
|
||
connected directed two-cycle contains parallel edges.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create a directed graph.
|
||
All edges will be oriented in the same direction along
|
||
the cycle or path.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mutual</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create mutual edges in directed
|
||
graphs. It is ignored for undirected graphs.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>circular</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create a closed ring (a cycle)
|
||
or an open path.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_EINVAL</code>: invalid number of vertices.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), the number of vertices in the graph.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a> for generating more general
|
||
(periodic or non-periodic) lattices.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.5.9.11.1"></a><p class="title"><b>Example 11.5. File <code class="code">examples/simple/igraph_ring.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
<span class="strong"><strong>#include</strong></span> <stdio.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
igraph_t graph;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* Create a directed path graph on 10 vertices. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph.">igraph_ring</a></strong></span>(&graph, 10, IGRAPH_DIRECTED, <span class="emphasis"><em>/* mutual= */</em></span> 0, <span class="emphasis"><em>/* circular= */</em></span> 0);
|
||
|
||
<span class="emphasis"><em>/* Output the edge list of the graph. */</em></span>
|
||
<span class="strong"><strong>printf</strong></span>("10-path graph:\n");
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_write_graph_edgelist" title="1.2. igraph_write_graph_edgelist — Writes the edge list of a graph to a file.">igraph_write_graph_edgelist</a></strong></span>(&graph, stdout);
|
||
|
||
<span class="emphasis"><em>/* Destroy the graph. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="emphasis"><em>/* Create a 4-cycle graph. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph.">igraph_ring</a></strong></span>(&graph, 4, IGRAPH_UNDIRECTED, <span class="emphasis"><em>/* mutual= */</em></span> 0, <span class="emphasis"><em>/* circular= */</em></span> 1);
|
||
|
||
<span class="emphasis"><em>/* Output the edge list of the graph. */</em></span>
|
||
<span class="strong"><strong>printf</strong></span>("\n4-cycle graph:\n");
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_write_graph_edgelist" title="1.2. igraph_write_graph_edgelist — Writes the edge list of a graph to a file.">igraph_write_graph_edgelist</a></strong></span>(&graph, stdout);
|
||
|
||
<span class="emphasis"><em>/* Destroy the graph. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_path_graph"></a>4.8. <code class="function">igraph_path_graph</code> — A path graph <code class="constant">P_n</code>.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.10.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_path_graph(
|
||
igraph_t *graph, igraph_int_t n,
|
||
igraph_bool_t directed, igraph_bool_t mutual);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
Creates the path graph <code class="constant">P_n</code> on <em class="parameter"><code>n</code></em> vertices.
|
||
|
||
</p>
|
||
<p>
|
||
This is a convenience wrapper to <a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create a directed graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mutual</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create mutual edges in directed
|
||
graphs. It is ignored for undirected graphs.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), the number of vertices in the graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_cycle_graph"></a>4.9. <code class="function">igraph_cycle_graph</code> — A cycle graph <code class="constant">C_n</code>.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.11.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_cycle_graph(
|
||
igraph_t *graph, igraph_int_t n,
|
||
igraph_bool_t directed, igraph_bool_t mutual);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
Creates the cycle graph <code class="constant">C_n</code> on <em class="parameter"><code>n</code></em> vertices.
|
||
|
||
</p>
|
||
<p>
|
||
When <em class="parameter"><code>n</code></em> is 1 or 2, the result may not be a simple graph:
|
||
the one-cycle contains a self-loop and the undirected or reciprocally
|
||
connected directed two-cycle contains parallel edges.
|
||
|
||
</p>
|
||
<p>
|
||
This is a convenience wrapper to <a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create a directed graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mutual</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create mutual edges in directed
|
||
graphs. It is ignored for undirected graphs.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), the number of vertices in the graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_lcf"></a>4.10. <code class="function">igraph_lcf</code> — Creates a graph from LCF notation.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.12.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_lcf(igraph_t *graph, igraph_int_t n,
|
||
const igraph_vector_int_t *shifts,
|
||
igraph_int_t repeats);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
LCF notation (named after Lederberg, Coxeter and Frucht) is a concise notation
|
||
for 3-regular Hamiltonian graphs. It consists of three parameters: the
|
||
number of vertices in the graph, a list of shifts giving additional
|
||
edges to a cycle backbone, and another integer giving how many times
|
||
the shifts should be performed. See
|
||
<a class="ulink" href="https://mathworld.wolfram.com/LCFNotation.html" target="_top">https://mathworld.wolfram.com/LCFNotation.html</a> for details.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer constant giving the number of vertices. This
|
||
is normally set to the number of shifts multiplied by the
|
||
number of repeats.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>shifts</code></em>:</span></p></td>
|
||
<td><p>
|
||
An integer vector giving the shifts.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>repeats</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of repeats for the shifts.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_lcf_small" title="4.11. igraph_lcf_small — Shorthand to create a graph from LCF notation, giving shifts as the arguments."><code class="function">igraph_lcf_small()</code></a>, <a class="link" href="igraph-Generators.html#igraph_extended_chordal_ring" title="4.13. igraph_extended_chordal_ring — Create an extended chordal ring."><code class="function">igraph_extended_chordal_ring()</code></a>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), linear in the number of vertices plus
|
||
the number of edges.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_lcf_small"></a>4.11. <code class="function">igraph_lcf_small</code> — Shorthand to create a graph from LCF notation, giving shifts as the arguments.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.13.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_lcf_small(igraph_t *graph, igraph_int_t n, ...);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function provides a shorthand to give the shifts of the LCF notation
|
||
directly as function arguments. See <a class="link" href="igraph-Generators.html#igraph_lcf" title="4.10. igraph_lcf — Creates a graph from LCF notation."><code class="function">igraph_lcf()</code></a> for an explanation
|
||
of LCF notation.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>...</code></em>:</span></p></td>
|
||
<td><p>
|
||
The shifts and the number of repeats for the shifts,
|
||
plus an additional 0 to mark the end of the arguments.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
See <a class="link" href="igraph-Generators.html#igraph_lcf" title="4.10. igraph_lcf — Creates a graph from LCF notation."><code class="function">igraph_lcf()</code></a> for a similar function using an
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects"><code class="function">igraph_vector_t</code></a> instead of the variable length argument list;
|
||
<a class="link" href="igraph-Generators.html#igraph_circulant" title="4.12. igraph_circulant — Creates a circulant graph."><code class="function">igraph_circulant()</code></a> to create circulant graphs.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the number of vertices plus the number
|
||
of edges.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.5.13.10.1"></a><p class="title"><b>Example 11.6. File <code class="code">examples/simple/igraph_lcf.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
|
||
igraph_t g1, g2;
|
||
igraph_vector_int_t edges;
|
||
igraph_bool_t iso;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>// Heawood graph through LCF notation: [5, -5]^7</em></span>
|
||
<span class="emphasis"><em>// The number of vertices is normally the number of shifts</em></span>
|
||
<span class="emphasis"><em>// multiplied by the number of repeats, in this case 2*7 = 14.</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_lcf_small" title="4.11. igraph_lcf_small — Shorthand to create a graph from LCF notation, giving shifts as the arguments.">igraph_lcf_small</a></strong></span>(&g1,
|
||
<span class="emphasis"><em>/* n */</em></span> 14,
|
||
<span class="emphasis"><em>/* shifts */</em></span> 5, -5,
|
||
<span class="emphasis"><em>/* repeats */</em></span> 7,
|
||
0);
|
||
|
||
<span class="strong"><strong>printf</strong></span>("edges:\n");
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&edges, 0);
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_get_edgelist" title="26.11. igraph_get_edgelist — The list of edges in a graph.">igraph_get_edgelist</a></strong></span>(&g1, &edges, false);
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&edges);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&edges);
|
||
|
||
<span class="emphasis"><em>// Built-in Heawood graph:</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_famous" title="8.1. igraph_famous — Create a famous graph by simply providing its name.">igraph_famous</a></strong></span>(&g2, "Heawood");
|
||
<span class="strong"><strong><a class="link" href="igraph-Isomorphism.html#igraph_isomorphic" title="1.1. igraph_isomorphic — Are two graphs isomorphic?">igraph_isomorphic</a></strong></span>(&g1, &g2, &iso);
|
||
<span class="strong"><strong>printf</strong></span>("isomorphic: %s\n", iso ? "true" : "false");
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g2);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g1);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_circulant"></a>4.12. <code class="function">igraph_circulant</code> — Creates a circulant graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.14.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_circulant(igraph_t *graph, igraph_int_t n, const igraph_vector_int_t *shifts, igraph_bool_t directed);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
A circulant graph <code class="literal">G(n, shifts)</code> consists of <em class="parameter"><code>n</code></em> vertices <code class="literal">v_0</code>, ...,
|
||
<code class="literal">v_(n-1)</code> such that for each <code class="constant">s_i</code> in the list of offsets <em class="parameter"><code>shifts</code></em>, <code class="constant">v_j</code> is
|
||
connected to <code class="literal">v_((j + s_i) mod n)</code> for all j.
|
||
|
||
</p>
|
||
<p>
|
||
The function can generate either directed or undirected graphs. It does not generate
|
||
multi-edges or self-loops.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, the result will
|
||
be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of vertices in the circulant graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>shifts</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer vector, a list of the offsets within the circulant graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, whether to create a directed graph.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>, <a class="link" href="igraph-Generators.html#igraph_generalized_petersen" title="9.3. igraph_generalized_petersen — Creates a Generalized Petersen graph."><code class="function">igraph_generalized_petersen()</code></a>,
|
||
<a class="link" href="igraph-Generators.html#igraph_extended_chordal_ring" title="4.13. igraph_extended_chordal_ring — Create an extended chordal ring."><code class="function">igraph_extended_chordal_ring()</code></a>, <a class="link" href="igraph-Generators.html#igraph_lcf" title="4.10. igraph_lcf — Creates a graph from LCF notation."><code class="function">igraph_lcf()</code></a>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V| |shifts|), the number of vertices in the graph times the number
|
||
of shifts.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_extended_chordal_ring"></a>4.13. <code class="function">igraph_extended_chordal_ring</code> — Create an extended chordal ring.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.5.15.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_extended_chordal_ring(
|
||
igraph_t *graph, igraph_int_t nodes, const igraph_matrix_int_t *W,
|
||
igraph_bool_t directed);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
An extended chordal ring is a cycle graph with additional chords
|
||
connecting its vertices.
|
||
|
||
Each row <code class="constant">L</code> of the matrix <em class="parameter"><code>W</code></em> specifies a set of chords to be
|
||
inserted, in the following way: vertex <code class="constant">i</code> will connect to a vertex
|
||
<code class="literal">L[(i mod p)]</code> steps ahead of it along the cycle, where
|
||
<code class="constant">p</code> is the length of <code class="constant">L</code>.
|
||
In other words, vertex <code class="constant">i</code> will be connected to vertex
|
||
<code class="literal">(i + L[(i mod p)]) mod nodes</code>. If multiple edges are
|
||
defined in this way, this will output a non-simple graph. The result
|
||
can be simplified using <a class="link" href="igraph-Operators.html#igraph_simplify" title="3.11. igraph_simplify — Removes loop and/or multiple edges from the graph."><code class="function">igraph_simplify()</code></a>.
|
||
|
||
</p>
|
||
<p>
|
||
See also Kotsis, G: Interconnection Topologies for Parallel Processing
|
||
Systems, PARS Mitteilungen 11, 1-6, 1993. The igraph extended chordal
|
||
rings are not identical to the ones in the paper. In igraph
|
||
the matrix specifies which edges to add. In the paper, a condition is
|
||
specified which should simultaneously hold between two endpoints and
|
||
the reverse endpoints.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, the result
|
||
will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer constant, the number of vertices in the
|
||
graph. It must be at least 3.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>W</code></em>:</span></p></td>
|
||
<td><p>
|
||
The matrix specifying the extra edges. The number of
|
||
columns should divide the number of total vertices. The elements
|
||
are allowed to be negative.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether the graph should be directed.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>, <a class="link" href="igraph-Generators.html#igraph_lcf" title="4.10. igraph_lcf — Creates a graph from LCF notation."><code class="function">igraph_lcf()</code></a>, <a class="link" href="igraph-Generators.html#igraph_circulant" title="4.12. igraph_circulant — Creates a circulant graph."><code class="function">igraph_circulant()</code></a>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the number of vertices plus the number
|
||
of edges.
|
||
|
||
</p>
|
||
</div>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="tree-generators"></a>5. Tree generators</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_kary_tree">5.1. <code class="function">igraph_kary_tree</code> — Creates a k-ary tree in which almost all vertices have k children.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_symmetric_tree">5.2. <code class="function">igraph_symmetric_tree</code> — Creates a symmetric tree with the specified number of branches at each level.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_regular_tree">5.3. <code class="function">igraph_regular_tree</code> — Creates a regular tree.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_tree_from_parent_vector">5.4. <code class="function">igraph_tree_from_parent_vector</code> — Constructs a tree or forest from a vector encoding the parent of each vertex.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_from_prufer">5.5. <code class="function">igraph_from_prufer</code> — Generates a tree from a Prüfer sequence.</a></span></dt>
|
||
</dl></div>
|
||
<p>These functions generate tree graphs.</p>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_kary_tree"></a>5.1. <code class="function">igraph_kary_tree</code> — Creates a k-ary tree in which almost all vertices have k children.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.6.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_kary_tree(igraph_t *graph, igraph_int_t n, igraph_int_t children,
|
||
igraph_tree_mode_t type);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
To obtain a completely symmetric tree with <code class="constant">l</code> layers, where each
|
||
vertex has precisely <em class="parameter"><code>children</code></em> descendants, use
|
||
<code class="literal">n = (children^(l+1) - 1) / (children - 1)</code>.
|
||
Such trees are often called <code class="literal">k</code>-ary trees, where <code class="constant">k</code> refers
|
||
to the number of children.
|
||
|
||
</p>
|
||
<p>
|
||
Note that for <code class="literal">n=0</code>, the null graph is returned,
|
||
which is not considered to be a tree by <a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree."><code class="function">igraph_is_tree()</code></a>.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>children</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of children of a vertex in the
|
||
tree.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>type</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant, gives whether to create a directed tree, and
|
||
if this is the case, also its orientation. Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_OUT</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point
|
||
from the parents to their children.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_IN</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point from
|
||
the children to their parents.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
undirected tree.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_EINVAL</code>: invalid number of vertices.
|
||
<code class="constant">IGRAPH_INVMODE</code>: invalid mode argument.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the
|
||
number of vertices plus the number of edges in the graph.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_regular_tree" title="5.3. igraph_regular_tree — Creates a regular tree."><code class="function">igraph_regular_tree()</code></a>, <a class="link" href="igraph-Generators.html#igraph_symmetric_tree" title="5.2. igraph_symmetric_tree — Creates a symmetric tree with the specified number of branches at each level."><code class="function">igraph_symmetric_tree()</code></a> and <a class="link" href="igraph-Generators.html#igraph_star" title="4.1. igraph_star — Creates a star graph, every vertex connects only to the center."><code class="function">igraph_star()</code></a>
|
||
for creating other regular structures; <a class="link" href="igraph-Generators.html#igraph_from_prufer" title="5.5. igraph_from_prufer — Generates a tree from a Prüfer sequence."><code class="function">igraph_from_prufer()</code></a> and
|
||
<a class="link" href="igraph-Generators.html#igraph_tree_from_parent_vector" title="5.4. igraph_tree_from_parent_vector — Constructs a tree or forest from a vector encoding the parent of each vertex."><code class="function">igraph_tree_from_parent_vector()</code></a> for creating arbitrary trees;
|
||
<a class="link" href="igraph-Games.html#igraph_tree_game" title="6.4. igraph_tree_game — Generates a random tree with the given number of nodes."><code class="function">igraph_tree_game()</code></a> for uniform random sampling of trees;
|
||
<a class="link" href="igraph-Generators.html#igraph_realize_degree_sequence" title="6.1. igraph_realize_degree_sequence — Generates a graph with the given degree sequence."><code class="function">igraph_realize_degree_sequence()</code></a> with <code class="constant">IGRAPH_REALIZE_DEGSEQ_SMALLEST</code>
|
||
to create a tree with given degrees.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.6.3.11.1"></a><p class="title"><b>Example 11.7. File <code class="code">examples/simple/igraph_kary_tree.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
igraph_t graph;
|
||
igraph_bool_t res;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* Create a directed binary tree on 15 nodes,</em></span>
|
||
<span class="emphasis"><em> with edges pointing towards the root. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children.">igraph_kary_tree</a></strong></span>(&graph, 15, 2, IGRAPH_TREE_IN);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree.">igraph_is_tree</a></strong></span>(&graph, &res, NULL, IGRAPH_IN);
|
||
<span class="strong"><strong>printf</strong></span>("Is it an in-tree? %s\n", res ? "Yes" : "No");
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree.">igraph_is_tree</a></strong></span>(&graph, &res, NULL, IGRAPH_OUT);
|
||
<span class="strong"><strong>printf</strong></span>("Is it an out-tree? %s\n", res ? "Yes" : "No");
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_symmetric_tree"></a>5.2. <code class="function">igraph_symmetric_tree</code> — Creates a symmetric tree with the specified number of branches at each level.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.6.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_symmetric_tree(igraph_t *graph, const igraph_vector_int_t *branches,
|
||
igraph_tree_mode_t type);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
This function creates a tree in which all vertices at distance <code class="constant">d</code> from the
|
||
root have <em class="parameter"><code>branching_counts</code></em>[d] children.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>branches</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector detailing the number of branches at each level.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>type</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant, gives whether to create a directed tree, and
|
||
if this is the case, also its orientation. Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_OUT</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point
|
||
from the parents to their children.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_IN</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point from
|
||
the children to their parents.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
undirected tree.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_INVMODE</code>: invalid mode argument.
|
||
<code class="constant">IGRAPH_EINVAL</code>: invalid number of children.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the
|
||
number of vertices plus the number of edges in the graph.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a>, <a class="link" href="igraph-Generators.html#igraph_regular_tree" title="5.3. igraph_regular_tree — Creates a regular tree."><code class="function">igraph_regular_tree()</code></a> and <a class="link" href="igraph-Generators.html#igraph_star" title="4.1. igraph_star — Creates a star graph, every vertex connects only to the center."><code class="function">igraph_star()</code></a>
|
||
for creating other regular tree structures;
|
||
<a class="link" href="igraph-Generators.html#igraph_from_prufer" title="5.5. igraph_from_prufer — Generates a tree from a Prüfer sequence."><code class="function">igraph_from_prufer()</code></a> for creating arbitrary trees;
|
||
<a class="link" href="igraph-Games.html#igraph_tree_game" title="6.4. igraph_tree_game — Generates a random tree with the given number of nodes."><code class="function">igraph_tree_game()</code></a> for uniform random sampling of trees.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.6.4.10.1"></a><p class="title"><b>Example 11.8. File <code class="code">examples/simple/igraph_symmetric_tree.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
|
||
igraph_t graph;
|
||
igraph_bool_t res;
|
||
igraph_vector_int_t v;
|
||
<span class="strong"><strong>igraph_vector_int_init_int</strong></span>(&v, 3, 3, 4, 5);
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* Create a directed symmetric tree with 2 levels -</em></span>
|
||
<span class="emphasis"><em> 3 children in first and 4 children in second level,</em></span>
|
||
<span class="emphasis"><em> 5 children in third level</em></span>
|
||
<span class="emphasis"><em> with edges pointing towards the root. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_symmetric_tree" title="5.2. igraph_symmetric_tree — Creates a symmetric tree with the specified number of branches at each level.">igraph_symmetric_tree</a></strong></span>(&graph, &v, IGRAPH_TREE_IN);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree.">igraph_is_tree</a></strong></span>(&graph, &res, NULL, IGRAPH_IN);
|
||
<span class="strong"><strong>printf</strong></span>("Is it an in-tree? %s\n", res ? "Yes" : "No");
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree.">igraph_is_tree</a></strong></span>(&graph, &res, NULL, IGRAPH_OUT);
|
||
<span class="strong"><strong>printf</strong></span>("Is it an out-tree? %s\n", res ? "Yes" : "No");
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&v);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_regular_tree"></a>5.3. <code class="function">igraph_regular_tree</code> — Creates a regular tree.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.6.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_regular_tree(igraph_t *graph, igraph_int_t h, igraph_int_t k, igraph_tree_mode_t type);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
All vertices of a regular tree, except its leaves, have the same total degree <em class="parameter"><code>k</code></em>.
|
||
This is different from a k-ary tree (<a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a>), where all
|
||
vertices have the same number of children, thus the degre of the root is
|
||
one less than the degree of the other internal vertices. Regular trees
|
||
are also referred to as Bethe lattices.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>h</code></em>:</span></p></td>
|
||
<td><p>
|
||
The height of the tree, i.e. the distance between the root and the leaves.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>k</code></em>:</span></p></td>
|
||
<td><p>
|
||
The degree of the regular tree.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>type</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant, gives whether to create a directed tree, and
|
||
if this is the case, also its orientation. Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_OUT</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point
|
||
from the parents to their children.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_IN</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point from
|
||
the children to their parents.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_UNDIRECTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
undirected tree.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the
|
||
number of vertices plus the number of edges in the graph.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a> to create k-ary tree where each vertex has the same
|
||
number of children, i.e. out-degree, instead of the same total degree.
|
||
<a class="link" href="igraph-Generators.html#igraph_symmetric_tree" title="5.2. igraph_symmetric_tree — Creates a symmetric tree with the specified number of branches at each level."><code class="function">igraph_symmetric_tree()</code></a> to use a different number of children at each level.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.6.5.10.1"></a><p class="title"><b>Example 11.9. File <code class="code">examples/simple/igraph_regular_tree.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
igraph_t tree;
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> eccentricity;
|
||
igraph_bool_t is_tree;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* Create a Bethe lattice with 5 levels, i.e. height 4. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_regular_tree" title="5.3. igraph_regular_tree — Creates a regular tree.">igraph_regular_tree</a></strong></span>(&tree, 4, 3, IGRAPH_TREE_UNDIRECTED);
|
||
|
||
<span class="emphasis"><em>/* Bethe lattices are trees. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree.">igraph_is_tree</a></strong></span>(&tree, &is_tree, NULL, IGRAPH_ALL);
|
||
<span class="strong"><strong>printf</strong></span>("Is it a tree? %s\n", is_tree ? "Yes." : "No.");
|
||
|
||
<span class="emphasis"><em>/* Compute and print eccentricities. The root is the most central. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_init" title="2.2.1. igraph_vector_init — Initializes a vector object (constructor).">igraph_vector_init</a></strong></span>(&eccentricity, 0);
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_eccentricity" title="3.24. igraph_eccentricity — Eccentricity of some vertices.">igraph_eccentricity</a></strong></span>(&tree, NULL, &eccentricity, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_ALL);
|
||
<span class="strong"><strong>printf</strong></span>("Vertex eccentricities:\n");
|
||
<span class="strong"><strong>igraph_vector_print</strong></span>(&eccentricity);
|
||
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_destroy" title="2.2.5. igraph_vector_destroy — Destroys a vector object.">igraph_vector_destroy</a></strong></span>(&eccentricity);
|
||
|
||
<span class="emphasis"><em>/* Clean up. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&tree);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_tree_from_parent_vector"></a>5.4. <code class="function">igraph_tree_from_parent_vector</code> — Constructs a tree or forest from a vector encoding the parent of each vertex.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.6.6.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_tree_from_parent_vector(
|
||
igraph_t *graph,
|
||
const igraph_vector_int_t *parents,
|
||
igraph_tree_mode_t type);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Rooted trees and forests are conveniently represented using a <em class="parameter"><code>parents</code></em>
|
||
vector where the ID of the parent of vertex <code class="constant">v</code> is stored in <code class="literal">parents[v]</code>.
|
||
This function serves to construct an igraph graph from a parent vector representation.
|
||
The result is guaranteed to be a forest or a tree. If the <em class="parameter"><code>parents</code></em> vector
|
||
is found to encode a cycle or a self-loop, an error is raised.
|
||
|
||
</p>
|
||
<p>
|
||
Several igraph functions produce such vectors, such as graph traversal
|
||
functions (<a class="link" href="igraph-Visitors.html#igraph_bfs" title="1.1. igraph_bfs — Breadth-first search."><code class="function">igraph_bfs()</code></a> and <a class="link" href="igraph-Visitors.html#igraph_dfs" title="2.1. igraph_dfs — Depth-first search."><code class="function">igraph_dfs()</code></a>), shortest path functions
|
||
that construct a shortest path tree, as well as some other specialized
|
||
functions like <a class="link" href="igraph-Flows.html#igraph_dominator_tree" title="1.3. igraph_dominator_tree — Calculates the dominator tree of a flowgraph."><code class="function">igraph_dominator_tree()</code></a> or <a class="link" href="igraph-Flows.html#igraph_cohesive_blocks" title="6.1. igraph_cohesive_blocks — Identifies the hierarchical cohesive block structure of a graph."><code class="function">igraph_cohesive_blocks()</code></a>.
|
||
Vertices which do not have parents (i.e. roots) get a negative entry in the
|
||
<em class="parameter"><code>parents</code></em> vector.
|
||
|
||
</p>
|
||
<p>
|
||
Use <a class="link" href="igraph-Visitors.html#igraph_bfs" title="1.1. igraph_bfs — Breadth-first search."><code class="function">igraph_bfs()</code></a> or <a class="link" href="igraph-Visitors.html#igraph_dfs" title="2.1. igraph_dfs — Depth-first search."><code class="function">igraph_dfs()</code></a> to convert a forest into a parent
|
||
vector representation. For trees, i.e. forests with a single root, it is
|
||
more convenient to use <a class="link" href="igraph-Visitors.html#igraph_bfs_simple" title="1.2. igraph_bfs_simple — Breadth-first search, single-source version"><code class="function">igraph_bfs_simple()</code></a>.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>parents</code></em>:</span></p></td>
|
||
<td><p>
|
||
The parent vector. <code class="literal">parents[v]</code> is the ID of
|
||
the parent vertex of <code class="constant">v</code>. <code class="literal">parents[v] < 0</code> indicates that
|
||
<code class="constant">v</code> does not have a parent.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>type</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Constant, gives whether to create a directed tree, and
|
||
if this is the case, also its orientation. Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_OUT</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point from the parents to their children.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_IN</code></span></p></td>
|
||
<td><p>
|
||
|
||
directed tree, the edges point from the children to their parents.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_TREE_UNDIRECTED undirected tree.</code></span></p></td>
|
||
<td><p>
|
||
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Visitors.html#igraph_bfs" title="1.1. igraph_bfs — Breadth-first search."><code class="function">igraph_bfs()</code></a>, <a class="link" href="igraph-Visitors.html#igraph_bfs_simple" title="1.2. igraph_bfs_simple — Breadth-first search, single-source version"><code class="function">igraph_bfs_simple()</code></a> for back-conversion;
|
||
<a class="link" href="igraph-Generators.html#igraph_from_prufer" title="5.5. igraph_from_prufer — Generates a tree from a Prüfer sequence."><code class="function">igraph_from_prufer()</code></a> for creating trees from Prüfer sequences;
|
||
<a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree."><code class="function">igraph_is_tree()</code></a> and <a class="link" href="igraph-Structural.html#igraph_is_forest" title="16.4. igraph_is_forest — Decides whether the graph is a forest."><code class="function">igraph_is_forest()</code></a> to check if a graph
|
||
is a tree or forest.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(n) where n is the length of <em class="parameter"><code>parents</code></em>.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_from_prufer"></a>5.5. <code class="function">igraph_from_prufer</code> — Generates a tree from a Prüfer sequence.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.6.7.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_from_prufer(igraph_t *graph, const igraph_vector_int_t *prufer);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
A Prüfer sequence is a unique sequence of integers associated
|
||
with a labelled tree. A tree on <code class="literal">n</code> vertices can be represented
|
||
by a sequence of <code class="literal">n-2</code> integers, each between <code class="literal">0</code> and
|
||
<code class="literal">n-1</code> (inclusive).
|
||
|
||
The algorithm used by this function is based on
|
||
Paulius Micikevičius, Saverio Caminiti, Narsingh Deo:
|
||
Linear-time Algorithms for Encoding Trees as Sequences of Node Labels
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>prufer</code></em>:</span></p></td>
|
||
<td><p>
|
||
The Prüfer sequence
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td>
|
||
<p>
|
||
Error code:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ENOMEM</code></span></p></td>
|
||
<td><p>
|
||
|
||
there is not enough memory to perform the operation.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVAL</code></span></p></td>
|
||
<td><p>
|
||
|
||
invalid Prüfer sequence given
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Structural.html#igraph_to_prufer" title="16.5. igraph_to_prufer — Converts a tree to its Prüfer sequence."><code class="function">igraph_to_prufer()</code></a>, <a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a>, <a class="link" href="igraph-Games.html#igraph_tree_game" title="6.4. igraph_tree_game — Generates a random tree with the given number of nodes."><code class="function">igraph_tree_game()</code></a>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), where |V| is the number of vertices in the tree.
|
||
|
||
|
||
</p>
|
||
</div>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="degree-graph-generators"></a>6. Graphs with given degrees</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_realize_degree_sequence">6.1. <code class="function">igraph_realize_degree_sequence</code> — Generates a graph with the given degree sequence.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_realize_bipartite_degree_sequence">6.2. <code class="function">igraph_realize_bipartite_degree_sequence</code> — Generates a bipartite graph with the given bidegree sequence.</a></span></dt>
|
||
</dl></div>
|
||
<p>These functions generate graphs with the specified degrees.</p>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_realize_degree_sequence"></a>6.1. <code class="function">igraph_realize_degree_sequence</code> — Generates a graph with the given degree sequence.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.7.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_realize_degree_sequence(
|
||
igraph_t *graph,
|
||
const igraph_vector_int_t *outdeg, const igraph_vector_int_t *indeg,
|
||
igraph_edge_type_sw_t allowed_edge_types,
|
||
igraph_realize_degseq_t method);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
This function generates an undirected graph that realizes a given degree
|
||
sequence, or a directed graph that realizes a given pair of out- and
|
||
in-degree sequences.
|
||
|
||
</p>
|
||
<p>
|
||
Simple undirected graphs are constructed using the Havel-Hakimi algorithm
|
||
(undirected case), or the analogous Kleitman-Wang algorithm (directed case).
|
||
These algorithms work by choosing an arbitrary vertex and connecting all its
|
||
stubs to other vertices of highest degree. In the directed case, the
|
||
"highest" (in, out) degree pairs are determined based on lexicographic
|
||
ordering. This step is repeated until all degrees have been connected up.
|
||
|
||
</p>
|
||
<p>
|
||
Loopless multigraphs are generated using an analogous algorithm: an arbitrary
|
||
vertex is chosen, and it is connected with a single connection to a highest
|
||
remaining degee vertex. If self-loops are also allowed, the same algorithm
|
||
is used, but if a non-zero vertex remains at the end of the procedure, the
|
||
graph is completed by adding self-loops to it. Thus, the result will contain
|
||
at most one vertex with self-loops.
|
||
|
||
</p>
|
||
<p>
|
||
The <code class="constant">method</code> parameter controls the order in which the vertices to be
|
||
connected are chosen. In the undirected case, <code class="constant">IGRAPH_REALIZE_DEGSEQ_SMALLEST</code>
|
||
produces a connected graph when one exists. This makes this method suitable
|
||
for constructing trees with a given degree sequence.
|
||
|
||
</p>
|
||
<p>
|
||
For a undirected simple graph, the time complexity is O(V + alpha(V) * E).
|
||
For an undirected multi graph, the time complexity is O(V * E + V log V).
|
||
For a directed graph, the time complexity is O(E + V^2 log V).
|
||
|
||
</p>
|
||
<p>
|
||
References:
|
||
|
||
</p>
|
||
<p>
|
||
V. Havel:
|
||
Poznámka o existenci konečných grafů (A remark on the existence of finite graphs),
|
||
Časopis pro pěstování matematiky 80, 477-480 (1955).
|
||
<a class="ulink" href="http://eudml.org/doc/19050" target="_top">http://eudml.org/doc/19050</a>
|
||
|
||
</p>
|
||
<p>
|
||
S. L. Hakimi:
|
||
On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph,
|
||
Journal of the SIAM 10, 3 (1962).
|
||
<a class="ulink" href="https://www.jstor.org/stable/2098770" target="_top">https://www.jstor.org/stable/2098770</a>
|
||
|
||
</p>
|
||
<p>
|
||
D. J. Kleitman and D. L. Wang:
|
||
Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors,
|
||
Discrete Mathematics 6, 1 (1973).
|
||
<a class="ulink" href="https://doi.org/10.1016/0012-365X%2873%2990037-X" target="_top">https://doi.org/10.1016/0012-365X%2873%2990037-X</a>
|
||
|
||
P. L. Erdős, I. Miklós, Z. Toroczkai:
|
||
A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs,
|
||
The Electronic Journal of Combinatorics 17.1 (2010).
|
||
<a class="ulink" href="http://eudml.org/doc/227072" target="_top">http://eudml.org/doc/227072</a>
|
||
|
||
</p>
|
||
<p>
|
||
Sz. Horvát and C. D. Modes:
|
||
Connectedness matters: construction and exact random sampling of connected networks (2021).
|
||
<a class="ulink" href="https://doi.org/10.1088/2632-072X/abced5" target="_top">https://doi.org/10.1088/2632-072X/abced5</a>
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>outdeg</code></em>:</span></p></td>
|
||
<td><p>
|
||
The degree sequence of an undirected graph (if <em class="parameter"><code>indeg</code></em> is NULL),
|
||
or the out-degree sequence of a directed graph (if <em class="parameter"><code>indeg</code></em> is given).
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>indeg</code></em>:</span></p></td>
|
||
<td><p>
|
||
The in-degree sequence of a directed graph. Pass <code class="constant">NULL</code> to
|
||
generate an undirected graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
The types of edges to allow in the graph. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>. For directed graphs, only <code class="constant">IGRAPH_SIMPLE_SW</code> is
|
||
implemented at this moment.
|
||
For undirected graphs, the following values are valid:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_SIMPLE_SW</code></span></p></td>
|
||
<td><p>
|
||
|
||
simple graphs (i.e. no self-loops or multi-edges allowed).
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_SW</code></span></p></td>
|
||
<td><p>
|
||
|
||
single self-loops are allowed, but not multi-edges; currently not implemented.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_MULTI_SW</code></span></p></td>
|
||
<td><p>
|
||
|
||
multi-edges are allowed, but not self-loops.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_SW | IGRAPH_MULTI_SW</code></span></p></td>
|
||
<td><p>
|
||
|
||
both self-loops and multi-edges are allowed.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>method</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
The method to generate the graph. Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_REALIZE_DEGSEQ_SMALLEST</code></span></p></td>
|
||
<td><p>
|
||
|
||
The vertex with smallest remaining degree is selected first. The
|
||
result is usually a graph with high negative degree assortativity.
|
||
In the undirected case, this method is guaranteed to generate a
|
||
connected graph, regardless of whether multi-edges are allowed,
|
||
provided that a connected realization exists (see Horvát and Modes,
|
||
2021, as well as <a class="ulink" href="http://szhorvat.net/pelican/hh-connected-graphs.html" target="_top">http://szhorvat.net/pelican/hh-connected-graphs.html</a>).
|
||
This method can be used to construct a tree from its degrees.
|
||
In the directed case it tends to generate weakly connected graphs,
|
||
but this is not guaranteed.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_REALIZE_DEGSEQ_LARGEST</code></span></p></td>
|
||
<td><p>
|
||
|
||
The vertex with the largest remaining degree is selected first. The
|
||
result is usually a graph with high positive degree assortativity, and
|
||
is often disconnected.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_REALIZE_DEGSEQ_INDEX</code></span></p></td>
|
||
<td><p>
|
||
|
||
The vertices are selected in order of their index (i.e. their position
|
||
in the degree vector). Note that sorting the degree vector and using
|
||
the <code class="constant">INDEX</code> method is not equivalent to the <code class="constant">SMALLEST</code> method above,
|
||
as <code class="constant">SMALLEST</code> uses the smallest <span class="emphasis"><em>remaining</em></span> degree for selecting
|
||
vertices, not the smallest <span class="emphasis"><em>initial</em></span> degree.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td>
|
||
<p>
|
||
Error code:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_UNIMPLEMENTED</code></span></p></td>
|
||
<td><p>
|
||
|
||
The requested method is not implemented.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_ENOMEM</code></span></p></td>
|
||
<td><p>
|
||
|
||
There is not enough memory to perform the operation.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_EINVAL</code></span></p></td>
|
||
<td><p>
|
||
|
||
Invalid method parameter, or invalid in- and/or out-degree vectors.
|
||
The degree vectors should be non-negative, the length
|
||
and sum of <em class="parameter"><code>outdeg</code></em> and <em class="parameter"><code>indeg</code></em> should match for directed graphs.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Structural.html#igraph_is_graphical" title="10.1. igraph_is_graphical — Is there a graph with the given degree sequence?"><code class="function">igraph_is_graphical()</code></a> to test graphicality without generating a graph;
|
||
<a class="link" href="igraph-Generators.html#igraph_realize_bipartite_degree_sequence" title="6.2. igraph_realize_bipartite_degree_sequence — Generates a bipartite graph with the given bidegree sequence."><code class="function">igraph_realize_bipartite_degree_sequence()</code></a> to create bipartite graphs
|
||
from two degree sequence;
|
||
<a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence."><code class="function">igraph_degree_sequence_game()</code></a> to generate random graphs with a given
|
||
degree sequence;
|
||
<a class="link" href="igraph-Games.html#igraph_k_regular_game" title="4.2. igraph_k_regular_game — Generates a random graph where each vertex has the same degree."><code class="function">igraph_k_regular_game()</code></a> to generate random regular graphs;
|
||
<a class="link" href="igraph-Games.html#igraph_rewire" title="4.3. igraph_rewire — Randomly rewires a graph while preserving its degree sequence."><code class="function">igraph_rewire()</code></a> to randomly rewire the edges of a graph while
|
||
preserving its degree sequence.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.7.3.19.1"></a><p class="title"><b>Example 11.10. File <code class="code">examples/simple/igraph_realize_degree_sequence.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
<span class="strong"><strong>#include</strong></span> <stdio.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void){
|
||
igraph_t g1, g2, g3;
|
||
igraph_int_t nodes = 500, A = 0, power = 1, m = 1;
|
||
igraph_real_t assortativity;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_seed" title="3.3. igraph_rng_seed — Seeds a random number generator.">igraph_rng_seed</a></strong></span>(<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_default" title="2.1. igraph_rng_default — Query the default random number generator.">igraph_rng_default</a></strong></span>(), 42);
|
||
<span class="strong"><strong>printf</strong></span>("Demonstration of difference in assortativities of graphs with the same degree sequence but different linkages:\n\nInitial graph based on the Barabasi-Albert model with %" IGRAPH_PRId " nodes.\n", nodes);
|
||
|
||
<span class="emphasis"><em>/* Graph 1 generated by a randomized graph generator */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.">igraph_barabasi_game</a></strong></span>(&g1, nodes, power, m, NULL, <span class="emphasis"><em>/* outpref */</em></span> 0, A, IGRAPH_UNDIRECTED, IGRAPH_BARABASI_PSUMTREE, <span class="emphasis"><em>/* start from */</em></span> NULL);
|
||
|
||
igraph_vector_int_t degree;
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&degree, nodes);
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&g1, &degree, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_ALL, IGRAPH_NO_LOOPS);
|
||
|
||
<span class="emphasis"><em>/* Measuring assortativity of the first graph */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_assortativity_degree" title="21.3. igraph_assortativity_degree — Assortativity of a graph based on vertex degree.">igraph_assortativity_degree</a></strong></span>(&g1, &assortativity, IGRAPH_UNDIRECTED);
|
||
<span class="strong"><strong>printf</strong></span>("Assortativity of initial graph = %g\n\n", assortativity);
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g1);
|
||
|
||
<span class="emphasis"><em>/* Graph 2 (with the same degree sequence) generated by selecting vertices with the smallest degree first */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_realize_degree_sequence" title="6.1. igraph_realize_degree_sequence — Generates a graph with the given degree sequence.">igraph_realize_degree_sequence</a></strong></span>(&g2, &degree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_SMALLEST);
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_assortativity_degree" title="21.3. igraph_assortativity_degree — Assortativity of a graph based on vertex degree.">igraph_assortativity_degree</a></strong></span>(&g2, &assortativity, IGRAPH_UNDIRECTED);
|
||
<span class="strong"><strong>printf</strong></span>("Assortativity after choosing vertices with the smallest degrees first = %g\n\n", assortativity);
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g2);
|
||
|
||
<span class="emphasis"><em>/* Graph 3 (with the same degree sequence) generated by selecting vertices with the largest degree first */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_realize_degree_sequence" title="6.1. igraph_realize_degree_sequence — Generates a graph with the given degree sequence.">igraph_realize_degree_sequence</a></strong></span>(&g3, &degree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_LARGEST);
|
||
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_assortativity_degree" title="21.3. igraph_assortativity_degree — Assortativity of a graph based on vertex degree.">igraph_assortativity_degree</a></strong></span>(&g3, &assortativity, IGRAPH_UNDIRECTED);
|
||
<span class="strong"><strong>printf</strong></span>("Assortativity after choosing vertices with the largest degrees first = %g\n", assortativity);
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g3);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&degree);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_realize_bipartite_degree_sequence"></a>6.2. <code class="function">igraph_realize_bipartite_degree_sequence</code> — Generates a bipartite graph with the given bidegree sequence.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.7.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_realize_bipartite_degree_sequence(
|
||
igraph_t *graph,
|
||
const igraph_vector_int_t *degrees1, const igraph_vector_int_t *degrees2,
|
||
const igraph_edge_type_sw_t allowed_edge_types, const igraph_realize_degseq_t method
|
||
);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function generates a bipartite graph with the given bidegree sequence,
|
||
using a Havel-Hakimi-like construction algorithm. The order in which vertices
|
||
are connected up is controlled by the <em class="parameter"><code>method</code></em> parameter. When using the
|
||
<code class="constant">IGRAPH_REALIZE_DEGSEQ_SMALLEST</code> method, it is ensured that the graph will be
|
||
connected if and only if the given bidegree sequence is potentially connected.
|
||
|
||
</p>
|
||
<p>
|
||
The vertices of the graph will be ordered so that those having <em class="parameter"><code>degrees1</code></em>
|
||
come first, followed by <em class="parameter"><code>degrees2</code></em>.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>degrees1</code></em>:</span></p></td>
|
||
<td><p>
|
||
The degree sequence of the first partition.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>degrees2</code></em>:</span></p></td>
|
||
<td><p>
|
||
The degree sequence of the second partition.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
The types of edges to allow in the graph.
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_SIMPLE_SW</code></span></p></td>
|
||
<td><p>
|
||
|
||
simple graph (i.e. no multi-edges allowed).
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_MULTI_SW</code></span></p></td>
|
||
<td><p>
|
||
|
||
multi-edges are allowed
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>method</code></em>:</span></p></td>
|
||
<td>
|
||
<p>
|
||
Controls the order in which vertices are selected for connection.
|
||
Possible values:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_REALIZE_DEGSEQ_SMALLEST</code></span></p></td>
|
||
<td><p>
|
||
|
||
The vertex with smallest remaining degree is selected first, from either
|
||
partition. The result is usually a graph with high negative degree
|
||
assortativity. This method is guaranteed to generate a connected graph,
|
||
if one exists.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_REALIZE_DEGSEQ_LARGEST</code></span></p></td>
|
||
<td><p>
|
||
|
||
The vertex with the largest remaining degree is selected first, from
|
||
either parition. The result is usually a graph with high positive degree
|
||
assortativity, and is often disconnected.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">IGRAPH_REALIZE_DEGSEQ_INDEX</code></span></p></td>
|
||
<td><p>
|
||
|
||
The vertices are selected in order of their index.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p></p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Structural.html#igraph_is_bigraphical" title="10.2. igraph_is_bigraphical — Is there a bipartite graph with the given bi-degree-sequence?"><code class="function">igraph_is_bigraphical()</code></a> to test bigraphicality without generating a graph.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="complete-graph-generators"></a>7. Complete graphs</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_full">7.1. <code class="function">igraph_full</code> — Creates a full graph (complete graph).</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_full_citation">7.2. <code class="function">igraph_full_citation</code> — Creates a full citation graph (a complete directed acyclic graph).</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_full_multipartite">7.3. <code class="function">igraph_full_multipartite</code> — Creates a full multipartite graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_turan">7.4. <code class="function">igraph_turan</code> — Creates a Turán graph.</a></span></dt>
|
||
</dl></div>
|
||
<p>These functions produce single and multipartite complete graphs, as well as related graphs.</p>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_full"></a>7.1. <code class="function">igraph_full</code> — Creates a full graph (complete graph).</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.8.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_full(igraph_t *graph, igraph_int_t n, igraph_bool_t directed,
|
||
igraph_bool_t loops);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
In a full graph every possible edge is present: every vertex is
|
||
connected to every other vertex. <span class="command"><strong>igraph</strong></span> generalizes the usual
|
||
concept of complete graphs in graph theory to graphs with self-loops
|
||
as well as to directed graphs.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to create a directed graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to include self-loops.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code:
|
||
<code class="constant">IGRAPH_EINVAL</code>: invalid number of vertices.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|^2) = O(|E|),
|
||
where |V| is the number of vertices and |E| is the number of edges.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a>, <a class="link" href="igraph-Generators.html#igraph_star" title="4.1. igraph_star — Creates a star graph, every vertex connects only to the center."><code class="function">igraph_star()</code></a>, <a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a>
|
||
for creating other regular structures.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.8.3.10.1"></a><p class="title"><b>Example 11.11. File <code class="code">examples/simple/igraph_full.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
<span class="strong"><strong>#include</strong></span> <stdio.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
igraph_t graph;
|
||
igraph_int_t n_vertices = 10;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="emphasis"><em>/* Create an undirected complete graph. */</em></span>
|
||
<span class="emphasis"><em>/* Use IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS instead of true and false for better readability. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_full" title="7.1. igraph_full — Creates a full graph (complete graph).">igraph_full</a></strong></span>(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
|
||
<span class="strong"><strong>printf</strong></span>("The undirected complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n",
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&graph), <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&graph));
|
||
|
||
<span class="emphasis"><em>/* Remember to destroy the object at the end. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="emphasis"><em>/* Create a directed complete graph. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_full" title="7.1. igraph_full — Creates a full graph (complete graph).">igraph_full</a></strong></span>(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
|
||
<span class="strong"><strong>printf</strong></span>("The directed complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n",
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&graph), <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&graph));
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="emphasis"><em>/* Create an undirected complete graph with self-loops. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_full" title="7.1. igraph_full — Creates a full graph (complete graph).">igraph_full</a></strong></span>(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
|
||
<span class="strong"><strong>printf</strong></span>("The undirected complete graph on %" IGRAPH_PRId " vertices with self-loops has %" IGRAPH_PRId " edges.\n",
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&graph), <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&graph));
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="emphasis"><em>/* Create a directed graph with self-loops. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_full" title="7.1. igraph_full — Creates a full graph (complete graph).">igraph_full</a></strong></span>(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_LOOPS);
|
||
<span class="strong"><strong>printf</strong></span>("The directed complete graph on %" IGRAPH_PRId " vertices with self-loops has %" IGRAPH_PRId " edges.\n",
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&graph), <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&graph));
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&graph);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_full_citation"></a>7.2. <code class="function">igraph_full_citation</code> — Creates a full citation graph (a complete directed acyclic graph).</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.8.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_full_citation(igraph_t *graph, igraph_int_t n,
|
||
igraph_bool_t directed);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This is a directed graph, where every <code class="literal">i->j</code> edge is
|
||
present if and only if <code class="literal">j<i</code>.
|
||
If the <em class="parameter"><code>directed</code></em> argument is false then an undirected graph is
|
||
created, and it is just a complete graph.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, the result
|
||
is stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of vertices.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Whether to created a directed graph. If false an
|
||
undirected graph is created.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_full" title="7.1. igraph_full — Creates a full graph (complete graph)."><code class="function">igraph_full()</code></a>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|^2) = O(|E|),
|
||
where |V| is the number of vertices and |E| is the number of edges.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_full_multipartite"></a>7.3. <code class="function">igraph_full_multipartite</code> — Creates a full multipartite graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.8.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_full_multipartite(igraph_t *graph,
|
||
igraph_vector_int_t *types,
|
||
const igraph_vector_int_t *n,
|
||
igraph_bool_t directed,
|
||
igraph_neimode_t mode);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
A multipartite graph contains two or more types of vertices and connections
|
||
are only possible between two vertices of different types. This function
|
||
creates a complete multipartite graph.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, the graph will be
|
||
created here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>types</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an integer vector. If not a null pointer,
|
||
the type of each vertex will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an integer vector, the number of vertices
|
||
of each type.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean, whether to create a directed graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
|
||
<td><p>
|
||
A constant that gives the type of connections for
|
||
directed graphs. If <code class="constant">IGRAPH_OUT</code>, then edges point from vertices
|
||
of low-index vertices to high-index vertices; if
|
||
<code class="constant">IGRAPH_IN</code>, then the opposite direction is realized;
|
||
<code class="constant">IGRAPH_ALL</code>, then mutual edges will be created.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), linear in the number of vertices and
|
||
edges.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Bipartite.html#igraph_full_bipartite" title="2.2. igraph_full_bipartite — Creates a complete bipartite graph."><code class="function">igraph_full_bipartite()</code></a> for complete bipartite graphs,
|
||
<a class="link" href="igraph-Generators.html#igraph_turan" title="7.4. igraph_turan — Creates a Turán graph."><code class="function">igraph_turan()</code></a> for Turán graphs.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_turan"></a>7.4. <code class="function">igraph_turan</code> — Creates a Turán graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.8.6.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_turan(igraph_t *graph,
|
||
igraph_vector_int_t *types,
|
||
igraph_int_t n,
|
||
igraph_int_t r);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Turán graphs are complete multipartite graphs with the property
|
||
that the sizes of the partitions are as close to equal as possible.
|
||
|
||
</p>
|
||
<p>
|
||
The Turán graph with <em class="parameter"><code>n</code></em> vertices and <em class="parameter"><code>r</code></em> partitions is the densest
|
||
graph on <em class="parameter"><code>n</code></em> vertices that does not contain a clique of size
|
||
<code class="literal">r+1</code>.
|
||
|
||
</p>
|
||
<p>
|
||
This function generates undirected graphs. The null graph is
|
||
returned when the number of vertices is zero. A complete graph is
|
||
returned if the number of partitions is greater than the number of
|
||
vertices.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an igraph_t object, the graph will be
|
||
created here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>types</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an integer vector. If not a null pointer,
|
||
the type (partition index) of each vertex will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of vertices in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>r</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of partitions of the graph, must be
|
||
positive.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), linear in the number of vertices and
|
||
edges.
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_full_multipartite" title="7.3. igraph_full_multipartite — Creates a full multipartite graph."><code class="function">igraph_full_multipartite()</code></a> for full multipartite graphs.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="pre-defined-generators"></a>8. Pre-defined graphs</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_famous">8.1. <code class="function">igraph_famous</code> — Create a famous graph by simply providing its name.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_atlas">8.2. <code class="function">igraph_atlas</code> — Create a small graph from the <span class="quote">“<span class="quote">Graph Atlas</span>”</span>.</a></span></dt>
|
||
</dl></div>
|
||
<p>These functions return graphs from various graph collections.</p>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_famous"></a>8.1. <code class="function">igraph_famous</code> — Create a famous graph by simply providing its name.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.9.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_famous(igraph_t *graph, const char *name);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p>
|
||
The name of the graph can be simply supplied as a string.
|
||
Note that this function creates graphs which don't take any parameters,
|
||
there are separate functions for graphs with parameters, e.g. <a class="link" href="igraph-Generators.html#igraph_full" title="7.1. igraph_full — Creates a full graph (complete graph)."><code class="function">igraph_full()</code></a> for creating a full graph.
|
||
|
||
</p>
|
||
<p>
|
||
The following graphs are supported:
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Bull</code></span></p></td>
|
||
<td><p>
|
||
|
||
The bull graph, 5 vertices, 5 edges, resembles the
|
||
head of a bull if drawn properly.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Chvatal</code></span></p></td>
|
||
<td><p>
|
||
|
||
This is the smallest triangle-free graph that is
|
||
both 4-chromatic and 4-regular. According to the Grunbaum
|
||
conjecture there exists an m-regular, m-chromatic graph
|
||
with n vertices for every m>1 and n>2. The Chvatal graph
|
||
is an example for m=4 and n=12. It has 24 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Coxeter</code></span></p></td>
|
||
<td><p>
|
||
|
||
A non-Hamiltonian cubic symmetric graph with 28
|
||
vertices and 42 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Cubical</code></span></p></td>
|
||
<td><p>
|
||
|
||
The Platonic graph of the cube. A convex regular
|
||
polyhedron with 8 vertices and 12 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Diamond</code></span></p></td>
|
||
<td><p>
|
||
|
||
A graph with 4 vertices and 5 edges, resembles a
|
||
schematic diamond if drawn properly.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Dodecahedral, Dodecahedron</code></span></p></td>
|
||
<td><p>
|
||
|
||
Another Platonic solid
|
||
with 20 vertices and 30 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Folkman</code></span></p></td>
|
||
<td><p>
|
||
|
||
The semisymmetric graph with minimum number of
|
||
vertices, 20 and 40 edges. A semisymmetric graph is
|
||
regular, edge transitive and not vertex transitive.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Franklin</code></span></p></td>
|
||
<td><p>
|
||
|
||
This is a graph whose embedding to the Klein
|
||
bottle can be colored with six colors, it is a
|
||
counterexample to the necessity of the Heawood
|
||
conjecture on a Klein bottle. It has 12 vertices and 18
|
||
edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Frucht</code></span></p></td>
|
||
<td><p>
|
||
|
||
The Frucht Graph is the smallest cubical graph
|
||
whose automorphism group consists only of the identity
|
||
element. It has 12 vertices and 18 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Grotzsch, Groetzsch</code></span></p></td>
|
||
<td><p>
|
||
|
||
The Grötzsch graph is a triangle-free graph with
|
||
11 vertices, 20 edges, and chromatic number 4. It is named after
|
||
German mathematician Herbert Grötzsch, and its existence
|
||
demonstrates that the assumption of planarity is necessary in
|
||
Grötzsch's theorem that every triangle-free planar
|
||
graph is 3-colorable.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Heawood</code></span></p></td>
|
||
<td><p>
|
||
|
||
The Heawood graph is an undirected graph with 14
|
||
vertices and 21 edges. The graph is cubic, and all cycles in the
|
||
graph have six or more edges. Every smaller cubic graph has shorter
|
||
cycles, so this graph is the 6-cage, the smallest cubic graph of
|
||
girth 6.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Herschel</code></span></p></td>
|
||
<td><p>
|
||
|
||
The Herschel graph is the smallest
|
||
nonhamiltonian polyhedral graph. It is the
|
||
unique such graph on 11 nodes, and has 18 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">House</code></span></p></td>
|
||
<td><p>
|
||
|
||
The house graph is a 5-vertex, 6-edge graph, the
|
||
schematic draw of a house if drawn properly, basically a
|
||
triangle on top of a square.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">HouseX</code></span></p></td>
|
||
<td><p>
|
||
|
||
The same as the house graph with an X in the square. 5
|
||
vertices and 8 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Icosahedral, Icosahedron</code></span></p></td>
|
||
<td><p>
|
||
|
||
A Platonic solid with 12
|
||
vertices and 30 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Krackhardt_Kite</code></span></p></td>
|
||
<td><p>
|
||
|
||
A social network with 10 vertices and 18 edges.
|
||
Krackhardt, D. Assessing the Political Landscape:
|
||
Structure, Cognition, and Power in Organizations.
|
||
Admin. Sci. Quart. 35, 342-369, 1990.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Levi</code></span></p></td>
|
||
<td><p>
|
||
|
||
The graph is a 4-arc transitive cubic graph, it has
|
||
30 vertices and 45 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">McGee</code></span></p></td>
|
||
<td><p>
|
||
|
||
The McGee graph is the unique 3-regular 7-cage
|
||
graph, it has 24 vertices and 36 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Meredith</code></span></p></td>
|
||
<td><p>
|
||
|
||
The Meredith graph is a quartic graph on 70
|
||
nodes and 140 edges that is a counterexample to the conjecture that
|
||
every 4-regular 4-connected graph is Hamiltonian.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Noperfectmatching</code></span></p></td>
|
||
<td><p>
|
||
|
||
A connected graph with 16 vertices and
|
||
27 edges containing no perfect matching. A matching in a graph
|
||
is a set of pairwise non-incident edges; that is, no two edges
|
||
share a common vertex. A perfect matching is a matching
|
||
which covers all vertices of the graph.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Nonline</code></span></p></td>
|
||
<td><p>
|
||
|
||
A graph whose connected components are the 9
|
||
graphs whose presence as a vertex-induced subgraph in a
|
||
graph makes a nonline graph. It has 50 vertices and 72 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Octahedral, Octahedron</code></span></p></td>
|
||
<td><p>
|
||
|
||
Platonic solid with 6
|
||
vertices and 12 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Petersen</code></span></p></td>
|
||
<td><p>
|
||
|
||
A 3-regular graph with 10 vertices and 15 edges. It is
|
||
the smallest hypohamiltonian graph, i.e. it is
|
||
non-hamiltonian but removing any single vertex from it makes it
|
||
Hamiltonian.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Robertson</code></span></p></td>
|
||
<td><p>
|
||
|
||
The unique (4,5)-cage graph, i.e. a 4-regular
|
||
graph of girth 5. It has 19 vertices and 38 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Smallestcyclicgroup</code></span></p></td>
|
||
<td><p>
|
||
|
||
A smallest nontrivial graph
|
||
whose automorphism group is cyclic. It has 9 vertices and
|
||
15 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Tetrahedral, Tetrahedron</code></span></p></td>
|
||
<td><p>
|
||
|
||
Platonic solid with 4
|
||
vertices and 6 edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Thomassen</code></span></p></td>
|
||
<td><p>
|
||
|
||
The smallest hypotraceable graph,
|
||
on 34 vertices and 52 edges. A hypotracable graph does
|
||
not contain a Hamiltonian path but after removing any
|
||
single vertex from it the remainder always contains a
|
||
Hamiltonian path. A graph containing a Hamiltonian path
|
||
is called traceable.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Tutte</code></span></p></td>
|
||
<td><p>
|
||
|
||
Tait's Hamiltonian graph conjecture states that
|
||
every 3-connected 3-regular planar graph is Hamiltonian.
|
||
This graph is a counterexample. It has 46 vertices and 69
|
||
edges.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Uniquely3colorable</code></span></p></td>
|
||
<td><p>
|
||
|
||
Returns a 12-vertex, triangle-free
|
||
graph with chromatic number 3 that is uniquely
|
||
3-colorable.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Walther</code></span></p></td>
|
||
<td><p>
|
||
|
||
An identity graph with 25 vertices and 31
|
||
edges. An identity graph has a single graph automorphism,
|
||
the trivial one.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">Zachary</code></span></p></td>
|
||
<td><p>
|
||
|
||
Social network of friendships between 34 members of a
|
||
karate club at a US university in the 1970s. See
|
||
W. W. Zachary, An information flow model for conflict and
|
||
fission in small groups, Journal of Anthropological
|
||
Research 33, 452-473 (1977).
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>name</code></em>:</span></p></td>
|
||
<td><p>
|
||
Character constant, the name of the graph to be
|
||
created, it is case insensitive.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code, <code class="constant">IGRAPH_EINVAL</code> if there is no graph with the
|
||
given name.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Other functions for creating graph structures:
|
||
<a class="link" href="igraph-Generators.html#igraph_ring" title="4.7. igraph_ring — Creates a cycle graph or a path graph."><code class="function">igraph_ring()</code></a>, <a class="link" href="igraph-Generators.html#igraph_kary_tree" title="5.1. igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children."><code class="function">igraph_kary_tree()</code></a>, <a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a>,
|
||
<a class="link" href="igraph-Generators.html#igraph_full" title="7.1. igraph_full — Creates a full graph (complete graph)."><code class="function">igraph_full()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the number of vertices plus the number
|
||
of edges in the graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_atlas"></a>8.2. <code class="function">igraph_atlas</code> — Create a small graph from the <span class="quote">“<span class="quote">Graph Atlas</span>”</span>.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.9.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_atlas(igraph_t *graph, igraph_int_t number);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
The graph atlas contains all simple undirected unlabeled graphs on between
|
||
0 and 7 vertices. The number of the graph is given as a parameter.
|
||
The graphs are listed:
|
||
</p>
|
||
<div class="orderedlist"><ol class="orderedlist" type="1">
|
||
<li class="listitem"><p>
|
||
in increasing order of number of vertices;
|
||
|
||
</p></li>
|
||
<li class="listitem"><p>
|
||
for a fixed number of vertices, in increasing order of the
|
||
number of edges;
|
||
|
||
</p></li>
|
||
<li class="listitem"><p>
|
||
for fixed numbers of vertices and edges, in lexicographically
|
||
increasing order of the degree sequence, for example
|
||
111223 < 112222;
|
||
|
||
</p></li>
|
||
<li class="listitem"><p>
|
||
for fixed degree sequence, in increasing number of
|
||
automorphisms.
|
||
|
||
</p></li>
|
||
</ol></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p>
|
||
The data was converted from the NetworkX software package,
|
||
see <a class="ulink" href="https://networkx.org/" target="_top">https://networkx.org/</a>.
|
||
|
||
</p>
|
||
<p>
|
||
See <span class="emphasis"><em> An Atlas of Graphs </em></span> by Ronald C. Read and Robin J. Wilson,
|
||
Oxford University Press, 1998.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>number</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of the graph to generate. Must be between 0 and
|
||
1252 (inclusive). Graphs on 0-7 vertices start at numbers 0, 1, 2, 4,
|
||
8, 19, 53, and 209, respectively.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Added in version 0.2.
|
||
|
||
</p>
|
||
<p>
|
||
Time complexity: O(|V|+|E|), the number of vertices plus the number of
|
||
edges.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.12.9.4.11.1"></a><p class="title"><b>Example 11.12. File <code class="code">examples/simple/igraph_atlas.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
igraph_t g;
|
||
|
||
<span class="emphasis"><em>/* Initialize the library. */</em></span>
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_atlas" title="8.2. igraph_atlas — Create a small graph from the “Graph Atlas”.">igraph_atlas</a></strong></span>(&g, 45);
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_write_graph_edgelist" title="1.2. igraph_write_graph_edgelist — Writes the edge list of a graph to a file.">igraph_write_graph_edgelist</a></strong></span>(&g, stdout);
|
||
<span class="strong"><strong>printf</strong></span>("\n");
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_atlas" title="8.2. igraph_atlas — Create a small graph from the “Graph Atlas”.">igraph_atlas</a></strong></span>(&g, 0);
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_write_graph_edgelist" title="1.2. igraph_write_graph_edgelist — Writes the edge list of a graph to a file.">igraph_write_graph_edgelist</a></strong></span>(&g, stdout);
|
||
<span class="strong"><strong>printf</strong></span>("\n");
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_atlas" title="8.2. igraph_atlas — Create a small graph from the “Graph Atlas”.">igraph_atlas</a></strong></span>(&g, 1252);
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_write_graph_edgelist" title="1.2. igraph_write_graph_edgelist — Writes the edge list of a graph to a file.">igraph_write_graph_edgelist</a></strong></span>(&g, stdout);
|
||
<span class="strong"><strong>printf</strong></span>("\n");
|
||
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&g);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<p>
|
||
</p>
|
||
</div>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="other-generators"></a>9. Other well-known graphs from graph theory</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_de_bruijn">9.1. <code class="function">igraph_de_bruijn</code> — Generate a de Bruijn graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_kautz">9.2. <code class="function">igraph_kautz</code> — Generate a Kautz graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_generalized_petersen">9.3. <code class="function">igraph_generalized_petersen</code> — Creates a Generalized Petersen graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Generators.html#igraph_mycielski_graph">9.4. <code class="function">igraph_mycielski_graph</code> — The Mycielski graph of order <em class="parameter"><code>k</code></em>.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_de_bruijn"></a>9.1. <code class="function">igraph_de_bruijn</code> — Generate a de Bruijn graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.10.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_de_bruijn(igraph_t *graph, igraph_int_t m, igraph_int_t n);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
A de Bruijn graph represents relationships between strings. An alphabet
|
||
of <code class="constant">m</code> letters are used and strings of length <code class="constant">n</code> are considered.
|
||
A vertex corresponds to every possible string and there is a directed edge
|
||
from vertex <code class="constant">v</code> to vertex <code class="constant">w</code> if the string of <code class="constant">v</code> can be transformed into
|
||
the string of <code class="constant">w</code> by removing its first letter and appending a letter to it.
|
||
|
||
</p>
|
||
<p>
|
||
Please note that the graph will have <code class="constant">m</code> to the power <code class="constant">n</code> vertices and
|
||
even more edges, so probably you don't want to supply too big numbers for
|
||
<code class="constant">m</code> and <code class="constant">n</code>.
|
||
|
||
</p>
|
||
<p>
|
||
De Bruijn graphs have some interesting properties, please see another source,
|
||
e.g. Wikipedia for details.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, the result will be
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the number of letters in the alphabet.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the length of the strings.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_kautz" title="9.2. igraph_kautz — Generate a Kautz graph."><code class="function">igraph_kautz()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_kautz"></a>9.2. <code class="function">igraph_kautz</code> — Generate a Kautz graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.10.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_kautz(igraph_t *graph, igraph_int_t m, igraph_int_t n);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
A Kautz graph is a labeled graph, vertices are labeled by strings
|
||
of length <code class="constant">n</code>+1 above an alphabet with <code class="constant">m</code>+1 letters, with
|
||
the restriction that every two consecutive letters in the string
|
||
must be different. There is a directed edge from a vertex <code class="constant">v</code> to
|
||
another vertex <code class="constant">w</code> if it is possible to transform the string of
|
||
<code class="constant">v</code> into the string of <code class="constant">w</code> by removing the first letter and
|
||
appending a letter to it. For string length 1 the new letter
|
||
cannot equal the old letter, so there are no loops.
|
||
|
||
</p>
|
||
<p>
|
||
Kautz graphs have some interesting properties, see e.g. Wikipedia
|
||
for details.
|
||
|
||
</p>
|
||
<p>
|
||
Vincent Matossian wrote the first version of this function in R,
|
||
thanks.
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, the result
|
||
will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, <code class="constant">m</code>+1 is the number of letters in the alphabet.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, <code class="constant">n</code>+1 is the length of the strings.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_de_bruijn" title="9.1. igraph_de_bruijn — Generate a de Bruijn graph."><code class="function">igraph_de_bruijn()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|* [(m+1)/m]^n +|E|), in practice it is more
|
||
like O(|V|+|E|). |V| is the number of vertices, |E| is the number
|
||
of edges and <code class="constant">m</code> and <code class="constant">n</code> are the corresponding arguments.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_generalized_petersen"></a>9.3. <code class="function">igraph_generalized_petersen</code> — Creates a Generalized Petersen graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.10.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_generalized_petersen(igraph_t *graph, igraph_int_t n, igraph_int_t k);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
The generalized Petersen graph <code class="literal">G(n, k)</code> consists of <em class="parameter"><code>n</code></em> vertices
|
||
<code class="constant">v_0</code>, ..., <code class="constant">v_n</code> forming an "outer" cycle graph, and <em class="parameter"><code>n</code></em> additional vertices
|
||
<code class="constant">u_0</code>, ..., <code class="constant">u_n</code> forming an "inner" circulant graph where <code class="literal">u_i</code>
|
||
is connected to <code class="literal">u_(i + k mod n)</code>. Additionally, all <code class="constant">v_i</code> are
|
||
connected to <code class="constant">u_i</code>.
|
||
|
||
</p>
|
||
<p>
|
||
<code class="literal">G(n, k)</code> has <code class="constant">2n</code> vertices and <code class="constant">3n</code> edges. The Petersen graph
|
||
itself is <code class="literal">G(5, 2)</code>.
|
||
|
||
</p>
|
||
<p>
|
||
Reference:
|
||
|
||
</p>
|
||
<p>
|
||
M. E. Watkins,
|
||
A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs,
|
||
Journal of Combinatorial Theory 6, 152-164 (1969).
|
||
<a class="ulink" href="https://doi.org/10.1016%2FS0021-9800%2869%2980116-X" target="_top">https://doi.org/10.1016%2FS0021-9800%2869%2980116-X</a>
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object, the result will
|
||
be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, <code class="constant">n</code> is the number of vertices in the inner and outer
|
||
cycle/circulant graphs. It must be at least 3.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>k</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, <code class="constant">k</code> is the shift of the circulant graph. It must be
|
||
positive and less than <code class="literal">n/2</code>.
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Generators.html#igraph_famous" title="8.1. igraph_famous — Create a famous graph by simply providing its name."><code class="function">igraph_famous()</code></a> for the original Petersen graph.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|), the number of vertices in the graph.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_mycielski_graph"></a>9.4. <code class="function">igraph_mycielski_graph</code> — The Mycielski graph of order <em class="parameter"><code>k</code></em>.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.12.10.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_mycielski_graph(igraph_t *graph, igraph_int_t k);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
The Mycielski graph of order <em class="parameter"><code>k</code></em>, denoted <code class="constant">M_k</code>, is a triangle-free graph on
|
||
<em class="parameter"><code>k</code></em> vertices with chromatic number <em class="parameter"><code>k</code></em>. It is defined through the Mycielski
|
||
construction described in the documentation of <a class="link" href="igraph-Operators.html#igraph_mycielskian" title="3.10. igraph_mycielskian — Generate the Mycielskian of a graph with k iterations."><code class="function">igraph_mycielskian()</code></a>.
|
||
|
||
</p>
|
||
<p>
|
||
Some authors define Mycielski graphs only for <code class="literal">k > 1</code>.
|
||
igraph extends this to all <code class="literal">k >= 0</code>.
|
||
The first few Mycielski graphs are:
|
||
</p>
|
||
<div class="orderedlist"><ol class="orderedlist" type="1">
|
||
<li class="listitem"><p>
|
||
M_0: Null graph
|
||
|
||
</p></li>
|
||
<li class="listitem"><p>
|
||
M_1: Single vertex
|
||
|
||
</p></li>
|
||
<li class="listitem"><p>
|
||
M_2: Path graph with 2 vertices
|
||
|
||
</p></li>
|
||
<li class="listitem"><p>
|
||
M_3: Cycle graph with 5 vertices
|
||
|
||
</p></li>
|
||
<li class="listitem"><p>
|
||
M_4: Grötzsch graph (a triangle-free graph with chromatic number 4)
|
||
|
||
</p></li>
|
||
</ol></div>
|
||
<p>
|
||
|
||
The vertex count of <code class="constant">M_k</code> is
|
||
<code class="literal">n_k = 3 * 2^(k-2) - 1</code> for <code class="literal">k > 1</code> and <code class="constant">k</code> otherwise.
|
||
The edge count is
|
||
<code class="literal">m_k = (7 * 3^(k-2) + 1) / 2 - 3 * 2^(k - 2)</code> for <code class="literal">k > 1</code>
|
||
and 0 otherwise.
|
||
|
||
</p>
|
||
<p><b>Arguments: </b>
|
||
</p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph object. The generated
|
||
Mycielski graph will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>k</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the order of the Mycielski graph (must be non-negative).
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
</p>
|
||
<p><b>Returns: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
Error code.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p><b>See also: </b></p>
|
||
<div class="variablelist"><table border="0" class="variablelist">
|
||
<colgroup>
|
||
<col align="left" valign="top">
|
||
<col>
|
||
</colgroup>
|
||
<tbody><tr>
|
||
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
|
||
<td><p>
|
||
<a class="link" href="igraph-Operators.html#igraph_mycielskian" title="3.10. igraph_mycielskian — Generate the Mycielskian of a graph with k iterations."><code class="function">igraph_mycielskian()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(3^k), i.e. exponential in <em class="parameter"><code>k</code></em>.
|
||
|
||
</p>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
<table class="navigation-footer" width="100%" summary="Navigation footer" cellpadding="2" cellspacing="0"><tr valign="middle">
|
||
<td align="left"><a accesskey="p" href="igraph-Attributes.html"><b>← Chapter 10. Graph, vertex and edge attributes</b></a></td>
|
||
<td align="right"><a accesskey="n" href="igraph-Games.html"><b>Chapter 12. Stochastic graph generators ("games") →</b></a></td>
|
||
</tr></table>
|
||
</body>
|
||
</html>
|