Abdelrahman Said
2791 lines
120 KiB
HTML
2791 lines
120 KiB
HTML
<html>
|
||
<head>
|
||
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
|
||
<title>Chapter 23. Maximum flows, minimum cuts and related measures</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-Coloring.html" title="Chapter 22. Graph coloring">
|
||
<link rel="next" href="igraph-Separators.html" title="Chapter 24. Vertex separators">
|
||
<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-Coloring.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-Separators.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-Flows"></a>Chapter 23. Maximum flows, minimum cuts and related measures</h1></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Flows.html#maximum-flows">1. Maximum flows</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#cuts-and-minimum-cuts">2. Cuts and minimum cuts</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#connectivity">3. Connectivity</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#edge-and-vertex-disjoint-paths">4. Edge- and vertex-disjoint paths</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#graph-adhesion-and-cohesion">5. Graph adhesion and cohesion</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#cohesive-blocks">6. Cohesive blocks</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
||
<a name="maximum-flows"></a>1. Maximum flows</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_maxflow">1.1. <code class="function">igraph_maxflow</code> — Maximum network flow between a pair of vertices.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_maxflow_value">1.2. <code class="function">igraph_maxflow_value</code> — Maximum flow in a network with the push/relabel algorithm.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_dominator_tree">1.3. <code class="function">igraph_dominator_tree</code> — Calculates the dominator tree of a flowgraph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_maxflow_stats_t">1.4. <code class="function">igraph_maxflow_stats_t</code> — Data structure holding statistics from the push-relabel maximum flow solver.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_maxflow"></a>1.1. <code class="function">igraph_maxflow</code> — Maximum network flow between a pair of vertices.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.2.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_maxflow(const igraph_t *graph, igraph_real_t *value,
|
||
igraph_vector_t *flow, igraph_vector_int_t *cut,
|
||
igraph_vector_int_t *partition, igraph_vector_int_t *partition2,
|
||
igraph_int_t source, igraph_int_t target,
|
||
const igraph_vector_t *capacity,
|
||
igraph_maxflow_stats_t *stats);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function implements the Goldberg-Tarjan algorithm for
|
||
calculating value of the maximum flow in a directed or undirected
|
||
graph. The algorithm was given in Andrew V. Goldberg, Robert
|
||
E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of
|
||
the ACM, 35(4), 921-940, 1988
|
||
<a class="ulink" href="https://doi.org/10.1145/48014.61051" target="_top">https://doi.org/10.1145/48014.61051</a>.
|
||
|
||
</p>
|
||
<p>
|
||
The input of the function is a graph, a vector
|
||
of real numbers giving the capacity of the edges and two vertices
|
||
of the graph, the source and the target. A flow is a function
|
||
assigning positive real numbers to the edges and satisfying two
|
||
requirements: (1) the flow value is less than the capacity of the
|
||
edge and (2) at each vertex except the source and the target, the
|
||
incoming flow (i.e. the sum of the flow on the incoming edges) is
|
||
the same as the outgoing flow (i.e. the sum of the flow on the
|
||
outgoing edges). The value of the flow is the incoming flow at the
|
||
target vertex. The maximum flow is the flow with the maximum
|
||
value.
|
||
|
||
</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, either directed or undirected.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>value</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real number, the value of the maximum
|
||
will be placed here, unless it is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>flow</code></em>:</span></p></td>
|
||
<td><p>
|
||
If not a null pointer, then it must be a pointer to an
|
||
initialized vector. The vector will be resized, and the flow
|
||
on each edge will be placed in it, in the order of the edge
|
||
IDs. For undirected graphs this argument is bit trickier,
|
||
since for these the flow direction is not predetermined by
|
||
the edge direction. For these graphs the elements of the
|
||
<em class="parameter"><code>flow</code></em> vector can be negative, this means that the flow
|
||
goes from the bigger vertex ID to the smaller one. Positive
|
||
values mean that the flow goes from the smaller vertex ID to
|
||
the bigger one.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cut</code></em>:</span></p></td>
|
||
<td><p>
|
||
A null pointer or a pointer to an initialized vector.
|
||
If not a null pointer, then the minimum cut corresponding to
|
||
the maximum flow is stored here, i.e. all edge IDs that are
|
||
part of the minimum cut are stored in the vector.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition</code></em>:</span></p></td>
|
||
<td><p>
|
||
A null pointer or a pointer to an initialized
|
||
vector. If not a null pointer, then the first partition of
|
||
the minimum cut that corresponds to the maximum flow will be
|
||
placed here. The first partition is always the one that
|
||
contains the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition2</code></em>:</span></p></td>
|
||
<td><p>
|
||
A null pointer or a pointer to an initialized
|
||
vector. If not a null pointer, then the second partition of
|
||
the minimum cut that corresponds to the maximum flow will be
|
||
placed here. The second partition is always the one that
|
||
contains the target vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector containing the capacity of the edges. If <code class="constant">NULL</code>, then
|
||
every edge is considered to have capacity 1.0.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>stats</code></em>:</span></p></td>
|
||
<td><p>
|
||
Counts of the number of different operations
|
||
performed by the algorithm are 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>
|
||
|
||
Time complexity: O(|V|^3). In practice it is much faster, but I
|
||
cannot prove a better lower bound for the data structure I've
|
||
used. In fact, this implementation runs much faster than the
|
||
<code class="constant">hi_pr</code> implementation discussed in
|
||
B. V. Cherkassky and A. V. Goldberg: On implementing the
|
||
push-relabel method for the maximum flow problem, (Algorithmica,
|
||
19:390--410, 1997) on all the graph classes I've tried.
|
||
|
||
</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-Flows.html#igraph_mincut_value" title="2.6. igraph_mincut_value — The minimum edge cut in a graph."><code class="function">igraph_mincut_value()</code></a>, <a class="link" href="igraph-Flows.html#igraph_edge_connectivity" title="3.2. igraph_edge_connectivity — The minimum edge connectivity in a graph."><code class="function">igraph_edge_connectivity()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_vertex_connectivity" title="3.4. igraph_vertex_connectivity — The vertex connectivity of a graph."><code class="function">igraph_vertex_connectivity()</code></a> for
|
||
properties based on the maximum flow.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.24.2.2.11.1"></a><p class="title"><b>Example 23.1. File <code class="code">examples/simple/flow.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_real_t flow;
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> capacity;
|
||
igraph_int_t source, target;
|
||
FILE *infile;
|
||
<a class="link" href="igraph-Flows.html#igraph_maxflow_stats_t" title="1.4. igraph_maxflow_stats_t — Data structure holding statistics from the push-relabel maximum flow solver.">igraph_maxflow_stats_t</a> stats;
|
||
|
||
<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-Data-structures.html#igraph_vector_init" title="2.2.1. igraph_vector_init — Initializes a vector object (constructor).">igraph_vector_init</a></strong></span>(&capacity, 0);
|
||
|
||
<span class="emphasis"><em>/***************/</em></span>
|
||
infile = <span class="strong"><strong>fopen</strong></span>("ak-4102.max", "r");
|
||
<span class="strong"><strong><a class="link" href="igraph-Foreign.html#igraph_read_graph_dimacs_flow" title="1.7. igraph_read_graph_dimacs_flow — Read a graph in DIMACS format.">igraph_read_graph_dimacs_flow</a></strong></span>(
|
||
&g, infile, 0, 0, &source, &target, &capacity, IGRAPH_DIRECTED);
|
||
<span class="strong"><strong>fclose</strong></span>(infile);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm.">igraph_maxflow_value</a></strong></span>(&g, &flow, source, target, &capacity, &stats);
|
||
|
||
<span class="strong"><strong>if</strong></span> (flow != 8207) {
|
||
<span class="strong"><strong>return</strong></span> 1;
|
||
}
|
||
<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>/***************/</em></span>
|
||
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
<span class="emphasis"><em>/* infile=fopen("ak-8198.max", "r"); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */</em></span>
|
||
<span class="emphasis"><em>/* IGRAPH_DIRECTED); */</em></span>
|
||
<span class="emphasis"><em>/* fclose(infile); */</em></span>
|
||
|
||
<span class="emphasis"><em>/* t=timer(); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */</em></span>
|
||
<span class="emphasis"><em>/* t=timer()-t; */</em></span>
|
||
<span class="emphasis"><em>/* printf("8198: %g (time %.10f)\n", flow, t); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_destroy(&g); */</em></span>
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
<span class="emphasis"><em>/* infile=fopen("ak-16390.max", "r"); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */</em></span>
|
||
<span class="emphasis"><em>/* IGRAPH_DIRECTED); */</em></span>
|
||
<span class="emphasis"><em>/* fclose(infile); */</em></span>
|
||
|
||
<span class="emphasis"><em>/* t=timer(); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */</em></span>
|
||
<span class="emphasis"><em>/* t=timer()-t; */</em></span>
|
||
<span class="emphasis"><em>/* printf("16390: %g (time %.10f)\n", flow, t); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_destroy(&g); */</em></span>
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
<span class="emphasis"><em>/* infile=fopen("ak-32774.max", "r"); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */</em></span>
|
||
<span class="emphasis"><em>/* IGRAPH_DIRECTED); */</em></span>
|
||
<span class="emphasis"><em>/* fclose(infile); */</em></span>
|
||
|
||
<span class="emphasis"><em>/* t=timer(); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */</em></span>
|
||
<span class="emphasis"><em>/* t=timer()-t; */</em></span>
|
||
<span class="emphasis"><em>/* printf("32774: %g (time %.10f)\n", flow, t); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_destroy(&g); */</em></span>
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
<span class="emphasis"><em>/* infile=fopen("ak-65542.max", "r"); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */</em></span>
|
||
<span class="emphasis"><em>/* IGRAPH_DIRECTED); */</em></span>
|
||
<span class="emphasis"><em>/* fclose(infile); */</em></span>
|
||
|
||
<span class="emphasis"><em>/* t=timer(); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */</em></span>
|
||
<span class="emphasis"><em>/* t=timer()-t; */</em></span>
|
||
<span class="emphasis"><em>/* printf("65542: %g (time %.10f)\n", flow, t); */</em></span>
|
||
<span class="emphasis"><em>/* igraph_destroy(&g); */</em></span>
|
||
<span class="emphasis"><em>/* /\***************\/ */</em></span>
|
||
|
||
<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>(&capacity);
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
</pre>
|
||
<p></p>
|
||
</div>
|
||
</div>
|
||
<br class="example-break">
|
||
</div>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.24.2.2.11.2"></a><p class="title"><b>Example 23.2. File <code class="code">examples/simple/flow2.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) {
|
||
<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>();
|
||
|
||
igraph_t g;
|
||
igraph_real_t flow_value;
|
||
igraph_vector_int_t cut;
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> capacity;
|
||
igraph_vector_int_t partition, partition2;
|
||
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> flow;
|
||
igraph_int_t i;
|
||
<a class="link" href="igraph-Flows.html#igraph_maxflow_stats_t" title="1.4. igraph_maxflow_stats_t — Data structure holding statistics from the push-relabel maximum flow solver.">igraph_maxflow_stats_t</a> stats;
|
||
|
||
<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, 6, IGRAPH_DIRECTED,
|
||
0, 1, 1, 2, 2, 3, 0, 5, 5, 4, 4, 3, 3, 0, -1);
|
||
<span class="strong"><strong>igraph_vector_init_int_end</strong></span>(&capacity, -1, 3, 1, 2, 10, 1, 3, 2, -1);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&cut, 0);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&partition, 0);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&partition2, 0);
|
||
<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>(&flow, 0);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices.">igraph_maxflow</a></strong></span>(&g, &flow_value, &flow, &cut, &partition, &partition2,
|
||
<span class="emphasis"><em>/*source=*/</em></span> 0, <span class="emphasis"><em>/*target=*/</em></span> 2, &capacity, &stats);
|
||
|
||
igraph_int_t nc = <span class="strong"><strong>igraph_vector_int_size</strong></span>(&cut);
|
||
<span class="strong"><strong>printf</strong></span>("flow value: %g\n", (double) flow_value);
|
||
<span class="strong"><strong>printf</strong></span>("flow: ");
|
||
<span class="strong"><strong>igraph_vector_print</strong></span>(&flow);
|
||
<span class="strong"><strong>printf</strong></span>("first partition: ");
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&partition);
|
||
<span class="strong"><strong>printf</strong></span>("second partition: ");
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&partition2);
|
||
<span class="strong"><strong>printf</strong></span>("edges in the cut: ");
|
||
<span class="strong"><strong>for</strong></span> (i = 0; i < nc; i++) {
|
||
igraph_int_t edge = <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>(cut)[i];
|
||
igraph_int_t from = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_FROM" title="5.2.6. IGRAPH_FROM — The source vertex of an edge.">IGRAPH_FROM</a></strong></span>(&g, edge);
|
||
igraph_int_t to = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_TO" title="5.2.7. IGRAPH_TO — The target vertex of an edge.">IGRAPH_TO</a></strong></span>(&g, edge);
|
||
<span class="strong"><strong>printf</strong></span>("%" IGRAPH_PRId "-%" IGRAPH_PRId " (%g), ", from, to, <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>(capacity)[edge]);
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("\n");
|
||
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&cut);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&partition2);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&partition);
|
||
<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>(&capacity);
|
||
<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>(&flow);
|
||
<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 class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_maxflow_value"></a>1.2. <code class="function">igraph_maxflow_value</code> — Maximum flow in a network with the push/relabel algorithm.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.2.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_maxflow_value(const igraph_t *graph, igraph_real_t *value,
|
||
igraph_int_t source, igraph_int_t target,
|
||
const igraph_vector_t *capacity,
|
||
igraph_maxflow_stats_t *stats);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function implements the Goldberg-Tarjan algorithm for
|
||
calculating value of the maximum flow in a directed or undirected
|
||
graph. The algorithm was given in Andrew V. Goldberg, Robert
|
||
E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of
|
||
the ACM, 35(4), 921-940, 1988
|
||
<a class="ulink" href="https://doi.org/10.1145/48014.61051" target="_top">https://doi.org/10.1145/48014.61051</a>.
|
||
|
||
</p>
|
||
<p>
|
||
The input of the function is a graph, a vector
|
||
of real numbers giving the capacity of the edges and two vertices
|
||
of the graph, the source and the target. A flow is a function
|
||
assigning positive real numbers to the edges and satisfying two
|
||
requirements: (1) the flow value is less than the capacity of the
|
||
edge and (2) at each vertex except the source and the target, the
|
||
incoming flow (i.e. the sum of the flow on the incoming edges) is
|
||
the same as the outgoing flow (i.e. the sum of the flow on the
|
||
outgoing edges). The value of the flow is the incoming flow at the
|
||
target vertex. The maximum flow is the flow with the maximum
|
||
value.
|
||
|
||
</p>
|
||
<p>
|
||
According to a theorem by Ford and Fulkerson
|
||
(L. R. Ford Jr. and D. R. Fulkerson. Maximal flow through a
|
||
network. Canadian J. Math., 8:399-404, 1956.) the maximum flow
|
||
between two vertices is the same as the
|
||
minimum cut between them (also called the minimum s-t cut). So <a class="link" href="igraph-Flows.html#igraph_st_mincut_value" title="2.2. igraph_st_mincut_value — The minimum s-t cut in a graph."><code class="function">igraph_st_mincut_value()</code></a> gives the same result in all cases as <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
|
||
</p>
|
||
<p>
|
||
Note that the value of the maximum flow is the same as the
|
||
minimum cut in the 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>
|
||
The input graph, either directed or undirected.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>value</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real number, the result will be placed here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector containing the capacity of the edges. If NULL, then
|
||
every edge is considered to have capacity 1.0.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>stats</code></em>:</span></p></td>
|
||
<td><p>
|
||
Counts of the number of different operations
|
||
preformed by the algorithm are 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>
|
||
|
||
Time complexity: O(|V|^3).
|
||
|
||
</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-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices."><code class="function">igraph_maxflow()</code></a> to calculate the actual flow.
|
||
<a class="link" href="igraph-Flows.html#igraph_mincut_value" title="2.6. igraph_mincut_value — The minimum edge cut in a graph."><code class="function">igraph_mincut_value()</code></a>, <a class="link" href="igraph-Flows.html#igraph_edge_connectivity" title="3.2. igraph_edge_connectivity — The minimum edge connectivity in a graph."><code class="function">igraph_edge_connectivity()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_vertex_connectivity" title="3.4. igraph_vertex_connectivity — The vertex connectivity of a graph."><code class="function">igraph_vertex_connectivity()</code></a> for
|
||
properties based on the maximum flow.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_dominator_tree"></a>1.3. <code class="function">igraph_dominator_tree</code> — Calculates the dominator tree of a flowgraph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.2.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_dominator_tree(const igraph_t *graph,
|
||
igraph_int_t root,
|
||
igraph_vector_int_t *dom,
|
||
igraph_t *domtree,
|
||
igraph_vector_int_t *leftout,
|
||
igraph_neimode_t mode);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
A flowgraph is a directed graph with a distinguished start (or
|
||
root) vertex r, such that for any vertex v, there is a path from r
|
||
to v. A vertex v dominates another vertex w (not equal to v), if
|
||
every path from r to w contains v. Vertex v is the immediate
|
||
dominator or w, v=idom(w), if v dominates w and every other
|
||
dominator of w dominates v. The edges {(idom(w), w)| w is not r}
|
||
form a directed tree, rooted at r, called the dominator tree of the
|
||
graph. Vertex v dominates vertex w if and only if v is an ancestor
|
||
of w in the dominator tree.
|
||
|
||
</p>
|
||
<p>This function implements the Lengauer-Tarjan algorithm
|
||
to construct the dominator tree of a directed graph. For details
|
||
please see Thomas Lengauer, Robert Endre Tarjan: A fast algorithm
|
||
for finding dominators in a flowgraph, ACM Transactions on
|
||
Programming Languages and Systems (TOPLAS) I/1, 121--141, 1979.
|
||
<a class="ulink" href="https://doi.org/10.1145/357062.357071" target="_top">https://doi.org/10.1145/357062.357071</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>
|
||
A directed graph. If it is not a flowgraph, and it
|
||
contains some vertices not reachable from the root vertex,
|
||
then these vertices will be collected in the <em class="parameter"><code>leftout</code></em>
|
||
vector.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>root</code></em>:</span></p></td>
|
||
<td><p>
|
||
The ID of the root (or source) vertex, this will be the
|
||
root of the tree.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>dom</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector or a null pointer. If
|
||
not a null pointer, then the immediate dominator of each
|
||
vertex will be stored here. For vertices that are not
|
||
reachable from the root, <code class="literal">-2</code> is stored here. For
|
||
the root vertex itself, <code class="literal">-1</code> is added.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>domtree</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an <span class="emphasis"><em>uninitialized</em></span> <span class="type">igraph_t</span>,
|
||
or <code class="constant">NULL</code>. If not a null pointer, then the dominator tree
|
||
is returned here. The graph contains the vertices that are unreachable
|
||
from the root (if any), these will be isolates.
|
||
Graph and vertex attributes are preserved, but edge attributes
|
||
are discarded.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>leftout</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector object, or <code class="constant">NULL</code>. If
|
||
not <code class="constant">NULL</code>, then the IDs of the vertices that are unreachable
|
||
from the root vertex (and thus not part of the dominator
|
||
tree) are stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
|
||
<td><p>
|
||
Constant, must be <code class="constant">IGRAPH_IN</code> or <code class="constant">IGRAPH_OUT</code>. If it
|
||
is <code class="constant">IGRAPH_IN</code>, then all directions are considered as
|
||
opposite to the original one in the input 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>
|
||
|
||
Time complexity: very close to O(|E|+|V|), linear in the number of
|
||
edges and vertices. More precisely, it is O(|V|+|E|alpha(|E|,|V|)),
|
||
where alpha(|E|,|V|) is a functional inverse of Ackermann's
|
||
function.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.24.2.4.9.1"></a><p class="title"><b>Example 23.3. File <code class="code">examples/simple/dominator_tree.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 g, domtree;
|
||
igraph_vector_int_t dom;
|
||
igraph_vector_int_t leftout;
|
||
|
||
<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>igraph_vector_int_init</strong></span>(&dom, 0);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&leftout, 0);
|
||
|
||
<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, 10, IGRAPH_DIRECTED,
|
||
0, 9,
|
||
1, 0, 1, 2,
|
||
2, 3, 2, 7,
|
||
3, 1,
|
||
4, 1, 4, 3,
|
||
5, 2, 5, 3, 5, 4, 5, 8,
|
||
6, 5, 6, 9,
|
||
8, 7,
|
||
-1);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Flows.html#igraph_dominator_tree" title="1.3. igraph_dominator_tree — Calculates the dominator tree of a flowgraph.">igraph_dominator_tree</a></strong></span>(&g, <span class="emphasis"><em>/*root=*/</em></span> 9, &dom, &domtree,
|
||
&leftout, <span class="emphasis"><em>/*mode=*/</em></span> IGRAPH_IN);
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&dom);
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&leftout);
|
||
<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>(&domtree, stdout);
|
||
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&dom);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&leftout);
|
||
<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>(&domtree);
|
||
<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 class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_maxflow_stats_t"></a>1.4. <code class="function">igraph_maxflow_stats_t</code> — Data structure holding statistics from the push-relabel maximum flow solver.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.2.5.2"></a><pre class="programlisting">
|
||
typedef struct {
|
||
igraph_int_t nopush, norelabel, nogap, nogapnodes, nobfs;
|
||
</pre>
|
||
<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>nopush</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of push operations performed.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>norelabel</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of relabel operarions performed.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>nogap</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of times the gap heuristics was used.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>nogapnodes</code></em>:</span></p></td>
|
||
<td><p>
|
||
The total number of vertices that were
|
||
omitted form further calculations because of the gap
|
||
heuristics.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>nobfs</code></em>:</span></p></td>
|
||
<td><p>
|
||
The number of times the reverse BFS was run to
|
||
assign good values to the height function. This includes
|
||
an initial run before the whole algorithm, so it is always
|
||
at least one.
|
||
</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="cuts-and-minimum-cuts"></a>2. Cuts and minimum cuts</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_st_mincut">2.1. <code class="function">igraph_st_mincut</code> — Minimum cut between a source and a target vertex.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_st_mincut_value">2.2. <code class="function">igraph_st_mincut_value</code> — The minimum s-t cut in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_all_st_cuts">2.3. <code class="function">igraph_all_st_cuts</code> — List all edge-cuts between two vertices in a directed graph</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_all_st_mincuts">2.4. <code class="function">igraph_all_st_mincuts</code> — All minimum s-t cuts of a directed graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_mincut">2.5. <code class="function">igraph_mincut</code> — Calculates the minimum cut in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_mincut_value">2.6. <code class="function">igraph_mincut_value</code> — The minimum edge cut in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_gomory_hu_tree">2.7. <code class="function">igraph_gomory_hu_tree</code> — Gomory-Hu tree of a graph.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_st_mincut"></a>2.1. <code class="function">igraph_st_mincut</code> — Minimum cut between a source and a target vertex.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.3.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_st_mincut(const igraph_t *graph, igraph_real_t *value,
|
||
igraph_vector_int_t *cut, igraph_vector_int_t *partition,
|
||
igraph_vector_int_t *partition2,
|
||
igraph_int_t source, igraph_int_t target,
|
||
const igraph_vector_t *capacity);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Finds the edge set that has the smallest total capacity among all
|
||
edge sets that disconnect the source and target vertices.
|
||
|
||
</p>
|
||
<p>The calculation is performed using maximum flow
|
||
techniques, by calling <a class="link" href="igraph-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices."><code class="function">igraph_maxflow()</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>
|
||
The input graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>value</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real variable, the value of the cut is
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cut</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector, the edge IDs that are included
|
||
in the cut are stored here. This argument is ignored if it
|
||
is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector, the vertex IDs of the
|
||
vertices in the first partition of the cut are stored
|
||
here. The first partition is always the one that contains the
|
||
source vertex. This argument is ignored if it is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition2</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector, the vertex IDs of the
|
||
vertices in the second partition of the cut are stored here.
|
||
The second partition is always the one that contains the
|
||
target vertex. This argument is ignored if it is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
Integer, the id of the target vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector containing the capacity of the edges. If a
|
||
null pointer, then every edge is considered to have capacity
|
||
1.0.
|
||
</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-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices."><code class="function">igraph_maxflow()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: see <a class="link" href="igraph-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices."><code class="function">igraph_maxflow()</code></a>.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_st_mincut_value"></a>2.2. <code class="function">igraph_st_mincut_value</code> — The minimum s-t cut in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.3.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_st_mincut_value(const igraph_t *graph, igraph_real_t *value,
|
||
igraph_int_t source, igraph_int_t target,
|
||
const igraph_vector_t *capacity);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p> The minimum s-t cut in a weighted (=valued) graph is the
|
||
total minimum edge weight needed to remove from the graph to
|
||
eliminate all paths from a given vertex (<em class="parameter"><code>source</code></em>) to
|
||
another vertex (<em class="parameter"><code>target</code></em>). Directed paths are considered in
|
||
directed graphs, and undirected paths in undirected graphs. </p>
|
||
<p> The minimum s-t cut between two vertices is known to be same
|
||
as the maximum flow between these two vertices. So this function
|
||
calls <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a> to do the calculation.
|
||
|
||
</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>value</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real variable, the result will be stored
|
||
here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to the capacity vector, it should contain
|
||
non-negative numbers and its length should be the same the
|
||
the number of edges in the graph. It can be a null pointer, then
|
||
every edge has unit capacity.
|
||
</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|^3), see also the discussion for <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>, |V| is the number of vertices.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_all_st_cuts"></a>2.3. <code class="function">igraph_all_st_cuts</code> — List all edge-cuts between two vertices in a directed graph</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.3.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_all_st_cuts(const igraph_t *graph,
|
||
igraph_vector_int_list_t *cuts,
|
||
igraph_vector_int_list_t *partition1s,
|
||
igraph_int_t source,
|
||
igraph_int_t target);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function lists all edge-cuts between a source and a target
|
||
vertex. Every cut is listed exactly once. The implemented algorithm
|
||
is described in JS Provan and DR Shier: A Paradigm for listing
|
||
(s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996.
|
||
|
||
</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, is must be directed.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cuts</code></em>:</span></p></td>
|
||
<td><p>
|
||
An initialized list of integer vectors, the cuts are stored
|
||
here. Each vector will contain the IDs of the edges in
|
||
the cut. This argument is ignored if it is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition1s</code></em>:</span></p></td>
|
||
<td><p>
|
||
An initialized list of integer vectors, the list of
|
||
vertex sets generating the actual edge cuts are stored
|
||
here. Each vector contains a set of vertex IDs. If X is such
|
||
a set, then all edges going from X to the complement of X
|
||
form an (s, t) edge-cut in the graph. This argument is
|
||
ignored if it is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</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(n(|V|+|E|)), where |V| is the number of
|
||
vertices, |E| is the number of edges, and n is the number of cuts.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_all_st_mincuts"></a>2.4. <code class="function">igraph_all_st_mincuts</code> — All minimum s-t cuts of a directed graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.3.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_all_st_mincuts(const igraph_t *graph, igraph_real_t *value,
|
||
igraph_vector_int_list_t *cuts,
|
||
igraph_vector_int_list_t *partition1s,
|
||
igraph_int_t source,
|
||
igraph_int_t target,
|
||
const igraph_vector_t *capacity);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function lists all edge cuts between two vertices, in a directed graph,
|
||
with minimum total capacity. Possibly, multiple cuts may have the same total
|
||
capacity, although there is often only one minimum cut in weighted graphs.
|
||
It is recommended to supply integer-values capacities. Otherwise, not all
|
||
minimum cuts may be detected because of numerical roundoff errors.
|
||
The implemented algorithm is described in JS Provan and DR
|
||
Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15,
|
||
351--372, 1996.
|
||
|
||
</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, it must be directed.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>value</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a real number or <code class="constant">NULL</code>. The value of the minimum cut
|
||
is stored here, unless it is a null pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cuts</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to initialized list of integer vectors or <code class="constant">NULL</code>.
|
||
The cuts are stored here as lists of vertex IDs.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition1s</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized list of integer vectors or <code class="constant">NULL</code>.
|
||
The list of vertex sets, generating the actual edge cuts, are stored
|
||
here. Each vector contains a set of vertex IDs. If X is such
|
||
a set, then all edges going from X to the complement of X
|
||
form an (s,t) edge-cut in the graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector of edge capacities. All capacities must be
|
||
strictly positive. If this is a null pointer, then all edges
|
||
are assumed to have capacity one.
|
||
</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(n(|V|+|E|))+O(F), where |V| is the number of
|
||
vertices, |E| is the number of edges, and n is the number of cuts;
|
||
O(F) is the time complexity of the maximum flow algorithm, see <a class="link" href="igraph-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices."><code class="function">igraph_maxflow()</code></a>.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.24.3.5.8.2"></a><p class="title"><b>Example 23.4. File <code class="code">examples/simple/igraph_all_st_mincuts.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_list_t partitions;
|
||
igraph_vector_int_list_t cuts;
|
||
igraph_real_t value;
|
||
|
||
<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, 5, IGRAPH_DIRECTED,
|
||
0, 1, 1, 2, 2, 3, 3, 4,
|
||
-1);
|
||
|
||
<span class="strong"><strong>igraph_vector_int_list_init</strong></span>(&partitions, 0);
|
||
<span class="strong"><strong>igraph_vector_int_list_init</strong></span>(&cuts, 0);
|
||
<span class="strong"><strong><a class="link" href="igraph-Flows.html#igraph_all_st_mincuts" title="2.4. igraph_all_st_mincuts — All minimum s-t cuts of a directed graph.">igraph_all_st_mincuts</a></strong></span>(&g, &value, &cuts, &partitions,
|
||
<span class="emphasis"><em>/*source=*/</em></span> 0, <span class="emphasis"><em>/*target=*/</em></span> 4,
|
||
<span class="emphasis"><em>/*capacity=*/</em></span> 0);
|
||
|
||
igraph_int_t i, e, m, n = <span class="strong"><strong>igraph_vector_int_list_size</strong></span>(&partitions);
|
||
<span class="strong"><strong>printf</strong></span>("Found %" IGRAPH_PRId " cuts, value: %g\n", n, value);
|
||
<span class="strong"><strong>for</strong></span> (i = 0; i < n; i++) {
|
||
igraph_vector_int_t *vec = <span class="strong"><strong>igraph_vector_int_list_get_ptr</strong></span>(&partitions, i);
|
||
igraph_vector_int_t *vec2 = <span class="strong"><strong>igraph_vector_int_list_get_ptr</strong></span>(&cuts, i);
|
||
<span class="strong"><strong>printf</strong></span>("Partition %" IGRAPH_PRId ": ", i);
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(vec);
|
||
<span class="strong"><strong>if</strong></span> (vec2) {
|
||
<span class="strong"><strong>printf</strong></span>("Cut %" IGRAPH_PRId ":\n", i);
|
||
m = <span class="strong"><strong>igraph_vector_int_size</strong></span>(vec2);
|
||
<span class="strong"><strong>for</strong></span> (e = 0; e < m; e++) {
|
||
igraph_int_t from = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_FROM" title="5.2.6. IGRAPH_FROM — The source vertex of an edge.">IGRAPH_FROM</a></strong></span>(&g, <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>(*vec2)[e]), to = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_TO" title="5.2.7. IGRAPH_TO — The target vertex of an edge.">IGRAPH_TO</a></strong></span>(&g, <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>(*vec2)[e]);
|
||
<span class="strong"><strong>printf</strong></span>(" %" IGRAPH_PRId " -> %" IGRAPH_PRId "\n", from, to);
|
||
}
|
||
}
|
||
}
|
||
|
||
<span class="strong"><strong>igraph_vector_int_list_destroy</strong></span>(&partitions);
|
||
<span class="strong"><strong>igraph_vector_int_list_destroy</strong></span>(&cuts);
|
||
<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 class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_mincut"></a>2.5. <code class="function">igraph_mincut</code> — Calculates the minimum cut in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.3.6.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_mincut(const igraph_t *graph,
|
||
igraph_real_t *value,
|
||
igraph_vector_int_t *partition,
|
||
igraph_vector_int_t *partition2,
|
||
igraph_vector_int_t *cut,
|
||
const igraph_vector_t *capacity);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
This function calculates the minimum cut in a graph.
|
||
The minimum cut is the minimum set of edges which needs to be
|
||
removed to disconnect the graph. The minimum is calculated using
|
||
the weights (<em class="parameter"><code>capacity</code></em>) of the edges, so the cut with the minimum
|
||
total capacity is calculated.
|
||
|
||
</p>
|
||
<p> For directed graphs an implementation based on
|
||
calculating 2|V|-2 maximum flows is used.
|
||
For undirected graphs we use the Stoer-Wagner
|
||
algorithm, as described in M. Stoer and F. Wagner: A simple min-cut
|
||
algorithm, Journal of the ACM, 44 585-591, 1997.
|
||
|
||
</p>
|
||
<p>
|
||
The first implementation of the actual cut calculation for
|
||
undirected graphs was made by Gregory Benison, thanks Greg.
|
||
|
||
</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>value</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to a float, the value of the cut will be
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector, the ids
|
||
of the vertices in the first partition after separating the
|
||
graph will be stored here. The vector will be resized as
|
||
needed. This argument is ignored if it is a NULL pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>partition2</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector the ids
|
||
of the vertices in the second partition will be stored here.
|
||
The vector will be resized as needed. This argument is ignored
|
||
if it is a NULL pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cut</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an initialized vector, the IDs of the edges
|
||
in the cut will be stored here. This argument is ignored if it
|
||
is a NULL pointer.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
A numeric vector giving the capacities of the
|
||
edges. If a null pointer then all edges have unit capacity.
|
||
</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-Flows.html#igraph_mincut_value" title="2.6. igraph_mincut_value — The minimum edge cut in a graph."><code class="function">igraph_mincut_value()</code></a>, a simpler interface for calculating
|
||
the value of the cut only.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: for directed graphs it is O(|V|^4), but see the
|
||
remarks at <a class="link" href="igraph-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices."><code class="function">igraph_maxflow()</code></a>. For undirected graphs it is
|
||
O(|V||E|+|V|^2 log|V|). |V| and |E| are the number of vertices and
|
||
edges respectively.
|
||
|
||
</p>
|
||
<div class="hideshow" onClick="toggle(this, event)">
|
||
<div class="example">
|
||
<a name="id-1.24.3.6.12.2"></a><p class="title"><b>Example 23.5. File <code class="code">examples/simple/igraph_mincut.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>print_mincut</strong></span>(<span class="strong"><strong>const</strong></span> igraph_t *graph, igraph_real_t value,
|
||
<span class="strong"><strong>const</strong></span> igraph_vector_int_t *partition,
|
||
<span class="strong"><strong>const</strong></span> igraph_vector_int_t *partition2,
|
||
<span class="strong"><strong>const</strong></span> igraph_vector_int_t *cut,
|
||
<span class="strong"><strong>const</strong></span> <a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects">igraph_vector_t</a> *capacity) {
|
||
|
||
igraph_int_t i, nc = <span class="strong"><strong>igraph_vector_int_size</strong></span>(cut);
|
||
igraph_bool_t directed = <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(graph);
|
||
|
||
<span class="strong"><strong>printf</strong></span>("mincut value: %g\n", (double) value);
|
||
<span class="strong"><strong>printf</strong></span>("first partition: ");
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(partition);
|
||
<span class="strong"><strong>printf</strong></span>("second partition: ");
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(partition2);
|
||
<span class="strong"><strong>printf</strong></span>("edges in the cut: ");
|
||
<span class="strong"><strong>for</strong></span> (i = 0; i < nc; i++) {
|
||
igraph_int_t edge = <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>(*cut)[i];
|
||
igraph_int_t from = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_FROM" title="5.2.6. IGRAPH_FROM — The source vertex of an edge.">IGRAPH_FROM</a></strong></span>(graph, edge);
|
||
igraph_int_t to = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_TO" title="5.2.7. IGRAPH_TO — The target vertex of an edge.">IGRAPH_TO</a></strong></span> (graph, edge);
|
||
<span class="strong"><strong>if</strong></span> (!directed && from > to) {
|
||
igraph_int_t tmp = from;
|
||
from = to;
|
||
to = tmp;
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("%" IGRAPH_PRId "-%" IGRAPH_PRId " (%g), ", from, to, <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>(*capacity)[edge]);
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("\n");
|
||
|
||
<span class="strong"><strong>return</strong></span> 0;
|
||
}
|
||
|
||
int <span class="strong"><strong>main</strong></span>(void) {
|
||
|
||
igraph_t g;
|
||
igraph_vector_int_t partition, partition2, cut;
|
||
<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_real_t value;
|
||
|
||
<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>igraph_vector_int_init</strong></span>(&partition, 0);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&partition2, 0);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&cut, 0);
|
||
|
||
<span class="emphasis"><em>/* -------------------------------------------- */</em></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_UNDIRECTED,
|
||
0, 1, 0, 4, 1, 2, 1, 4, 1, 5, 2, 3, 2, 6, 3, 6, 3, 7, 4, 5, 5, 6, 6, 7,
|
||
-1);
|
||
<span class="strong"><strong>igraph_vector_init_int_end</strong></span>(&weights, -1, 2, 3, 3, 2, 2, 4, 2, 2, 2, 3, 1, 3, -1);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Flows.html#igraph_mincut" title="2.5. igraph_mincut — Calculates the minimum cut in a graph.">igraph_mincut</a></strong></span>(&g, &value, &partition, &partition2, &cut, &weights);
|
||
<span class="strong"><strong>print_mincut</strong></span>(&g, value, &partition, &partition2, &cut, &weights);
|
||
|
||
<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><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>/* -------------------------------------------- */</em></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, 6, IGRAPH_DIRECTED,
|
||
0, 1, 1, 2, 2, 3, 0, 5, 5, 4, 4, 3, 3, 0, -1);
|
||
<span class="strong"><strong>igraph_vector_init_int_end</strong></span>(&weights, -1, 3, 1, 2, 10, 1, 3, 2, -1);
|
||
|
||
<span class="strong"><strong><a class="link" href="igraph-Flows.html#igraph_mincut" title="2.5. igraph_mincut — Calculates the minimum cut in a graph.">igraph_mincut</a></strong></span>(&g, &value, &partition, &partition2, &cut, &weights);
|
||
<span class="strong"><strong>print_mincut</strong></span>(&g, value, &partition, &partition2, &cut, &weights);
|
||
|
||
<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><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>/* -------------------------------------------- */</em></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, 5, IGRAPH_DIRECTED,
|
||
4, 3, 3, 2, 2, 1, 1, 0,
|
||
-1);
|
||
<span class="strong"><strong>igraph_vector_init_int_end</strong></span>(&weights, -1, 1, 1, 1, 1, -1);
|
||
<span class="strong"><strong><a class="link" href="igraph-Flows.html#igraph_mincut" title="2.5. igraph_mincut — Calculates the minimum cut in a graph.">igraph_mincut</a></strong></span>(&g, &value, &partition, &partition2, &cut, &weights);
|
||
<span class="strong"><strong>print_mincut</strong></span>(&g, value, &partition, &partition2, &cut, &weights);
|
||
|
||
<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><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>/* -------------------------------------------- */</em></span>
|
||
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&cut);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&partition2);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&partition);
|
||
|
||
<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_mincut_value"></a>2.6. <code class="function">igraph_mincut_value</code> — The minimum edge cut in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.3.7.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_mincut_value(const igraph_t *graph, igraph_real_t *res,
|
||
const igraph_vector_t *capacity);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p> The minimum edge cut in a graph is the total minimum
|
||
weight of the edges needed to remove from the graph to make the
|
||
graph <span class="emphasis"><em>not</em></span> strongly connected. (If the original graph is not
|
||
strongly connected then this is zero.) Note that in undirected
|
||
graphs strong connectedness is the same as weak connectedness. </p>
|
||
<p> The minimum cut can be calculated with maximum flow
|
||
techniques, although the current implementation does this only for
|
||
directed graphs and a separate non-flow based implementation is
|
||
used for undirected graphs. See Mechthild Stoer and Frank Wagner: A
|
||
simple min-cut algorithm, Journal of the ACM 44 585--591, 1997.
|
||
For directed graphs
|
||
the maximum flow is calculated between a fixed vertex and all the
|
||
other vertices in the graph and this is done in both
|
||
directions. Then the minimum is taken to get the minimum cut.
|
||
|
||
</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 a real variable, the result will be stored
|
||
here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to the capacity vector, it should contain
|
||
the same number of non-negative numbers as the number of edges in
|
||
the graph. If a null pointer then all edges will have unit capacity.
|
||
</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-Flows.html#igraph_mincut" title="2.5. igraph_mincut — Calculates the minimum cut in a graph."><code class="function">igraph_mincut()</code></a>, <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>, <a class="link" href="igraph-Flows.html#igraph_st_mincut_value" title="2.2. igraph_st_mincut_value — The minimum s-t cut in a graph."><code class="function">igraph_st_mincut_value()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
Time complexity: O(log(|V|)*|V|^2) for undirected graphs and
|
||
O(|V|^4) for directed graphs, but see also the discussion at the
|
||
documentation of <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_gomory_hu_tree"></a>2.7. <code class="function">igraph_gomory_hu_tree</code> — Gomory-Hu tree of a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.3.8.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_gomory_hu_tree(const igraph_t *graph,
|
||
igraph_t *tree,
|
||
igraph_vector_t *flows,
|
||
const igraph_vector_t *capacity);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p>
|
||
The Gomory-Hu tree is a concise representation of the value of all the
|
||
maximum flows (or minimum cuts) in a graph. The vertices of the tree
|
||
correspond exactly to the vertices of the original graph in the same order.
|
||
Edges of the Gomory-Hu tree are annotated by flow values. The value of
|
||
the maximum flow (or minimum cut) between an arbitrary (u,v) vertex
|
||
pair in the original graph is then given by the minimum flow value (i.e.
|
||
edge annotation) along the shortest path between u and v in the
|
||
Gomory-Hu tree.
|
||
|
||
</p>
|
||
<p>This implementation uses Gusfield's algorithm to construct the
|
||
Gomory-Hu tree. See the following paper for more details:
|
||
|
||
</p>
|
||
<p>
|
||
Reference:
|
||
|
||
</p>
|
||
<p>
|
||
Gusfield D: Very simple methods for all pairs network flow analysis. SIAM J
|
||
Comput 19(1):143-155, 1990
|
||
<a class="ulink" href="https://doi.org/10.1137/0219009" target="_top">https://doi.org/10.1137/0219009</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>
|
||
The input graph.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>tree</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized graph; the result will be
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>flows</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an uninitialized vector; the flow values
|
||
corresponding to each edge in the Gomory-Hu tree will
|
||
be returned here. You may pass a NULL pointer here if you are
|
||
not interested in the flow values.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>capacity</code></em>:</span></p></td>
|
||
<td><p>
|
||
Vector containing the capacity of the edges. If NULL, then
|
||
every edge is considered to have capacity 1.0.
|
||
</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|^4) since it performs a max-flow calculation
|
||
between vertex zero and every other vertex and max-flow is
|
||
O(|V|^3).
|
||
|
||
</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-Flows.html#igraph_maxflow" title="1.1. igraph_maxflow — Maximum network flow between a pair of vertices."><code class="function">igraph_maxflow()</code></a>
|
||
</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="connectivity"></a>3. Connectivity</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_st_edge_connectivity">3.1. <code class="function">igraph_st_edge_connectivity</code> — Edge connectivity of a pair of vertices.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_edge_connectivity">3.2. <code class="function">igraph_edge_connectivity</code> — The minimum edge connectivity in a graph.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_st_vertex_connectivity">3.3. <code class="function">igraph_st_vertex_connectivity</code> — The vertex connectivity of a pair of vertices.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_vertex_connectivity">3.4. <code class="function">igraph_vertex_connectivity</code> — The vertex connectivity of a graph.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_st_edge_connectivity"></a>3.1. <code class="function">igraph_st_edge_connectivity</code> — Edge connectivity of a pair of vertices.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.4.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_st_edge_connectivity(const igraph_t *graph,
|
||
igraph_int_t *res,
|
||
igraph_int_t source,
|
||
igraph_int_t target);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
The edge connectivity of two vertices (<em class="parameter"><code>source</code></em> and <em class="parameter"><code>target</code></em>) is the
|
||
minimum number of edges that have to be deleted from the graph to eliminate
|
||
all paths from <em class="parameter"><code>source</code></em> to <em class="parameter"><code>target</code></em>.
|
||
|
||
</p>
|
||
<p>This function uses the maximum flow algorithm to calculate
|
||
the edge connectivity.
|
||
|
||
</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, it has to be directed.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>res</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an integer, the result will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</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|^3).
|
||
|
||
</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-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>, <a class="link" href="igraph-Flows.html#igraph_edge_disjoint_paths" title="4.1. igraph_edge_disjoint_paths — The maximum number of edge-disjoint paths between two vertices."><code class="function">igraph_edge_disjoint_paths()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_edge_connectivity" title="3.2. igraph_edge_connectivity — The minimum edge connectivity in a graph."><code class="function">igraph_edge_connectivity()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_st_vertex_connectivity" title="3.3. igraph_st_vertex_connectivity — The vertex connectivity of a pair of vertices."><code class="function">igraph_st_vertex_connectivity()</code></a>, <a class="link" href="igraph-Flows.html#igraph_vertex_connectivity" title="3.4. igraph_vertex_connectivity — The vertex connectivity of a graph."><code class="function">igraph_vertex_connectivity()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_edge_connectivity"></a>3.2. <code class="function">igraph_edge_connectivity</code> — The minimum edge connectivity in a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.4.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_edge_connectivity(const igraph_t *graph,
|
||
igraph_int_t *res,
|
||
igraph_bool_t checks);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p> This is the minimum of the edge connectivity over all
|
||
pairs of vertices in the graph. </p>
|
||
<p>
|
||
The edge connectivity of a graph is the same as group adhesion as
|
||
defined in Douglas R. White and Frank Harary: The cohesiveness of
|
||
blocks in social networks: node connectivity and conditional
|
||
density, Sociological Methodology 31:305--359, 2001
|
||
<a class="ulink" href="https://doi.org/10.1111/0081-1750.00098" target="_top">https://doi.org/10.1111/0081-1750.00098</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>
|
||
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 integer, the result will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>checks</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean constant. Whether to check that the graph is
|
||
connected and also the degree of the vertices. If the graph is
|
||
not (strongly) connected then the connectivity is obviously zero. Otherwise
|
||
if the minimum degree is one then the edge connectivity is also
|
||
one. It is a good idea to perform these checks, as they can be
|
||
done quickly compared to the connectivity calculation itself.
|
||
They were suggested by Peter McMahan, thanks Peter.
|
||
</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(log(|V|)*|V|^2) for undirected graphs and
|
||
O(|V|^4) for directed graphs, but see also the discussion at the
|
||
documentation of <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
|
||
</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-Flows.html#igraph_st_edge_connectivity" title="3.1. igraph_st_edge_connectivity — Edge connectivity of a pair of vertices."><code class="function">igraph_st_edge_connectivity()</code></a>, <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_vertex_connectivity" title="3.4. igraph_vertex_connectivity — The vertex connectivity of a graph."><code class="function">igraph_vertex_connectivity()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_st_vertex_connectivity"></a>3.3. <code class="function">igraph_st_vertex_connectivity</code> — The vertex connectivity of a pair of vertices.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.4.4.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_st_vertex_connectivity(
|
||
const igraph_t *graph,
|
||
igraph_int_t *res,
|
||
igraph_int_t source,
|
||
igraph_int_t target,
|
||
igraph_vconn_nei_t neighbors);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
The vertex connectivity of two vertices (<em class="parameter"><code>source</code></em> and
|
||
<em class="parameter"><code>target</code></em>) is the minimum number of vertices that must be
|
||
deleted to eliminate all paths from <em class="parameter"><code>source</code></em> to <em class="parameter"><code>target</code></em>. Directed paths are considered in directed graphs.
|
||
|
||
</p>
|
||
<p>
|
||
The vertex connectivity of a pair is the same as the number
|
||
of different (i.e. node-independent) paths from source to
|
||
target, assuming no direct edges between them.
|
||
|
||
</p>
|
||
<p>
|
||
The current implementation uses maximum flow calculations to
|
||
obtain the result.
|
||
|
||
</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 integer, the result will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>neighbors</code></em>:</span></p></td>
|
||
<td><p>
|
||
A constant giving what to do if the two vertices
|
||
are connected. Possible values:
|
||
<code class="constant">IGRAPH_VCONN_NEI_ERROR</code>, stop with an error message,
|
||
<code class="constant">IGRAPH_VCONN_NEI_NEGATIVE</code>, return -1.
|
||
<code class="constant">IGRAPH_VCONN_NEI_NUMBER_OF_NODES</code>, return the number of nodes.
|
||
<code class="constant">IGRAPH_VCONN_NEI_IGNORE</code>, ignore the fact that the two vertices
|
||
are connected and calculate the number of vertices needed
|
||
to eliminate all paths except for the trivial (direct) paths
|
||
between <em class="parameter"><code>source</code></em> and <em class="parameter"><code>vertex</code></em>.
|
||
</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|^3), but see the discussion at <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
|
||
</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-Flows.html#igraph_vertex_connectivity" title="3.4. igraph_vertex_connectivity — The vertex connectivity of a graph."><code class="function">igraph_vertex_connectivity()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_edge_connectivity" title="3.2. igraph_edge_connectivity — The minimum edge connectivity in a graph."><code class="function">igraph_edge_connectivity()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_vertex_connectivity"></a>3.4. <code class="function">igraph_vertex_connectivity</code> — The vertex connectivity of a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.4.5.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_vertex_connectivity(
|
||
const igraph_t *graph, igraph_int_t *res,
|
||
igraph_bool_t checks);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p> The vertex connectivity of a graph is the minimum
|
||
vertex connectivity along each pairs of vertices in the graph.
|
||
</p>
|
||
<p> The vertex connectivity of a graph is the same as group
|
||
cohesion as defined in Douglas R. White and Frank Harary: The
|
||
cohesiveness of blocks in social networks: node connectivity and
|
||
conditional density, Sociological Methodology 31:305--359, 2001
|
||
<a class="ulink" href="https://doi.org/10.1111/0081-1750.00098" target="_top">https://doi.org/10.1111/0081-1750.00098</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>
|
||
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 integer, the result will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>checks</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean constant. Whether to check if the graph is
|
||
connected or complete and also the degree of the vertices. If the graph is
|
||
not (strongly) connected then the connectivity is obviously zero. Otherwise
|
||
if the minimum degree is 1 then the vertex connectivity is also
|
||
1. If the graph is complete, the connectivity is the vertex count
|
||
minus one. It is a good idea to perform these checks, as they can be
|
||
done quickly compared to the connectivity calculation itself.
|
||
They were suggested by Peter McMahan, thanks Peter.
|
||
</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|^5).
|
||
|
||
</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-Flows.html#igraph_st_vertex_connectivity" title="3.3. igraph_st_vertex_connectivity — The vertex connectivity of a pair of vertices."><code class="function">igraph_st_vertex_connectivity()</code></a>, <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>,
|
||
and <a class="link" href="igraph-Flows.html#igraph_edge_connectivity" title="3.2. igraph_edge_connectivity — The minimum edge connectivity in a graph."><code class="function">igraph_edge_connectivity()</code></a>.
|
||
</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="edge-and-vertex-disjoint-paths"></a>4. Edge- and vertex-disjoint paths</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_edge_disjoint_paths">4.1. <code class="function">igraph_edge_disjoint_paths</code> — The maximum number of edge-disjoint paths between two vertices.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_vertex_disjoint_paths">4.2. <code class="function">igraph_vertex_disjoint_paths</code> — Maximum number of vertex-disjoint paths between two vertices.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_edge_disjoint_paths"></a>4.1. <code class="function">igraph_edge_disjoint_paths</code> — The maximum number of edge-disjoint paths between two vertices.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.5.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_edge_disjoint_paths(const igraph_t *graph,
|
||
igraph_int_t *res,
|
||
igraph_int_t source,
|
||
igraph_int_t target);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
A set of paths between two vertices is called edge-disjoint if they do not
|
||
share any edges. The maximum number of edge-disjoint paths are calculated
|
||
by this function using maximum flow techniques. Directed paths are
|
||
considered in directed graphs.
|
||
|
||
</p>
|
||
<p>Note that the number of disjoint paths is the same as the
|
||
edge connectivity of the two vertices using uniform edge weights.
|
||
|
||
</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, can be directed or undirected.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>res</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an integer variable, the result will be
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</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|^3), but see the discussion at <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
|
||
</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-Flows.html#igraph_vertex_disjoint_paths" title="4.2. igraph_vertex_disjoint_paths — Maximum number of vertex-disjoint paths between two vertices."><code class="function">igraph_vertex_disjoint_paths()</code></a>, <a class="link" href="igraph-Flows.html#igraph_st_edge_connectivity" title="3.1. igraph_st_edge_connectivity — Edge connectivity of a pair of vertices."><code class="function">igraph_st_edge_connectivity()</code></a>, <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_vertex_disjoint_paths"></a>4.2. <code class="function">igraph_vertex_disjoint_paths</code> — Maximum number of vertex-disjoint paths between two vertices.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.5.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_vertex_disjoint_paths(const igraph_t *graph,
|
||
igraph_int_t *res,
|
||
igraph_int_t source,
|
||
igraph_int_t target);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
A set of paths between two vertices is called vertex-disjoint if
|
||
they share no vertices, other than the endpoints. This function computes
|
||
the largest number of such paths that can be constructed between
|
||
a source and a target vertex. The calculation is performed by using maximum
|
||
flow techniques.
|
||
|
||
</p>
|
||
<p>
|
||
When there are no edges from the source to the target, the number of
|
||
vertex-disjoint paths is the same as the vertex connectivity of
|
||
the two vertices. When some edges are present, each one of them
|
||
contributes one extra path.
|
||
|
||
</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 integer variable, the result will be
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>source</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the source vertex.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>target</code></em>:</span></p></td>
|
||
<td><p>
|
||
The id of the target vertex.
|
||
</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|^3).
|
||
|
||
</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-Flows.html#igraph_edge_disjoint_paths" title="4.1. igraph_edge_disjoint_paths — The maximum number of edge-disjoint paths between two vertices."><code class="function">igraph_edge_disjoint_paths()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_st_vertex_connectivity" title="3.3. igraph_st_vertex_connectivity — The vertex connectivity of a pair of vertices."><code class="function">igraph_st_vertex_connectivity()</code></a>, <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
</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="graph-adhesion-and-cohesion"></a>5. Graph adhesion and cohesion</h2></div></div></div>
|
||
<div class="toc"><dl class="toc">
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_adhesion">5.1. <code class="function">igraph_adhesion</code> — Graph adhesion, this is (almost) the same as edge connectivity.</a></span></dt>
|
||
<dt><span class="section"><a href="igraph-Flows.html#igraph_cohesion">5.2. <code class="function">igraph_cohesion</code> — Graph cohesion, this is the same as vertex connectivity.</a></span></dt>
|
||
</dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_adhesion"></a>5.1. <code class="function">igraph_adhesion</code> — Graph adhesion, this is (almost) the same as edge connectivity.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.6.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_adhesion(const igraph_t *graph,
|
||
igraph_int_t *res,
|
||
igraph_bool_t checks);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p> This quantity is defined by White and Harary in
|
||
The cohesiveness of blocks in social networks: node connectivity and
|
||
conditional density, (Sociological Methodology 31:305--359, 2001)
|
||
and basically it is the edge connectivity of the graph
|
||
with uniform edge weights.
|
||
|
||
</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, either directed or undirected.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>res</code></em>:</span></p></td>
|
||
<td><p>
|
||
Pointer to an integer, the result will be stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>checks</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean constant. Whether to check that the graph is
|
||
connected and also the degree of the vertices. If the graph is
|
||
not (strongly) connected then the adhesion is obviously zero. Otherwise
|
||
if the minimum degree is one then the adhesion is also
|
||
one. It is a good idea to perform these checks, as they can be
|
||
done quickly compared to the edge connectivity calculation itself.
|
||
They were suggested by Peter McMahan, thanks Peter.
|
||
* </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(log(|V|)*|V|^2) for undirected graphs and
|
||
O(|V|^4) for directed graphs, but see also the discussion at the
|
||
documentation of <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
|
||
</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-Flows.html#igraph_cohesion" title="5.2. igraph_cohesion — Graph cohesion, this is the same as vertex connectivity."><code class="function">igraph_cohesion()</code></a>, <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>, <a class="link" href="igraph-Flows.html#igraph_edge_connectivity" title="3.2. igraph_edge_connectivity — The minimum edge connectivity in a graph."><code class="function">igraph_edge_connectivity()</code></a>, <a class="link" href="igraph-Flows.html#igraph_mincut_value" title="2.6. igraph_mincut_value — The minimum edge cut in a graph."><code class="function">igraph_mincut_value()</code></a>.
|
||
</p></td>
|
||
</tr></tbody>
|
||
</table></div>
|
||
<p>
|
||
|
||
</p>
|
||
</div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_cohesion"></a>5.2. <code class="function">igraph_cohesion</code> — Graph cohesion, this is the same as vertex connectivity.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.6.3.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_cohesion(const igraph_t *graph,
|
||
igraph_int_t *res,
|
||
igraph_bool_t checks);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
</p>
|
||
<p> This quantity was defined by White and Harary in <span class="quote">“<span class="quote">The
|
||
cohesiveness of blocks in social networks: node connectivity and
|
||
conditional density</span>”</span>, (Sociological Methodology 31:305--359, 2001)
|
||
and it is the same as the vertex connectivity of a 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>
|
||
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 integer variable, the result will be
|
||
stored here.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>checks</code></em>:</span></p></td>
|
||
<td><p>
|
||
Boolean constant. Whether to check that the graph is
|
||
connected and also the degree of the vertices. If the graph is
|
||
not (strongly) connected then the cohesion is obviously zero. Otherwise
|
||
if the minimum degree is one then the cohesion is also
|
||
one. It is a good idea to perform these checks, as they can be
|
||
done quickly compared to the vertex connectivity calculation itself.
|
||
They were suggested by Peter McMahan, thanks Peter.
|
||
</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|^4), |V| is the number of vertices. In
|
||
practice it is more like O(|V|^2), see <a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
|
||
</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-Flows.html#igraph_vertex_connectivity" title="3.4. igraph_vertex_connectivity — The vertex connectivity of a graph."><code class="function">igraph_vertex_connectivity()</code></a>, <a class="link" href="igraph-Flows.html#igraph_adhesion" title="5.1. igraph_adhesion — Graph adhesion, this is (almost) the same as edge connectivity."><code class="function">igraph_adhesion()</code></a>,
|
||
<a class="link" href="igraph-Flows.html#igraph_maxflow_value" title="1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm."><code class="function">igraph_maxflow_value()</code></a>.
|
||
</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="cohesive-blocks"></a>6. Cohesive blocks</h2></div></div></div>
|
||
<div class="toc"><dl class="toc"><dt><span class="section"><a href="igraph-Flows.html#igraph_cohesive_blocks">6.1. <code class="function">igraph_cohesive_blocks</code> — Identifies the hierarchical cohesive block structure of a graph.</a></span></dt></dl></div>
|
||
<div class="section">
|
||
<div class="titlepage"><div><div><h3 class="title">
|
||
<a name="igraph_cohesive_blocks"></a>6.1. <code class="function">igraph_cohesive_blocks</code> — Identifies the hierarchical cohesive block structure of a graph.</h3></div></div></div>
|
||
<a class="indexterm" name="id-1.24.7.2.2"></a><p>
|
||
</p>
|
||
<div class="informalexample"><pre class="programlisting">
|
||
igraph_error_t igraph_cohesive_blocks(const igraph_t *graph,
|
||
igraph_vector_int_list_t *blocks,
|
||
igraph_vector_int_t *cohesion,
|
||
igraph_vector_int_t *parent,
|
||
igraph_t *block_tree);
|
||
</pre></div>
|
||
<p>
|
||
</p>
|
||
<p>
|
||
|
||
|
||
|
||
Cohesive blocking is a method of determining hierarchical subsets of
|
||
graph vertices based on their structural cohesion (or vertex
|
||
connectivity). For a given graph G, a subset of its vertices
|
||
S is said to be maximally k-cohesive if there is
|
||
no superset of S with vertex connectivity greater than or equal to k.
|
||
Cohesive blocking is a process through which, given a
|
||
k-cohesive set of vertices, maximally l-cohesive subsets are
|
||
recursively identified with l>k. Thus a hiearchy of vertex subsets
|
||
is found, with the entire graph G at its root.
|
||
|
||
</p>
|
||
<p>
|
||
This function implements cohesive blocking and
|
||
calculates the complete cohesive block hierarchy of a graph.
|
||
|
||
</p>
|
||
<p>
|
||
See the following reference for details:
|
||
|
||
</p>
|
||
<p>
|
||
J. Moody and D. R. White. Structural
|
||
cohesion and embeddedness: A hierarchical concept of social
|
||
groups. American Sociological Review, 68(1):103--127, Feb 2003.
|
||
<a class="ulink" href="https://doi.org/10.2307/3088904" target="_top">https://doi.org/10.2307/3088904</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>
|
||
The input graph. It must be undirected and simple. See
|
||
<a class="link" href="igraph-Structural.html#igraph_is_simple" title="20.1. igraph_is_simple — Decides whether the input graph is a simple graph."><code class="function">igraph_is_simple()</code></a>.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>blocks</code></em>:</span></p></td>
|
||
<td><p>
|
||
If not a null pointer, then it must be an initialized
|
||
list of integers vectors; the cohesive blocks will be stored here.
|
||
Each block is encoded with a vector of type <a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1. About igraph_vector_t objects"><code class="function">igraph_vector_int_t</code></a> that
|
||
contains the vertex IDs of the block.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>cohesion</code></em>:</span></p></td>
|
||
<td><p>
|
||
If not a null pointer, then it must be an initialized
|
||
vector and the cohesion of the blocks is stored here, in the same
|
||
order as the blocks in the <em class="parameter"><code>blocks</code></em> vector list.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>parent</code></em>:</span></p></td>
|
||
<td><p>
|
||
If not a null pointer, then it must be an initialized
|
||
vector and the block hierarchy is stored here. For each block, the
|
||
ID (i.e. the position in the <em class="parameter"><code>blocks</code></em> vector list) of its
|
||
parent block is stored. For the top block in the hierarchy,
|
||
<code class="literal">-1</code> is stored.
|
||
</p></td>
|
||
</tr>
|
||
<tr>
|
||
<td><p><span class="term"><em class="parameter"><code>block_tree</code></em>:</span></p></td>
|
||
<td><p>
|
||
If not a null pointer, then it must be a pointer
|
||
to an uninitialized graph, and the block hierarchy is stored
|
||
here as an igraph graph. The vertex IDs correspond to the order
|
||
of the blocks in the <em class="parameter"><code>blocks</code></em> vector.
|
||
</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.24.7.2.11.1"></a><p class="title"><b>Example 23.6. File <code class="code">examples/simple/cohesive_blocks.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_list_t blocks;
|
||
igraph_vector_int_t cohesion;
|
||
igraph_vector_int_t parent;
|
||
igraph_t block_tree;
|
||
igraph_int_t i;
|
||
|
||
<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_famous" title="8.1. igraph_famous — Create a famous graph by simply providing its name.">igraph_famous</a></strong></span>(&g, "zachary");
|
||
<span class="strong"><strong>igraph_vector_int_list_init</strong></span>(&blocks, 0);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&cohesion, 0);
|
||
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&parent, 0);
|
||
|
||
<span class="strong"><strong><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.">igraph_cohesive_blocks</a></strong></span>(&g, &blocks, &cohesion, &parent,
|
||
&block_tree);
|
||
|
||
<span class="strong"><strong>printf</strong></span>("Blocks:\n");
|
||
<span class="strong"><strong>for</strong></span> (i = 0; i < <span class="strong"><strong>igraph_vector_int_list_size</strong></span>(&blocks); i++) {
|
||
igraph_vector_int_t *sg = <span class="strong"><strong>igraph_vector_int_list_get_ptr</strong></span>(&blocks, i);
|
||
<span class="strong"><strong>printf</strong></span>(" ");
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(sg);
|
||
}
|
||
<span class="strong"><strong>printf</strong></span>("Cohesion:\n ");
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&cohesion);
|
||
<span class="strong"><strong>printf</strong></span>("Parents:\n ");
|
||
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&parent);
|
||
<span class="strong"><strong>printf</strong></span>("Block 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>(&block_tree, stdout);
|
||
|
||
<span class="strong"><strong>igraph_vector_int_list_destroy</strong></span>(&blocks);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&cohesion);
|
||
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&parent);
|
||
<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>(&block_tree);
|
||
|
||
<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>
|
||
<table class="navigation-footer" width="100%" summary="Navigation footer" cellpadding="2" cellspacing="0"><tr valign="middle">
|
||
<td align="left"><a accesskey="p" href="igraph-Coloring.html"><b>← Chapter 22. Graph coloring</b></a></td>
|
||
<td align="right"><a accesskey="n" href="igraph-Separators.html"><b>Chapter 24. Vertex separators →</b></a></td>
|
||
</tr></table>
|
||
</body>
|
||
</html>
|