diff options
23 files changed, 2736 insertions, 547 deletions
diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 4940ec78..6bc84373 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -969,3 +969,10 @@ pages={91-106}, language={English} } +@article{de2004topological, + title={Topological estimation using witness complexes}, + author={De Silva, Vin and Carlsson, Gunnar}, + journal={Proc. Sympos. Point-Based Graphics}, + pages={157--166}, + year={2004} +}
\ No newline at end of file diff --git a/src/Witness_complex/concept/Simplicial_complex_for_witness.h b/src/Witness_complex/concept/Simplicial_complex_for_witness.h index caaf0db6..b47de809 100644 --- a/src/Witness_complex/concept/Simplicial_complex_for_witness.h +++ b/src/Witness_complex/concept/Simplicial_complex_for_witness.h @@ -29,7 +29,7 @@ namespace witness_complex { /** \brief The concept Simplicial_Complex describes the requirements * for a type to implement a simplicial complex, - * used for example to build a 'Witness_complex'. + * used for example to build a Witness_complex. */ struct SimplicialComplexForWitness { /** Handle to specify a simplex. */ diff --git a/src/Witness_complex/doc/Witness_complex_doc.h b/src/Witness_complex/doc/Witness_complex_doc.h index 60dfd27b..ba258ddc 100644 --- a/src/Witness_complex/doc/Witness_complex_doc.h +++ b/src/Witness_complex/doc/Witness_complex_doc.h @@ -8,31 +8,102 @@ \image html "Witness_complex_representation.png" "Witness complex representation" - \section Definitions + \section witnessdefinitions Definitions - Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: + Witness complex is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: \li \f$W\f$ set of **witnesses** and - \li \f$L \subseteq W\f$ set of **landmarks**. + \li \f$L\f$ set of **landmarks**. - The simplices are based on landmarks - and a simplex belongs to the witness complex if and only if it is witnessed, that is: + Even though often the set of landmarks \f$L\f$ is a subset of the set of witnesses \f$ W\f$, it is not a requirement for the current implementation. - \f$ \sigma \subset L \f$ is witnessed if there exists a point \f$w \in W\f$ such that - w is closer to the vertices of \f$ \sigma \f$ than other points in \f$ L \f$ and all of its faces are witnessed as well. - - The data structure is described in \cite boissonnatmariasimplextreealgorithmica . + Landmarks are the vertices of the simplicial complex + and witnesses help to decide on which simplices are inserted via a predicate "is witnessed". - \section Implementation + De Silva and Carlsson in their paper \cite de2004topological differentiate **weak witnessing** and **strong witnessing**: - The principal class of this module is Gudhi::Witness_complex. + - *weak*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l) \leq d(w,l') \f$ + - *strong*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l) \leq d(w,l') \f$ - In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, where each row represents a witness and consists of landmarks sorted by distance to this witness. - This table can be constructed by two additional classes Landmark_choice_by_furthest_point and Landmark_choice_by_random_point also included in the module. + where \f$ d(.,.) \f$ is a distance function. + + Both definitions can be relaxed by a real value \f$\alpha\f$: + + - *weak*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ + - *strong*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ + + which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and **strong relaxed witness complex** respectively. + + \image html "swit.svg" "Strong witness witnesses the whole simplex in the witnessing ball" + + In particular case of 0-relaxation, weak complex corresponds to **witness complex** introduced in \cite de2004topological, whereas 0-relaxed strong witness complex consists of just vertices and is not very interesting. + Hence for small relaxation weak version is preferable. + However, to capture the homotopy type (for example using Gudhi::persistent_cohomology::Persistent_cohomology) it is often necessary to work with higher filtration values. In this case strong relaxed witness complex is faster to compute and offers similar results. + + \section witnessimplementation Implementation + + The two complexes described above are implemented in the corresponding classes + - Gudhi::witness_complex::Witness_complex + - Gudhi::witness_complex::Strong_witness_complex + + The construction of both of them follow the same scheme: + 1. Construct a search tree on landmarks (for that Gudhi::spatial_searching::Kd_tree_search is used internally). + 2. Construct lists of nearest landmarks for each witness (special internal structure Gudhi::witness_complex::Active_witness is used internally). + 3. Construct the witness complex for nearest landmark lists. + + The constructors take on the step 1, while the function 'create_complex' executes the steps 2 and 3. + + \section witnessexample1 Example 1: Constructing weak relaxed witness complex from an off file + + Let's start with a simple example, which reads an off point file and computes a weak witness complex. + + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{.cpp} + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Witness_complex.h> +#include <gudhi/pick_n_random_points.h> +#include <gudhi/Points_off_io.h> + +#include <CGAL/Epick_d.h> + +#include <string> +#include <vector> + +typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; +typedef typename K::Point_d Point_d; +typedef typename Gudhi::witness_complex::Witness_complex<K> Witness_complex; +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef std::vector< Point_d > Point_vector; + +int main(int argc, char * const argv[]) { + std::string file_name = argv[1]; + int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]); + double alpha2 = atof(argv[3]); + Gudhi::Simplex_tree<> simplex_tree; + + // Read the point file + Point_vector point_vector, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + point_vector = Point_vector(off_reader.get_point_cloud()); + + // Choose landmarks + Gudhi::subsampling::pick_n_random_points(point_vector, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + Witness_complex witness_complex(landmarks, + point_vector); + + witness_complex.create_complex(simplex_tree, alpha2, lim_dim); +} - *\image html "bench_Cy8.png" "Running time as function on number of landmarks" width=10cm - *\image html "bench_sphere.png" "Running time as function on number of witnesses for |L|=300" width=10cm + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + \section witnessexample2 Example2: Computing persistence using strong relaxed witness complex + + Here is an example of constructing a strong witness complex filtration and computing persistence on it: + + \include Witness_complex/example_strong_witness_persistence.cpp \copyright GNU General Public License v3. diff --git a/src/Witness_complex/doc/Witness_complex_representation.ipe b/src/Witness_complex/doc/Witness_complex_representation.ipe new file mode 100644 index 00000000..f9c45d5d --- /dev/null +++ b/src/Witness_complex/doc/Witness_complex_representation.ipe @@ -0,0 +1,280 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70107" creator="Ipe 7.1.10"> +<info created="D:20161010162425" modified="D:20161010162828"/> +<ipestyle name="basic"> +<symbol name="arrow/arc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/farc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/ptarc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fptarc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="mark/circle(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</symbol> +<symbol name="mark/disk(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +</path> +</symbol> +<symbol name="mark/fdisk(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +0.5 0 0 0.5 0 0 e +</path> +<path fill="sym-stroke" fillrule="eofill"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</group> +</symbol> +<symbol name="mark/box(sx)" transformations="translations"> +<path fill="sym-stroke" fillrule="eofill"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h +</path> +</symbol> +<symbol name="mark/square(sx)" transformations="translations"> +<path fill="sym-stroke"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +</path> +</symbol> +<symbol name="mark/fsquare(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h +</path> +<path fill="sym-stroke" fillrule="eofill"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h +</path> +</group> +</symbol> +<symbol name="mark/cross(sx)" transformations="translations"> +<group> +<path fill="sym-stroke"> +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h +</path> +<path fill="sym-stroke"> +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h +</path> +</group> +</symbol> +<symbol name="arrow/fnormal(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/pointed(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fpointed(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/linear(spx)"> +<path stroke="sym-stroke" pen="sym-pen"> +-1 0.333 m +0 0 l +-1 -0.333 l +</path> +</symbol> +<symbol name="arrow/fdouble(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/double(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<pen name="heavier" value="0.8"/> +<pen name="fat" value="1.2"/> +<pen name="ultrafat" value="2"/> +<symbolsize name="large" value="5"/> +<symbolsize name="small" value="2"/> +<symbolsize name="tiny" value="1.1"/> +<arrowsize name="large" value="10"/> +<arrowsize name="small" value="5"/> +<arrowsize name="tiny" value="3"/> +<color name="red" value="1 0 0"/> +<color name="green" value="0 1 0"/> +<color name="blue" value="0 0 1"/> +<color name="yellow" value="1 1 0"/> +<color name="orange" value="1 0.647 0"/> +<color name="gold" value="1 0.843 0"/> +<color name="purple" value="0.627 0.125 0.941"/> +<color name="gray" value="0.745"/> +<color name="brown" value="0.647 0.165 0.165"/> +<color name="navy" value="0 0 0.502"/> +<color name="pink" value="1 0.753 0.796"/> +<color name="seagreen" value="0.18 0.545 0.341"/> +<color name="turquoise" value="0.251 0.878 0.816"/> +<color name="violet" value="0.933 0.51 0.933"/> +<color name="darkblue" value="0 0 0.545"/> +<color name="darkcyan" value="0 0.545 0.545"/> +<color name="darkgray" value="0.663"/> +<color name="darkgreen" value="0 0.392 0"/> +<color name="darkmagenta" value="0.545 0 0.545"/> +<color name="darkorange" value="1 0.549 0"/> +<color name="darkred" value="0.545 0 0"/> +<color name="lightblue" value="0.678 0.847 0.902"/> +<color name="lightcyan" value="0.878 1 1"/> +<color name="lightgray" value="0.827"/> +<color name="lightgreen" value="0.565 0.933 0.565"/> +<color name="lightyellow" value="1 1 0.878"/> +<dashstyle name="dashed" value="[4] 0"/> +<dashstyle name="dotted" value="[1 3] 0"/> +<dashstyle name="dash dotted" value="[4 2 1 2] 0"/> +<dashstyle name="dash dot dotted" value="[4 2 1 2 1 2] 0"/> +<textsize name="large" value="\large"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="small" value="\small"/> +<textsize name="footnote" value="\footnotesize"/> +<textsize name="tiny" value="\tiny"/> +<textstyle name="center" begin="\begin{center}" end="\end{center}"/> +<textstyle name="itemize" begin="\begin{itemize}" end="\end{itemize}"/> +<textstyle name="item" begin="\begin{itemize}\item{}" end="\end{itemize}"/> +<gridsize name="4 pts" value="4"/> +<gridsize name="8 pts (~3 mm)" value="8"/> +<gridsize name="16 pts (~6 mm)" value="16"/> +<gridsize name="32 pts (~12 mm)" value="32"/> +<gridsize name="10 pts (~3.5 mm)" value="10"/> +<gridsize name="20 pts (~7 mm)" value="20"/> +<gridsize name="14 pts (~5 mm)" value="14"/> +<gridsize name="28 pts (~10 mm)" value="28"/> +<gridsize name="56 pts (~20 mm)" value="56"/> +<anglesize name="90 deg" value="90"/> +<anglesize name="60 deg" value="60"/> +<anglesize name="45 deg" value="45"/> +<anglesize name="30 deg" value="30"/> +<anglesize name="22.5 deg" value="22.5"/> +<opacity name="10%" value="0.1"/> +<opacity name="30%" value="0.3"/> +<opacity name="50%" value="0.5"/> +<opacity name="75%" value="0.75"/> +<tiling name="falling" angle="-60" step="4" width="1"/> +<tiling name="rising" angle="30" step="4" width="1"/> +</ipestyle> +<page> +<layer name="alpha"/> +<view layers="alpha" active="alpha"/> +<use layer="alpha" name="mark/fdisk(sfx)" pos="288 672" size="normal" stroke="darkblue" fill="white"/> +<path stroke="darkblue"> +48.8262 0 0 48.8262 288 672 e +</path> +<text transformations="translations" pos="292 676" stroke="darkblue" type="label" width="6.559" height="4.289" depth="0" valign="baseline">$\omega$</text> +<path stroke="black"> +284 720 m +280 624 l +268 648 l +h +</path> +<use name="mark/fdisk(sfx)" pos="284 720" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="268 648" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="280 624" size="normal" stroke="black" fill="white"/> +<text matrix="1 0 0 1 0 8" transformations="translations" pos="268 672" stroke="black" type="label" width="6.05" height="4.289" depth="0" valign="baseline">$\sigma$</text> +<use name="mark/fdisk(sfx)" pos="344 672" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="356 716" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="364 628" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="244 708" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="196 632" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="200 696" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="168 716" size="normal" stroke="black" fill="white"/> +</page> +</ipe> diff --git a/src/Witness_complex/doc/Witness_complex_representation.png b/src/Witness_complex/doc/Witness_complex_representation.png Binary files differindex 1d31a490..16e0504e 100644 --- a/src/Witness_complex/doc/Witness_complex_representation.png +++ b/src/Witness_complex/doc/Witness_complex_representation.png diff --git a/src/Witness_complex/doc/swit.svg b/src/Witness_complex/doc/swit.svg new file mode 100644 index 00000000..6ffb5fff --- /dev/null +++ b/src/Witness_complex/doc/swit.svg @@ -0,0 +1,1303 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Created with Inkscape (http://www.inkscape.org/) --> + +<svg + xmlns:ns0="http://www.iki.fi/pav/software/textext/" + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:xlink="http://www.w3.org/1999/xlink" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="113.73116mm" + height="84.14254mm" + viewBox="0 0 402.98441 298.14286" + id="svg2" + version="1.1" + inkscape:version="0.91 r13725" + sodipodi:docname="swit.svg"> + <sodipodi:namedview + id="base" + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1.0" + inkscape:pageopacity="0.0" + inkscape:pageshadow="2" + inkscape:zoom="0.98994949" + inkscape:cx="402.72174" + inkscape:cy="258.46971" + inkscape:document-units="px" + inkscape:current-layer="layer1" + showgrid="false" + inkscape:window-width="1366" + inkscape:window-height="704" + inkscape:window-x="0" + inkscape:window-y="27" + inkscape:window-maximized="1" + fit-margin-top="0" + fit-margin-left="0" + fit-margin-right="0" + fit-margin-bottom="0" /> + <defs + id="defs4"> + <marker + inkscape:stockid="Arrow1Lend" + orient="auto" + refY="0" + refX="0" + id="Arrow1Lend" + style="overflow:visible" + inkscape:isstock="true"> + <path + inkscape:connector-curvature="0" + id="path5009" + d="M 0,0 5,-5 -12.5,0 5,5 0,0 Z" + style="fill:#000080;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1pt;stroke-opacity:1" + transform="matrix(-0.8,0,0,-0.8,-10,0)" /> + </marker> + <marker + inkscape:stockid="Arrow1Lend" + orient="auto" + refY="0" + refX="0" + id="Arrow1Lend-8" + style="overflow:visible" + inkscape:isstock="true"> + <path + inkscape:connector-curvature="0" + id="path5009-5" + d="M 0,0 5,-5 -12.5,0 5,5 0,0 Z" + style="fill:#000080;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1pt;stroke-opacity:1" + transform="matrix(-0.8,0,0,-0.8,-10,0)" /> + </marker> + </defs> + <metadata + id="metadata7"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <g + transform="translate(-130.29351,-300.82484)" + id="layer1" + inkscape:groupmode="layer" + inkscape:label="Layer 1"> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="148.57143" + cy="449.89627" + cx="338.71756" + id="path4136" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" + d="m 318.19805,571.02449 0,-94.95433 -64.64976,-92.42896 164.14979,-30.80966 42.4264,120.71323 -141.92643,3.03046 100.0051,-123.23861 z" + id="path4301" + inkscape:connector-curvature="0" /> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" + d="m 318.70313,571.52957 -65.65992,-187.3833 206.5762,88.89343 z" + id="path4303" + inkscape:connector-curvature="0" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="450.05875" + cx="338.13837" + id="path4138" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4147" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$w$" + transform="matrix(2.7020226,0,0,2.7020226,-261.85036,103.80999)" + style="fill:#000080"> + <defs + id="defs4149"> + <g + id="g4151"> + <symbol + id="textext-20f8880a-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4154" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-20f8880a-1" + overflow="visible" + style="overflow:visible"> + <path + id="path4157" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-20f8880a-2" + style="fill:#000080"> + <g + id="g4160" + style="fill:#000080;fill-opacity:1"> + <use + id="use4162" + y="134.765" + x="223.43201" + xlink:href="#textext-20f8880a-1" + width="100%" + height="100%" + style="fill:#000080" /> + </g> + </g> + </g> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="383.79077" + cx="252.85715" + id="path4138-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="353.07648" + cx="418.57144" + id="path4138-3-7" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="475.93362" + cx="317.85715" + id="path4138-3-0" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="570.21936" + cx="317.85715" + id="path4138-3-9" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="473.07648" + cx="459.28571" + id="path4138-3-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="478.07648" + cx="133.57143" + id="path4138-3-6" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="320.21936" + cx="155.71428" + id="path4138-3-06" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="340.73929" + cx="490.7774" + id="path4138-3-2" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="559.76758" + cx="490.60406" + id="path4138-3-61" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + id="g4147-8" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$w$" + transform="matrix(2.7020226,0,0,2.7020226,-152.29409,72.785446)" + style="fill:#000000"> + <defs + id="defs4149-7"> + <g + id="g4151-9"> + <symbol + id="textext-20f8880a-0-2" + overflow="visible" + style="overflow:visible"> + <path + id="path4154-0" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-20f8880a-1-2" + overflow="visible" + style="overflow:visible"> + <path + id="path4157-3" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-20f8880a-2-7" + style="fill:#000000" /> + </g> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4558" + style="fill:#000080" + transform="matrix(2.7020226,0,0,2.7020226,-254.3195,202.59004)" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$\\sigma \\subset L$"> + <defs + id="defs4560"> + <g + id="g4562"> + <symbol + id="textext-b73c230a-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4565" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-1" + overflow="visible" + style="overflow:visible"> + <path + id="path4568" + d="m 5.15625,-3.71875 c 0.140625,0 0.5,0 0.5,-0.34375 0,-0.234375 -0.21875,-0.234375 -0.390625,-0.234375 l -2.28125,0 c -1.5,0 -2.609375,1.640625 -2.609375,2.828125 0,0.875 0.59375,1.578125 1.5,1.578125 1.171875,0 2.5,-1.203125 2.5,-2.734375 0,-0.171875 0,-0.65625 -0.3125,-1.09375 z M 1.890625,-0.109375 C 1.390625,-0.109375 1,-0.46875 1,-1.1875 c 0,-0.296875 0.109375,-1.109375 0.46875,-1.703125 0.421875,-0.6875 1.015625,-0.828125 1.359375,-0.828125 0.828125,0 0.90625,0.65625 0.90625,0.96875 0,0.46875 -0.203125,1.28125 -0.53125,1.796875 -0.390625,0.578125 -0.9375,0.84375 -1.3125,0.84375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-2" + overflow="visible" + style="overflow:visible"> + <path + id="path4571" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-3" + overflow="visible" + style="overflow:visible"> + <path + id="path4574" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-4" + overflow="visible" + style="overflow:visible"> + <path + id="path4577" + d="m 6.5625,-4.984375 c 0.171875,0 0.359375,0 0.359375,-0.203125 0,-0.203125 -0.1875,-0.203125 -0.359375,-0.203125 l -2.671875,0 c -1.703125,0 -3.0625,1.296875 -3.0625,2.890625 0,1.609375 1.359375,2.90625 3.0625,2.90625 l 2.671875,0 c 0.171875,0 0.359375,0 0.359375,-0.203125 C 6.921875,0 6.734375,0 6.5625,0 L 3.90625,0 c -1.546875,0 -2.6875,-1.15625 -2.6875,-2.5 0,-1.328125 1.140625,-2.484375 2.6875,-2.484375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-b73c230a-5"> + <g + id="g4580" + style="fill:#000000;fill-opacity:1"> + <use + id="use4582" + y="134.765" + x="223.43201" + xlink:href="#textext-b73c230a-1" + width="100%" + height="100%" /> + </g> + <g + id="g4584" + style="fill:#000000;fill-opacity:1"> + <use + id="use4586" + y="134.765" + x="232.25" + xlink:href="#textext-b73c230a-4" + width="100%" + height="100%" /> + </g> + <g + id="g4588" + style="fill:#000000;fill-opacity:1"> + <use + id="use4590" + y="134.765" + x="242.76601" + xlink:href="#textext-b73c230a-2" + width="100%" + height="100%" /> + </g> + </g> + </g> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:#000080;fill-rule:evenodd;stroke:#000080;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow1Lend)" + d="m 337.85714,449.50504 148.57143,-8.57143" + id="path5000" + inkscape:connector-curvature="0" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + ns0:text="$\\sqrt{d(w,L)^2 + \\alpha^2}$" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + transform="matrix(1.3935573,-0.10159094,0.10159094,1.3935573,55.220877,276.38005)" + style="fill:#000080;stroke:#000080" + id="g5407"> + <defs + id="defs5409"> + <g + id="g5411"> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-0"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5414" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-1"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 4.234375,11.5625 c 0.296875,0 0.3125,-0.01563 0.40625,-0.203125 l 5.453125,-11.375 c 0.07813,-0.140625 0.07813,-0.15625 0.07813,-0.1875 0,-0.109375 -0.07813,-0.203125 -0.203125,-0.203125 -0.125,0 -0.171875,0.09375 -0.21875,0.203125 L 4.609375,10.53125 2.484375,5.578125 1.09375,6.65625 1.25,6.8125 1.953125,6.265625 Z m 0,0" + id="path5417" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-2"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5420" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-3"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 5.140625,-6.8125 c 0,0 0,-0.109375 -0.125,-0.109375 -0.15625,0 -1.09375,0.09375 -1.265625,0.109375 -0.078125,0.015625 -0.140625,0.0625 -0.140625,0.1875 0,0.125 0.09375,0.125 0.234375,0.125 0.484375,0 0.5,0.0625 0.5,0.171875 L 4.3125,-6.125 3.71875,-3.765625 C 3.53125,-4.140625 3.25,-4.40625 2.796875,-4.40625 c -1.15625,0 -2.390625,1.46875 -2.390625,2.921875 0,0.9375 0.546875,1.59375 1.3125,1.59375 0.203125,0 0.703125,-0.046875 1.296875,-0.75 0.078125,0.421875 0.4375,0.75 0.90625,0.75 0.359375,0 0.578125,-0.234375 0.75,-0.546875 0.15625,-0.359375 0.296875,-0.96875 0.296875,-0.984375 0,-0.109375 -0.09375,-0.109375 -0.125,-0.109375 -0.09375,0 -0.109375,0.046875 -0.140625,0.1875 -0.171875,0.640625 -0.34375,1.234375 -0.75,1.234375 -0.28125,0 -0.296875,-0.265625 -0.296875,-0.453125 0,-0.25 0.015625,-0.3125 0.046875,-0.484375 z m -2.0625,5.625 C 3.015625,-1 3.015625,-0.984375 2.875,-0.8125 2.4375,-0.265625 2.03125,-0.109375 1.75,-0.109375 c -0.5,0 -0.640625,-0.546875 -0.640625,-0.9375 0,-0.5 0.3125,-1.71875 0.546875,-2.1875 0.3125,-0.578125 0.75,-0.953125 1.15625,-0.953125 0.640625,0 0.78125,0.8125 0.78125,0.875 0,0.0625 -0.015625,0.125 -0.03125,0.171875 z m 0,0" + id="path5423" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-4"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + id="path5426" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-5"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 2.03125,-0.015625 c 0,-0.65625 -0.25,-1.046875 -0.640625,-1.046875 -0.328125,0 -0.53125,0.25 -0.53125,0.53125 C 0.859375,-0.265625 1.0625,0 1.390625,0 1.5,0 1.640625,-0.046875 1.734375,-0.125 1.765625,-0.15625 1.78125,-0.15625 1.78125,-0.15625 c 0.015625,0 0.015625,0 0.015625,0.140625 0,0.75 -0.34375,1.34375 -0.671875,1.671875 -0.109375,0.109375 -0.109375,0.125 -0.109375,0.15625 0,0.078125 0.046875,0.109375 0.09375,0.109375 0.109375,0 0.921875,-0.765625 0.921875,-1.9375 z m 0,0" + id="path5429" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-6"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + id="path5432" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-7"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 4.75,-2.359375 c 0,-1.5625 -0.921875,-2.046875 -1.65625,-2.046875 -1.375,0 -2.6875,1.421875 -2.6875,2.828125 0,0.9375 0.59375,1.6875 1.625,1.6875 0.625,0 1.34375,-0.234375 2.09375,-0.84375 0.125,0.53125 0.453125,0.84375 0.90625,0.84375 0.53125,0 0.84375,-0.546875 0.84375,-0.703125 0,-0.078125 -0.0625,-0.109375 -0.125,-0.109375 -0.0625,0 -0.09375,0.03125 -0.125,0.109375 -0.1875,0.484375 -0.546875,0.484375 -0.5625,0.484375 -0.3125,0 -0.3125,-0.78125 -0.3125,-1.015625 0,-0.203125 0,-0.234375 0.109375,-0.34375 C 5.796875,-2.65625 6,-3.8125 6,-3.8125 6,-3.84375 5.984375,-3.921875 5.875,-3.921875 c -0.09375,0 -0.09375,0.03125 -0.140625,0.21875 -0.1875,0.625 -0.515625,1.375 -0.984375,1.96875 z m -0.65625,1.375 c -0.890625,0.765625 -1.65625,0.875 -2.046875,0.875 -0.59375,0 -0.90625,-0.453125 -0.90625,-1.09375 0,-0.484375 0.265625,-1.5625 0.578125,-2.0625 C 2.1875,-4 2.734375,-4.1875 3.078125,-4.1875 c 0.984375,0 0.984375,1.3125 0.984375,2.078125 0,0.375 0,0.953125 0.03125,1.125 z m 0,0" + id="path5435" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-8"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5438" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-9"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 3.296875,2.390625 c 0,-0.03125 0,-0.046875 -0.171875,-0.21875 C 1.890625,0.921875 1.5625,-0.96875 1.5625,-2.5 c 0,-1.734375 0.375,-3.46875 1.609375,-4.703125 0.125,-0.125 0.125,-0.140625 0.125,-0.171875 0,-0.078125 -0.03125,-0.109375 -0.09375,-0.109375 -0.109375,0 -1,0.6875 -1.59375,1.953125 -0.5,1.09375 -0.625,2.203125 -0.625,3.03125 0,0.78125 0.109375,1.984375 0.65625,3.125 C 2.25,1.84375 3.09375,2.5 3.203125,2.5 c 0.0625,0 0.09375,-0.03125 0.09375,-0.109375 z m 0,0" + id="path5441" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-10"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 2.875,-2.5 c 0,-0.765625 -0.109375,-1.96875 -0.65625,-3.109375 -0.59375,-1.21875 -1.453125,-1.875 -1.546875,-1.875 -0.0625,0 -0.109375,0.046875 -0.109375,0.109375 0,0.03125 0,0.046875 0.1875,0.234375 0.984375,0.984375 1.546875,2.5625 1.546875,4.640625 0,1.71875 -0.359375,3.46875 -1.59375,4.71875 C 0.5625,2.34375 0.5625,2.359375 0.5625,2.390625 0.5625,2.453125 0.609375,2.5 0.671875,2.5 0.765625,2.5 1.671875,1.8125 2.25,0.546875 2.765625,-0.546875 2.875,-1.65625 2.875,-2.5 Z m 0,0" + id="path5444" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-11"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 4.078125,-2.296875 2.78125,0 C 7,-2.296875 7.1875,-2.296875 7.1875,-2.5 7.1875,-2.6875 7,-2.6875 6.859375,-2.6875 l -2.78125,0 0,-2.796875 c 0,-0.140625 0,-0.328125 -0.203125,-0.328125 -0.203125,0 -0.203125,0.1875 -0.203125,0.328125 l 0,2.796875 -2.78125,0 c -0.140625,0 -0.328125,0 -0.328125,0.1875 0,0.203125 0.1875,0.203125 0.328125,0.203125 l 2.78125,0 0,2.796875 c 0,0.140625 0,0.328125 0.203125,0.328125 0.203125,0 0.203125,-0.1875 0.203125,-0.328125 z m 0,0" + id="path5447" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-12"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5450" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-13"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 3.515625,-1.265625 -0.234375,0 c -0.015625,0.15625 -0.09375,0.5625 -0.1875,0.625 -0.046875,0.046875 -0.578125,0.046875 -0.6875,0.046875 l -1.28125,0 c 0.734375,-0.640625 0.984375,-0.84375 1.390625,-1.171875 0.515625,-0.40625 1,-0.84375 1,-1.5 0,-0.84375 -0.734375,-1.359375 -1.625,-1.359375 -0.859375,0 -1.453125,0.609375 -1.453125,1.25 0,0.34375 0.296875,0.390625 0.375,0.390625 0.15625,0 0.359375,-0.125 0.359375,-0.375 0,-0.125 -0.046875,-0.375 -0.40625,-0.375 C 0.984375,-4.21875 1.453125,-4.375 1.78125,-4.375 c 0.703125,0 1.0625,0.546875 1.0625,1.109375 0,0.609375 -0.4375,1.078125 -0.65625,1.328125 L 0.515625,-0.265625 C 0.4375,-0.203125 0.4375,-0.1875 0.4375,0 l 2.875,0 z m 0,0" + id="path5453" /> + </symbol> + </g> + </defs> + <g + style="fill:#000080;stroke:#000080" + id="textext-da5ef958-14"> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5456"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-1" + x="223.43201" + y="126.247" + id="use5458" /> + </g> + <path + inkscape:connector-curvature="0" + style="fill:#000080;stroke:#000080;stroke-width:0.398;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1" + d="m -4.6875e-4,0.001125 59.07031275,0" + transform="matrix(1,0,0,-1,233.395,126.048)" + id="path5460" /> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5462"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-3" + x="233.395" + y="134.765" + id="use5464" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5466"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-9" + x="238.58" + y="134.765" + id="use5468" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5470"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-4" + x="242.455" + y="134.765" + id="use5472" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5474"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-5" + x="249.85622" + y="134.765" + id="use5476" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5478"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-6" + x="254.28758" + y="134.765" + id="use5480" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5482"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-10" + x="261.06299" + y="134.765" + id="use5484" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5486"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-13" + x="264.93701" + y="131.88699" + id="use5488" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5490"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-11" + x="271.621" + y="134.765" + id="use5492" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5494"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-7" + x="281.58301" + y="134.765" + id="use5496" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5498"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-13" + x="287.99301" + y="131.88699" + id="use5500" /> + </g> + </g> + </g> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="148.57143" + cy="449.89627" + cx="738.71753" + id="path4136-7" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="450.05875" + cx="738.13837" + id="path4138-8" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4147-5" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$w$" + transform="matrix(2.7020226,0,0,2.7020226,138.14964,103.80999)" + style="fill:#000080"> + <defs + id="defs4149-9"> + <g + id="g4151-7"> + <symbol + id="textext-20f8880a-0-5" + overflow="visible" + style="overflow:visible"> + <path + id="path4154-3" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-20f8880a-1-8" + overflow="visible" + style="overflow:visible"> + <path + id="path4157-8" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-20f8880a-2-3" + style="fill:#000080"> + <g + id="g4160-1" + style="fill:#000080;fill-opacity:1"> + <use + id="use4162-8" + y="134.765" + x="223.43201" + xlink:href="#textext-20f8880a-1-8" + width="100%" + height="100%" + style="fill:#000080" /> + </g> + </g> + </g> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="342.37451" + cx="681.14148" + id="path4138-3-96" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="353.07648" + cx="818.57141" + id="path4138-3-7-4" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="492.09607" + cx="668.35968" + id="path4138-3-0-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="570.21936" + cx="717.85718" + id="path4138-3-9-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="473.07648" + cx="859.28564" + id="path4138-3-3-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="478.07648" + cx="533.57141" + id="path4138-3-6-8" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="350.52393" + cx="594.1001" + id="path4138-3-06-6" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="331.64792" + cx="927.14288" + id="path4138-3-2-0" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="505.21936" + cx="930" + id="path4138-3-61-4" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4558-8" + style="fill:#000080" + transform="matrix(2.7020226,0,0,2.7020226,145.6805,202.59004)" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$\\sigma \\subset L$"> + <defs + id="defs4560-8"> + <g + id="g4562-8"> + <symbol + id="textext-b73c230a-0-9" + overflow="visible" + style="overflow:visible"> + <path + id="path4565-7" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-1-7" + overflow="visible" + style="overflow:visible"> + <path + id="path4568-6" + d="m 5.15625,-3.71875 c 0.140625,0 0.5,0 0.5,-0.34375 0,-0.234375 -0.21875,-0.234375 -0.390625,-0.234375 l -2.28125,0 c -1.5,0 -2.609375,1.640625 -2.609375,2.828125 0,0.875 0.59375,1.578125 1.5,1.578125 1.171875,0 2.5,-1.203125 2.5,-2.734375 0,-0.171875 0,-0.65625 -0.3125,-1.09375 z M 1.890625,-0.109375 C 1.390625,-0.109375 1,-0.46875 1,-1.1875 c 0,-0.296875 0.109375,-1.109375 0.46875,-1.703125 0.421875,-0.6875 1.015625,-0.828125 1.359375,-0.828125 0.828125,0 0.90625,0.65625 0.90625,0.96875 0,0.46875 -0.203125,1.28125 -0.53125,1.796875 -0.390625,0.578125 -0.9375,0.84375 -1.3125,0.84375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-2-4" + overflow="visible" + style="overflow:visible"> + <path + id="path4571-3" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-3-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4574-3" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-4-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4577-9" + d="m 6.5625,-4.984375 c 0.171875,0 0.359375,0 0.359375,-0.203125 0,-0.203125 -0.1875,-0.203125 -0.359375,-0.203125 l -2.671875,0 c -1.703125,0 -3.0625,1.296875 -3.0625,2.890625 0,1.609375 1.359375,2.90625 3.0625,2.90625 l 2.671875,0 c 0.171875,0 0.359375,0 0.359375,-0.203125 C 6.921875,0 6.734375,0 6.5625,0 L 3.90625,0 c -1.546875,0 -2.6875,-1.15625 -2.6875,-2.5 0,-1.328125 1.140625,-2.484375 2.6875,-2.484375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-b73c230a-5-2"> + <g + id="g4580-5" + style="fill:#000000;fill-opacity:1"> + <use + id="use4582-4" + y="134.765" + x="223.43201" + xlink:href="#textext-b73c230a-1-7" + width="100%" + height="100%" /> + </g> + <g + id="g4584-0" + style="fill:#000000;fill-opacity:1"> + <use + id="use4586-5" + y="134.765" + x="232.25" + xlink:href="#textext-b73c230a-4-0" + width="100%" + height="100%" /> + </g> + <g + id="g4588-9" + style="fill:#000000;fill-opacity:1"> + <use + id="use4590-4" + y="134.765" + x="242.76601" + xlink:href="#textext-b73c230a-2-4" + width="100%" + height="100%" /> + </g> + </g> + </g> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:#000080;fill-rule:evenodd;stroke:#000080;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow1Lend-8)" + d="m 737.85714,449.50504 148.57143,-8.57143" + id="path5000-6" + inkscape:connector-curvature="0" /> + <circle + r="80.779091" + cy="449.46512" + cx="737.3952" + id="path6334" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:0.98999999;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1.06622958;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:3.19868871, 3.19868871;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + id="g6495" + style="fill:#000080;stroke:#000080" + transform="matrix(1.3952558,-0.07472613,0.07472613,1.3952558,431.03302,272.05923)" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$\\sqrt{d(w,L \\setminus \\sigma)^2 + \\alpha^2}$"> + <defs + id="defs6497"> + <g + id="g6499"> + <symbol + id="textext-c0d6e8dc-0" + overflow="visible" + style="overflow:visible"> + <path + id="path6502" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-1" + overflow="visible" + style="overflow:visible"> + <path + id="path6505" + d="m 4.234375,11.5625 c 0.296875,0 0.3125,-0.01563 0.40625,-0.203125 l 5.453125,-11.375 c 0.07813,-0.140625 0.07813,-0.15625 0.07813,-0.1875 0,-0.109375 -0.07813,-0.203125 -0.203125,-0.203125 -0.125,0 -0.171875,0.09375 -0.21875,0.203125 L 4.609375,10.53125 2.484375,5.578125 1.09375,6.65625 1.25,6.8125 1.953125,6.265625 Z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-2" + overflow="visible" + style="overflow:visible"> + <path + id="path6508" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-3" + overflow="visible" + style="overflow:visible"> + <path + id="path6511" + d="m 5.140625,-6.8125 c 0,0 0,-0.109375 -0.125,-0.109375 -0.15625,0 -1.09375,0.09375 -1.265625,0.109375 -0.078125,0.015625 -0.140625,0.0625 -0.140625,0.1875 0,0.125 0.09375,0.125 0.234375,0.125 0.484375,0 0.5,0.0625 0.5,0.171875 L 4.3125,-6.125 3.71875,-3.765625 C 3.53125,-4.140625 3.25,-4.40625 2.796875,-4.40625 c -1.15625,0 -2.390625,1.46875 -2.390625,2.921875 0,0.9375 0.546875,1.59375 1.3125,1.59375 0.203125,0 0.703125,-0.046875 1.296875,-0.75 0.078125,0.421875 0.4375,0.75 0.90625,0.75 0.359375,0 0.578125,-0.234375 0.75,-0.546875 0.15625,-0.359375 0.296875,-0.96875 0.296875,-0.984375 0,-0.109375 -0.09375,-0.109375 -0.125,-0.109375 -0.09375,0 -0.109375,0.046875 -0.140625,0.1875 -0.171875,0.640625 -0.34375,1.234375 -0.75,1.234375 -0.28125,0 -0.296875,-0.265625 -0.296875,-0.453125 0,-0.25 0.015625,-0.3125 0.046875,-0.484375 z m -2.0625,5.625 C 3.015625,-1 3.015625,-0.984375 2.875,-0.8125 2.4375,-0.265625 2.03125,-0.109375 1.75,-0.109375 c -0.5,0 -0.640625,-0.546875 -0.640625,-0.9375 0,-0.5 0.3125,-1.71875 0.546875,-2.1875 0.3125,-0.578125 0.75,-0.953125 1.15625,-0.953125 0.640625,0 0.78125,0.8125 0.78125,0.875 0,0.0625 -0.015625,0.125 -0.03125,0.171875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-4" + overflow="visible" + style="overflow:visible"> + <path + id="path6514" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-5" + overflow="visible" + style="overflow:visible"> + <path + id="path6517" + d="m 2.03125,-0.015625 c 0,-0.65625 -0.25,-1.046875 -0.640625,-1.046875 -0.328125,0 -0.53125,0.25 -0.53125,0.53125 C 0.859375,-0.265625 1.0625,0 1.390625,0 1.5,0 1.640625,-0.046875 1.734375,-0.125 1.765625,-0.15625 1.78125,-0.15625 1.78125,-0.15625 c 0.015625,0 0.015625,0 0.015625,0.140625 0,0.75 -0.34375,1.34375 -0.671875,1.671875 -0.109375,0.109375 -0.109375,0.125 -0.109375,0.15625 0,0.078125 0.046875,0.109375 0.09375,0.109375 0.109375,0 0.921875,-0.765625 0.921875,-1.9375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-6" + overflow="visible" + style="overflow:visible"> + <path + id="path6520" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-7" + overflow="visible" + style="overflow:visible"> + <path + id="path6523" + d="m 5.15625,-3.71875 c 0.140625,0 0.5,0 0.5,-0.34375 0,-0.234375 -0.21875,-0.234375 -0.390625,-0.234375 l -2.28125,0 c -1.5,0 -2.609375,1.640625 -2.609375,2.828125 0,0.875 0.59375,1.578125 1.5,1.578125 1.171875,0 2.5,-1.203125 2.5,-2.734375 0,-0.171875 0,-0.65625 -0.3125,-1.09375 z M 1.890625,-0.109375 C 1.390625,-0.109375 1,-0.46875 1,-1.1875 c 0,-0.296875 0.109375,-1.109375 0.46875,-1.703125 0.421875,-0.6875 1.015625,-0.828125 1.359375,-0.828125 0.828125,0 0.90625,0.65625 0.90625,0.96875 0,0.46875 -0.203125,1.28125 -0.53125,1.796875 -0.390625,0.578125 -0.9375,0.84375 -1.3125,0.84375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-8" + overflow="visible" + style="overflow:visible"> + <path + id="path6526" + d="m 4.75,-2.359375 c 0,-1.5625 -0.921875,-2.046875 -1.65625,-2.046875 -1.375,0 -2.6875,1.421875 -2.6875,2.828125 0,0.9375 0.59375,1.6875 1.625,1.6875 0.625,0 1.34375,-0.234375 2.09375,-0.84375 0.125,0.53125 0.453125,0.84375 0.90625,0.84375 0.53125,0 0.84375,-0.546875 0.84375,-0.703125 0,-0.078125 -0.0625,-0.109375 -0.125,-0.109375 -0.0625,0 -0.09375,0.03125 -0.125,0.109375 -0.1875,0.484375 -0.546875,0.484375 -0.5625,0.484375 -0.3125,0 -0.3125,-0.78125 -0.3125,-1.015625 0,-0.203125 0,-0.234375 0.109375,-0.34375 C 5.796875,-2.65625 6,-3.8125 6,-3.8125 6,-3.84375 5.984375,-3.921875 5.875,-3.921875 c -0.09375,0 -0.09375,0.03125 -0.140625,0.21875 -0.1875,0.625 -0.515625,1.375 -0.984375,1.96875 z m -0.65625,1.375 c -0.890625,0.765625 -1.65625,0.875 -2.046875,0.875 -0.59375,0 -0.90625,-0.453125 -0.90625,-1.09375 0,-0.484375 0.265625,-1.5625 0.578125,-2.0625 C 2.1875,-4 2.734375,-4.1875 3.078125,-4.1875 c 0.984375,0 0.984375,1.3125 0.984375,2.078125 0,0.375 0,0.953125 0.03125,1.125 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-9" + overflow="visible" + style="overflow:visible"> + <path + id="path6529" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-10" + overflow="visible" + style="overflow:visible"> + <path + id="path6532" + d="m 3.296875,2.390625 c 0,-0.03125 0,-0.046875 -0.171875,-0.21875 C 1.890625,0.921875 1.5625,-0.96875 1.5625,-2.5 c 0,-1.734375 0.375,-3.46875 1.609375,-4.703125 0.125,-0.125 0.125,-0.140625 0.125,-0.171875 0,-0.078125 -0.03125,-0.109375 -0.09375,-0.109375 -0.109375,0 -1,0.6875 -1.59375,1.953125 -0.5,1.09375 -0.625,2.203125 -0.625,3.03125 0,0.78125 0.109375,1.984375 0.65625,3.125 C 2.25,1.84375 3.09375,2.5 3.203125,2.5 c 0.0625,0 0.09375,-0.03125 0.09375,-0.109375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-11" + overflow="visible" + style="overflow:visible"> + <path + id="path6535" + d="m 2.875,-2.5 c 0,-0.765625 -0.109375,-1.96875 -0.65625,-3.109375 -0.59375,-1.21875 -1.453125,-1.875 -1.546875,-1.875 -0.0625,0 -0.109375,0.046875 -0.109375,0.109375 0,0.03125 0,0.046875 0.1875,0.234375 0.984375,0.984375 1.546875,2.5625 1.546875,4.640625 0,1.71875 -0.359375,3.46875 -1.59375,4.71875 C 0.5625,2.34375 0.5625,2.359375 0.5625,2.390625 0.5625,2.453125 0.609375,2.5 0.671875,2.5 0.765625,2.5 1.671875,1.8125 2.25,0.546875 2.765625,-0.546875 2.875,-1.65625 2.875,-2.5 Z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-12" + overflow="visible" + style="overflow:visible"> + <path + id="path6538" + d="m 4.078125,-2.296875 2.78125,0 C 7,-2.296875 7.1875,-2.296875 7.1875,-2.5 7.1875,-2.6875 7,-2.6875 6.859375,-2.6875 l -2.78125,0 0,-2.796875 c 0,-0.140625 0,-0.328125 -0.203125,-0.328125 -0.203125,0 -0.203125,0.1875 -0.203125,0.328125 l 0,2.796875 -2.78125,0 c -0.140625,0 -0.328125,0 -0.328125,0.1875 0,0.203125 0.1875,0.203125 0.328125,0.203125 l 2.78125,0 0,2.796875 c 0,0.140625 0,0.328125 0.203125,0.328125 0.203125,0 0.203125,-0.1875 0.203125,-0.328125 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-13" + overflow="visible" + style="overflow:visible"> + <path + id="path6541" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-14" + overflow="visible" + style="overflow:visible"> + <path + id="path6544" + d="m 4,2.25 c 0.046875,0.140625 0.09375,0.25 0.234375,0.25 0.109375,0 0.1875,-0.09375 0.1875,-0.203125 0,-0.03125 0,-0.046875 -0.046875,-0.15625 l -3.40625,-9.375 c -0.0625,-0.171875 -0.09375,-0.25 -0.21875,-0.25 -0.109375,0 -0.203125,0.09375 -0.203125,0.203125 0,0.03125 0,0.046875 0.046875,0.15625 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-15" + overflow="visible" + style="overflow:visible"> + <path + id="path6547" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-16" + overflow="visible" + style="overflow:visible"> + <path + id="path6550" + d="m 3.515625,-1.265625 -0.234375,0 c -0.015625,0.15625 -0.09375,0.5625 -0.1875,0.625 -0.046875,0.046875 -0.578125,0.046875 -0.6875,0.046875 l -1.28125,0 c 0.734375,-0.640625 0.984375,-0.84375 1.390625,-1.171875 0.515625,-0.40625 1,-0.84375 1,-1.5 0,-0.84375 -0.734375,-1.359375 -1.625,-1.359375 -0.859375,0 -1.453125,0.609375 -1.453125,1.25 0,0.34375 0.296875,0.390625 0.375,0.390625 0.15625,0 0.359375,-0.125 0.359375,-0.375 0,-0.125 -0.046875,-0.375 -0.40625,-0.375 C 0.984375,-4.21875 1.453125,-4.375 1.78125,-4.375 c 0.703125,0 1.0625,0.546875 1.0625,1.109375 0,0.609375 -0.4375,1.078125 -0.65625,1.328125 L 0.515625,-0.265625 C 0.4375,-0.203125 0.4375,-0.1875 0.4375,0 l 2.875,0 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-c0d6e8dc-17" + style="fill:#000080;stroke:#000080"> + <g + id="g6553" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6555" + y="126.247" + x="223.43201" + xlink:href="#textext-c0d6e8dc-1" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <path + id="path6557" + transform="matrix(1,0,0,-1,233.395,126.048)" + d="m -4.6875e-4,0.001125 74.52734375,0" + style="fill:#000080;stroke:#000080;stroke-width:0.398;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1" + inkscape:connector-curvature="0" /> + <g + id="g6559" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6561" + y="134.765" + x="233.395" + xlink:href="#textext-c0d6e8dc-3" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6563" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6565" + y="134.765" + x="238.58" + xlink:href="#textext-c0d6e8dc-10" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6567" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6569" + y="134.765" + x="242.455" + xlink:href="#textext-c0d6e8dc-4" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6571" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6573" + y="134.765" + x="249.85622" + xlink:href="#textext-c0d6e8dc-5" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6575" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6577" + y="134.765" + x="254.28758" + xlink:href="#textext-c0d6e8dc-6" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6579" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6581" + y="134.765" + x="263.27701" + xlink:href="#textext-c0d6e8dc-14" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6583" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6585" + y="134.765" + x="270.47198" + xlink:href="#textext-c0d6e8dc-7" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6587" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6589" + y="134.765" + x="276.522" + xlink:href="#textext-c0d6e8dc-11" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6591" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6593" + y="131.88699" + x="280.397" + xlink:href="#textext-c0d6e8dc-16" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6595" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6597" + y="134.765" + x="287.07999" + xlink:href="#textext-c0d6e8dc-12" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6599" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6601" + y="134.765" + x="297.043" + xlink:href="#textext-c0d6e8dc-8" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6603" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6605" + y="131.88699" + x="303.453" + xlink:href="#textext-c0d6e8dc-16" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + </g> + </g> + </g> + <g + transform="translate(-130.29351,-300.82484)" + style="display:none" + inkscape:label="Layer 2" + id="layer2" + inkscape:groupmode="layer"> + <circle + r="32.857143" + cy="448.79074" + cx="337.85715" + id="path5639" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:0.98999999;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:3, 3;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + </g> +</svg> diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index 857ec819..848239b5 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -1,17 +1,29 @@ cmake_minimum_required(VERSION 2.6) project(Witness_complex_examples) -# A simple example - add_executable( witness_complex_from_file witness_complex_from_file.cpp ) - add_test( witness_complex_from_bunny ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file - ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off 100) if(CGAL_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.6.0) if (EIGEN3_FOUND) - add_executable ( witness_complex_sphere witness_complex_sphere.cpp ) - target_link_libraries(witness_complex_sphere ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_test( witness_complex_sphere_10 ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_sphere 10) + add_executable( Witness_complex_example_off example_witness_complex_off.cpp ) + add_executable ( Witness_complex_example_sphere example_witness_complex_sphere.cpp ) + + add_executable ( Witness_complex_example_witness_persistence example_witness_complex_persistence.cpp ) + target_link_libraries(Witness_complex_example_witness_persistence ${Boost_PROGRAM_OPTIONS_LIBRARY}) + + add_executable ( Witness_complex_example_strong_witness_persistence example_strong_witness_persistence.cpp ) + target_link_libraries(Witness_complex_example_strong_witness_persistence ${Boost_PROGRAM_OPTIONS_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(Witness_complex_example_witness_persistence ${TBB_LIBRARIES}) + target_link_libraries(Witness_complex_example_strong_witness_persistence ${TBB_LIBRARIES}) + endif() + + add_test(Witness_complex_test_torus_persistence + ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_example_witness_persistence + ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off -l 20 -a 0.5) + add_test(Witness_complex_test_torus_persistence + ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_example_strong_witness_persistence + ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off -l 20 -a 0.5) endif(EIGEN3_FOUND) endif (NOT CGAL_VERSION VERSION_LESS 4.6.0) endif() diff --git a/src/Witness_complex/example/example_strong_witness_persistence.cpp b/src/Witness_complex/example/example_strong_witness_persistence.cpp new file mode 100644 index 00000000..a0563ee2 --- /dev/null +++ b/src/Witness_complex/example/example_strong_witness_persistence.cpp @@ -0,0 +1,152 @@ +#include <gudhi/Simplex_tree.h> +#include <gudhi/Strong_witness_complex.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Points_off_io.h> +#include <gudhi/pick_n_random_points.h> + +#include <boost/program_options.hpp> + +#include <CGAL/Epick_d.h> + +#include <string> +#include <vector> +#include <limits> // infinity + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; +typedef typename K::Point_d Point_d; + +typedef typename std::vector<Point_d> Point_vector; +typedef typename Gudhi::witness_complex::Strong_witness_complex<K> Strong_witness_complex; +typedef Gudhi::Simplex_tree<> SimplexTree; + +typedef int Vertex_handle; +typedef double Filtration_value; + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string file_name; + std::string filediag; + Filtration_value max_squared_alpha; + int p, nbL, lim_d; + Filtration_value min_persistence; + SimplexTree simplex_tree; + + program_options(argc, argv, nbL, file_name, filediag, max_squared_alpha, p, lim_d, min_persistence); + + // Extract the points from the file file_name + Point_vector witnesses, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + if (!off_reader.is_valid()) { + std::cerr << "Witness complex - Unable to read file " << file_name << "\n"; + exit(-1); // ----- >> + } + witnesses = Point_vector(off_reader.get_point_cloud()); + std::cout << "Successfully read " << witnesses.size() << " points.\n"; + std::cout << "Ambient dimension is " << witnesses[0].dimension() << ".\n"; + + // Choose landmarks from witnesses + Gudhi::subsampling::pick_n_random_points(witnesses, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + Strong_witness_complex strong_witness_complex(landmarks, + witnesses); + + strong_witness_complex.create_complex(simplex_tree, max_squared_alpha); + + std::cout << "The complex contains " << simplex_tree.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << simplex_tree.dimension() << " \n"; + + // Sort the simplices in the order of the filtration + simplex_tree.initialize_filtration(); + + // Compute the persistence diagram of the complex + persistent_cohomology::Persistent_cohomology<SimplexTree, Field_Zp > pcoh(simplex_tree); + // initializes the coefficient field for homology + pcoh.init_coefficients(p); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (filediag.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(filediag); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence) { + + namespace po = boost::program_options; + + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&file_name), + "Name of file containing a point set in off format."); + + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("landmarks,l", po::value<int>(&nbL), + "Number of landmarks to choose from the point cloud.") + ("output-file,o", po::value<std::string>(&filediag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-sq-alpha,a", po::value<Filtration_value>(&max_squared_alpha)->default_value(std::numeric_limits<Filtration_value>::infinity()), + "Maximal length of an edge for the Rips complex construction.") + ("field-charac,p", po::value<int>(&p)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence)->default_value(0), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals") + ("cpx-dimension,d", po::value<int>(&dim_max)->default_value(std::numeric_limits<int>::max()), + "Maximal dimension of the strong witness complex we want to compute."); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + po::variables_map vm; + + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of a Strong witness complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} + diff --git a/src/Witness_complex/example/example_witness_complex_off.cpp b/src/Witness_complex/example/example_witness_complex_off.cpp new file mode 100644 index 00000000..2677499a --- /dev/null +++ b/src/Witness_complex/example/example_witness_complex_off.cpp @@ -0,0 +1,61 @@ +#include <sys/types.h> +#include <sys/stat.h> + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Witness_complex.h> +#include <gudhi/pick_n_random_points.h> +#include <gudhi/Points_off_io.h> + +#include <CGAL/Epick_d.h> + +#include <iostream> +#include <fstream> +#include <ctime> +#include <string> +#include <vector> + +typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; +typedef typename K::Point_d Point_d; +typedef typename Gudhi::witness_complex::Witness_complex<K> Witness_complex; +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef std::vector< Point_d > Point_vector; + +int main(int argc, char * const argv[]) { + if (argc != 4) { + std::cerr << "Usage: " << argv[0] + << " path_to_point_file number_of_landmarks max_squared_alpha limit_dimension\n"; + return 0; + } + + std::string file_name = argv[1]; + int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]); + double alpha2 = atof(argv[3]); + clock_t start, end; + Gudhi::Simplex_tree<> simplex_tree; + + // Read the point file + Point_vector point_vector, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + if (!off_reader.is_valid()) { + std::cerr << "Witness complex - Unable to read file " << file_name << "\n"; + exit(-1); // ----- >> + } + point_vector = Point_vector(off_reader.get_point_cloud()); + + std::cout << "Successfully read " << point_vector.size() << " points.\n"; + std::cout << "Ambient dimension is " << point_vector[0].dimension() << ".\n"; + + // Choose landmarks + Gudhi::subsampling::pick_n_random_points(point_vector, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + start = clock(); + Witness_complex witness_complex(landmarks, + point_vector); + + witness_complex.create_complex(simplex_tree, alpha2, lim_dim); + end = clock(); + std::cout << "Witness complex took " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + std::cout << "Number of simplices is: " << simplex_tree.num_simplices() << "\n"; +} diff --git a/src/Witness_complex/example/example_witness_complex_persistence.cpp b/src/Witness_complex/example/example_witness_complex_persistence.cpp new file mode 100644 index 00000000..00f00aae --- /dev/null +++ b/src/Witness_complex/example/example_witness_complex_persistence.cpp @@ -0,0 +1,152 @@ +#include <gudhi/Simplex_tree.h> +#include <gudhi/Witness_complex.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Points_off_io.h> +#include <gudhi/pick_n_random_points.h> + +#include <boost/program_options.hpp> + +#include <CGAL/Epick_d.h> + +#include <string> +#include <vector> +#include <limits> // infinity + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; +typedef typename K::Point_d Point_d; + +typedef typename std::vector<Point_d> Point_vector; +typedef typename Gudhi::witness_complex::Witness_complex<K> Witness_complex; +typedef Gudhi::Simplex_tree<> SimplexTree; + +typedef int Vertex_handle; +typedef double Filtration_value; + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string file_name; + std::string filediag; + Filtration_value max_squared_alpha; + int p, nbL, lim_d; + Filtration_value min_persistence; + SimplexTree simplex_tree; + + program_options(argc, argv, nbL, file_name, filediag, max_squared_alpha, p, lim_d, min_persistence); + + // Extract the points from the file file_name + Point_vector witnesses, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + if (!off_reader.is_valid()) { + std::cerr << "Witness complex - Unable to read file " << file_name << "\n"; + exit(-1); // ----- >> + } + witnesses = Point_vector(off_reader.get_point_cloud()); + std::cout << "Successfully read " << witnesses.size() << " points.\n"; + std::cout << "Ambient dimension is " << witnesses[0].dimension() << ".\n"; + + // Choose landmarks from witnesses + Gudhi::subsampling::pick_n_random_points(witnesses, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + Witness_complex witness_complex(landmarks, + witnesses); + + witness_complex.create_complex(simplex_tree, max_squared_alpha); + + std::cout << "The complex contains " << simplex_tree.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << simplex_tree.dimension() << " \n"; + + // Sort the simplices in the order of the filtration + simplex_tree.initialize_filtration(); + + // Compute the persistence diagram of the complex + persistent_cohomology::Persistent_cohomology<SimplexTree, Field_Zp > pcoh(simplex_tree); + // initializes the coefficient field for homology + pcoh.init_coefficients(p); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (filediag.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(filediag); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence) { + + namespace po = boost::program_options; + + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&file_name), + "Name of file containing a point set in off format."); + + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("landmarks,l", po::value<int>(&nbL), + "Number of landmarks to choose from the point cloud.") + ("output-file,o", po::value<std::string>(&filediag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-sq-alpha,a", po::value<Filtration_value>(&max_squared_alpha)->default_value(std::numeric_limits<Filtration_value>::infinity()), + "Maximal length of an edge for the Rips complex construction.") + ("field-charac,p", po::value<int>(&p)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence)->default_value(0), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals") + ("cpx-dimension,d", po::value<int>(&dim_max)->default_value(std::numeric_limits<int>::max()), + "Maximal dimension of the weak witness complex we want to compute."); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + po::variables_map vm; + + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of a Weak witness complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} + diff --git a/src/Witness_complex/example/witness_complex_sphere.cpp b/src/Witness_complex/example/example_witness_complex_sphere.cpp index e6f88274..42fb9f8d 100644 --- a/src/Witness_complex/example/witness_complex_sphere.cpp +++ b/src/Witness_complex/example/example_witness_complex_sphere.cpp @@ -1,24 +1,3 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2015 INRIA Sophia Antipolis-Méditerranée (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ #define BOOST_PARAMETER_MAX_ARITY 12 @@ -27,10 +6,11 @@ #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> -#include <gudhi/Construct_closest_landmark_table.h> #include <gudhi/pick_n_random_points.h> #include <gudhi/reader_utils.h> +#include <CGAL/Epick_d.h> + #include <iostream> #include <fstream> #include <ctime> @@ -52,6 +32,8 @@ void write_data(Data_range & data, std::string filename) { } int main(int argc, char * const argv[]) { + typedef Gudhi::witness_complex::Witness_complex<CGAL::Epick_d<CGAL::Dynamic_dimension_tag>> Witness_complex; + if (argc != 2) { std::cerr << "Usage: " << argv[0] << " number_of_landmarks \n"; @@ -61,13 +43,12 @@ int main(int argc, char * const argv[]) { int number_of_landmarks = atoi(argv[1]); clock_t start, end; - // Construct the Simplex Tree - Gudhi::Simplex_tree<> simplex_tree; - std::vector< std::pair<int, double> > l_time; // Read the point file for (int nbP = 500; nbP < 10000; nbP += 500) { + // Construct the Simplex Tree + Gudhi::Simplex_tree<> simplex_tree; Point_Vector point_vector, landmarks; generate_points_sphere(point_vector, nbP, 4); std::cout << "Successfully generated " << point_vector.size() << " points.\n"; @@ -75,16 +56,18 @@ int main(int argc, char * const argv[]) { // Choose landmarks start = clock(); - std::vector<std::vector< int > > knn; - Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks)); - Gudhi::witness_complex::construct_closest_landmark_table(point_vector, landmarks, knn); + Gudhi::subsampling::pick_n_random_points(point_vector, number_of_landmarks, std::back_inserter(landmarks)); // Compute witness complex - Gudhi::witness_complex::witness_complex(knn, number_of_landmarks, point_vector[0].size(), simplex_tree); + Witness_complex witness_complex(landmarks, + point_vector); + witness_complex.create_complex(simplex_tree, 0); end = clock(); double time = static_cast<double>(end - start) / CLOCKS_PER_SEC; std::cout << "Witness complex for " << number_of_landmarks << " landmarks took " << time << " s. \n"; + //assert(1 == 0); + //std::cout << simplex_tree << "\n"; std::cout << "Number of simplices is: " << simplex_tree.num_simplices() << "\n"; l_time.push_back(std::make_pair(nbP, time)); } diff --git a/src/Witness_complex/example/generators.h b/src/Witness_complex/example/generators.h index ac445261..731a52b0 100644 --- a/src/Witness_complex/example/generators.h +++ b/src/Witness_complex/example/generators.h @@ -25,10 +25,12 @@ #include <CGAL/Epick_d.h> #include <CGAL/point_generators_d.h> +#include <CGAL/Random.h> #include <fstream> #include <string> #include <vector> +#include <cmath> typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; typedef K::FT FT; @@ -144,4 +146,21 @@ void generate_points_sphere(Point_Vector& W, int nbP, int dim) { W.push_back(*rp++); } +/** \brief Generate nbP points on a (flat) d-torus embedded in R^{2d} + * + */ +void generate_points_torus(Point_Vector& W, int nbP, int dim) { + CGAL::Random rand; + const double pi = std::acos(-1); + for (int i = 0; i < nbP; i++) { + std::vector<FT> point; + for (int j = 0; j < dim; j++) { + double alpha = rand.uniform_real((double)0, 2*pi); + point.push_back(sin(alpha)); + point.push_back(cos(alpha)); + } + W.push_back(Point_d(point)); + } +} + #endif // EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_ diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp deleted file mode 100644 index bb641b3c..00000000 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ /dev/null @@ -1,83 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2015 INRIA Sophia Antipolis-Méditerranée (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -#include <sys/types.h> -#include <sys/stat.h> - -#include <gudhi/Points_off_io.h> -#include <gudhi/Simplex_tree.h> -#include <gudhi/Witness_complex.h> -#include <gudhi/Construct_closest_landmark_table.h> -#include <gudhi/pick_n_random_points.h> -#include <gudhi/reader_utils.h> - -#include <iostream> -#include <fstream> -#include <ctime> -#include <string> -#include <vector> - -typedef std::vector< Vertex_handle > typeVectorVertex; -typedef std::vector< std::vector <double> > Point_Vector; - -int main(int argc, char * const argv[]) { - if (argc != 3) { - std::cerr << "Usage: " << argv[0] - << " path_to_point_file.off nbL \n"; - return 0; - } - - std::string off_file_name = argv[1]; - int nbL = atoi(argv[2]); - clock_t start, end; - - // Construct the Simplex Tree - Gudhi::Simplex_tree<> simplex_tree; - - // Read the OFF file (input file name given as parameter) and triangulate points - Gudhi::Points_off_reader<std::vector <double>> off_reader(off_file_name); - // Check the read operation was correct - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << off_file_name << std::endl; - } - // Read the point file - Point_Vector point_vector = off_reader.get_point_cloud(); - std::cout << "Successfully read " << point_vector.size() << " points.\n"; - std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; - - // Choose landmarks - start = clock(); - std::vector<std::vector< int > > knn; - Point_Vector landmarks; - Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks)); - Gudhi::witness_complex::construct_closest_landmark_table(point_vector, landmarks, knn); - end = clock(); - std::cout << "Landmark choice for " << nbL << " landmarks took " - << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; - - // Compute witness complex - start = clock(); - Gudhi::witness_complex::witness_complex(knn, nbL, point_vector[0].size(), simplex_tree); - end = clock(); - std::cout << "Witness complex took " - << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; -} diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h new file mode 100644 index 00000000..fce7d3d1 --- /dev/null +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h @@ -0,0 +1,75 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef ACTIVE_WITNESS_H_ +#define ACTIVE_WITNESS_H_ + +#include <gudhi/Active_witness/Active_witness_iterator.h> +#include <vector> +#include <utility> + +namespace Gudhi { + +namespace witness_complex { + + // /** \class Active_witness + // * \brief Class representing a list of nearest neighbors to a given witness. + // * \details Every element is a pair of a landmark identifier and the squared distance to it. + // */ +template< typename Id_distance_pair, + typename INS_range > +class Active_witness { +public: + typedef Active_witness<Id_distance_pair, INS_range> ActiveWitness; + typedef typename INS_range::iterator INS_iterator; + typedef Active_witness_iterator< ActiveWitness, Id_distance_pair, INS_iterator > iterator; + typedef typename std::list<Id_distance_pair> Table; + + Table end_element_table_ = {Id_distance_pair(-1,0)}; + typename Table::iterator end_pointer = end_element_table_.begin(); + + Table nearest_landmark_table_; + INS_range search_range_; + INS_iterator iterator_last_; + INS_iterator iterator_end_; + + Active_witness(INS_range search_range) + : search_range_(search_range), iterator_last_(search_range.begin()), iterator_end_(search_range.end()) + { + nearest_landmark_table_.push_back(*iterator_last_); + } + + iterator begin() + { + return iterator(this, nearest_landmark_table_.begin()); + } + + iterator end() + { + return iterator(this); + } +}; + +} +} + +#endif diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h new file mode 100644 index 00000000..ae051bea --- /dev/null +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h @@ -0,0 +1,111 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef ACTIVE_WITNESS_ITERATOR_H_ +#define ACTIVE_WITNESS_ITERATOR_H_ + +#include <boost/iterator/iterator_facade.hpp> +#include <vector> + +namespace Gudhi { + +namespace witness_complex { + + // /** \brief Iterator in the nearest landmark list. + // * \details After the iterator reaches the end of the list, + // * the list is augmented by a (nearest landmark, distance) pair if possible. + // * If all the landmarks are present in the list, iterator returns the specific end value + // * of the corresponding 'Active_witness' object. + // */ + +template< typename Active_witness, + typename Id_distance_pair, + typename INS_iterator > +class Active_witness_iterator + : public boost::iterator_facade< Active_witness_iterator <Active_witness, Id_distance_pair, INS_iterator> +, Id_distance_pair const +, boost::forward_traversal_tag +, Id_distance_pair const> { + friend class boost::iterator_core_access; + + //typedef Active_witness<Id_distance_pair, INS_iterator> Active_witness; + typedef typename std::list<Id_distance_pair>::iterator Pair_iterator; + typedef typename Gudhi::witness_complex::Active_witness_iterator<Active_witness, Id_distance_pair, INS_iterator> Iterator; + + + Active_witness *aw_; + Pair_iterator lh_; // landmark handle + //INS_iterator iterator_last; + //INS_iterator iterator_end; + +public: + Active_witness_iterator(Active_witness* aw) + : aw_(aw), lh_(aw_->end_pointer) + { + } + + Active_witness_iterator(Active_witness* aw, Pair_iterator lh) + : aw_(aw), lh_(lh) + { + } + +private : + + Id_distance_pair& dereference() const + { + return *lh_; + } + + bool equal(const Iterator& other) const + { + return (lh_ == other.lh_); + } + + void increment() + { + // if neighbor search is at its end, check if lh_++ is end + if (aw_->iterator_last_ == aw_->iterator_end_) { + if (lh_++ == aw_->nearest_landmark_table_.end()) { + lh_ = aw_->end_pointer; + return; + } + return; + } + // if the id of the current landmark is the same as the last one + if (lh_->first == aw_->iterator_last_->first) { + // if the next iterator is end, lh_it = end pointer + if (++(aw_->iterator_last_) == aw_->iterator_end_) { + lh_ = aw_->end_pointer; + return; + } + else + aw_->nearest_landmark_table_.push_back(*(aw_->iterator_last_)); + } + lh_++; + } + +}; + +} +} + +#endif diff --git a/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h deleted file mode 100644 index ef711c34..00000000 --- a/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h +++ /dev/null @@ -1,90 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2015 INRIA Sophia Antipolis-Méditerranée (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -#ifndef CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ -#define CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ - -#include <boost/range/size.hpp> - -#include <queue> // for priority_queue<> -#include <utility> // for pair<> -#include <iterator> -#include <vector> -#include <set> - -namespace Gudhi { - -namespace witness_complex { - - /** - * \ingroup witness_complex - * \brief Construct the closest landmark tables for all witnesses. - * \details Output a table 'knn', each line of which represents a witness and - * consists of landmarks sorted by - * euclidean distance from the corresponding witness. - * - * The type WitnessContainer is a random access range and - * the type LandmarkContainer is a range. - * The type KNearestNeighbors can be seen as - * Witness_range<Closest_landmark_range<Vertex_handle>>, where - * Witness_range and Closest_landmark_range are random access ranges and - * Vertex_handle is the label type of a vertex in a simplicial complex. - * Closest_landmark_range needs to have push_back operation. - */ - - template <typename WitnessContainer, - typename LandmarkContainer, - typename KNearestNeighbours> - void construct_closest_landmark_table(WitnessContainer const &points, - LandmarkContainer const &landmarks, - KNearestNeighbours &knn) { - int nbP = boost::size(points); - assert(nbP >= boost::size(landmarks)); - - int dim = boost::size(*std::begin(points)); - typedef std::pair<double, int> dist_i; - typedef bool (*comp)(dist_i, dist_i); - knn = KNearestNeighbours(nbP); - for (int points_i = 0; points_i < nbP; points_i++) { - std::priority_queue<dist_i, std::vector<dist_i>, comp> l_heap([](dist_i j1, dist_i j2) { - return j1.first > j2.first; - }); - typename LandmarkContainer::const_iterator landmarks_it; - int landmarks_i = 0; - for (landmarks_it = landmarks.begin(), landmarks_i = 0; landmarks_it != landmarks.end(); - ++landmarks_it, landmarks_i++) { - dist_i dist = std::make_pair(euclidean_distance(points[points_i], *landmarks_it), landmarks_i); - l_heap.push(dist); - } - for (int i = 0; i < dim + 1; i++) { - dist_i dist = l_heap.top(); - knn[points_i].push_back(dist.second); - l_heap.pop(); - } - } - } - -} // namespace witness_complex - -} // namespace Gudhi - -#endif // CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ diff --git a/src/Witness_complex/include/gudhi/Strong_witness_complex.h b/src/Witness_complex/include/gudhi/Strong_witness_complex.h new file mode 100644 index 00000000..c7b8c27b --- /dev/null +++ b/src/Witness_complex/include/gudhi/Strong_witness_complex.h @@ -0,0 +1,174 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Siargey Kachanovich + * + * Copyright (C) 2015 INRIA (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef STRONG_WITNESS_COMPLEX_H_ +#define STRONG_WITNESS_COMPLEX_H_ + +#include <utility> +#include <vector> +#include <list> +#include <limits> + +#include <gudhi/Active_witness/Active_witness.h> +#include <gudhi/Kd_tree_search.h> + +namespace gss = Gudhi::spatial_searching; + +namespace Gudhi { + +namespace witness_complex { + +/** + * \private + * \class Strong_witness_complex + * \brief Constructs strong witness complex for the given sets of witnesses and landmarks. + * \ingroup witness_complex + * + * \tparam Kernel_ requires a <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class, which + * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't. + * \tparam DimensionTag can be either <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dimension__tag.html">Dimension_tag<d></a> + * if you know the intrinsic dimension at compile-time, + * or <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dynamic__dimension__tag.html">CGAL::Dynamic_dimension_tag</a> + * if you don't. + */ +template< class Kernel_ > +class Strong_witness_complex { +private: + typedef Kernel_ K; + typedef typename K::Point_d Point_d; + typedef typename K::FT FT; + typedef std::vector<Point_d> Point_range; + typedef gss::Kd_tree_search<Kernel_, Point_range> Kd_tree; + typedef typename Kd_tree::INS_range Nearest_landmark_range; + typedef typename std::vector<Nearest_landmark_range> Nearest_landmark_table; + typedef typename Nearest_landmark_range::iterator Nearest_landmark_row_iterator; + + typedef std::vector< double > Point_t; + typedef std::vector< Point_t > Point_Vector; + + typedef FT Filtration_value; + + + typedef std::size_t Witness_id; + typedef typename Nearest_landmark_range::Point_with_transformed_distance Id_distance_pair; + typedef typename Id_distance_pair::first_type Landmark_id; + typedef Active_witness<Id_distance_pair, Nearest_landmark_range> ActiveWitness; + typedef std::list< ActiveWitness > ActiveWitnessList; + typedef std::vector< Landmark_id > typeVectorVertex; + typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex; + + typedef Landmark_id Vertex_handle; + + private: + Point_range witnesses_, landmarks_; + Kd_tree landmark_tree_; + + public: + ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /* @name Constructor + */ + + //@{ + + /** + * \brief Initializes member variables before constructing simplicial complex. + * \details Records landmarks from the range 'landmarks' into a + * table internally, as well as witnesses from the range 'witnesses'. + */ + template< typename LandmarkRange, + typename WitnessRange > + Strong_witness_complex(const LandmarkRange & landmarks, + const WitnessRange & witnesses) + : witnesses_(witnesses), landmarks_(landmarks), landmark_tree_(landmarks_) + { + } + + + /** \brief Returns the point corresponding to the given vertex. + */ + template <typename Vertex_handle> + Point_d get_point( Vertex_handle vertex ) const + { + return landmarks_[vertex]; + } + + /** \brief Outputs the strong witness complex of relaxation 'max_alpha_square' + * in a simplicial complex data structure. + * @param[out] complex Simplicial complex data structure, which is a model of + * SimplicialComplexForWitness concept. + * @param[in] max_alpha_square Maximal squared relaxation parameter. + * @param[in] limit_dimension Represents the maximal dimension of the simplicial complex + * (default value = no limit). + */ + template < typename SimplicialComplexForWitness > + bool create_complex(SimplicialComplexForWitness& complex, + FT max_alpha_square, + Landmark_id limit_dimension = std::numeric_limits<Landmark_id>::max()-1) + { + std::size_t nbL = landmarks_.size(); + Landmark_id complex_dim = 0; + if (complex.num_vertices() > 0) { + std::cerr << "Strong witness complex cannot create complex - complex is not empty.\n"; + return false; + } + if (max_alpha_square < 0) { + std::cerr << "Strong witness complex cannot create complex - squared relaxation parameter must be non-negative.\n"; + return false; + } + if (limit_dimension < 0) { + std::cerr << "Strong witness complex cannot create complex - limit dimension must be non-negative.\n"; + return false; + } + typeVectorVertex vv; + for (unsigned i = 0; i != nbL; ++i) { + // initial fill of 0-dimensional simplices + vv = {i}; + complex.insert_simplex(vv, Filtration_value(0.0)); + } + for (auto w: witnesses_) { + ActiveWitness aw(landmark_tree_.query_incremental_nearest_neighbors(w)); + typeVectorVertex simplex; + typename ActiveWitness::iterator aw_it = aw.begin(); + float lim_dist2 = aw.begin()->second + max_alpha_square; + while ((Landmark_id)simplex.size() <= limit_dimension + 1 && aw_it != aw.end() && aw_it->second < lim_dist2) { + simplex.push_back(aw_it->first); + complex.insert_simplex_and_subfaces(simplex, aw_it->second - aw.begin()->second); + aw_it++; + } + if ((Landmark_id)simplex.size() - 1 > complex_dim) + complex_dim = simplex.size() - 1; + } + complex.set_dimension(complex_dim); + return true; + } + + //@} +}; + +} // namespace witness_complex + +} // namespace Gudhi + +#endif diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 489cdf11..c1d402c6 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -4,7 +4,7 @@ * * Author(s): Siargey Kachanovich * - * Copyright (C) 2015 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2015 INRIA (France) * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -23,66 +23,62 @@ #ifndef WITNESS_COMPLEX_H_ #define WITNESS_COMPLEX_H_ -// Needed for the adjacency graph in bad link search -#include <boost/graph/graph_traits.hpp> -#include <boost/graph/adjacency_list.hpp> -#include <boost/graph/connected_components.hpp> +#include <gudhi/Active_witness/Active_witness.h> +#include <gudhi/Kd_tree_search.h> -#include <boost/range/size.hpp> - -#include <gudhi/distance_functions.h> - -#include <algorithm> #include <utility> #include <vector> #include <list> -#include <set> -#include <queue> #include <limits> -#include <ctime> -#include <iostream> -namespace Gudhi { +namespace gss = Gudhi::spatial_searching; +namespace Gudhi { + namespace witness_complex { -// /* -// * \private -// \class Witness_complex -// \brief Constructs the witness complex for the given set of witnesses and landmarks. -// \ingroup witness_complex -// */ -template< class SimplicialComplex> +/** + * \private + * \class Witness_complex + * \brief Constructs (weak) witness complex for the given sets of witnesses and landmarks. + * \ingroup witness_complex + * + * \tparam Kernel_ requires a <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class, which + * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't. +*/ +template< class Kernel_ > class Witness_complex { - private: - struct Active_witness { - int witness_id; - int landmark_id; - - Active_witness(int witness_id_, int landmark_id_) - : witness_id(witness_id_), - landmark_id(landmark_id_) { } - }; - - private: - typedef typename SimplicialComplex::Simplex_handle Simplex_handle; - typedef typename SimplicialComplex::Vertex_handle Vertex_handle; - +private: + typedef Kernel_ K; + typedef typename K::Point_d Point_d; + typedef typename K::FT FT; + typedef std::vector<Point_d> Point_range; + typedef gss::Kd_tree_search<Kernel_, Point_range> Kd_tree; + typedef typename Kd_tree::INS_range Nearest_landmark_range; + typedef typename std::vector<Nearest_landmark_range> Nearest_landmark_table; + typedef typename Nearest_landmark_range::iterator Nearest_landmark_row_iterator; + typedef std::vector< double > Point_t; typedef std::vector< Point_t > Point_Vector; - typedef std::vector< Vertex_handle > typeVectorVertex; + typedef FT Filtration_value; + + + typedef std::size_t Witness_id; + typedef typename Nearest_landmark_range::Point_with_transformed_distance Id_distance_pair; + typedef typename Id_distance_pair::first_type Landmark_id; + typedef Active_witness<Id_distance_pair, Nearest_landmark_range> ActiveWitness; + typedef std::list< ActiveWitness > ActiveWitnessList; + typedef std::vector< Landmark_id > typeVectorVertex; typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex; - typedef std::pair< Simplex_handle, bool > typePairSimplexBool; - typedef int Witness_id; - typedef int Landmark_id; - typedef std::list< Vertex_handle > ActiveWitnessList; + typedef Landmark_id Vertex_handle; private: - int nbL_; // Number of landmarks - SimplicialComplex& sc_; // Simplicial complex - + Point_range witnesses_, landmarks_; + Kd_tree landmark_tree_; + public: ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /* @name Constructor @@ -90,174 +86,185 @@ class Witness_complex { //@{ - // Witness_range<Closest_landmark_range<Vertex_handle>> + /** + * \brief Initializes member variables before constructing simplicial complex. + * \details Records landmarks from the range 'landmarks' into a + * table internally, as well as witnesses from the range 'witnesses'. + */ + template< typename LandmarkRange, + typename WitnessRange > + Witness_complex(const LandmarkRange & landmarks, + const WitnessRange & witnesses) + : witnesses_(witnesses), landmarks_(landmarks), landmark_tree_(landmarks_) + { + } - /* - * \brief Iterative construction of the witness complex. - * \details The witness complex is written in sc_ basing on a matrix knn of - * nearest neighbours of the form {witnesses}x{landmarks}. - * - * The type KNearestNeighbors can be seen as - * Witness_range<Closest_landmark_range<Vertex_handle>>, where - * Witness_range and Closest_landmark_range are random access ranges. - * - * Constructor takes into account at most (dim+1) - * first landmarks from each landmark range to construct simplices. - * - * Landmarks are supposed to be in [0,nbL_-1] + /** \brief Returns the point corresponding to the given vertex. + * @param[in] vertex Vertex handle of the point to retrieve. + */ + Point_d get_point( Vertex_handle vertex ) const + { + return landmarks_[vertex]; + } + + /** \brief Outputs the (weak) witness complex of relaxation 'max_alpha_square' + * in a simplicial complex data structure. + * @param[out] complex Simplicial complex data structure compatible which is a model of + * SimplicialComplexForWitness concept. + * @param[in] max_alpha_square Maximal squared relaxation parameter. + * @param[in] limit_dimension Represents the maximal dimension of the simplicial complex + * (default value = no limit). */ - template< typename KNearestNeighbors > - Witness_complex(KNearestNeighbors const & knn, - int nbL, - int dim, - SimplicialComplex & sc) : nbL_(nbL), sc_(sc) { - // Construction of the active witness list - int nbW = boost::size(knn); + template < typename SimplicialComplexForWitness > + bool create_complex(SimplicialComplexForWitness& complex, + FT max_alpha_square, + Landmark_id limit_dimension = std::numeric_limits<Landmark_id>::max()) + { + std::size_t nbL = landmarks_.size(); + if (complex.num_vertices() > 0) { + std::cerr << "Witness complex cannot create complex - complex is not empty.\n"; + return false; + } + if (max_alpha_square < 0) { + std::cerr << "Witness complex cannot create complex - squared relaxation parameter must be non-negative.\n"; + return false; + } + if (limit_dimension < 0) { + std::cerr << "Witness complex cannot create complex - limit dimension must be non-negative.\n"; + return false; + } typeVectorVertex vv; - int counter = 0; - /* The list of still useful witnesses - * it will diminuish in the course of iterations - */ - ActiveWitnessList active_w; // = new ActiveWitnessList(); - for (Vertex_handle i = 0; i != nbL_; ++i) { + ActiveWitnessList active_witnesses; + for (unsigned i = 0; i != nbL; ++i) { // initial fill of 0-dimensional simplices // by doing it we don't assume that landmarks are necessarily witnesses themselves anymore - counter++; vv = {i}; - sc_.insert_simplex(vv); - // TODO(SK) Error if not inserted : normally no need here though + complex.insert_simplex(vv, Filtration_value(0.0)); } - int k = 1; /* current dimension in iterative construction */ - for (int i = 0; i != nbW; ++i) - active_w.push_back(i); - while (!active_w.empty() && k < dim) { - typename ActiveWitnessList::iterator it = active_w.begin(); - while (it != active_w.end()) { - typeVectorVertex simplex_vector; - /* THE INSERTION: Checking if all the subfaces are in the simplex tree*/ - bool ok = all_faces_in(knn, *it, k); - if (ok) { - for (int i = 0; i != k + 1; ++i) - simplex_vector.push_back(knn[*it][i]); - sc_.insert_simplex(simplex_vector); - // TODO(SK) Error if not inserted : normally no need here though - ++it; - } else { - active_w.erase(it++); // First increase the iterator and then erase the previous element - } - } + Landmark_id k = 1; /* current dimension in iterative construction */ + for (auto w: witnesses_) + active_witnesses.push_back(ActiveWitness(landmark_tree_.query_incremental_nearest_neighbors(w))); + ActiveWitness aw_copy(active_witnesses.front()); + while (!active_witnesses.empty() && k <= limit_dimension ) { + typename ActiveWitnessList::iterator aw_it = active_witnesses.begin(); + std::vector<Landmark_id> simplex; + simplex.reserve(k+1); + while (aw_it != active_witnesses.end()) { + bool ok = add_all_faces_of_dimension(k, + max_alpha_square, + std::numeric_limits<double>::infinity(), + aw_it->begin(), + simplex, + complex, + aw_it->end()); + assert(simplex.empty()); + if (!ok) + active_witnesses.erase(aw_it++); //First increase the iterator and then erase the previous element + else + aw_it++; + } k++; } + complex.set_dimension(k-1); + return true; } //@} private: + /* \brief Adds recursively all the faces of a certain dimension dim witnessed by the same witness + * Iterator is needed to know until how far we can take landmarks to form simplexes + * simplex is the prefix of the simplexes to insert + * The output value indicates if the witness rests active or not + */ + template < typename SimplicialComplexForWitness > + bool add_all_faces_of_dimension(int dim, + double alpha2, + double norelax_dist2, + typename ActiveWitness::iterator curr_l, + std::vector<Landmark_id>& simplex, + SimplicialComplexForWitness& sc, + typename ActiveWitness::iterator end) + { + if (curr_l == end) + return false; + bool will_be_active = false; + typename ActiveWitness::iterator l_it = curr_l; + if (dim > 0) + for (; l_it->second - alpha2 <= norelax_dist2 && l_it != end; ++l_it) { + simplex.push_back(l_it->first); + if (sc.find(simplex) != sc.null_simplex()) { + typename ActiveWitness::iterator next_it = l_it; + will_be_active = add_all_faces_of_dimension(dim-1, + alpha2, + norelax_dist2, + ++next_it, + simplex, + sc, + end) || will_be_active; + } + assert(!simplex.empty()); + simplex.pop_back(); + // If norelax_dist is infinity, change to first omitted distance + if (l_it->second <= norelax_dist2) + norelax_dist2 = l_it->second; + typename ActiveWitness::iterator next_it = l_it; + will_be_active = add_all_faces_of_dimension(dim, + alpha2, + norelax_dist2, + ++next_it, + simplex, + sc, + end) || will_be_active; + } + else if (dim == 0) + for (; l_it->second - alpha2 <= norelax_dist2 && l_it != end; ++l_it) { + simplex.push_back(l_it->first); + double filtration_value = 0; + // if norelax_dist is infinite, relaxation is 0. + if (l_it->second > norelax_dist2) + filtration_value = l_it->second - norelax_dist2; + if (all_faces_in(simplex, &filtration_value, sc)) { + will_be_active = true; + sc.insert_simplex(simplex, filtration_value); + } + assert(!simplex.empty()); + simplex.pop_back(); + // If norelax_dist is infinity, change to first omitted distance + if (l_it->second < norelax_dist2) + norelax_dist2 = l_it->second; + } + return will_be_active; + } + /* \brief Check if the facets of the k-dimensional simplex witnessed * by witness witness_id are already in the complex. * inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id */ - template <typename KNearestNeighbors> - bool all_faces_in(KNearestNeighbors const &knn, int witness_id, int k) { - std::vector< Vertex_handle > facet; - // CHECK ALL THE FACETS - for (int i = 0; i != k + 1; ++i) { - facet = {}; - for (int j = 0; j != k + 1; ++j) { - if (j != i) { - facet.push_back(knn[witness_id][j]); - } - } // endfor - if (sc_.find(facet) == sc_.null_simplex()) - return false; - } // endfor - return true; - } + template < typename SimplicialComplexForWitness > + bool all_faces_in(typeVectorVertex& simplex, + double* filtration_value, + SimplicialComplexForWitness& sc) + { + typedef typename SimplicialComplexForWitness::Simplex_handle Simplex_handle; - template <typename T> - static void print_vector(const std::vector<T>& v) { - std::cout << "["; - if (!v.empty()) { - std::cout << *(v.begin()); - for (auto it = v.begin() + 1; it != v.end(); ++it) { - std::cout << ","; - std::cout << *it; + typeVectorVertex facet; + for (typename typeVectorVertex::iterator not_it = simplex.begin(); not_it != simplex.end(); ++not_it) + { + facet.clear(); + for (typename typeVectorVertex::iterator it = simplex.begin(); it != simplex.end(); ++it) + if (it != not_it) + facet.push_back(*it); + Simplex_handle facet_sh = sc.find(facet); + if (facet_sh == sc.null_simplex()) + return false; + else if (sc.filtration(facet_sh) > *filtration_value) + *filtration_value = sc.filtration(facet_sh); } - } - std::cout << "]"; - } - - public: - // /* - // * \brief Verification if every simplex in the complex is witnessed by witnesses in knn. - // * \param print_output =true will print the witnesses for each simplex - // * \remark Added for debugging purposes. - // */ - template< class KNearestNeighbors > - bool is_witness_complex(KNearestNeighbors const & knn, bool print_output) { - for (Simplex_handle sh : sc_.complex_simplex_range()) { - bool is_witnessed = false; - typeVectorVertex simplex; - int nbV = 0; // number of verticed in the simplex - for (Vertex_handle v : sc_.simplex_vertex_range(sh)) - simplex.push_back(v); - nbV = simplex.size(); - for (typeVectorVertex w : knn) { - bool has_vertices = true; - for (Vertex_handle v : simplex) - if (std::find(w.begin(), w.begin() + nbV, v) == w.begin() + nbV) { - has_vertices = false; - } - if (has_vertices) { - is_witnessed = true; - if (print_output) { - std::cout << "The simplex "; - print_vector(simplex); - std::cout << " is witnessed by the witness "; - print_vector(w); - std::cout << std::endl; - } - break; - } - } - if (!is_witnessed) { - if (print_output) { - std::cout << "The following simplex is not witnessed "; - print_vector(simplex); - std::cout << std::endl; - } - assert(is_witnessed); - return false; - } - } return true; } }; - /** - * \ingroup witness_complex - * \brief Iterative construction of the witness complex. - * \details The witness complex is written in simplicial complex sc_ - * basing on a matrix knn of - * nearest neighbours of the form {witnesses}x{landmarks}. - * - * The type KNearestNeighbors can be seen as - * Witness_range<Closest_landmark_range<Vertex_handle>>, where - * Witness_range and Closest_landmark_range are random access ranges. - * - * Procedure takes into account at most (dim+1) - * first landmarks from each landmark range to construct simplices. - * - * Landmarks are supposed to be in [0,nbL_-1] - */ - template <class KNearestNeighbors, class SimplicialComplexForWitness> - void witness_complex(KNearestNeighbors const & knn, - int nbL, - int dim, - SimplicialComplexForWitness & sc) { - Witness_complex<SimplicialComplexForWitness>(knn, nbL, dim, sc); - } - } // namespace witness_complex } // namespace Gudhi diff --git a/src/Witness_complex/test/CMakeLists.txt b/src/Witness_complex/test/CMakeLists.txt index bb55b0f1..8d68ea1f 100644 --- a/src/Witness_complex/test/CMakeLists.txt +++ b/src/Witness_complex/test/CMakeLists.txt @@ -10,21 +10,11 @@ if (GPROF_PATH) set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") endif() -add_executable ( simple_witness_complexUT simple_witness_complex.cpp ) -target_link_libraries(simple_witness_complexUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +add_executable ( Witness_complex_test_simple_witness_complex test_simple_witness_complex.cpp ) +target_link_libraries(Witness_complex_test_simple_witness_complex ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) # Unitary tests definition and xml result file generation -add_test(NAME simple_witness_complexUT - COMMAND ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complexUT +add_test(NAME simple_witness_complex + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_test_simple_witness_complex # XML format for Jenkins xUnit plugin - --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/simple_witness_complexUT.xml --log_level=test_suite --report_level=no) - -add_executable ( witness_complex_pointsUT witness_complex_points.cpp ) -target_link_libraries(witness_complex_pointsUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) - -# Unitary tests definition and xml result file generation -add_test(NAME witness_complex_pointsUT - COMMAND ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_pointsUT - # XML format for Jenkins xUnit plugin - --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/witness_complex_pointsUT.xml --log_level=test_suite --report_level=no) - + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Witness_complex_test_simple_witness_complexUT.xml --log_level=test_suite --report_level=no) diff --git a/src/Witness_complex/test/simple_witness_complex.cpp b/src/Witness_complex/test/simple_witness_complex.cpp deleted file mode 100644 index 03df78ee..00000000 --- a/src/Witness_complex/test/simple_witness_complex.cpp +++ /dev/null @@ -1,59 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2016 INRIA Sophia Antipolis-Méditerranée (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -#define BOOST_TEST_DYN_LINK -#define BOOST_TEST_MODULE "simple_witness_complex" -#include <boost/test/unit_test.hpp> -#include <boost/mpl/list.hpp> - -#include <gudhi/Simplex_tree.h> -#include <gudhi/Witness_complex.h> - -#include <iostream> -#include <ctime> -#include <vector> - -typedef Gudhi::Simplex_tree<> Simplex_tree; -typedef std::vector< Vertex_handle > typeVectorVertex; -typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex; - -BOOST_AUTO_TEST_CASE(simple_witness_complex) { - Simplex_tree complex; - std::vector< typeVectorVertex > knn; - - knn.push_back({1, 0, 5, 2, 6, 3, 4}); - knn.push_back({2, 6, 4, 5, 0, 1, 3}); - knn.push_back({3, 4, 2, 1, 5, 6, 0}); - knn.push_back({4, 2, 1, 3, 5, 6, 0}); - knn.push_back({5, 1, 6, 0, 2, 3, 4}); - knn.push_back({6, 0, 5, 2, 1, 3, 4}); - knn.push_back({0, 5, 6, 1, 2, 3, 4}); - knn.push_back({2, 6, 4, 5, 3, 1, 0}); - knn.push_back({1, 2, 5, 4, 3, 6, 0}); - knn.push_back({3, 4, 0, 6, 5, 1, 2}); - knn.push_back({5, 0, 1, 3, 6, 2, 4}); - knn.push_back({5, 6, 1, 0, 2, 3, 4}); - knn.push_back({1, 6, 0, 5, 2, 3, 4}); - WitnessComplex witnessComplex(knn, 7, 7, complex); - - BOOST_CHECK(witnessComplex.is_witness_complex(knn, false)); -} diff --git a/src/Witness_complex/test/test_simple_witness_complex.cpp b/src/Witness_complex/test/test_simple_witness_complex.cpp new file mode 100644 index 00000000..a0a1b36c --- /dev/null +++ b/src/Witness_complex/test/test_simple_witness_complex.cpp @@ -0,0 +1,80 @@ +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "simple_witness_complex" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + +#include <CGAL/Epick_d.h> + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Witness_complex.h> +#include <gudhi/Strong_witness_complex.h> + +#include <iostream> +#include <ctime> +#include <vector> + +typedef Gudhi::Simplex_tree<> Simplex_tree; +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> Kernel; +typedef typename Kernel::FT FT; +typedef typename Kernel::Point_d Point_d; +typedef Gudhi::witness_complex::Witness_complex<Kernel> WitnessComplex; +typedef Gudhi::witness_complex::Strong_witness_complex<Kernel> StrongWitnessComplex; + +/* All landmarks and witnesses are taken on the grid in the following manner. + LWLWL + WW.WW + L...L + WW.WW + LWLWL + + Witness complex consists of 8 vertices, 12 edges and 4 triangles + */ + +BOOST_AUTO_TEST_CASE(simple_witness_complex) { + Simplex_tree complex, relaxed_complex, strong_relaxed_complex; + + std::vector<Point_d> witnesses, landmarks; + + landmarks.push_back(Point_d(std::vector<FT>{-2,-2})); + landmarks.push_back(Point_d(std::vector<FT>{-2, 0})); + landmarks.push_back(Point_d(std::vector<FT>{-2, 2})); + landmarks.push_back(Point_d(std::vector<FT>{ 0,-2})); + landmarks.push_back(Point_d(std::vector<FT>{ 0, 2})); + landmarks.push_back(Point_d(std::vector<FT>{ 2,-2})); + landmarks.push_back(Point_d(std::vector<FT>{ 2, 0})); + landmarks.push_back(Point_d(std::vector<FT>{ 2, 2})); + witnesses.push_back(Point_d(std::vector<FT>{-2,-1})); + witnesses.push_back(Point_d(std::vector<FT>{-2, 1})); + witnesses.push_back(Point_d(std::vector<FT>{-1,-2})); + witnesses.push_back(Point_d(std::vector<FT>{-1,-1})); + witnesses.push_back(Point_d(std::vector<FT>{-1, 1})); + witnesses.push_back(Point_d(std::vector<FT>{-1, 2})); + witnesses.push_back(Point_d(std::vector<FT>{ 1,-2})); + witnesses.push_back(Point_d(std::vector<FT>{ 1,-1})); + witnesses.push_back(Point_d(std::vector<FT>{ 1, 1})); + witnesses.push_back(Point_d(std::vector<FT>{ 1, 2})); + witnesses.push_back(Point_d(std::vector<FT>{ 2,-1})); + witnesses.push_back(Point_d(std::vector<FT>{ 2, 1})); + + WitnessComplex witness_complex(landmarks, + witnesses); + witness_complex.create_complex(complex, 0); + + std::cout << "complex.num_simplices() = " << complex.num_simplices() << std::endl; + BOOST_CHECK(complex.num_simplices() == 24); + + witness_complex.create_complex(relaxed_complex, 8.01); + + std::cout << "relaxed_complex.num_simplices() = " << relaxed_complex.num_simplices() << std::endl; + BOOST_CHECK(relaxed_complex.num_simplices() == 239); + + StrongWitnessComplex strong_witness_complex(landmarks, + witnesses); + + strong_witness_complex.create_complex(strong_relaxed_complex, 9.1); + + std::cout << "strong_relaxed_complex.num_simplices() = " << strong_relaxed_complex.num_simplices() << std::endl; + BOOST_CHECK(strong_relaxed_complex.num_simplices() == 239); + +} diff --git a/src/Witness_complex/test/witness_complex_points.cpp b/src/Witness_complex/test/witness_complex_points.cpp deleted file mode 100644 index d40bbf14..00000000 --- a/src/Witness_complex/test/witness_complex_points.cpp +++ /dev/null @@ -1,58 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2016 INRIA Sophia Antipolis-Méditerranée (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -#define BOOST_TEST_DYN_LINK -#define BOOST_TEST_MODULE "witness_complex_points" -#include <boost/test/unit_test.hpp> -#include <boost/mpl/list.hpp> - -#include <gudhi/Simplex_tree.h> -#include <gudhi/Witness_complex.h> -#include <gudhi/Construct_closest_landmark_table.h> -#include <gudhi/pick_n_random_points.h> - -#include <iostream> -#include <vector> - -typedef std::vector<double> Point; -typedef std::vector< Vertex_handle > typeVectorVertex; -typedef Gudhi::Simplex_tree<> Simplex_tree; -typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex; - -BOOST_AUTO_TEST_CASE(witness_complex_points) { - std::vector< typeVectorVertex > knn; - std::vector< Point > points, landmarks; - // Add grid points as witnesses - for (double i = 0; i < 10; i += 1.0) - for (double j = 0; j < 10; j += 1.0) - for (double k = 0; k < 10; k += 1.0) - points.push_back(Point({i, j, k})); - - bool b_print_output = false; - // First test: random choice - Simplex_tree complex1; - Gudhi::subsampling::pick_n_random_points(points, 100, std::back_inserter(landmarks)); - Gudhi::witness_complex::construct_closest_landmark_table(points, landmarks, knn); - assert(!knn.empty()); - WitnessComplex witnessComplex1(knn, 100, 3, complex1); - BOOST_CHECK(witnessComplex1.is_witness_complex(knn, b_print_output)); -} diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index 1a2cb6ba..46c43a90 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -358,7 +358,9 @@ make \endverbatim * @example Skeleton_blocker/Skeleton_blocker_link.cpp * @example Tangential_complex/example_basic.cpp * @example Tangential_complex/example_with_perturb.cpp - * @example Witness_complex/witness_complex_from_file.cpp - * @example Witness_complex/witness_complex_sphere.cpp + * @example Witness_complex/example_strong_witness_persistence.cpp + * @example Witness_complex/example_witness_complex_off.cpp + * @example Witness_complex/example_witness_complex_persistence.cpp + * @example Witness_complex/example_witness_complex_sphere.cpp */ |
