24.10/documentation/doxygen/html/index.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.11.0"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>LAL: Linear Arrangement Library: Documentation of the Linear Arrangement Library</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="clipboard.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="cookie.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  extensions: ["tex2jax.js"],
  jax: ["input/TeX","output/HTML-CSS"],
});
</script>
<script type="text/javascript" async="async" src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr id="projectrow">
  <td id="projectalign">
   <div id="projectname">LAL: Linear Arrangement Library<span id="projectnumber">&#160;24.10.00</span>
   </div>
   <div id="projectbrief">A library focused on algorithms on linear arrangements of graphs.</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.11.0 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&amp;dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&amp;dn=expat.txt MIT */
$(function() { codefold.init(0); });
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&amp;dn=expat.txt MIT */
$(function() {
  initMenu('',true,false,'search.php','Search',false);
  $(function() { init_search(); });
});
/* @license-end */
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="doc-content">
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&amp;dn=expat.txt MIT */
$(function(){ initResizable(false); });
/* @license-end */
</script>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>

<div><div class="header">
  <div class="headertitle"><div class="title">Documentation of the Linear Arrangement Library </div></div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>This library offers a wide variety of algorithms related to linear arrangements of graphs so as to provide researchers (mainly, but not exclusively) in the field of Quantitative Linguistics with a toolset with which they can perform statistical analyses on different corpora of treebanks efficiently and effectively. This library implements several state-of-the-art algorithms and offers a variety of functionalities. While most of the functions have been generalised to be applicable to general graphs, we also provide specialised functions for trees, which are more efficient than their more general counterparts. In order to understand the documentation of the functions and classes in this library, readers are urged to read through the <a class="el" href="LAL_concepts.html">Important concepts in LAL</a> page to learn about the terminology and notation.</p>
