Abdelrahman Said
1446 lines
62 KiB
HTML
1446 lines
62 KiB
HTML
<html>
|
||
<head>
|
||
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
|
||
<title>Chapter 20. Graph motifs, dyad census and triad census</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-Cliques.html" title="Chapter 19. Cliques and independent vertex sets">
|
||
<link rel="next" href="igraph-Isomorphism.html" title="Chapter 21. Graph isomorphism">
|
||
<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-Cliques.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-Isomorphism.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-Motifs"></a>Chapter 20. Graph motifs, dyad census and triad census</h1></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_dyad_census">1. <code class="function">igraph_dyad_census</code> — Dyad census, as defined by Holland and Leinhardt.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_triad_census">2. <code class="function">igraph_triad_census</code> — Triad census, as defined by Davis and Leinhardt.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#finding-triangles">3. Finding triangles</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#graph-motifs">4. Graph motifs</a></span></dt>
|
||
</dl></div>
|
||
<p>
|
||
This section deals with functions which find small induced subgraphs in a
|
||
graph. These were first defined for subgraphs of two and three vertices
|
||
by Holland and Leinhardt, and named dyad census and triad census.
|
||
</p>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="igraph_dyad_census"></a>1. <code class="function">igraph_dyad_census</code> — Dyad census, as defined by Holland and Leinhardt.</h2></div></div></div>
|
||
<a class="indexterm" name="id-1.21.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_dyad_census(const igraph_t *graph, igraph_real_t *mut,
|
||
igraph_real_t *asym, igraph_real_t *null);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Dyad census means classifying each pair of vertices of a directed
|
||
graph into three categories: mutual (there is at least one edge from
|
||
<code class="constant">a</code> to <code class="constant">b</code> and also from <code class="constant">b</code> to <code class="constant">a</code>); asymmetric (there is at least
|
||
one edge either from <code class="constant">a</code> to <code class="constant">b</code> or from <code class="constant">b</code> to <code class="constant">a</code>, but not the other
|
||
way) and null (no edges between <code class="constant">a</code> and <code class="constant">b</code> in either direction).
|
||
|
||
</p>
|
||
<p>
|
||
Holland, P.W. and Leinhardt, S. (1970). A Method for Detecting
|
||
Structure in Sociometric Data. American Journal of Sociology,
|
||
70, 492-513.
|
||
|
||
</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>
|
||
The input graph. For an undirected graph, there are no
|
||
asymmetric connections.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mut</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real, the number of mutual dyads is
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>asym</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real, the number of asymmetric dyads
|
||
is stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>null</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real, the number of null dyads is
|
||
stored here.
|
||
</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_reciprocity" title="26.3. igraph_reciprocity — Calculates the reciprocity of a directed graph."><code class="function">igraph_reciprocity()</code></a>, <a class="link" href="igraph-Motifs.html#igraph_triad_census" title="2. igraph_triad_census — Triad census, as defined by Davis and Leinhardt."><code class="function">igraph_triad_census()</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><h2 class="title" style="clear: both">
|
||
<a name="igraph_triad_census"></a>2. <code class="function">igraph_triad_census</code> — Triad census, as defined by Davis and Leinhardt.</h2></div></div></div>
|
||
<a class="indexterm" name="id-1.21.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_triad_census(const igraph_t *graph, igraph_vector_t *res);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Calculating the triad census means classifying every triple of
|
||
vertices in a directed graph based on the type of pairwise
|
||
connections it contains, i.e. mutual, asymmetric or no connection.
|
||
A triple can be in one of 16 states, commonly described using
|
||
Davis and Leinhardt's "MAN labels". The <em class="parameter"><code>res</code></em> vector will
|
||
contain the counts of these in the following order:
|
||
|
||
</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"> 0: 003</code></span></p></td>
|
||
<td><p>
|
||
|
||
A, B, C, the empty graph.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 1: 012</code></span></p></td>
|
||
<td><p>
|
||
|
||
A->B, C, a graph with a single directed edge.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 2: 102</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<->B, C, a graph with a mutual connection between two vertices.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 3: 021D</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<-B->C, the binary out-tree.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 4: 021U</code></span></p></td>
|
||
<td><p>
|
||
|
||
A->B<-C, the binary in-tree.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 5: 021C</code></span></p></td>
|
||
<td><p>
|
||
|
||
A->B->C, the directed line.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 6: 111D</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<->B<-C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 7: 111U</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<->B->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 8: 030T</code></span></p></td>
|
||
<td><p>
|
||
|
||
A->B<-C, A->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant"> 9: 030C</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<-B<-C, A->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">10: 201</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<->B<->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">11: 120D</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<-B->C, A<->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">12: 120U</code></span></p></td>
|
||
<td><p>
|
||
|
||
A->B<-C, A<->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">13: 120C</code></span></p></td>
|
||
<td><p>
|
||
|
||
A->B->C, A<->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">14: 210</code></span></p></td>
|
||
<td><p>
|
||
|
||
A->B<->C, A<->C.
|
||
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><code class="constant">15: 300</code></span></p></td>
|
||
<td><p>
|
||
|
||
A<->B<->C, A<->C, the complete graph.
|
||
|
||
</p></td>
|
||
</tr>
|
||
</tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<p>
|
||
This function is intended for directed graphs. If the input is undirected,
|
||
a warning is shown, and undirected edges will be interpreted as mutual.
|
||
|
||
</p>
|
||
<p>
|
||
This function calls <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a> which is an
|
||
implementation of the FANMOD motif finder tool, see <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a> for details. Note that the order of the
|
||
triads is not the same for <a class="link" href="igraph-Motifs.html#igraph_triad_census" title="2. igraph_triad_census — Triad census, as defined by Davis and Leinhardt."><code class="function">igraph_triad_census()</code></a> and <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a>.
|
||
|
||
</p>
|
||
<p>
|
||
References:
|
||
|
||
</p>
|
||
<p>
|
||
Davis, J.A. and Leinhardt, S. (1972). The Structure of
|
||
Positive Interpersonal Relations in Small Groups. In J. Berger
|
||
(Ed.), Sociological Theories in Progress, Volume 2, 218-251.
|
||
Boston: Houghton Mifflin.
|
||
|
||
</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>
|
||
The input graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>res</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector, the result is stored
|
||
here in the same order as given in the list above. Note that this
|
||
order is different than the one used by <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a>.
|
||
</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-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a>, <a class="link" href="igraph-Motifs.html#igraph_dyad_census" title="1. igraph_dyad_census — Dyad census, as defined by Holland and Leinhardt."><code class="function">igraph_dyad_census()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: TODO.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="finding-triangles"></a>3. Finding triangles</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_count_adjacent_triangles">3.1. <code class="function">igraph_count_adjacent_triangles</code> — Count the number of triangles a vertex is part of.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_count_triangles">3.2. <code class="function">igraph_count_triangles</code> — Counts triangles in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_list_triangles">3.3. <code class="function">igraph_list_triangles</code> — Find all triangles in a graph.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_count_adjacent_triangles"></a>3.1. <code class="function">igraph_count_adjacent_triangles</code> — Count the number of triangles a vertex is part of.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.5.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_count_adjacent_triangles(const igraph_t *graph,
|
||
igraph_vector_t *res,
|
||
const igraph_vs_t vids);
|
||
</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>
|
||
The input graph. Edge directions and multiplicities are ignored.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>res</code></em>:</span></p></td>
|
||
<td><p>
|
||
Initiliazed vector, the results are stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>vids</code></em>:</span></p></td>
|
||
<td><p>
|
||
The vertices to perform the calculation for.
|
||
</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 mode.
|
||
</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-Motifs.html#igraph_list_triangles" title="3.3. igraph_list_triangles — Find all triangles in a graph."><code class="function">igraph_list_triangles()</code></a> to list triangles,
|
||
<a class="link" href="igraph-Motifs.html#igraph_count_triangles" title="3.2. igraph_count_triangles — Counts triangles in a graph."><code class="function">igraph_count_triangles()</code></a> to count all triangles at once.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(d^2 n), d is the average vertex degree of the
|
||
queried vertices, n is their number.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_count_triangles"></a>3.2. <code class="function">igraph_count_triangles</code> — Counts triangles in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.5.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_count_triangles(const igraph_t *graph, igraph_real_t *res);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
|
||
This function computes the total number of triangles, i.e. fully connected
|
||
vertex triples, in a graph. Edge directions, edge multiplicities, and self-loops
|
||
are ignored.
|
||
|
||
</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>
|
||
The graph object. Edge directions and multiplicites are ignored.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>res</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real variable, the result will be stored here.
|
||
</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_ENOMEM</code>: not enough memory for
|
||
temporary data.
|
||
</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-Motifs.html#igraph_list_triangles" title="3.3. igraph_list_triangles — Find all triangles in a graph."><code class="function">igraph_list_triangles()</code></a>, <a class="link" href="igraph-Motifs.html#igraph_count_adjacent_triangles" title="3.1. igraph_count_adjacent_triangles — Count the number of triangles a vertex is part of."><code class="function">igraph_count_adjacent_triangles()</code></a>,
|
||
<a class="link" href="igraph-Structural.html#igraph_transitivity_undirected" title="17.1. igraph_transitivity_undirected — Calculates the transitivity (clustering coefficient) of a graph."><code class="function">igraph_transitivity_undirected()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(|V|*d^2), |V| is the number of vertices in
|
||
the graph, d is the average node degree.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_list_triangles"></a>3.3. <code class="function">igraph_list_triangles</code> — Find all triangles in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.5.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_list_triangles(const igraph_t *graph,
|
||
igraph_vector_int_t *res);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p>
|
||
The triangles are reported as a long list of vertex ID triplets. Use
|
||
the <code class="constant">int</code> variant of <a class="link" href="igraph-Data-structures.html#igraph_matrix_view_from_vector" title="3.5.2. igraph_matrix_view_from_vector — Creates a matrix view that treats an existing vector as a matrix."><code class="function">igraph_matrix_view_from_vector()</code></a> to create a
|
||
matrix view into the vector where each triangle is stored in a column of the
|
||
matrix (see the example).
|
||
|
||
</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>
|
||
The input graph, edge directions are ignored.
|
||
Multiple edges are ignored.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>res</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized integer vector, the result
|
||
is stored here, in a long list of triples of vertex IDs.
|
||
Each triple is a triangle in the graph. Each triangle is
|
||
listed exactly once.
|
||
</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-Motifs.html#igraph_count_triangles" title="3.2. igraph_count_triangles — Counts triangles in a graph."><code class="function">igraph_count_triangles()</code></a> to count the triangles,
|
||
<a class="link" href="igraph-Motifs.html#igraph_count_adjacent_triangles" title="3.1. igraph_count_adjacent_triangles — Count the number of triangles a vertex is part of."><code class="function">igraph_count_adjacent_triangles()</code></a> to count the triangles a vertex
|
||
participates in, <a class="link" href="igraph-Structural.html#igraph_transitivity_undirected" title="17.1. igraph_transitivity_undirected — Calculates the transitivity (clustering coefficient) of a graph."><code class="function">igraph_transitivity_undirected()</code></a> to compute
|
||
the global clustering coefficient.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(d^2 n), d is the average degree, n is the number
|
||
of vertices.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.21.5.4.11.1"></a><p class="title"><b>Example 20.1. File <code class="code">examples/simple/igraph_list_triangles.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 v;
|
||
|
||
<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_full" title="7.1. igraph_full — Creates a full graph (complete graph).">igraph_full</a></strong></span>(&g, 5, 0, IGRAPH_NO_LOOPS);
|
||
|
||
<span class="strong"><strong>printf</strong></span>("Triangles in a full graph of 5 vertices:\n");
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&v, 0);
|
||
<span class="strong"><strong><a class="link" href="igraph-Motifs.html#igraph_list_triangles" title="3.3. igraph_list_triangles — Find all triangles in a graph.">igraph_list_triangles</a></strong></span>(&g, &v);
|
||
|
||
<span class="strong"><strong>const</strong></span> igraph_matrix_int_t result = <span class="strong"><strong>igraph_matrix_int_view_from_vector</strong></span>(&v, <span class="emphasis"><em>/* nrow = */</em></span> 3);
|
||
<span class="strong"><strong>igraph_matrix_int_print</strong></span>(&result);
|
||
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&v);
|
||
<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="graph-motifs"></a>4. Graph motifs</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_motifs_randesu">4.1. <code class="function">igraph_motifs_randesu</code> — Count the number of motifs in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_motifs_randesu_no">4.2. <code class="function">igraph_motifs_randesu_no</code> — Count the total number of motifs in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_motifs_randesu_estimate">4.3. <code class="function">igraph_motifs_randesu_estimate</code> — Estimate the total number of motifs in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_motifs_randesu_callback">4.4. <code class="function">igraph_motifs_randesu_callback</code> — Finds motifs in a graph and calls a function for each of them.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Motifs.html#igraph_motifs_handler_t">4.5. <code class="function">igraph_motifs_handler_t</code> — Callback type for <code class="constant">igraph_motifs_randesu_callback</code>.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_motifs_randesu"></a>4.1. <code class="function">igraph_motifs_randesu</code> — Count the number of motifs in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.6.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_motifs_randesu(const igraph_t *graph, igraph_vector_t *hist,
|
||
igraph_int_t size, const igraph_vector_t *cut_prob);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p>
|
||
Motifs are small weakly connected induced subgraphs of a given structure in a
|
||
graph. It is argued that the motif profile (i.e. the number of
|
||
different motifs in the graph) is characteristic for different
|
||
types of networks and network function is related to the motifs in
|
||
the graph.
|
||
|
||
</p>
|
||
<p>
|
||
This function is able to find directed motifs of sizes three
|
||
and four and undirected motifs of sizes three to six
|
||
(i.e. the number of different subgraphs with three to six
|
||
vertices in the network).
|
||
|
||
</p>
|
||
<p>
|
||
In a big network the total number of motifs can be very large, so
|
||
it takes a lot of time to find all of them. In this case, a sampling
|
||
method can be used. This function is capable of doing sampling via the
|
||
<em class="parameter"><code>cut_prob</code></em> argument. This argument gives the probability that
|
||
a branch of the motif search tree will not be explored. See
|
||
S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif
|
||
detection, Bioinformatics 22(9), 1152--1153, 2006 for details.
|
||
<a class="ulink" href="https://doi.org/10.1093/bioinformatics/btl038" target="_top">https://doi.org/10.1093/bioinformatics/btl038</a>
|
||
|
||
</p>
|
||
<p>
|
||
Set the <em class="parameter"><code>cut_prob</code></em> argument to a zero vector for finding all
|
||
motifs.
|
||
|
||
</p>
|
||
<p>
|
||
Directed motifs will be counted in directed graphs and undirected
|
||
motifs in undirected 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>
|
||
The graph to find the motifs in.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>hist</code></em>:</span></p></td>
|
||
<td><p>
|
||
The result of the computation, it gives the number of
|
||
motifs found for each isomorphism class. See
|
||
<a class="link" href="igraph-Isomorphism.html#igraph_isoclass" title="5.1. igraph_isoclass — Determine the isomorphism class of small graphs."><code class="function">igraph_isoclass()</code></a> for help about isomorphism classes.
|
||
Note that this function does <span class="emphasis"><em>not</em></span> count isomorphism
|
||
classes that are not connected and will report NaN (more
|
||
precisely <code class="constant">IGRAPH_NAN</code>) for them.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>size</code></em>:</span></p></td>
|
||
<td><p>
|
||
The size of the motifs to search for. For directed graphs,
|
||
only 3 and 4 are implemented, for undirected, 3 to 6.
|
||
The limitation is not in the motif finding code, but the graph
|
||
isomorphism code.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cut_prob</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector of probabilities for cutting the search tree
|
||
at a given level. The first element is the first level, etc.
|
||
To perform a complete search and find all motifs, supply
|
||
either an all-zero vector of length <em class="parameter"><code>size</code></em>, or (since
|
||
igraph 0.10.14) a <code class="constant">NULL</code> pointer.
|
||
</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-Motifs.html#igraph_motifs_randesu_estimate" title="4.3. igraph_motifs_randesu_estimate — Estimate the total number of motifs in a graph."><code class="function">igraph_motifs_randesu_estimate()</code></a> for estimating the number
|
||
of motifs in a graph, this can help to set the <em class="parameter"><code>cut_prob</code></em>
|
||
parameter; <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_no" title="4.2. igraph_motifs_randesu_no — Count the total number of motifs in a graph."><code class="function">igraph_motifs_randesu_no()</code></a> to calculate the total
|
||
number of motifs of a given size in a graph;
|
||
<a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_callback" title="4.4. igraph_motifs_randesu_callback — Finds motifs in a graph and calls a function for each of them."><code class="function">igraph_motifs_randesu_callback()</code></a> for calling a callback function
|
||
for every motif found; <a class="link" href="igraph-Isomorphism.html#igraph_subisomorphic_lad" title="4.1. igraph_subisomorphic_lad — Check subgraph isomorphism with the LAD algorithm"><code class="function">igraph_subisomorphic_lad()</code></a> for finding
|
||
subgraphs on more than 4 (directed) or 6 (undirected) vertices;
|
||
<a class="link" href="igraph-Isomorphism.html#igraph_graph_count" title="5.4. igraph_graph_count — The number of unlabelled graphs on the given number of vertices."><code class="function">igraph_graph_count()</code></a> to find the number of graph on a given
|
||
number of vertices, i.e. the length of the <em class="parameter"><code>hist</code></em> vector.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: TODO.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.21.6.2.15.1"></a><p class="title"><b>Example 20.2. File <code class="code">examples/simple/igraph_motifs_randesu.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
<span class="emphasis"><em>/* This is a callback function suitable for use with igraph_motifs_randesu_callback().</em></span>
|
||
<span class="emphasis"><em> * It prints each motif it is calld with. */</em></span>
|
||
<a class="link" href="igraph-Error.html#igraph_error_t" title="3.1. igraph_error_t — Return type for functions returning an error code.">igraph_error_t</a> <span class="strong"><strong>print_motif</strong></span>(<span class="strong"><strong>const</strong></span> igraph_t *graph, <span class="strong"><strong>const</strong></span> igraph_vector_int_t *vids,
|
||
igraph_int_t isoclass, void* extra) {
|
||
<span class="strong"><strong>printf</strong></span>("Found isoclass %2" IGRAPH_PRId ": ", isoclass);
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(vids);
|
||
<span class="strong"><strong>return</strong></span> IGRAPH_SUCCESS; <span class="emphasis"><em>/* Return 'IGRAPH_SUCCESS': do not interrupt the search. */</em></span>
|
||
}
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
|
||
igraph_t graph;
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> hist;
|
||
|
||
<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>/* Compute the 4-motif distritbuion in Zachary's karate club network. */</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>(&graph, "Zachary");
|
||
<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>(&hist, 0);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph.">igraph_motifs_randesu</a></strong></span>(&graph, &hist, 4, NULL);
|
||
|
||
<span class="emphasis"><em>/* Compute the total number of motifs (connected 4-vertex subgraphs)</em></span>
|
||
<span class="emphasis"><em> * so that we can print the normalized distribution. */</em></span>
|
||
igraph_real_t sum = 0.0;
|
||
igraph_int_t n = <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_size" title="2.11.2. igraph_vector_size — The size of the vector.">igraph_vector_size</a></strong></span>(&hist);
|
||
<span class="strong"><strong>for</strong></span> (igraph_int_t i=0; i < n; i++) {
|
||
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong>isnan</strong></span>(<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>(hist)[i])) {
|
||
sum += <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>(hist)[i];
|
||
}
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("4-motif distribution:\n");
|
||
<span class="strong"><strong>for</strong></span> (igraph_int_t i=0; i < n; i++) {
|
||
<span class="emphasis"><em>/* Print NaN values in a platform-independent manner: */</em></span>
|
||
<span class="strong"><strong>igraph_real_printf</strong></span>(<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>(hist)[i] / sum);
|
||
<span class="strong"><strong>printf</strong></span>(" ");
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("\n\n");
|
||
|
||
<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>(&hist);
|
||
<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>/* Identify the vertices of each three-motif in a small Kautz graph. */</em></span>
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_kautz" title="9.2. igraph_kautz — Generate a Kautz graph.">igraph_kautz</a></strong></span>(&graph, 2, 1);
|
||
<span class="strong"><strong><a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_callback" title="4.4. igraph_motifs_randesu_callback — Finds motifs in a graph and calls a function for each of them.">igraph_motifs_randesu_callback</a></strong></span>(&graph, 3, NULL, &print_motif, NULL);
|
||
<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_motifs_randesu_no"></a>4.2. <code class="function">igraph_motifs_randesu_no</code> — Count the total number of motifs in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.6.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_motifs_randesu_no(
|
||
const igraph_t *graph, igraph_real_t *no, igraph_int_t size,
|
||
const igraph_vector_t *cut_prob
|
||
);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function counts the total number of (weakly) connected
|
||
induced subgraphs on <em class="parameter"><code>size</code></em> vertices, without assigning isomorphism
|
||
classes to them. Arbitrarily large motif sizes are supported.
|
||
|
||
</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>
|
||
The graph object to study.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>no</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an <code class="constant">igraph_real_t</code>, the result will be stored here.
|
||
Note that even though the result is an integer, we need to use
|
||
<code class="constant">igraph_real_t</code> to avoid overflow when igraph is compiled with
|
||
32-bit integers.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>size</code></em>:</span></p></td>
|
||
<td><p>
|
||
The size of the motifs to count.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cut_prob</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector of probabilities for cutting the search tree
|
||
at a given level. The first element is the first level, etc.
|
||
To perform a complete search and find all connected subgraphs,
|
||
supply either an all-zero vector of length <em class="parameter"><code>size</code></em>, or (since
|
||
igraph 0.10.14) a <code class="constant">NULL</code> pointer.
|
||
</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-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a>, <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_estimate" title="4.3. igraph_motifs_randesu_estimate — Estimate the total number of motifs in a graph."><code class="function">igraph_motifs_randesu_estimate()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: TODO.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_motifs_randesu_estimate"></a>4.3. <code class="function">igraph_motifs_randesu_estimate</code> — Estimate the total number of motifs in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.6.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_motifs_randesu_estimate(const igraph_t *graph, igraph_real_t *est,
|
||
igraph_int_t size, const igraph_vector_t *cut_prob,
|
||
igraph_int_t sample_size,
|
||
const igraph_vector_int_t *parsample);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function estimates the total number of (weakly) connected induced
|
||
subgraphs on <em class="parameter"><code>size</code></em> vertices. For example, an undirected complete graph
|
||
on <code class="constant">n</code> vertices will have one motif of size <code class="constant">n</code>, and <code class="constant">n</code> motifs
|
||
of <em class="parameter"><code>size</code></em> <code class="literal">n - 1</code>. As another example, one triangle
|
||
and a separate vertex will have zero motifs of size four.
|
||
|
||
</p>
|
||
<p>
|
||
This function is useful for large graphs for which it is not
|
||
feasible to count all connected subgraphs, as there are too
|
||
many of them.
|
||
|
||
</p>
|
||
<p>
|
||
The estimate is made by taking a sample of vertices and counting all
|
||
connected subgraphs in which these vertices are included. There is also
|
||
a <em class="parameter"><code>cut_prob</code></em> parameter which gives the probabilities to cut a branch of
|
||
the search tree.
|
||
|
||
</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>
|
||
The graph object to study.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>est</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an <code class="constant">igraph_real_t</code>, the result will be stored here.
|
||
Note that even though the result is an integer, we need to use
|
||
<code class="constant">igraph_real_t</code> to avoid overflow when igraph is compiled with
|
||
32-bit integers.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>size</code></em>:</span></p></td>
|
||
<td><p>
|
||
The size of the subgraphs to look for.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cut_prob</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector of probabilities for cutting the search tree
|
||
at a given level. The first element is the first level, etc.
|
||
To perform a complete search and find all motifs, supply
|
||
either an all-zero vector of length <em class="parameter"><code>size</code></em>, or (since
|
||
igraph 0.10.14) a <code class="constant">NULL</code> pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>sample_size</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of vertices to use as the
|
||
sample. This parameter is only used if the <em class="parameter"><code>parsample</code></em>
|
||
argument is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>parsample</code></em>:</span></p></td>
|
||
<td><p>
|
||
Either pointer to an initialized vector or a null
|
||
pointer. If a vector then the vertex IDs in the vector are
|
||
used as a sample. If a null pointer then the <em class="parameter"><code>sample_size</code></em>
|
||
argument is used to create a sample of vertices drawn with
|
||
uniform probability.
|
||
</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-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a>, <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_no" title="4.2. igraph_motifs_randesu_no — Count the total number of motifs in a graph."><code class="function">igraph_motifs_randesu_no()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: TODO.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_motifs_randesu_callback"></a>4.4. <code class="function">igraph_motifs_randesu_callback</code> — Finds motifs in a graph and calls a function for each of them.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.6.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_motifs_randesu_callback(
|
||
const igraph_t *graph,
|
||
igraph_int_t size, const igraph_vector_t *cut_prob,
|
||
igraph_motifs_handler_t *callback, void* extra);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p>
|
||
Similarly to <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a>, this function is able to find
|
||
directed motifs of sizes three and four and undirected motifs of sizes
|
||
three to six (i.e. the number of different subgraphs with three to six
|
||
vertices in the network). However, instead of
|
||
counting them, the function will call a callback function for each motif
|
||
found to allow further tests or post-processing.
|
||
|
||
</p>
|
||
<p>
|
||
The <em class="parameter"><code>cut_prob</code></em> argument also allows sampling the motifs, just like for
|
||
<a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph."><code class="function">igraph_motifs_randesu()</code></a>. Set the <em class="parameter"><code>cut_prob</code></em> argument to a zero vector
|
||
for finding all motifs.
|
||
|
||
</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>
|
||
The graph to find the motifs in.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>size</code></em>:</span></p></td>
|
||
<td><p>
|
||
The size of the motifs to search for. Only three and
|
||
four are implemented currently. The limitation is not in the
|
||
motif finding code, but the graph isomorphism code.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cut_prob</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector of probabilities for cutting the search tree
|
||
at a given level. The first element is the first level, etc.
|
||
To perform a complete search and find all motifs, supply
|
||
either an all-zero vector of length <em class="parameter"><code>size</code></em>, or (since
|
||
igraph 0.10.14) a <code class="constant">NULL</code> pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>callback</code></em>:</span></p></td>
|
||
<td><p>
|
||
A pointer to a function of type <a class="link" href="igraph-Motifs.html#igraph_motifs_handler_t" title="4.5. igraph_motifs_handler_t — Callback type for igraph_motifs_randesu_callback."><code class="function">igraph_motifs_handler_t</code></a>.
|
||
This function will be called whenever a new motif is found.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>extra</code></em>:</span></p></td>
|
||
<td><p>
|
||
Extra argument to pass to the callback function.
|
||
</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: TODO.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.21.6.5.10.1"></a><p class="title"><b>Example 20.3. File <code class="code">examples/simple/igraph_motifs_randesu.c</code></b></p>
|
||
<div class="example-contents">
|
||
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> <igraph.h>
|
||
|
||
<span class="emphasis"><em>/* This is a callback function suitable for use with igraph_motifs_randesu_callback().</em></span>
|
||
<span class="emphasis"><em> * It prints each motif it is calld with. */</em></span>
|
||
<a class="link" href="igraph-Error.html#igraph_error_t" title="3.1. igraph_error_t — Return type for functions returning an error code.">igraph_error_t</a> <span class="strong"><strong>print_motif</strong></span>(<span class="strong"><strong>const</strong></span> igraph_t *graph, <span class="strong"><strong>const</strong></span> igraph_vector_int_t *vids,
|
||
igraph_int_t isoclass, void* extra) {
|
||
<span class="strong"><strong>printf</strong></span>("Found isoclass %2" IGRAPH_PRId ": ", isoclass);
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(vids);
|
||
<span class="strong"><strong>return</strong></span> IGRAPH_SUCCESS; <span class="emphasis"><em>/* Return 'IGRAPH_SUCCESS': do not interrupt the search. */</em></span>
|
||
}
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
|
||
igraph_t graph;
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> hist;
|
||
|
||
<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>/* Compute the 4-motif distritbuion in Zachary's karate club network. */</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>(&graph, "Zachary");
|
||
<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>(&hist, 0);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Motifs.html#igraph_motifs_randesu" title="4.1. igraph_motifs_randesu — Count the number of motifs in a graph.">igraph_motifs_randesu</a></strong></span>(&graph, &hist, 4, NULL);
|
||
|
||
<span class="emphasis"><em>/* Compute the total number of motifs (connected 4-vertex subgraphs)</em></span>
|
||
<span class="emphasis"><em> * so that we can print the normalized distribution. */</em></span>
|
||
igraph_real_t sum = 0.0;
|
||
igraph_int_t n = <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_size" title="2.11.2. igraph_vector_size — The size of the vector.">igraph_vector_size</a></strong></span>(&hist);
|
||
<span class="strong"><strong>for</strong></span> (igraph_int_t i=0; i < n; i++) {
|
||
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong>isnan</strong></span>(<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>(hist)[i])) {
|
||
sum += <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>(hist)[i];
|
||
}
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("4-motif distribution:\n");
|
||
<span class="strong"><strong>for</strong></span> (igraph_int_t i=0; i < n; i++) {
|
||
<span class="emphasis"><em>/* Print NaN values in a platform-independent manner: */</em></span>
|
||
<span class="strong"><strong>igraph_real_printf</strong></span>(<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>(hist)[i] / sum);
|
||
<span class="strong"><strong>printf</strong></span>(" ");
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("\n\n");
|
||
|
||
<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>(&hist);
|
||
<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>/* Identify the vertices of each three-motif in a small Kautz graph. */</em></span>
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Generators.html#igraph_kautz" title="9.2. igraph_kautz — Generate a Kautz graph.">igraph_kautz</a></strong></span>(&graph, 2, 1);
|
||
<span class="strong"><strong><a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_callback" title="4.4. igraph_motifs_randesu_callback — Finds motifs in a graph and calls a function for each of them.">igraph_motifs_randesu_callback</a></strong></span>(&graph, 3, NULL, &print_motif, NULL);
|
||
<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_motifs_handler_t"></a>4.5. <code class="function">igraph_motifs_handler_t</code> — Callback type for <code class="constant">igraph_motifs_randesu_callback</code>.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.21.6.6.2"></a><pre class="programlisting">
|
||
typedef igraph_error_t igraph_motifs_handler_t(const igraph_t *graph,
|
||
const igraph_vector_int_t *vids,
|
||
igraph_int_t isoclass,
|
||
void *extra);
|
||
</pre>
|
||
<p>
|
||
|
||
|
||
<a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_callback" title="4.4. igraph_motifs_randesu_callback — Finds motifs in a graph and calls a function for each of them."><code class="function">igraph_motifs_randesu_callback()</code></a> calls a specified callback
|
||
function whenever a new motif is found during a motif search. This
|
||
callback function must be of type <code class="constant">igraph_motifs_handler_t</code>. It has
|
||
the following arguments:
|
||
|
||
</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>
|
||
The graph that that algorithm is working on. Of course
|
||
this must not be modified.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>vids</code></em>:</span></p></td>
|
||
<td><p>
|
||
The IDs of the vertices in the motif that has just been
|
||
found. This vector is owned by the motif search algorithm, so do not
|
||
modify or destroy it; make a copy of it if you need it later.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>isoclass</code></em>:</span></p></td>
|
||
<td><p>
|
||
The isomorphism class of the motif that has just been
|
||
found. Use <a class="link" href="igraph-Isomorphism.html#igraph_graph_count" title="5.4. igraph_graph_count — The number of unlabelled graphs on the given number of vertices."><code class="function">igraph_graph_count()</code></a> to find the maximum possible
|
||
isoclass for graphs of a given size. See <a class="link" href="igraph-Isomorphism.html#igraph_isoclass" title="5.1. igraph_isoclass — Determine the isomorphism class of small graphs."><code class="function">igraph_isoclass</code></a> and
|
||
<a class="link" href="igraph-Isomorphism.html#igraph_isoclass_subgraph" title="5.2. igraph_isoclass_subgraph — The isomorphism class of a subgraph of a graph."><code class="function">igraph_isoclass_subgraph</code></a> for more information.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>extra</code></em>:</span></p></td>
|
||
<td><p>
|
||
The extra argument that was passed to <a class="link" href="igraph-Motifs.html#igraph_motifs_randesu_callback" title="4.4. igraph_motifs_randesu_callback — Finds motifs in a graph and calls a function for each of them."><code class="function">igraph_motifs_randesu_callback()</code></a>.
|
||
</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>
|
||
<code class="constant">IGRAPH_SUCCESS</code> to continue the motif search,
|
||
<code class="constant">IGRAPH_STOP</code> to stop the motif search and return to the caller
|
||
normally. Any other return value is interpreted as an igraph error code,
|
||
which will terminate the search and return the same error code to the
|
||
caller.
|
||
</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-Motifs.html#igraph_motifs_randesu_callback" title="4.4. igraph_motifs_randesu_callback — Finds motifs in a graph and calls a function for each of them."><code class="function">igraph_motifs_randesu_callback()</code></a>
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</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-Cliques.html"><b>← Chapter 19. Cliques and independent vertex sets</b></a></td>
|
||
<td align="right"><a accesskey="n" href="igraph-Isomorphism.html"><b>Chapter 21. Graph isomorphism →</b></a></td>
|
||
</tr></table>
|
||
</body>
|
||
</html>
|