<p>The main goal of this library is to provide algorithms with which the library's users can use to do statistical studies. One of the most attractive features offered in this library is that of treebank collection processing. This library offers a class that automatically processes a collection and computes several metrics based on the capabilities of the library. See class <a class="el" href="classlal_1_1io_1_1treebank__collection__processor.html">lal::io::treebank_collection_processor</a> and <a class="el" href="classlal_1_1io_1_1treebank__processor.html">lal::io::treebank_processor</a> for details. We also provide classes for custom processing of treebanks (see <a class="el" href="classlal_1_1io_1_1treebank__collection__reader.html">lal::io::treebank_collection_reader</a> and <a class="el" href="classlal_1_1io_1_1treebank__reader.html">lal::io::treebank_reader</a>).</p>
<p>All the features of syntactic dependency trees that can be calculated with the algorithms in this library are gathered in the namespaces <a class="el" href="namespacelal_1_1linarr.html">lal::linarr</a> and in <a class="el" href="namespacelal_1_1properties.html">lal::properties</a>. These features include, but are not limited to,</p><ul>
<li>the sum of edge lengths \(D\) (<a class="el" href="namespacelal_1_1linarr.html#ab70693683a8da54a2e4350c665067cf1">lal::linarr::sum_edge_lengths</a>),</li>
<li>the expectation and variance of the sum of edge lengths<ul>
<li>expectation of \(D\) in uniformly random unconstrained arrangements (<a class="el" href="namespacelal_1_1properties.html#a80c20fa410c8b9b216afe7f5241209a6">lal::properties::exp_sum_edge_lengths</a>),</li>
<li>variance of \(D\) in uniformly random unconstrained arrangements (<a class="el" href="namespacelal_1_1properties.html#ade6a3f20263e2a982cfc5dc59facaf40">lal::properties::var_sum_edge_lengths</a>),</li>
<li>expectation of \(D\) in uniformly random bipartite arrangements (<a class="el" href="namespacelal_1_1properties.html#ada47cac794ac356fffa07e54ac0c58cb">lal::properties::exp_sum_edge_lengths_bipartite</a>),</li>
<li>expectation of \(D\) in uniformly random planar arrangements (<a class="el" href="namespacelal_1_1properties.html#ac053f8c3c640e10636970e6800b6e661">lal::properties::exp_sum_edge_lengths_planar</a>),</li>
<li>expectation of \(D\) in uniformly random projective arrangements (<a class="el" href="namespacelal_1_1properties.html#af19d68977283afd82cae661106bbb0f8">lal::properties::exp_sum_edge_lengths_projective</a>),</li>
</ul>
</li>
<li>the computation of optimal arrangements with respect to the sum of edge lengths:<ul>
<li>minimum unconstrained arrangements (<a class="el" href="namespacelal_1_1linarr.html#a450d0dd41fec42a39bb1204ecedaaa91">lal::linarr::min_sum_edge_lengths</a>), with free choice on the algorithm to be used (<a class="el" href="namespacelal_1_1linarr.html#a1c6a617eb12e032ee641fd390776ff3f">lal::linarr::algorithms_Dmin</a>),</li>
<li>minimum bipartite arrangements (<a class="el" href="namespacelal_1_1linarr.html#a5b0afdaae4943c26a3ba771d47ed92fb">lal::linarr::min_sum_edge_lengths_bipartite</a>),</li>
<li>minimum planar arrangements (<a class="el" href="namespacelal_1_1linarr.html#a8ee049d439a7e8dd41ac0145679a84bb">lal::linarr::min_sum_edge_lengths_planar</a>), with free choice on the algorithm to be used (<a class="el" href="namespacelal_1_1linarr.html#a4a49efcc64c3b63502ad8cc18d508ce3">lal::linarr::algorithms_Dmin_planar</a>),</li>
<li>minimum projective arrangements (<a class="el" href="namespacelal_1_1linarr.html#aff8ac86ade398306f32ee39692ebfe4a">lal::linarr::min_sum_edge_lengths_projective</a>), with free choice on the algorithm to be used (<a class="el" href="namespacelal_1_1linarr.html#a30bc00af5439a56f037ed84875f1911f">lal::linarr::algorithms_Dmin_projective</a>),</li>
<li>maximum arrangements with at most one thistle vertex (<a class="el" href="namespacelal_1_1linarr.html#a7c8fab121c5848258cca520291219485">lal::linarr::max_sum_edge_lengths_1_le_thistle</a>),</li>
<li>maximum arrangements with exactly one thistle vertex (<a class="el" href="namespacelal_1_1linarr.html#a78ceee860452715ca4739adc28e53226">lal::linarr::max_sum_edge_lengths_1_eq_thistle</a>),</li>
<li>maximum bipartite arrangements (<a class="el" href="namespacelal_1_1linarr.html#a19e9a8803e21a8cfdef8f2f327e4a1ae">lal::linarr::max_sum_edge_lengths_bipartite</a>),</li>
<li>maximum planar arrangements (<a class="el" href="namespacelal_1_1linarr.html#aadd6d6ed9cadb57228200d32c3a99191">lal::linarr::max_sum_edge_lengths_planar</a>),</li>
<li>maximum projective arrangements (<a class="el" href="namespacelal_1_1linarr.html#a0886a4326be3b40cf34ee526514d60ab">lal::linarr::max_sum_edge_lengths_projective</a>),</li>
</ul>
</li>
<li>the number of crossings (<a class="el" href="namespacelal_1_1linarr.html#a3806eb869914f45cf79c15e8aa7d2a51">lal::linarr::num_crossings</a>), and the expectation and variance of the number of crossings (see <a class="el" href="namespacelal_1_1properties.html#ab8ff16428584d88aba05a4b677444a4b">lal::properties::exp_num_crossings</a> and <a class="el" href="namespacelal_1_1properties.html#aa58446707ce2f604cf693edbb8f122db">lal::properties::var_num_crossings</a>),</li>
<li>any moment of the degree of the vertices of a graph (see <a class="el" href="namespacelal_1_1properties.html#a317c023347f5c68745d207d1fba0a3f3">lal::properties::moment_degree</a> and its variants),</li>
<li>the mean dependency distance (<a class="el" href="namespacelal_1_1linarr.html#a2030c0f279ced9571405cebe5675e241">lal::linarr::mean_dependency_distance</a>),</li>
<li>the mean dependency distance over ensembles of graphs (<a class="el" href="namespacelal_1_1linarr.html#a1f8c78736426eea6282258b26534c7e5">lal::linarr::mean_dependency_distance_1level</a> and <a class="el" href="namespacelal_1_1linarr.html#ac837af66d13aa3e2865a6737aec34e7a">lal::linarr::mean_dependency_distance_2level</a>),</li>
<li>the mean hierarchical distance (<a class="el" href="namespacelal_1_1properties.html#a0c70ec4072e1df27592aa7a51876c1a9">lal::properties::mean_hierarchical_distance</a>),</li>
<li>the headedness of a tree (<a class="el" href="namespacelal_1_1linarr.html#acc15417e84e2d272ca8d49a266929e12">lal::linarr::head_initial</a>),</li>
<li>the type of syntactic dependency trees according to their projectivity (<a class="el" href="namespacelal_1_1linarr.html#a7f4c5571263d6aaeddeaecc3d37f7e1c">lal::linarr::syntactic_dependency_tree_classify</a>).</li>
<li>calculation of the centre of a tree (<a class="el" href="namespacelal_1_1properties.html#ada5517f223bcb1369b625a840dc9c8fa">lal::properties::tree_centre</a>), the centroid of a tree (<a class="el" href="namespacelal_1_1properties.html#adda281d4c9e024ea87844756ffbd945e">lal::properties::tree_centroid</a>), a tree's diameter (<a class="el" href="namespacelal_1_1properties.html#a3b40731d0c6eb1115f4ca7c655841078">lal::properties::tree_diameter</a>).</li>
</ul>
<p>As extra features, useful for experimentation, are the generation of different types of trees, all of which are available in the <a class="el" href="namespacelal_1_1generate.html">lal::generate</a> namespace. We have implemented existing techniques (cited accordingly) or made or own to enumerate</p><ul>
<li>all labelled (<a class="el" href="classlal_1_1generate_1_1all__lab__free__trees.html">lal::generate::all_lab_free_trees</a>) and unlabelled (<a class="el" href="classlal_1_1generate_1_1all__ulab__free__trees.html">lal::generate::all_ulab_free_trees</a>) free trees,</li>
<li>all labelled (<a class="el" href="classlal_1_1generate_1_1all__lab__rooted__trees.html">lal::generate::all_lab_rooted_trees</a>) and unlabelled (<a class="el" href="classlal_1_1generate_1_1all__ulab__rooted__trees.html">lal::generate::all_ulab_rooted_trees</a>) rooted trees,</li>
<li>all projective arrangements of rooted trees (<a class="el" href="classlal_1_1generate_1_1all__projective__arrangements.html">lal::generate::all_projective_arrangements</a>),</li>
<li>all planar arrangements of free trees (<a class="el" href="classlal_1_1generate_1_1all__planar__arrangements.html">lal::generate::all_planar_arrangements</a>),</li>
</ul>
<p>and to generate uniformly at random</p><ul>
<li>labelled (<a class="el" href="classlal_1_1generate_1_1rand__lab__free__trees.html">lal::generate::rand_lab_free_trees</a>) and unlabelled (<a class="el" href="classlal_1_1generate_1_1rand__ulab__free__trees.html">lal::generate::rand_ulab_free_trees</a>) free trees,</li>
<li>labelled (<a class="el" href="classlal_1_1generate_1_1rand__lab__rooted__trees.html">lal::generate::rand_lab_rooted_trees</a>) and unlabelled (<a class="el" href="classlal_1_1generate_1_1rand__ulab__rooted__trees.html">lal::generate::rand_ulab_rooted_trees</a>) rooted trees,</li>
<li>projective arrangements of rooted trees (<a class="el" href="classlal_1_1generate_1_1rand__projective__arrangements.html">lal::generate::rand_projective_arrangements</a>),</li>
<li>planar arrangements of free trees (<a class="el" href="classlal_1_1generate_1_1rand__planar__arrangements.html">lal::generate::rand_planar_arrangements</a>).</li>
</ul>
<p>The documentation of each class includes usage examples.</p>
<p>This library implements several types of graphs that can be found in the <a class="el" href="namespacelal_1_1graphs.html">lal::graphs</a> namespace.</p>
<h1><a class="anchor" id="MP_basic_DS"></a>
The basic data structures in this library</h1>
<p>In order to be able to use the library comfortably, its users must take good note of the different data structures that are the library's core.</p>
<p>With LAL, most metrics can be calculated as exact rational numbers (see <a class="el" href="classlal_1_1numeric_1_1rational.html">lal::numeric::rational</a>), but also as floating point values of double precision. For the former, add the suffix '_rational' at the end of the function name. For example, the function <a class="el" href="namespacelal_1_1properties.html#aa58446707ce2f604cf693edbb8f122db">lal::properties::var_num_crossings</a> returns the variance of the number of crossings 'C' as a floating point value. By adding the suffix, i.e., <a class="el" href="namespacelal_1_1properties.html#ad80fca59dc093300ae576c379a768452">lal::properties::var_num_crossings_rational</a>, we obtain said variance as an exact rational value. To see what a rational value is in the context of this library, see the documentation of the namespace <a class="el" href="namespacelal_1_1numeric.html">lal::numeric</a>.</p>
<h2><a class="anchor" id="MP_basic_DS_integer_rational"></a>
Exact integer and rational arithmetic</h2>
<p>Most operations in this library are done using exact integer and rational arithmetic. Such arithmetic is powered by the GMP library (see <a class="el" href="citelist.html#CITEREF_GMP_library">[26]</a>). We have wrapped their C structures into the classes <a class="el" href="classlal_1_1numeric_1_1integer.html">lal::numeric::integer</a> and <a class="el" href="classlal_1_1numeric_1_1rational.html">lal::numeric::rational</a>.</p>
<h2><a class="anchor" id="MP_basic_DS_graphs"></a>
The different types of graphs</h2>
<p>As it should be expected, this library offers a number of different graph abstractions: undirected graphs (see <a class="el" href="classlal_1_1graphs_1_1undirected__graph.html">lal::graphs::undirected_graph</a>), directed graphs (see <a class="el" href="classlal_1_1graphs_1_1directed__graph.html">lal::graphs::directed_graph</a>), free trees (see <a class="el" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a>) and roted trees (see <a class="el" href="classlal_1_1graphs_1_1rooted__tree.html">lal::graphs::rooted_tree</a>), all of which can be found within the <a class="el" href="namespacelal_1_1graphs.html">lal::graphs</a> namespace.</p>
<h3><a class="anchor" id="MP_basic_DS_graphs_internal"></a>
The internal structure of graphs</h3>
<p>Although all graphs should be regarded as unlabelled, each node carries an implicit labelling. Such labelling has a most trivial nature since each node is labelled with a number between 0 and the total number of vertices minus one.</p>
<p>Due to most graphs being sparse, the data structure of choice are adjacency lists where each vertex has a list of neighbouring nodes, or simply neighbors, associated to it. The user can affect the order of appearance of neighbors in multiple ways. One of them is, evidently, the order in which edges are added. Another way is via the <a class="el" href="classlal_1_1graphs_1_1graph.html#abe2c7decb104857bd857c769feb75c98">lal::graphs::graph::normalize</a> function, which sorts every list of neighbors increasingly by index. By default, the addition of edges is normalising, namely the following code</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t(4);</div>
<div class="line">t.add_edge(0,1,<span class="keyword">false</span>,<span class="keyword">false</span>).add_edge(0,3,<span class="keyword">false</span>,<span class="keyword">false</span>).add_edge(0,2,<span class="keyword">false</span>,<span class="keyword">false</span>);</div>
<div class="line">t.normalize();</div>
<div class="line">cout &lt;&lt; t &lt;&lt; endl;</div>
<div class="ttc" id="aclasslal_1_1graphs_1_1free__tree_html"><div class="ttname"><a href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a></div><div class="ttdoc">Free tree graph class.</div><div class="ttdef"><b>Definition</b> free_tree.hpp:60</div></div>
</div><!-- fragment --><p>produces the same output as</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t(4);</div>
<div class="line">t.add_edge(0,1).add_edge(0,3).add_edge(0,2);</div>
<div class="line">cout &lt;&lt; t &lt;&lt; endl;</div>
</div><!-- fragment --><p>which is</p>
<pre class="fragment">0: 1 2 3
1: 0
2: 0
3: 0
</pre><p>The output is easy to interpret: the first line indicates the nodes are incident to vertex 0, the second line indicates the nodes incident to vertex 1, and so on. Without normalisation (neither the call to <a class="el" href="classlal_1_1graphs_1_1graph.html#abe2c7decb104857bd857c769feb75c98">lal::graphs::free_tree::normalize</a>, and using 'false' in the optional parameters), the output is</p>
<pre class="fragment">0: 1 3 2
1: 0
2: 0
3: 0
</pre><p>where only the first line changes.</p>
<p>Such normalisation is required by some of the algorithms in this library. Without proper normalisation, the algorithms are not likely to compute correct values. The parameter that governs the graphs' normalisation is called the normalisation parameter.</p>
<p>The adjacency list structure has been extended to directed graphs in a way that the user can query them for in-degree (see <a class="el" href="classlal_1_1graphs_1_1directed__graph.html#aad08168cf9fd02b362013916bf308210">lal::graphs::directed_graph::get_in_degree</a>) and in-neighbors (see <a class="el" href="classlal_1_1graphs_1_1directed__graph.html#a6bd3b9aaaab43d22af76dea13c4c8371">lal::graphs::directed_graph::get_in_neighbors</a>).</p>
<h1><a class="anchor" id="MP_terminology"></a>
Basic terminology and notation</h1>
<p><b>NOTE</b> Pages <a class="el" href="LAL_notation.html">Notation in the library's documentation</a> and <a class="el" href="LAL_concepts.html">Important concepts in LAL</a> further explain everything there is to know about notation and concepts.</p>
<p>Users will note, after browsing through the library's documentation, that several concepts are quite ubiquitous. The <a class="el" href="namespacelal.html#ae5688e9acca02d5865dfc724e480ce25">lal::node</a> type is simply a typedef of an unsigned integer type, and the <a class="el" href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a> type is simply a STL's pair of nodes. Moreover, users need to have a deep understanding of what a head vector is (see <a class="el" href="namespacelal.html#a2eb5b7f5b50ff908a7a67889a9ea744d">lal::head_vector</a>), which is what allows users to easily read trees from files and process a file containing a large collection of trees (see <a class="el" href="namespacelal_1_1io.html">lal::io</a> namespace).</p>
<p>A more advanced concept is that of linear arrangement (see <a class="el" href="classlal_1_1linear__arrangement.html">lal::linear_arrangement</a>). In this library, a linear arrangement is viewed as a function that relates each node to a position in a linear sequence. Due to the properties of such functions, a linear arrangement is implemented with the STL's vector. Note that the concept of linear arrangement has been detached from that of trees, and the pair of a linear arrangement and a tree forms, in the context of the library, a syntactic dependency tree (this is why this class is not implemented). The symbol of choice for representing a linear arrangement in the library is the greek letter for the number pi \(\pi\).</p>
<p>Now, many functions (see those fuctions within the <a class="el" href="namespacelal_1_1linarr.html">lal::linarr</a> namespace) admit a linear arrangement which can be empty. Whenever it is empty, i.e., the value of the parameter is an empty vector, the positions of the nodes of the graphs in question are given by their implicit label. Such empty arrangement is called, in the context of the library, the identity arrangement symbolised with \(\pi_I\). Therefore, the following measurement of the sum of the lengths of the edges are equivalent</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t(4);</div>
<div class="line">t.add_edges({<a class="code hl_typedef" href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a>(0,1), <a class="code hl_typedef" href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a>(1,2), <a class="code hl_typedef" href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a>(2,3)});</div>
<div class="line">uint64_t D1 = <a class="code hl_function" href="namespacelal_1_1linarr.html#ab70693683a8da54a2e4350c665067cf1">lal::linarr::sum_edge_lengths</a>(t);</div>
<div class="line">uint64_t D2 = <a class="code hl_function" href="namespacelal_1_1linarr.html#ab70693683a8da54a2e4350c665067cf1">lal::linarr::sum_edge_lengths</a>(t, {0,1,2,3});</div>
<div class="ttc" id="anamespacelal_1_1linarr_html_ab70693683a8da54a2e4350c665067cf1"><div class="ttname"><a href="namespacelal_1_1linarr.html#ab70693683a8da54a2e4350c665067cf1">lal::linarr::sum_edge_lengths</a></div><div class="ttdeci">uint64_t sum_edge_lengths(const graphs::directed_graph &amp;g, const linear_arrangement &amp;pi={}) noexcept</div><div class="ttdoc">Computes the sum of the length of the edges in a linear arrangement.</div></div>
<div class="ttc" id="anamespacelal_html_a5969ec7ecc85697ebb9ec0ace78fbcab"><div class="ttname"><a href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a></div><div class="ttdeci">std::pair&lt; node, node &gt; edge</div><div class="ttdoc">See Edge page for further details.</div><div class="ttdef"><b>Definition</b> basic_types.hpp:56</div></div>
</div><!-- fragment --><p>The possibility of expliciting a linear arrangement increases the flexibility of the library. For example, for the purposes of illustration, one can calculate the expected sum of the length of the edges as follows</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t(4);</div>
<div class="line">t.add_edges({<a class="code hl_typedef" href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a>(0,1), <a class="code hl_typedef" href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a>(1,2), <a class="code hl_typedef" href="namespacelal.html#a5969ec7ecc85697ebb9ec0ace78fbcab">lal::edge</a>(2,3)});</div>
<div class="line"><a class="code hl_class" href="classlal_1_1numeric_1_1rational.html">lal::numeric::rational</a> Dt = 0;</div>
<div class="line"><a class="code hl_class" href="classlal_1_1linear__arrangement.html">lal::linear_arrangement</a> arr({0,1,2,3});</div>
<div class="line"><span class="keywordflow">do</span> {</div>
<div class="line">    arr.<a class="code hl_function" href="classlal_1_1linear__arrangement.html#a71f927053906157a4bc62811bc51855a">update_inverse</a>();</div>
<div class="line">    Dt += <a class="code hl_function" href="namespacelal_1_1linarr.html#ab70693683a8da54a2e4350c665067cf1">lal::linarr::sum_edge_lengths</a>(t, arr);</div>
<div class="line">}</div>
<div class="line"><span class="keywordflow">while</span> (std::next_permutation(arr.begin_direct(), arr.end_direct()));</div>
<div class="line">Dt /= 24;</div>
<div class="ttc" id="aclasslal_1_1linear__arrangement_html"><div class="ttname"><a href="classlal_1_1linear__arrangement.html">lal::linear_arrangement</a></div><div class="ttdoc">Linear arrangement of vertices.</div><div class="ttdef"><b>Definition</b> linear_arrangement.hpp:103</div></div>
<div class="ttc" id="aclasslal_1_1linear__arrangement_html_a71f927053906157a4bc62811bc51855a"><div class="ttname"><a href="classlal_1_1linear__arrangement.html#a71f927053906157a4bc62811bc51855a">lal::linear_arrangement::update_inverse</a></div><div class="ttdeci">void update_inverse() noexcept</div><div class="ttdoc">Updates the inverse arrangement using the direct arrangement.</div><div class="ttdef"><b>Definition</b> linear_arrangement.hpp:529</div></div>
<div class="ttc" id="aclasslal_1_1numeric_1_1rational_html"><div class="ttname"><a href="classlal_1_1numeric_1_1rational.html">lal::numeric::rational</a></div><div class="ttdoc">Exact rational number.</div><div class="ttdef"><b>Definition</b> rational.hpp:63</div></div>
</div><!-- fragment --><h1><a class="anchor" id="MP_effective_usage"></a>
Using the library effectively</h1>
<p>As a rule of the thumb, the user is encouraged not to change the default value of the parameters whenever they are given. However, certain operations can be less efficient than others, and sometimes it is even desirable to use values different from the default ones.</p>
<p>One the one hand, the wrong choice of operation can affect the library's performance gravely. For example, the addition/deletion of edges to/from graphs is slower when it is done edge by edge than when it is done in bulk. Users are highly encouraged to add/delete them in bulk using the appropriate functions (see, for example, <a class="el" href="classlal_1_1graphs_1_1undirected__graph.html#af8f699b61b172ec480a4f1a1714a5b9c">lal::graphs::undirected_graph::add_edges</a> and <a class="el" href="classlal_1_1graphs_1_1undirected__graph.html#a7764b9271466280346ef952acd76f3f9">lal::graphs::undirected_graph::remove_edges</a>). Although correct, the following code is discouraged</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t(10);</div>
<div class="line"><a class="code hl_typedef" href="namespacelal.html#ae5688e9acca02d5865dfc724e480ce25">lal::node</a> u, v;</div>
<div class="line"><span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; 9; ++i) {</div>
<div class="line">    cin &gt;&gt; u &gt;&gt; v;</div>
<div class="line">    t.add_edge(u,v);</div>
<div class="line">}</div>
<div class="ttc" id="anamespacelal_html_ae5688e9acca02d5865dfc724e480ce25"><div class="ttname"><a href="namespacelal.html#ae5688e9acca02d5865dfc724e480ce25">lal::node</a></div><div class="ttdeci">uint64_t node</div><div class="ttdoc">Node type. See Node / Vertex page for further details.</div><div class="ttdef"><b>Definition</b> basic_types.hpp:51</div></div>
</div><!-- fragment --><p>while the next piece of code is strongly encouraged whenever possible</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t(10);</div>
<div class="line">vector&lt;lal::edge&gt; e(9);</div>
<div class="line"><span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; 9; ++i) {</div>
<div class="line">    cin &gt;&gt; e[i].first &gt;&gt; e[i].second;</div>
<div class="line">}</div>
<div class="line">t.set_edges(e);</div>
</div><!-- fragment --><p>A similar reasoning should be applied to the deletion of edges.</p>
<p>Furthermore, graphs are seldom required to be normalized. For example, when calculating the variance of \(C\) (see <a class="el" href="namespacelal_1_1properties.html#aa58446707ce2f604cf693edbb8f122db">lal::properties::var_num_crossings</a>), it is mandatory that the graph be normalized, namely, the function has a precondition that requires the graph to be normalized. If such a function is to be called eventually then add all edges in bulk and with normalisation, or read the graph from disk also with normalisation. However, if such functions will never be called then the users are encouraged to set the normalisation parameter to false. For example, if the variance of \(C\) is to be calculated,</p>
<div class="fragment"><div class="line"><span class="keyword">const</span> <span class="keywordtype">string</span> filename = <span class="stringliteral">&quot;...&quot;</span>; <span class="comment">// a valid name of a file</span></div>
<div class="line"><span class="keyword">const</span> <a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t = *<a class="code hl_function" href="namespacelal_1_1io.html#a5fd63603805a9fb66903e678de24f97a">lal::io::read_edge_list</a>(filename);</div>
<div class="line"><span class="keywordtype">double</span> var_C = <a class="code hl_function" href="namespacelal_1_1properties.html#aa58446707ce2f604cf693edbb8f122db">lal::properties::var_num_crossings</a>(t);</div>
<div class="ttc" id="anamespacelal_1_1io_html_a5fd63603805a9fb66903e678de24f97a"><div class="ttname"><a href="namespacelal_1_1io.html#a5fd63603805a9fb66903e678de24f97a">lal::io::read_edge_list</a></div><div class="ttdeci">std::optional&lt; graph_t &gt; read_edge_list(const std::string &amp;filename, const bool norm=true, const bool check_norm=true) noexcept</div><div class="ttdoc">Reads a graph in edge list format.</div><div class="ttdef"><b>Definition</b> edge_list.hpp:174</div></div>
<div class="ttc" id="anamespacelal_1_1properties_html_aa58446707ce2f604cf693edbb8f122db"><div class="ttname"><a href="namespacelal_1_1properties.html#aa58446707ce2f604cf693edbb8f122db">lal::properties::var_num_crossings</a></div><div class="ttdeci">double var_num_crossings(const graphs::undirected_graph &amp;g, const bool reuse=true) noexcept</div><div class="ttdoc">Computes the variance of the number of crossings of a graph in unconstrained arrangements,...</div><div class="ttdef"><b>Definition</b> C_rla.hpp:116</div></div>
</div><!-- fragment --><p>but if not</p>
<div class="fragment"><div class="line"><span class="keyword">const</span> <span class="keywordtype">string</span> filename = <span class="stringliteral">&quot;...&quot;</span>; <span class="comment">// a valid name of a file</span></div>
<div class="line"><span class="keyword">const</span> <a class="code hl_class" href="classlal_1_1graphs_1_1free__tree.html">lal::graphs::free_tree</a> t = *<a class="code hl_function" href="namespacelal_1_1io.html#a5fd63603805a9fb66903e678de24f97a">lal::io::read_edge_list</a>(filename, <span class="keyword">false</span>);</div>
<div class="line"><span class="comment">// ...</span></div>
</div><!-- fragment --> </div></div><!-- PageDoc -->
<a href="doxygen_crawl.html"/>
</div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by&#160;<a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.11.0
</small></address>
</div><!-- doc-content -->
</body>
</html>