diff options
58 files changed, 4479 insertions, 911 deletions
diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index eec8c14f..b02929ab 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -228,6 +228,42 @@ language={English}, } %------------------------------------------------------------------ +@article{blockers2012, + author = {Dominique Attali and + Andr{\'e} Lieutier and + David Salinas}, + title = {Efficient Data Structure for Representing and Simplifying + Simplicial complexes in High Dimensions}, + journal = {Int. J. Comput. Geometry Appl.}, + volume = {22}, + number = {4}, + year = {2012}, + pages = {279-304}, + ee = {http://dx.doi.org/10.1142/S0218195912600060}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +%------------------------------------------------------------------ +@article{rips2012, + hal_id = {hal-00785072}, + url = {http://hal.archives-ouvertes.fr/hal-00785072}, + title = {{Vietoris-Rips Complexes also Provide Topologically Correct Reconstructions of Sampled Shapes}}, + author = {Attali, Dominique and Lieutier, Andr{\'e} and Salinas, David}, + keywords = {Shape reconstruction \sep Rips complexes \sep clique complexes \sep \v Cech complexes ; homotopy equivalence ; collapses ; high dimensions}, + language = {Anglais}, + affiliation = {Grenoble Images Parole Signal Automatique - GIPSA-lab , Laboratoire Jean Kuntzmann - LJK}, + pages = {448-465}, + journal = {Computational Geometry}, + volume = {46}, + number = {4, special issue }, + audience = {internationale }, + doi = {10.1016/j.comgeo.2012.02.009 }, + year = {2012}, + pdf = {http://hal.archives-ouvertes.fr/hal-00785072/PDF/2012-cgta-Rips.pdf}, +} + + +%------------------------------------------------------------------ @article{DBLP:journals/corr/abs-1210-1429, author = {Pawel Dlotko and Hubert Wagner}, @@ -373,6 +409,37 @@ proceedings{DBLP:conf/issac/1996, bibsource = {DBLP, http://dblp.uni-trier.de} } + +proceedings{DBLP:conf/issac/1996, + editor = {Erwin Engeler and + B. F. Caviness and + Yagati N. Lakshman}, + title = {Proceedings of the 1996 International Symposium on Symbolic + and Algebraic Computation, ISSAC '96, Zurich, Switzerland, + July 24-26, 1996}, + booktitle = {ISSAC}, + publisher = {ACM}, + year = {1996}, + isbn = {0-89791-796-0}, + ee = {http://dl.acm.org/citation.cfm?id=236869}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + + +@inproceedings{socg_blockers_2011, + author = {Attali, Dominique and Lieutier, Andr{\'e} and Salinas, David}, + title = {Efficient data structure for representing and simplifying simplicial complexes in high dimensions}, + booktitle = {Proceedings of the 27th annual ACM symposium on Computational geometry}, + series = {SoCG '11}, + year = {2011}, + location = {Paris, France}, + pages = {501--509}, + numpages = {9}, + keywords = {clique complexes, data structure, edge contraction, flag complexes, high dimensions, homotopy equivalence, shape reconstruction, shape simplification, simplicial complexes, vietoris-rips complexes}, +} + + + %------------------------------------------------------------------ %MISC @@ -565,8 +632,7 @@ inproceedings{DBLP:conf/soda/1997, - -inproceedings{attali-rips_approx, +@inproceedings{attali-rips_approx, author = {Dominique Attali and Andr{\'e} Lieutier and David Salinas}, @@ -582,6 +648,8 @@ inproceedings{attali-rips_approx, + + @article{Carlsson:2008:LBS:1325290.1325300, author = {Carlsson, Gunnar and Ishkhanov, Tigran and Silva, Vin and Zomorodian, Afra}, title = {On the Local Behavior of Spaces of Natural Images}, diff --git a/scripts/generate_version.sh b/scripts/generate_version.sh index 1a8ce4ab..1a8ce4ab 100644..100755 --- a/scripts/generate_version.sh +++ b/scripts/generate_version.sh diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 04773b0a..c209a020 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -28,4 +28,5 @@ else() add_subdirectory(example/Persistent_cohomology) add_subdirectory(example/Skeleton_blocker) add_subdirectory(example/Contraction) + endif() diff --git a/src/Contraction/example/Rips_contraction.cpp b/src/Contraction/example/Rips_contraction.cpp index acfb516d..2620b04f 100644 --- a/src/Contraction/example/Rips_contraction.cpp +++ b/src/Contraction/example/Rips_contraction.cpp @@ -1,9 +1,24 @@ -/* - * Rips_contraction.cpp - * - * Created on: Nov 28, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <list> #include <boost/timer/timer.hpp> #include <iostream> @@ -48,25 +63,28 @@ void build_rips(ComplexType& complex, double offset){ complex.add_edge(*p,*q); } +int main (int argc, char *argv[]) +{ + if (argc!=3){ + std::cerr << "Usage "<<argv[0]<<" GUDHIPATH/src/data/sphere3D.off 0.1 to load the file GUDHIPATH/src/data/sphere3D.off and contract the Rips complex built with paremeter 0.2.\n"; + return -1; + } - - -void test_contraction_rips(string name_file, double offset){ boost::timer::auto_cpu_timer t; Complex complex; // load the points - Skeleton_blocker_off_reader<Complex> off_reader(name_file,complex,true); + Skeleton_blocker_off_reader<Complex> off_reader(argv[1],complex,true); if(!off_reader.is_valid()){ - std::cerr << "Unable to read file:"<<name_file<<std::endl; - return; + std::cerr << "Unable to read file:"<<argv[1]<<std::endl; + return EXIT_FAILURE; } - std::cerr << "build the Rips complex"<<std::endl; + std::cout << "build the Rips complex"<<std::endl; - build_rips(complex,offset); + build_rips(complex,atof(argv[2])); - std::cerr << "Initial complex has "<< + std::cout << "Initial complex has "<< complex.num_vertices()<<" vertices, and "<< complex.num_edges()<<" edges."<<std::endl; @@ -77,24 +95,12 @@ void test_contraction_rips(string name_file, double offset){ contraction::make_remove_popable_blockers_visitor<Profile>()); contractor.contract_edges(); - std::cerr << "Resulting complex has "<< + std::cout << "Resulting complex has "<< complex.num_vertices()<<" vertices, "<< complex.num_edges()<<"edges and "<< complex.num_blockers()<<" blockers"<<std::endl; - -} - - -int main (int argc, char *argv[]) -{ - if (argc!=3){ - std::cerr << "Usage "<<argv[0]<<" GUDHIPATH/src/data/sphere3D.off 0.1 to load the file GUDHIPATH/src/data/sphere3D.off and contract the Rips complex built with paremeter 0.2.\n"; - return -1; - } - - std::string name_file(argv[1]); - test_contraction_rips(name_file,atof(argv[2])); + return EXIT_SUCCESS; } diff --git a/src/Contraction/include/gudhi/Contraction/Edge_profile.h b/src/Contraction/include/gudhi/Contraction/Edge_profile.h index 7005f02c..f90bd71a 100644 --- a/src/Contraction/include/gudhi/Contraction/Edge_profile.h +++ b/src/Contraction/include/gudhi/Contraction/Edge_profile.h @@ -1,9 +1,24 @@ -/* - * Edge_profile.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_EDGE_PROFILE_H_ #define GUDHI_EDGE_PROFILE_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h b/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h index ef670234..8ff19f20 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h @@ -1,9 +1,24 @@ -/* - * Contraction_visitor.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_CONTRACTION_VISITOR_H_ #define GUDHI_CONTRACTION_VISITOR_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h b/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h index e183a74d..60ef3b5f 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h @@ -1,9 +1,24 @@ -/* - * Cost_policy.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_COST_POLICY_H_ #define GUDHI_COST_POLICY_H_ @@ -14,6 +29,9 @@ namespace Gudhi{ namespace contraction { +/** +*@brief Policy to specify the cost of contracting an edge. +*/ template< typename EdgeProfile> class Cost_policy{ public: typedef typename EdgeProfile::Point Point; diff --git a/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h b/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h index b0202fae..de473944 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h @@ -1,9 +1,24 @@ -/* - * Dummy_valid_contraction.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_DUMMY_VALID_CONTRACTION_H_ #define GUDHI_DUMMY_VALID_CONTRACTION_H_ @@ -16,7 +31,9 @@ namespace contraction { - + /** + *@brief Policy that accept all edge contraction. + */ template< typename EdgeProfile> class Dummy_valid_contraction : public Valid_contraction_policy<EdgeProfile>{ public: typedef typename EdgeProfile::Point Point; diff --git a/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h b/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h index 32c8768e..b22ada0d 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h @@ -1,9 +1,24 @@ -/* - * Edge_length_cost.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_EDGE_LENGTH_COST_H_ #define GUDHI_EDGE_LENGTH_COST_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h b/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h index cad87e3e..93abac35 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h +++ b/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h @@ -1,10 +1,24 @@ -/* - * First_vertex_placement.h - * - * Created on: Feb 20, 2014 - * Author: David Salinas - * Copyright 2013 INRIA. All rights reserved - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_FIRST_VERTEX_PLACEMENT_H_ #define GUDHI_FIRST_VERTEX_PLACEMENT_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h index 77fb6f95..31c02e43 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h @@ -1,9 +1,24 @@ -/* - * Link_condition_valid_contraction.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_LINK_CONDITION_VALID_CONTRACTION_H_ #define GUDHI_LINK_CONDITION_VALID_CONTRACTION_H_ @@ -17,7 +32,9 @@ namespace Gudhi{ namespace contraction { - + /** + *@brief Policy that only accept edges verifying the link condition (and therefore whose contraction preserving homotopy type). + */ template< typename EdgeProfile> class Link_condition_valid_contraction : public Valid_contraction_policy<EdgeProfile>{ public: typedef typename EdgeProfile::Edge_handle Edge_handle; diff --git a/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h b/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h index 872c6d80..30f0a570 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h @@ -1,9 +1,24 @@ -/* - * Middle_placement.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_MIDDLE_PLACEMENT_H_ #define GUDHI_MIDDLE_PLACEMENT_H_ @@ -15,6 +30,8 @@ namespace Gudhi{ namespace contraction { + + template< typename EdgeProfile> class Middle_placement : public Placement_policy<EdgeProfile>{ public: diff --git a/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h b/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h index 78595f3b..37b36dfe 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h @@ -1,9 +1,24 @@ -/* - * Placement_policy.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_PLACEMENT_POLICY_H_ #define GUDHI_PLACEMENT_POLICY_H_ @@ -13,6 +28,10 @@ namespace Gudhi { namespace contraction { + + /** + *@brief Policy to specify where the merged point had to be placed after an edge contraction. + */ template< typename EdgeProfile> class Placement_policy{ public: typedef typename EdgeProfile::Point Point; diff --git a/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h b/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h index f6016e2d..a053042b 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h @@ -1,15 +1,34 @@ -/* - * Valid_contraction_policy.h - * - * Created on: Feb 13, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_VALID_CONTRACTION_POLICY_H_ #define GUDHI_VALID_CONTRACTION_POLICY_H_ namespace Gudhi { namespace contraction { + + /** + *@brief Policy to specify if an edge contraction is valid or not. + */ template< typename EdgeProfile> class Valid_contraction_policy{ public: typedef typename EdgeProfile::Point Point; diff --git a/src/Contraction/include/gudhi/Edge_contraction.h b/src/Contraction/include/gudhi/Edge_contraction.h index 049e3d81..6b6dab69 100644 --- a/src/Contraction/include/gudhi/Edge_contraction.h +++ b/src/Contraction/include/gudhi/Edge_contraction.h @@ -1,8 +1,23 @@ -/* - * Edge_contraction.h +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. * - * Created on: Nov 28, 2014 - * Author: dsalinas + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_EDGE_CONTRACTION_H_ diff --git a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h index 4dc7952c..56f4891f 100644 --- a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h +++ b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h @@ -1,8 +1,23 @@ -/* - * Skeleton_blocker_contractor.h +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. * - * Created on: Feb 11, 2014 - * Author: dsalinas + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKER_CONTRACTOR_H_ @@ -13,7 +28,6 @@ // todo remove the queue to be independent from cgald #include "gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h" -//#include <CGAL/Modifiable_priority_queue.h> #include <list> @@ -53,7 +67,9 @@ Valid_contraction_policy<Profile>* make_link_valid_contraction(){ } -// visitor that remove popable blockers after an edge contraction +/** +*@brief Visitor to remove popable blockers after an edge contraction. +*/ template <class Profile> class Contraction_visitor_remove_popable : public Contraction_visitor<Profile>{ public: @@ -101,9 +117,9 @@ Contraction_visitor<Profile>* make_remove_popable_blockers_visitor(){ *@class Skeleton_blocker_contractor *@brief Class that allows to contract iteratively edges of a simplicial complex. * - * @details Basically, the simplification algorithm consists in iteratively picking the + * @details The simplification algorithm consists in iteratively picking the * edge with lowest cost and performing an edge contraction if the contraction is valid. - * This class is policy based (and much inspired from the edge collapse package of CGAL). + * This class is policy based (and much inspired from the edge collapse package of CGAL http://doc.cgal.org/latest/Surface_mesh_simplification/index.html). * * Policies that can be changed are : * - the cost policy : how much cost an edge contraction @@ -111,7 +127,6 @@ Contraction_visitor<Profile>* make_remove_popable_blockers_visitor(){ * - the valid contraction policy : is the contraction valid. For instance, it can be * a topological condition (link condition) or a geometrical condition (normals messed up). * - * TODO expliquer la pile */ template< class GeometricSimplifiableComplex, diff --git a/src/Contraction/test/TestContraction.cpp b/src/Contraction/test/TestContraction.cpp index 1090c054..872f24a0 100644 --- a/src/Contraction/test/TestContraction.cpp +++ b/src/Contraction/test/TestContraction.cpp @@ -1,9 +1,24 @@ -/* - * TestContraction.cxx - * - * Created on: Feb 11, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <ctime> #include <list> @@ -12,7 +27,6 @@ //#include "Skeleton_blocker/Simplex.h" #include "gudhi/Skeleton_blocker_contractor.h" #include "gudhi/Utils.h" -#include "gudhi/iofile.h" #include "gudhi/Test.h" #include "gudhi/Skeleton_blocker_geometric_complex.h" //#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> diff --git a/src/Doxyfile b/src/Doxyfile index 3493d7c6..420824f4 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -831,7 +831,8 @@ EXAMPLE_RECURSIVE = NO # that contain images that are to be included in the documentation (see the # \image command). -IMAGE_PATH = doc/ +IMAGE_PATH = Skeleton_blocker/doc/ \ + common/doc/ # The INPUT_FILTER tag can be used to specify a program that doxygen should # invoke to filter for each input file. Doxygen will invoke the filter program @@ -1895,7 +1896,7 @@ ENABLE_PREPROCESSING = YES # The default value is: NO. # This tag requires that the tag ENABLE_PREPROCESSING is set to YES. -MACRO_EXPANSION = NO +MACRO_EXPANSION = YES # If the EXPAND_ONLY_PREDEF and MACRO_EXPANSION tags are both set to YES then # the macro expansion is limited to the macros specified with the PREDEFINED and @@ -1903,7 +1904,7 @@ MACRO_EXPANSION = NO # The default value is: NO. # This tag requires that the tag ENABLE_PREPROCESSING is set to YES. -EXPAND_ONLY_PREDEF = NO +EXPAND_ONLY_PREDEF = YES # If the SEARCH_INCLUDES tag is set to YES the includes files in the # INCLUDE_PATH will be searched if a #include is found. @@ -1935,7 +1936,7 @@ INCLUDE_FILE_PATTERNS = # recursively expanded use the := operator instead of the = operator. # This tag requires that the tag ENABLE_PREPROCESSING is set to YES. -PREDEFINED = +PREDEFINED = protected=private # If the MACRO_EXPANSION and EXPAND_ONLY_PREDEF tags are set to YES then this # tag can be used to specify a list of macro names that should be expanded. The @@ -2018,7 +2019,7 @@ PERL_PATH = /usr/bin/perl # powerful graphs. # The default value is: YES. -CLASS_DIAGRAMS = YES +CLASS_DIAGRAMS = NO # You can define message sequence charts within doxygen comments using the \msc # command. Doxygen will then run the mscgen tool (see: @@ -2091,7 +2092,7 @@ DOT_FONTPATH = # The default value is: YES. # This tag requires that the tag HAVE_DOT is set to YES. -CLASS_GRAPH = YES +CLASS_GRAPH = NO # If the COLLABORATION_GRAPH tag is set to YES then doxygen will generate a # graph for each documented class showing the direct and indirect implementation @@ -2100,7 +2101,7 @@ CLASS_GRAPH = YES # The default value is: YES. # This tag requires that the tag HAVE_DOT is set to YES. -COLLABORATION_GRAPH = YES +COLLABORATION_GRAPH = NO # If the GROUP_GRAPHS tag is set to YES then doxygen will generate a graph for # groups, showing the direct groups dependencies. @@ -2165,7 +2166,7 @@ INCLUDED_BY_GRAPH = YES # The default value is: NO. # This tag requires that the tag HAVE_DOT is set to YES. -CALL_GRAPH = YES +CALL_GRAPH = NO # If the CALLER_GRAPH tag is set to YES then doxygen will generate a caller # dependency graph for every global function or class method. @@ -2176,7 +2177,7 @@ CALL_GRAPH = YES # The default value is: NO. # This tag requires that the tag HAVE_DOT is set to YES. -CALLER_GRAPH = YES +CALLER_GRAPH = NO # If the GRAPHICAL_HIERARCHY tag is set to YES then doxygen will graphical # hierarchy of all classes instead of a textual one. diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index f638a0fb..27d64b8a 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -42,15 +42,22 @@ namespace Gudhi { namespace persistent_cohomology { -/** \defgroup persistent_cohomology Persistent Cohomology Package - * - * Computation of persistent cohomology using the algorithm of - * \cite DBLP:journals/dcg/SilvaMV11 and \cite DBLP:journals/corr/abs-1208-5018 - * and the Compressed Annotation Matrix - * implementation of \cite DBLP:conf/esa/BoissonnatDM13 - * - * - * +/** \defgroup persistent_cohomology Persistent Cohomology + * + + Computation of persistent cohomology using the algorithm of + \cite DBLP:journals/dcg/SilvaMV11 and \cite DBLP:journals/corr/abs-1208-5018 + and the Compressed Annotation Matrix + implementation of \cite DBLP:conf/esa/BoissonnatDM13 + + The theory of homology consists in attaching to a topological space a sequence of + (homology) groups, + capturing global topological features + like connected components, holes, cavities, etc. Persistent homology studies the evolution + -- birth, life and death -- of + these features when the topological space is changing. Consequently, the theory is essentially + composed of three elements: + topological spaces, their homology groups and an evolution scheme. The theory of homology consists in attaching to a topological space a sequence of (homology) groups, @@ -154,18 +161,19 @@ namespace persistent_cohomology { by increasing filtration values (breaking ties so as a simplex appears after its subsimplices of same filtration value) provides an indexing scheme. +\section Examples + We provide several example files: run these examples with -h for details on their use, and read the README file. + +\li <CODE>rips_persistence.cpp</CODE> computes the Rips complex of a point cloud and its persistence diagram. +\li <CODE>rips_multifield_persistence.cpp</CODE> computes the Rips complex of a point cloud and its persistence diagram +with a family of field coefficients. - <DT>Implementations:</DT> - We use the <EM>Compressed Annotation Matrix</EM> of \cite DBLP:conf/esa/BoissonnatDM13 to - implement the - persistent cohomology algorithm of \cite DBLP:journals/dcg/SilvaMV11 - and \cite DBLP:conf/compgeom/DeyFW14 for persistence in the class Persistent_cohomology. +\li <CODE>performance_rips_persistence.cpp</CODE> provides timings for the construction of the Rips complex on a set of +points sampling a Klein bottle in \f$\mathbb{R}^5\f$ with a simplex tree, its conversion to a +Hasse diagram and the computation of persistent homology and multi-field persistent homology for the +different representations. - The coefficient fields available as models of CoefficientField are Field_Zp - for \f$\mathbb{Z}_p\f$ (for any prime p) and Multi_field for the multi-field persistence algorithm - -- computing persistence simultaneously in various coefficient fields -- described - in \cite boissonnat:hal-00922572. \author ClĂ©ment Maria @@ -294,11 +302,11 @@ class Persistent_cohomology { public: /** \brief Initializes the coefficient field.*/ - void init_coefficients(uint8_t charac) { + void init_coefficients(uint16_t charac) { coeff_field_.init(charac); } /** \brief Initializes the coefficient field for multi-field persistent homology.*/ - void init_coefficients(uint8_t charac_min, uint8_t charac_max) { + void init_coefficients(uint16_t charac_min, uint16_t charac_max) { coeff_field_.init(charac_min, charac_max); } @@ -460,7 +468,7 @@ class Persistent_cohomology { if (w_y != coeff_field_.additive_identity()) { // if != 0 result_insert_a_ds = map_a_ds.insert(std::pair<Simplex_key, Arith_element>(cell_ref.key_, w_y)); if (!(result_insert_a_ds.second)) { // if cell_ref.key_ already a Key in map_a_ds - coeff_field_.plus_equal(result_insert_a_ds.first->second, w_y); + result_insert_a_ds.first->second = coeff_field_.plus_equal(result_insert_a_ds.first->second, w_y); if (result_insert_a_ds.first->second == coeff_field_.additive_identity()) { map_a_ds.erase(result_insert_a_ds.first); } @@ -632,16 +640,14 @@ class Persistent_cohomology { Cell * cell_tmp = cell_pool_->construct(Cell(other_it->first // key , coeff_field_.additive_identity(), &target)); - coeff_field_.plus_times_equal(cell_tmp->coefficient_, - other_it->second, w); + cell_tmp->coefficient_ = coeff_field_.plus_times_equal(cell_tmp->coefficient_, other_it->second, w); target.col_.insert(target_it, *cell_tmp); ++other_it; } else { // it1->key == it2->key // target_it->coefficient_ <- target_it->coefficient_ + other_it->second * w - coeff_field_.plus_times_equal(target_it->coefficient_, - other_it->second, w); + target_it->coefficient_ = coeff_field_.plus_times_equal(target_it->coefficient_, other_it->second, w); if (target_it->coefficient_ == coeff_field_.additive_identity()) { auto tmp_it = target_it; ++target_it; @@ -660,7 +666,7 @@ class Persistent_cohomology { } while (other_it != other.end()) { Cell * cell_tmp = cell_pool_->construct(Cell(other_it->first, coeff_field_.additive_identity(), &target)); - coeff_field_.plus_times_equal(cell_tmp->coefficient_, other_it->second, w); + cell_tmp->coefficient_ = coeff_field_.plus_times_equal(cell_tmp->coefficient_, other_it->second, w); target.col_.insert(target.col_.end(), *cell_tmp); ++other_it; diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h index 49883a4a..419bd2eb 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h @@ -46,7 +46,7 @@ class Field_Zp { add_id_all(0) { } - void init(uint8_t charac) { + void init(uint16_t charac) { assert(charac != 0); // division by zero Prime = charac; inverse_.clear(); @@ -61,29 +61,26 @@ class Field_Zp { } /** Set x <- x + w * y*/ - void plus_times_equal(Element & x, Element y, Element w) { + Element plus_times_equal(const Element& x, const Element& y, const Element& w) { assert(Prime != 0); // division by zero - x = (x + w * y) % Prime; + Element result = (x + w * y) % Prime; + if (result < 0) + result += Prime; + return result; } // operator= defined on Element /** Returns y * w */ - Element times(Element y, int w) { - assert(Prime != 0); // division by zero - Element res = (y * w) % Prime; - if (res < 0) - return res + Prime; - else - return res; + Element times(const Element& y, const Element& w) { + return plus_times_equal(0, y, (Element)w); } void clear_coefficient(Element x) { } - void plus_equal(Element & x, Element y) { - assert(Prime != 0); // division by zero - x = ((x + y) % Prime); + Element plus_equal(const Element& x, const Element& y) { + return plus_times_equal(x, y, (Element)1); } /** \brief Returns the additive idendity \f$0_{\Bbbk}\f$ of the field.*/ @@ -107,12 +104,12 @@ class Field_Zp { } /** \brief Returns the characteristic \f$p\f$ of the field.*/ - const uint8_t& characteristic() const { + const uint16_t& characteristic() const { return Prime; } private: - uint8_t Prime; + uint16_t Prime; /** Property map Element -> Element, which associate to an element its inverse in the field.*/ std::vector<Element> inverse_; const Element mult_id_all; diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h index 306877e7..91937c65 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h @@ -52,7 +52,7 @@ class Multi_field { /* Initialize the multi-field. The generation of prime numbers might fail with * a very small probability.*/ - void init(uint8_t min_prime, uint8_t max_prime) { + void init(uint16_t min_prime, uint16_t max_prime) { if (max_prime < 2) { std::cerr << "There is no prime less than " << max_prime << std::endl; } @@ -61,7 +61,7 @@ class Multi_field { << std::endl; } // fill the list of prime numbers - uint8_t curr_prime = min_prime; + uint16_t curr_prime = min_prime; mpz_t tmp_prime; mpz_init_set_ui(tmp_prime, min_prime); // test if min_prime is prime @@ -132,18 +132,12 @@ class Multi_field { } /** Returns y * w */ - Element times(const Element& y, int w) { - assert(prod_characteristics_ != 0); // division by zero - Element tmp = (y * w) % prod_characteristics_; - if (tmp < 0) - return prod_characteristics_ + tmp; - return tmp; + Element times(const Element& y, const Element& w) { + return plus_times_equal(0, y, w); } - void plus_equal(Element & x, const Element& y) { - assert(prod_characteristics_ != 0); // division by zero - x += y; - x %= prod_characteristics_; + Element plus_equal(const Element& x, const Element& y) { + return plus_times_equal(x, y, (Element)1); } /** \brief Returns the characteristic \f$p\f$ of the field.*/ @@ -172,14 +166,17 @@ class Multi_field { } /** Set x <- x + w * y*/ - void plus_times_equal(Element & x, const Element& y, const Element& w) { + Element plus_times_equal(const Element& x, const Element& y, const Element& w) { assert(prod_characteristics_ != 0); // division by zero - x = (x + w * y) % prod_characteristics_; + Element result = (x + w * y) % prod_characteristics_; + if (result < 0) + result += prod_characteristics_; + return result; } Element prod_characteristics_; // product of characteristics of the fields // represented by the multi-field class - std::vector<uint8_t> primes_; // all the characteristics of the fields + std::vector<uint16_t> primes_; // all the characteristics of the fields std::vector<Element> Uvect_; Element mult_id_all; const Element add_id_all; diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index db7ad2b8..12be6e5d 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -38,7 +38,7 @@ namespace Gudhi { -/** \defgroup simplex_tree Filtered Complexes Package +/** \defgroup simplex_tree Filtered Complexes * * A simplicial complex \f$\mathbf{K}\f$ * on a set of vertices \f$V = \{1, \cdots ,|V|\}\f$ is a collection of simplices diff --git a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h index 1fa9dc06..c0386590 100644 --- a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h +++ b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h @@ -16,17 +16,15 @@ namespace skbl { -/** \brief Concept that must be passed to - * the template class Skeleton_blockers_complex - * +/** \brief Concept for the template class passed for Skeleton_blocker_complex. + * Most importantly, it contains the nodes for vertices and edges + * (Graph_vertex and Graph_edge) that are stored in the simplicial + * complex. The user can redefine these classes to attach + * additional information to vertices and edges. */ struct SkeletonBlockerDS { /** - * @todo faire un default value pour les vertex_handle - */ - - /** * @brief index that allows to find the vertex in the boost graph */ typedef int boost_vertex_handle; diff --git a/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h b/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h index 23edaaef..fad680d0 100644 --- a/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h +++ b/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h @@ -9,10 +9,15 @@ #ifndef GUDHI_SKELETONBLOCKERGEOMETRICDS_H_ #define GUDHI_SKELETONBLOCKERGEOMETRICDS_H_ -/** \brief Concept that must be passed to - * the template class Skeleton_blocker_geometric_complex - * +/** + * \brief Concept for template class of Skeleton_blocker_geometric_complex . + * It must specify a GeometryTrait which contains a Point definition. + * + * Graph_vertex must specify how to access to a point. + * Graph_edge must specify how to access to an index. + * */ + //todo the index is just for contraction, to remove template<typename GeometryTrait> struct SkeletonBlockerGeometricDS : public SkeletonBlockerDS { @@ -35,11 +40,11 @@ struct SkeletonBlockerGeometricDS : public SkeletonBlockerDS /** * @brief Access to the point. */ - Point& point(){ return point_; } + Point& point(); /** * @brief Access to the point. */ - const Point& point() const { return point_; } + const Point& point(); }; /** diff --git a/src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h b/src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h deleted file mode 100644 index 5a80bc8d..00000000 --- a/src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h +++ /dev/null @@ -1,156 +0,0 @@ - -/*! \mainpage Skeleton blockers data-structure - -\author David Salinas - -\section Introduction -The Skeleton-blocker data-structure had been introduced in the two papers -\cite skbl_socg2011 \cite skbl_ijcga2012. -It proposes a light encoding for simplicial complexes by storing only an *implicit* representation of its -simplices. -Intuitively, it just stores the 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that -is very small in practice (see next section for a formal definition). -This data-structure handles every classical operations used for simplicial complexes such as - as simplex enumeration or simplex removal but operations that are particularly efficient - are operations that do not require simplex enumeration such as edge iteration, link computation or simplex contraction. - - -\todo{image wont include} - -\section Definitions - -We recall briefly classical definitions of simplicial complexes \cite Munkres. -An abstract simplex is a finite non-empty set and its dimension is its number of elements minus 1. -Whenever \f$\tau \subset \sigma\f$ and \f$\tau \neq \emptyset \f$, \f$ \tau \f$ is called a face of -\f$ \sigma\f$ and \f$ \sigma\f$ is called a coface of \f$ \tau \f$ . Furthermore, -when \f$ \tau \neq \sigma\f$ we say that \f$ \tau\f$ is a proper-face of \f$ \sigma\f$. -An abstract simplicial complex is a set of simplices that contains all the faces of its simplices. -The 1-skeleton of a simplicial complex (or its graph) consists of its elements of dimension lower than 2. - - -\image latex "images/ds_representation.eps" "My application" width=10cm - - -To encode, a simplicial complex, one can encodes all its simplices. -In case when this number gets too large, -a lighter and implicit version consists of encoding only its graph plus some elements called missing faces or blockers. -A blocker is a simplex of dimension greater than 1 -that does not belong to the complex but whose all proper faces does. - - -Remark that for a clique complex (i.e. a simplicial complex whose simplices are cliques of its graph), the set of blockers -is empty and the data-structure is then particularly sparse. -One famous example of clique-complex is the Rips complex which is intensively used -in topological data-analysis. -In practice, the set of blockers of a simplicial complex -remains also small when simplifying a Rips complex with edge contractions -but also for most of the simplicial complexes used in topological data-analysis such as Delaunay, Cech or Witness complexes. -For instance, the numbers of blockers is depicted for a random 3 dimensional sphere embedded into \f$R^4\f$ -in figure X. - - -\image latex "images/blockers_curve.eps" "My application" width=10cm - - - - -\section API - -\subsection Overview - -Four classes define a simplicial complex namely : - -\li <Code>Skeleton_blocker_complex</Code> : a simplicial complex with basic operations such as vertex/edge/simplex enumeration and construction -\li <Code>Skeleton_blocker_link_complex</Code> : the link of a simplex in a parent complex. It is represented as a sub complex -of the parent complex -\li <Code>Skeleton_blocker_simplifiable_complex</Code> : a simplicial complex with simplification operations such as edge contraction or simplex collapse -\li <Code>Skeleton_blocker_geometric_complex</Code> : a simplicial complex who has access to geometric points in \f$R^d\f$ - -The two last classes are derived classes from the <Code>Skeleton_blocker_complex</Code> class. The class <Code>Skeleton_blocker_link_complex</Code> inheritates from a template passed parameter -that may be either <Code>Skeleton_blocker_complex</Code> or <Code>Skeleton_blocker_geometric_complex</Code> (a link may store points coordinates or not). - -\todo{include links} - -\subsection Visitor - -The class <Code>Skeleton_blocker_complex</Code> has a visitor that is called when usual operations such as adding an edge or remove a vertex are called. -You may want to use this visitor to compute statistics or to update another data-structure (for instance this visitor is heavily used in the -<Code>Contraction</Code> package). - - - -\section Example - - -\subsection s Iterating through vertices, edges, blockers and simplices - -Iteration through vertices, edges, simplices or blockers is straightforward with c++11 for range loops. -Note that simplex iteration with this implicit data-structure just takes -a few more time compared to iteration via an explicit representation -such as the Simplex Tree. The following example computes the Euler Characteristic -of a simplicial complex. - - \code{.cpp} - typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; - typedef Complex::Vertex_handle Vertex_handle; - typedef Complex::Simplex_handle Simplex; - - const int n = 15; - - // build a full complex with 10 vertices and 2^n-1 simplices - Complex complex; - for(int i=0;i<n;i++) - complex.add_vertex(); - for(int i=0;i<n;i++) - for(int j=0;j<i;j++) - //note that add_edge adds the edge and all its cofaces - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - - // this is just to illustrate iterators, to count number of vertices - // or edges, complex.num_vertices() and complex.num_edges() are - // more appropriated! - unsigned num_vertices = 0; - for(auto v : complex.vertex_range()){ - ++num_vertices; - } - - unsigned num_edges = 0; - for(auto e : complex.edge_range()) - ++num_edges; - - unsigned euler = 0; - unsigned num_simplices = 0; - // we use a reference to a simplex instead of a copy - // value here because a simplex is a set of integers - // and copying it cost time - for(const Simplex & s : complex.simplex_range()){ - ++num_simplices; - if(s.dimension()%2 == 0) - euler += 1; - else - euler -= 1; - } - std::cout << "Saw "<<num_vertices<<" vertices, "<<num_edges<<" edges and "<<num_simplices<<" simplices"<<std::endl; - std::cout << "The Euler Characteristic is "<<euler<<std::endl; - \endcode - - -\verbatim -./SkeletonBlockerIteration -Saw 15 vertices, 105 edges and 32767 simplices -The Euler Characteristic is 1 - 0.537302s wall, 0.530000s user + 0.000000s system = 0.530000s CPU (98.6%) -\endverbatim - - - -\subsection Acknowledgements -The author wishes to thank Dominique Attali and AndrĂ© Lieutier for -their collaboration to write the two initial papers about this data-structure - and also Dominique for leaving him use a prototype. - - -\copyright GNU General Public License v3. -\verbatim Contact: David Salinas, david.salinas@inria.fr \endverbatim - -*/ diff --git a/src/Skeleton_blocker/doc/blocker_curve.svg b/src/Skeleton_blocker/doc/blocker_curve.svg new file mode 100644 index 00000000..0094a379 --- /dev/null +++ b/src/Skeleton_blocker/doc/blocker_curve.svg @@ -0,0 +1,2177 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Created with Inkscape (http://www.inkscape.org/) --> + +<svg + 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:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="744.09448819" + height="1052.3622047" + id="svg5493" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="New document 8"> + <defs + id="defs5495"> + <clipPath + id="clipPath6477" + clipPathUnits="userSpaceOnUse"> + <path + id="path6479" + d="m 2963.67,3669.26 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath6465" + clipPathUnits="userSpaceOnUse"> + <path + id="path6467" + d="m 2762.07,3669.26 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath6427" + clipPathUnits="userSpaceOnUse"> + <path + id="path6429" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6409" + clipPathUnits="userSpaceOnUse"> + <path + id="path6411" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" /> + </clipPath> + <clipPath + id="clipPath6399" + clipPathUnits="userSpaceOnUse"> + <path + id="path6401" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6381" + clipPathUnits="userSpaceOnUse"> + <path + id="path6383" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" /> + </clipPath> + <clipPath + id="clipPath6371" + clipPathUnits="userSpaceOnUse"> + <path + id="path6373" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6353" + clipPathUnits="userSpaceOnUse"> + <path + id="path6355" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" /> + </clipPath> + <clipPath + id="clipPath6343" + clipPathUnits="userSpaceOnUse"> + <path + id="path6345" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6325" + clipPathUnits="userSpaceOnUse"> + <path + id="path6327" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" /> + </clipPath> + <clipPath + id="clipPath6315" + clipPathUnits="userSpaceOnUse"> + <path + id="path6317" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6297" + clipPathUnits="userSpaceOnUse"> + <path + id="path6299" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" /> + </clipPath> + <clipPath + id="clipPath6287" + clipPathUnits="userSpaceOnUse"> + <path + id="path6289" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6269" + clipPathUnits="userSpaceOnUse"> + <path + id="path6271" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" /> + </clipPath> + <clipPath + id="clipPath6259" + clipPathUnits="userSpaceOnUse"> + <path + id="path6261" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6241" + clipPathUnits="userSpaceOnUse"> + <path + id="path6243" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" /> + </clipPath> + <clipPath + id="clipPath6231" + clipPathUnits="userSpaceOnUse"> + <path + id="path6233" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6211" + clipPathUnits="userSpaceOnUse"> + <path + id="path6213" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6189" + clipPathUnits="userSpaceOnUse"> + <path + id="path6191" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6169" + clipPathUnits="userSpaceOnUse"> + <path + id="path6171" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6149" + clipPathUnits="userSpaceOnUse"> + <path + id="path6151" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6129" + clipPathUnits="userSpaceOnUse"> + <path + id="path6131" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6109" + clipPathUnits="userSpaceOnUse"> + <path + id="path6111" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6089" + clipPathUnits="userSpaceOnUse"> + <path + id="path6091" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath6077" + clipPathUnits="userSpaceOnUse"> + <path + id="path6079" + d="m 5151,431 33,0 0,35 -33,0 0,-35 z" /> + </clipPath> + <clipPath + id="clipPath6065" + clipPathUnits="userSpaceOnUse"> + <path + id="path6067" + d="m 4705,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath6053" + clipPathUnits="userSpaceOnUse"> + <path + id="path6055" + d="m 4258,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath6041" + clipPathUnits="userSpaceOnUse"> + <path + id="path6043" + d="m 3812,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath6029" + clipPathUnits="userSpaceOnUse"> + <path + id="path6031" + d="m 3365,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath6017" + clipPathUnits="userSpaceOnUse"> + <path + id="path6019" + d="m 2919,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath6005" + clipPathUnits="userSpaceOnUse"> + <path + id="path6007" + d="m 2473,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath5993" + clipPathUnits="userSpaceOnUse"> + <path + id="path5995" + d="m 2026,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath5981" + clipPathUnits="userSpaceOnUse"> + <path + id="path5983" + d="m 1580,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath5969" + clipPathUnits="userSpaceOnUse"> + <path + id="path5971" + d="m 1133,431 66,0 0,34 -66,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath5957" + clipPathUnits="userSpaceOnUse"> + <path + id="path5959" + d="m 720,431 42,0 0,34 -42,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath5947" + clipPathUnits="userSpaceOnUse"> + <path + id="path5949" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath5935" + clipPathUnits="userSpaceOnUse"> + <path + id="path5937" + d="m 5151,539 33,0 0,66 -33,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5923" + clipPathUnits="userSpaceOnUse"> + <path + id="path5925" + d="m 4705.12,525.621 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5911" + clipPathUnits="userSpaceOnUse"> + <path + id="path5913" + d="m 4258.71,513.121 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5899" + clipPathUnits="userSpaceOnUse"> + <path + id="path5901" + d="m 3812.3,499.84 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5887" + clipPathUnits="userSpaceOnUse"> + <path + id="path5889" + d="m 3365.9,482.852 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5875" + clipPathUnits="userSpaceOnUse"> + <path + id="path5877" + d="m 2919.49,469.379 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5863" + clipPathUnits="userSpaceOnUse"> + <path + id="path5865" + d="m 2473,454 66,0 0,66 -66,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5851" + clipPathUnits="userSpaceOnUse"> + <path + id="path5853" + d="m 2026.72,439.648 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5839" + clipPathUnits="userSpaceOnUse"> + <path + id="path5841" + d="m 1580,431 66,0 0,60 -66,0 0,-60 z" /> + </clipPath> + <clipPath + id="clipPath5827" + clipPathUnits="userSpaceOnUse"> + <path + id="path5829" + d="m 1133,431 66,0 0,47 -66,0 0,-47 z" /> + </clipPath> + <clipPath + id="clipPath5815" + clipPathUnits="userSpaceOnUse"> + <path + id="path5817" + d="m 720,431 42,0 0,34 -42,0 0,-34 z" /> + </clipPath> + <clipPath + id="clipPath5805" + clipPathUnits="userSpaceOnUse"> + <path + id="path5807" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath5793" + clipPathUnits="userSpaceOnUse"> + <path + id="path5795" + d="m 5151,3499 33,0 0,66 -33,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5781" + clipPathUnits="userSpaceOnUse"> + <path + id="path5783" + d="m 4705.12,3186.68 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5769" + clipPathUnits="userSpaceOnUse"> + <path + id="path5771" + d="m 4258.71,2878.83 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5757" + clipPathUnits="userSpaceOnUse"> + <path + id="path5759" + d="m 3812.3,2568.4 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5745" + clipPathUnits="userSpaceOnUse"> + <path + id="path5747" + d="m 3365.9,2251.56 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5733" + clipPathUnits="userSpaceOnUse"> + <path + id="path5735" + d="m 2919,1940 66,0 0,66 -66,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5721" + clipPathUnits="userSpaceOnUse"> + <path + id="path5723" + d="m 2473.09,1628.36 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5709" + clipPathUnits="userSpaceOnUse"> + <path + id="path5711" + d="m 2026.72,1312.93 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5697" + clipPathUnits="userSpaceOnUse"> + <path + id="path5699" + d="m 1580,1005 66,0 0,66 -66,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5685" + clipPathUnits="userSpaceOnUse"> + <path + id="path5687" + d="m 1133.91,696.801 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5673" + clipPathUnits="userSpaceOnUse"> + <path + id="path5675" + d="m 720,431 42,0 0,37 -42,0 0,-37 z" /> + </clipPath> + <clipPath + id="clipPath5663" + clipPathUnits="userSpaceOnUse"> + <path + id="path5665" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + <clipPath + id="clipPath5651" + clipPathUnits="userSpaceOnUse"> + <path + id="path5653" + d="m 5151,1336 33,0 0,66 -33,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5639" + clipPathUnits="userSpaceOnUse"> + <path + id="path5641" + d="m 4705.12,1242.11 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5627" + clipPathUnits="userSpaceOnUse"> + <path + id="path5629" + d="m 4258.71,1148.95 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5615" + clipPathUnits="userSpaceOnUse"> + <path + id="path5617" + d="m 3812.3,1055.12 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5603" + clipPathUnits="userSpaceOnUse"> + <path + id="path5605" + d="m 3365.9,959.73 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5591" + clipPathUnits="userSpaceOnUse"> + <path + id="path5593" + d="m 2919.49,865.699 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5579" + clipPathUnits="userSpaceOnUse"> + <path + id="path5581" + d="m 2473.09,771.52 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5567" + clipPathUnits="userSpaceOnUse"> + <path + id="path5569" + d="m 2026.72,676.449 65,0 0,65 -65,0 0,-65 z" /> + </clipPath> + <clipPath + id="clipPath5555" + clipPathUnits="userSpaceOnUse"> + <path + id="path5557" + d="m 1580,583 66,0 0,66 -66,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5543" + clipPathUnits="userSpaceOnUse"> + <path + id="path5545" + d="m 1133,490 66,0 0,66 -66,0 0,-66 z" /> + </clipPath> + <clipPath + id="clipPath5531" + clipPathUnits="userSpaceOnUse"> + <path + id="path5533" + d="m 720,431 42,0 0,35 -42,0 0,-35 z" /> + </clipPath> + <clipPath + id="clipPath5521" + clipPathUnits="userSpaceOnUse"> + <path + id="path5523" + d="m 720,431 4464,0 0,3458 -4464,0 0,-3458 z" /> + </clipPath> + </defs> + <sodipodi:namedview + id="base" + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1.0" + inkscape:pageopacity="0.0" + inkscape:pageshadow="2" + inkscape:zoom="1.979899" + inkscape:cx="399.80267" + inkscape:cy="523.89309" + inkscape:document-units="px" + inkscape:current-layer="g5511" + showgrid="false" + inkscape:window-width="2560" + inkscape:window-height="1523" + inkscape:window-x="0" + inkscape:window-y="0" + inkscape:window-maximized="1" /> + <metadata + id="metadata5498"> + <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 + inkscape:label="Layer 1" + inkscape:groupmode="layer" + id="layer1"> + <g + transform="matrix(1.25,0,0,-1.25,15,802.36218)" + inkscape:label="ink_ext_XXXXXX" + id="g5509"> + <g + transform="scale(0.1,0.1)" + id="g5511"> + <path + id="path5513" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 0,0 5760,0 0,4320 L 0,4320 0,0 z" + inkscape:connector-curvature="0" /> + <path + id="path5515" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 720,431.988 4463.98,0 0,3456.02 -4463.98,0 0,-3456.02 z" + inkscape:connector-curvature="0" /> + <g + id="g5517"> + <g + clip-path="url(#clipPath5521)" + id="g5519"> + <path + id="path5525" + style="fill:none;stroke:#0000ff;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 728.949,432.969 437.461,89.57 446.4,93.32 446.41,93.09 446.37,95.071 446.4,94.179 446.41,94.031 446.4,95.39 446.41,93.83 446.41,93.16 446.36,94.34" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5527"> + <g + clip-path="url(#clipPath5531)" + id="g5529"> + <path + id="path5535" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 728.949,402.969 c 7.93,0 15.582,3.16 21.211,8.793 5.621,5.617 8.789,13.238 8.789,21.207 0,7.972 -3.168,15.582 -8.789,21.211 -5.629,5.621 -13.281,8.789 -21.211,8.789 -7.969,0 -15.59,-3.168 -21.25,-8.789 -5.629,-5.629 -8.75,-13.239 -8.75,-21.211 0,-7.969 3.121,-15.59 8.75,-21.207 5.66,-5.633 13.281,-8.793 21.25,-8.793" + inkscape:connector-curvature="0" /> + <path + id="path5537" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 728.949,402.969 c 7.93,0 15.582,3.16 21.211,8.793 5.621,5.617 8.789,13.238 8.789,21.207 0,7.972 -3.168,15.582 -8.789,21.211 -5.629,5.621 -13.281,8.789 -21.211,8.789 -7.969,0 -15.59,-3.168 -21.25,-8.789 -5.629,-5.629 -8.75,-13.239 -8.75,-21.211 0,-7.969 3.121,-15.59 8.75,-21.207 5.66,-5.633 13.281,-8.793 21.25,-8.793 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5539"> + <g + clip-path="url(#clipPath5543)" + id="g5541"> + <path + id="path5547" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1166.41,492.539 c 7.97,0 15.58,3.16 21.21,8.789 5.62,5.621 8.79,13.242 8.79,21.211 0,7.93 -3.17,15.582 -8.79,21.211 -5.63,5.629 -13.24,8.789 -21.21,8.789 -7.97,0 -15.59,-3.16 -21.21,-8.789 -5.63,-5.629 -8.79,-13.281 -8.79,-21.211 0,-7.969 3.16,-15.59 8.79,-21.211 5.62,-5.629 13.24,-8.789 21.21,-8.789" + inkscape:connector-curvature="0" /> + <path + id="path5549" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1166.41,492.539 c 7.97,0 15.58,3.16 21.21,8.789 5.62,5.621 8.79,13.242 8.79,21.211 0,7.93 -3.17,15.582 -8.79,21.211 -5.63,5.629 -13.24,8.789 -21.21,8.789 -7.97,0 -15.59,-3.16 -21.21,-8.789 -5.63,-5.629 -8.79,-13.281 -8.79,-21.211 0,-7.969 3.16,-15.59 8.79,-21.211 5.62,-5.629 13.24,-8.789 21.21,-8.789 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5551"> + <g + clip-path="url(#clipPath5555)" + id="g5553"> + <path + id="path5559" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1612.81,585.859 c 7.93,0 15.59,3.161 21.21,8.789 5.63,5.622 8.79,13.243 8.79,21.211 0,7.969 -3.16,15.59 -8.79,21.211 -5.62,5.629 -13.28,8.789 -21.21,8.789 -7.97,0 -15.58,-3.16 -21.21,-8.789 -5.62,-5.621 -8.79,-13.242 -8.79,-21.211 0,-7.968 3.17,-15.589 8.79,-21.211 5.63,-5.628 13.24,-8.789 21.21,-8.789" + inkscape:connector-curvature="0" /> + <path + id="path5561" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1612.81,585.859 c 7.93,0 15.59,3.161 21.21,8.789 5.63,5.622 8.79,13.243 8.79,21.211 0,7.969 -3.16,15.59 -8.79,21.211 -5.62,5.629 -13.28,8.789 -21.21,8.789 -7.97,0 -15.58,-3.16 -21.21,-8.789 -5.62,-5.621 -8.79,-13.242 -8.79,-21.211 0,-7.968 3.17,-15.589 8.79,-21.211 5.63,-5.628 13.24,-8.789 21.21,-8.789 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5563"> + <g + clip-path="url(#clipPath5567)" + id="g5565"> + <path + id="path5571" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2059.22,678.949 c 7.93,0 15.58,3.16 21.21,8.781 5.62,5.629 8.79,13.29 8.79,21.219 0,7.961 -3.17,15.582 -8.79,21.211 -5.63,5.621 -13.28,8.789 -21.21,8.789 -7.97,0 -15.63,-3.168 -21.25,-8.789 -5.63,-5.629 -8.75,-13.25 -8.75,-21.211 0,-7.929 3.12,-15.59 8.75,-21.219 5.62,-5.621 13.28,-8.781 21.25,-8.781" + inkscape:connector-curvature="0" /> + <path + id="path5573" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2059.22,678.949 c 7.93,0 15.58,3.16 21.21,8.781 5.62,5.629 8.79,13.29 8.79,21.219 0,7.961 -3.17,15.582 -8.79,21.211 -5.63,5.621 -13.28,8.789 -21.21,8.789 -7.97,0 -15.63,-3.168 -21.25,-8.789 -5.63,-5.629 -8.75,-13.25 -8.75,-21.211 0,-7.929 3.12,-15.59 8.75,-21.219 5.62,-5.621 13.28,-8.781 21.25,-8.781 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5575"> + <g + clip-path="url(#clipPath5579)" + id="g5577"> + <path + id="path5583" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2505.59,774.02 c 7.96,0 15.58,3.171 21.21,8.789 5.62,5.632 8.79,13.242 8.79,21.211 0,7.968 -3.17,15.589 -8.79,21.21 -5.63,5.629 -13.25,8.79 -21.21,8.79 -7.93,0 -15.59,-3.161 -21.21,-8.79 -5.63,-5.621 -8.79,-13.242 -8.79,-21.21 0,-7.969 3.16,-15.579 8.79,-21.211 5.62,-5.618 13.28,-8.789 21.21,-8.789" + inkscape:connector-curvature="0" /> + <path + id="path5585" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2505.59,774.02 c 7.96,0 15.58,3.171 21.21,8.789 5.62,5.632 8.79,13.242 8.79,21.211 0,7.968 -3.17,15.589 -8.79,21.21 -5.63,5.629 -13.25,8.79 -21.21,8.79 -7.93,0 -15.59,-3.161 -21.21,-8.79 -5.63,-5.621 -8.79,-13.242 -8.79,-21.21 0,-7.969 3.16,-15.579 8.79,-21.211 5.62,-5.618 13.28,-8.789 21.21,-8.789 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5587"> + <g + clip-path="url(#clipPath5591)" + id="g5589"> + <path + id="path5595" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2951.99,868.199 c 7.97,0 15.59,3.172 21.21,8.789 5.63,5.633 8.79,13.242 8.79,21.211 0,7.93 -3.16,15.59 -8.79,21.211 -5.62,5.629 -13.24,8.789 -21.21,8.789 -7.93,0 -15.58,-3.16 -21.21,-8.789 -5.62,-5.621 -8.79,-13.281 -8.79,-21.211 0,-7.969 3.17,-15.578 8.79,-21.211 5.63,-5.617 13.28,-8.789 21.21,-8.789" + inkscape:connector-curvature="0" /> + <path + id="path5597" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2951.99,868.199 c 7.97,0 15.59,3.172 21.21,8.789 5.63,5.633 8.79,13.242 8.79,21.211 0,7.93 -3.16,15.59 -8.79,21.211 -5.62,5.629 -13.24,8.789 -21.21,8.789 -7.93,0 -15.58,-3.16 -21.21,-8.789 -5.62,-5.621 -8.79,-13.281 -8.79,-21.211 0,-7.969 3.17,-15.578 8.79,-21.211 5.63,-5.617 13.28,-8.789 21.21,-8.789 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5599"> + <g + clip-path="url(#clipPath5603)" + id="g5601"> + <path + id="path5607" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3398.4,962.23 c 7.97,0 15.58,3.161 21.21,8.79 5.62,5.621 8.79,13.242 8.79,21.21 0,7.93 -3.17,15.58 -8.79,21.21 -5.63,5.62 -13.24,8.79 -21.21,8.79 -7.97,0 -15.59,-3.17 -21.21,-8.79 -5.63,-5.63 -8.79,-13.28 -8.79,-21.21 0,-7.968 3.16,-15.589 8.79,-21.21 5.62,-5.629 13.24,-8.79 21.21,-8.79" + inkscape:connector-curvature="0" /> + <path + id="path5609" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3398.4,962.23 c 7.97,0 15.58,3.161 21.21,8.79 5.62,5.621 8.79,13.242 8.79,21.21 0,7.93 -3.17,15.58 -8.79,21.21 -5.63,5.62 -13.24,8.79 -21.21,8.79 -7.97,0 -15.59,-3.17 -21.21,-8.79 -5.63,-5.63 -8.79,-13.28 -8.79,-21.21 0,-7.968 3.16,-15.589 8.79,-21.21 5.62,-5.629 13.24,-8.79 21.21,-8.79 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5611"> + <g + clip-path="url(#clipPath5615)" + id="g5613"> + <path + id="path5619" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3844.8,1057.62 c 7.97,0 15.59,3.16 21.22,8.79 5.62,5.62 8.78,13.28 8.78,21.21 0,7.97 -3.16,15.58 -8.78,21.21 -5.63,5.62 -13.25,8.79 -21.22,8.79 -7.96,0 -15.58,-3.17 -21.21,-8.79 -5.62,-5.63 -8.79,-13.24 -8.79,-21.21 0,-7.93 3.17,-15.59 8.79,-21.21 5.63,-5.63 13.25,-8.79 21.21,-8.79" + inkscape:connector-curvature="0" /> + <path + id="path5621" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3844.8,1057.62 c 7.97,0 15.59,3.16 21.22,8.79 5.62,5.62 8.78,13.28 8.78,21.21 0,7.97 -3.16,15.58 -8.78,21.21 -5.63,5.62 -13.25,8.79 -21.22,8.79 -7.96,0 -15.58,-3.17 -21.21,-8.79 -5.62,-5.63 -8.79,-13.24 -8.79,-21.21 0,-7.93 3.17,-15.59 8.79,-21.21 5.63,-5.63 13.25,-8.79 21.21,-8.79 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5623"> + <g + clip-path="url(#clipPath5627)" + id="g5625"> + <path + id="path5631" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4291.21,1151.45 c 7.93,0 15.59,3.16 21.21,8.78 5.63,5.63 8.79,13.25 8.79,21.22 0,7.93 -3.16,15.58 -8.79,21.21 -5.62,5.62 -13.28,8.79 -21.21,8.79 -7.97,0 -15.59,-3.17 -21.21,-8.79 -5.62,-5.63 -8.79,-13.28 -8.79,-21.21 0,-7.97 3.17,-15.59 8.79,-21.22 5.62,-5.62 13.24,-8.78 21.21,-8.78" + inkscape:connector-curvature="0" /> + <path + id="path5633" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4291.21,1151.45 c 7.93,0 15.59,3.16 21.21,8.78 5.63,5.63 8.79,13.25 8.79,21.22 0,7.93 -3.16,15.58 -8.79,21.21 -5.62,5.62 -13.28,8.79 -21.21,8.79 -7.97,0 -15.59,-3.17 -21.21,-8.79 -5.62,-5.63 -8.79,-13.28 -8.79,-21.21 0,-7.97 3.17,-15.59 8.79,-21.22 5.62,-5.62 13.24,-8.78 21.21,-8.78 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5635"> + <g + clip-path="url(#clipPath5639)" + id="g5637"> + <path + id="path5643" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4737.62,1244.61 c 7.93,0 15.58,3.16 21.21,8.79 5.62,5.62 8.79,13.24 8.79,21.21 0,7.93 -3.17,15.59 -8.79,21.21 -5.63,5.63 -13.28,8.79 -21.21,8.79 -7.97,0 -15.59,-3.16 -21.21,-8.79 -5.67,-5.62 -8.79,-13.28 -8.79,-21.21 0,-7.97 3.12,-15.59 8.79,-21.21 5.62,-5.63 13.24,-8.79 21.21,-8.79" + inkscape:connector-curvature="0" /> + <path + id="path5645" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4737.62,1244.61 c 7.93,0 15.58,3.16 21.21,8.79 5.62,5.62 8.79,13.24 8.79,21.21 0,7.93 -3.17,15.59 -8.79,21.21 -5.63,5.63 -13.28,8.79 -21.21,8.79 -7.97,0 -15.59,-3.16 -21.21,-8.79 -5.67,-5.62 -8.79,-13.28 -8.79,-21.21 0,-7.97 3.12,-15.59 8.79,-21.21 5.62,-5.63 13.24,-8.79 21.21,-8.79 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5647"> + <g + clip-path="url(#clipPath5651)" + id="g5649"> + <path + id="path5655" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 5183.98,1338.95 c 7.97,0 15.59,3.16 21.22,8.78 5.62,5.63 8.78,13.29 8.78,21.22 0,7.96 -3.16,15.62 -8.78,21.25 -5.63,5.62 -13.25,8.75 -21.22,8.75 -7.93,0 -15.58,-3.13 -21.21,-8.75 -5.62,-5.63 -8.79,-13.29 -8.79,-21.25 0,-7.93 3.17,-15.59 8.79,-21.22 5.63,-5.62 13.28,-8.78 21.21,-8.78" + inkscape:connector-curvature="0" /> + <path + id="path5657" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,1338.95 c 7.97,0 15.59,3.16 21.22,8.78 5.62,5.63 8.78,13.29 8.78,21.22 0,7.96 -3.16,15.62 -8.78,21.25 -5.63,5.62 -13.25,8.75 -21.22,8.75 -7.93,0 -15.58,-3.13 -21.21,-8.75 -5.62,-5.63 -8.79,-13.29 -8.79,-21.25 0,-7.93 3.17,-15.59 8.79,-21.22 5.63,-5.62 13.28,-8.78 21.21,-8.78 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5659"> + <g + clip-path="url(#clipPath5663)" + id="g5661"> + <path + id="path5667" + style="fill:none;stroke:#008000;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 728.949,434.609 437.461,294.692 446.4,308.549 446.41,307.58 446.37,315.43 446.4,311.91 446.41,311.29 446.4,316.84 446.41,310.43 446.41,307.85 446.36,312.7" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5669"> + <g + clip-path="url(#clipPath5673)" + id="g5671"> + <path + id="path5677" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 728.949,404.609 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5679" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 728.949,404.609 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5681"> + <g + clip-path="url(#clipPath5685)" + id="g5683"> + <path + id="path5689" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1166.41,699.301 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5691" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1166.41,699.301 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5693"> + <g + clip-path="url(#clipPath5697)" + id="g5695"> + <path + id="path5701" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1612.81,1007.85 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5703" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1612.81,1007.85 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5705"> + <g + clip-path="url(#clipPath5709)" + id="g5707"> + <path + id="path5713" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2059.22,1315.43 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5715" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2059.22,1315.43 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5717"> + <g + clip-path="url(#clipPath5721)" + id="g5719"> + <path + id="path5725" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2505.59,1630.86 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5727" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2505.59,1630.86 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5729"> + <g + clip-path="url(#clipPath5733)" + id="g5731"> + <path + id="path5737" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2951.99,1942.77 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5739" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2951.99,1942.77 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5741"> + <g + clip-path="url(#clipPath5745)" + id="g5743"> + <path + id="path5749" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3398.4,2254.06 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5751" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3398.4,2254.06 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5753"> + <g + clip-path="url(#clipPath5757)" + id="g5755"> + <path + id="path5761" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3844.8,2570.9 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5763" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3844.8,2570.9 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5765"> + <g + clip-path="url(#clipPath5769)" + id="g5767"> + <path + id="path5773" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4291.21,2881.33 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5775" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4291.21,2881.33 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5777"> + <g + clip-path="url(#clipPath5781)" + id="g5779"> + <path + id="path5785" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4737.62,3189.18 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5787" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4737.62,3189.18 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5789"> + <g + clip-path="url(#clipPath5793)" + id="g5791"> + <path + id="path5797" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 5183.98,3501.88 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path5799" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,3501.88 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5801"> + <g + clip-path="url(#clipPath5805)" + id="g5803"> + <path + id="path5809" + style="fill:none;stroke:#ff0000;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 728.949,432.148 437.461,13.122 446.4,13.128 446.41,13.75 446.37,14.692 446.4,15.039 446.41,13.473 446.4,16.988 446.41,13.281 446.41,12.5 446.36,13.399" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5811"> + <g + clip-path="url(#clipPath5815)" + id="g5813"> + <path + id="path5819" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 698.949,402.148 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5821" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 698.949,402.148 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5823"> + <g + clip-path="url(#clipPath5827)" + id="g5825"> + <path + id="path5831" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1136.41,415.27 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5833" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1136.41,415.27 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5835"> + <g + clip-path="url(#clipPath5839)" + id="g5837"> + <path + id="path5843" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1582.81,428.398 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5845" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1582.81,428.398 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5847"> + <g + clip-path="url(#clipPath5851)" + id="g5849"> + <path + id="path5855" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2029.22,442.148 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5857" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2029.22,442.148 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5859"> + <g + clip-path="url(#clipPath5863)" + id="g5861"> + <path + id="path5867" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2475.59,456.84 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5869" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2475.59,456.84 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5871"> + <g + clip-path="url(#clipPath5875)" + id="g5873"> + <path + id="path5879" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2921.99,471.879 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5881" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2921.99,471.879 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5883"> + <g + clip-path="url(#clipPath5887)" + id="g5885"> + <path + id="path5891" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3368.4,485.352 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5893" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3368.4,485.352 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5895"> + <g + clip-path="url(#clipPath5899)" + id="g5897"> + <path + id="path5903" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3814.8,502.34 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5905" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3814.8,502.34 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5907"> + <g + clip-path="url(#clipPath5911)" + id="g5909"> + <path + id="path5915" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4261.21,515.621 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5917" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4261.21,515.621 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5919"> + <g + clip-path="url(#clipPath5923)" + id="g5921"> + <path + id="path5927" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4707.62,528.121 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5929" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4707.62,528.121 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5931"> + <g + clip-path="url(#clipPath5935)" + id="g5933"> + <path + id="path5939" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 5153.98,541.52 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path5941" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5153.98,541.52 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5943"> + <g + clip-path="url(#clipPath5947)" + id="g5945"> + <path + id="path5951" + style="fill:none;stroke:#00bfbf;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 728.949,432.07 437.461,0.078 446.4,-0.117 446.41,0.078 446.37,0.161 446.4,0 446.41,-0.079 446.4,-0.043 446.41,-0.078 446.41,0.27 446.36,0.199" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5953"> + <g + clip-path="url(#clipPath5957)" + id="g5955"> + <path + id="path5961" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 728.949,462.07 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path5963" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 728.949,462.07 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5965"> + <g + clip-path="url(#clipPath5969)" + id="g5967"> + <path + id="path5973" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1166.41,462.148 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path5975" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1166.41,462.148 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5977"> + <g + clip-path="url(#clipPath5981)" + id="g5979"> + <path + id="path5985" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 1612.81,462.031 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path5987" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1612.81,462.031 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g5989"> + <g + clip-path="url(#clipPath5993)" + id="g5991"> + <path + id="path5997" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2059.22,462.109 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path5999" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2059.22,462.109 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6001"> + <g + clip-path="url(#clipPath6005)" + id="g6003"> + <path + id="path6009" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2505.59,462.27 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6011" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2505.59,462.27 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6013"> + <g + clip-path="url(#clipPath6017)" + id="g6015"> + <path + id="path6021" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2951.99,462.27 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6023" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2951.99,462.27 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6025"> + <g + clip-path="url(#clipPath6029)" + id="g6027"> + <path + id="path6033" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3398.4,462.191 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6035" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3398.4,462.191 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6037"> + <g + clip-path="url(#clipPath6041)" + id="g6039"> + <path + id="path6045" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 3844.8,462.148 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6047" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3844.8,462.148 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6049"> + <g + clip-path="url(#clipPath6053)" + id="g6051"> + <path + id="path6057" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4291.21,462.07 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6059" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4291.21,462.07 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6061"> + <g + clip-path="url(#clipPath6065)" + id="g6063"> + <path + id="path6069" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 4737.62,462.301 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6071" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4737.62,462.301 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6073"> + <g + clip-path="url(#clipPath6077)" + id="g6075"> + <path + id="path6081" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 5183.98,462.539 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6083" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,462.539 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6085"> + <g + clip-path="url(#clipPath6089)" + id="g6087"> + <path + id="path6093" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6095" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,431.988 0,40" + inkscape:connector-curvature="0" /> + <path + id="path6097" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,3888.01 0,-40" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6099"> + <text + id="text6101" + transform="matrix(1,0,0,-1,68.9766,30.2938)"> + <tspan + id="tspan6103" + y="0" + x="0" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">0</tspan> + </text> + </g> + <g + id="g6105"> + <g + clip-path="url(#clipPath6109)" + id="g6107"> + <path + id="path6113" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 1612.81,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6115" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1612.81,431.988 0,40" + inkscape:connector-curvature="0" /> + <path + id="path6117" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 1612.81,3888.01 0,-40" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6119"> + <text + id="text6121" + transform="matrix(1,0,0,-1,147.054,30.2938)"> + <tspan + id="tspan6123" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">1000</tspan> + </text> + </g> + <g + id="g6125"> + <g + clip-path="url(#clipPath6129)" + id="g6127"> + <path + id="path6133" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 2505.59,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6135" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2505.59,431.988 0,40" + inkscape:connector-curvature="0" /> + <path + id="path6137" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2505.59,3888.01 0,-40" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6139"> + <text + id="text6141" + transform="matrix(1,0,0,-1,236.115,30.2938)"> + <tspan + id="tspan6143" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">2000</tspan> + </text> + </g> + <g + id="g6145"> + <g + clip-path="url(#clipPath6149)" + id="g6147"> + <path + id="path6153" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 3398.4,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6155" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3398.4,431.988 0,40" + inkscape:connector-curvature="0" /> + <path + id="path6157" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 3398.4,3888.01 0,-40" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6159"> + <text + id="text6161" + transform="matrix(1,0,0,-1,325.418,30.2938)"> + <tspan + id="tspan6163" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">3000</tspan> + </text> + </g> + <g + id="g6165"> + <g + clip-path="url(#clipPath6169)" + id="g6167"> + <path + id="path6173" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 4291.21,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6175" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4291.21,431.988 0,40" + inkscape:connector-curvature="0" /> + <path + id="path6177" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 4291.21,3888.01 0,-40" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6179"> + <text + id="text6181" + transform="matrix(1,0,0,-1,414.534,30.2938)"> + <tspan + id="tspan6183" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">4000</tspan> + </text> + </g> + <g + id="g6185"> + <g + clip-path="url(#clipPath6189)" + id="g6187"> + <path + id="path6193" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 5183.98,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6195" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,431.988 0,40" + inkscape:connector-curvature="0" /> + <path + id="path6197" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,3888.01 0,-40" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6199"> + <text + id="text6201" + transform="matrix(1,0,0,-1,503.978,30.2938)"> + <tspan + id="tspan6203" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">5000</tspan> + <tspan + id="tspan6205" + sodipodi:role="line" + y="14.2969" + x="-266.052 -257.07599 -249.468 -237.78 -230.16 -222.78 -217.84801 -214.032 -206.688 -202.464 -198.64799 -191.54401 -184.164 -179.23199 -174.528 -171.192 -164.592 -157.21201" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">Number of vertices</tspan> + </text> + </g> + <g + id="g6207"> + <g + clip-path="url(#clipPath6211)" + id="g6209"> + <path + id="path6215" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,431.988 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6217" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,431.988 40,0" + inkscape:connector-curvature="0" /> + <path + id="path6219" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,431.988 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6221"> + <text + id="text6223" + transform="matrix(1,0,0,-1,61.9531,38.8328)"> + <tspan + id="tspan6225" + y="0" + x="0" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">0</tspan> + </text> + </g> + <g + id="g6227"> + <g + clip-path="url(#clipPath6231)" + id="g6229"> + <path + id="path6235" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,863.98 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6237"> + <g + clip-path="url(#clipPath6241)" + id="g6239"> + <path + id="path6245" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,863.98 40,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6247" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,863.98 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6249"> + <text + id="text6251" + transform="matrix(1,0,0,-1,31.4688,82.0328)"> + <tspan + id="tspan6253" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">20000</tspan> + </text> + </g> + <g + id="g6255"> + <g + clip-path="url(#clipPath6259)" + id="g6257"> + <path + id="path6263" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,1296.02 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6265"> + <g + clip-path="url(#clipPath6269)" + id="g6267"> + <path + id="path6273" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,1296.02 40,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6275" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,1296.02 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6277"> + <text + id="text6279" + transform="matrix(1,0,0,-1,31.1875,125.233)"> + <tspan + id="tspan6281" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">40000</tspan> + </text> + </g> + <g + id="g6283"> + <g + clip-path="url(#clipPath6287)" + id="g6285"> + <path + id="path6291" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,1728.01 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6293"> + <g + clip-path="url(#clipPath6297)" + id="g6295"> + <path + id="path6301" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,1728.01 40,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6303" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,1728.01 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6305"> + <text + id="text6307" + transform="matrix(1,0,0,-1,31.4375,168.433)"> + <tspan + id="tspan6309" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">60000</tspan> + </text> + </g> + <g + id="g6311"> + <g + clip-path="url(#clipPath6315)" + id="g6313"> + <path + id="path6319" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,2160 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6321"> + <g + clip-path="url(#clipPath6325)" + id="g6323"> + <path + id="path6329" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,2160 40,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6331" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,2160 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6333"> + <text + id="text6335" + transform="matrix(1,0,0,-1,31.4063,211.633)"> + <tspan + id="tspan6337" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">80000</tspan> + </text> + </g> + <g + id="g6339"> + <g + clip-path="url(#clipPath6343)" + id="g6341"> + <path + id="path6347" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,2591.99 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6349"> + <g + clip-path="url(#clipPath6353)" + id="g6351"> + <path + id="path6357" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,2591.99 40,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6359" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,2591.99 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6361"> + <text + id="text6363" + transform="matrix(1,0,0,-1,24.2656,254.833)"> + <tspan + id="tspan6365" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528 38.16" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">100000</tspan> + </text> + </g> + <g + id="g6367"> + <g + clip-path="url(#clipPath6371)" + id="g6369"> + <path + id="path6375" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,3023.98 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6377"> + <g + clip-path="url(#clipPath6381)" + id="g6379"> + <path + id="path6385" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,3023.98 40,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6387" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,3023.98 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6389"> + <text + id="text6391" + transform="matrix(1,0,0,-1,24.2656,298.033)"> + <tspan + id="tspan6393" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528 38.16" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">120000</tspan> + </text> + </g> + <g + id="g6395"> + <g + clip-path="url(#clipPath6399)" + id="g6397"> + <path + id="path6403" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,3456.02 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6405"> + <g + clip-path="url(#clipPath6409)" + id="g6407"> + <path + id="path6413" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,3456.02 40,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6415" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,3456.02 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6417"> + <text + id="text6419" + transform="matrix(1,0,0,-1,24.2656,341.233)"> + <tspan + id="tspan6421" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528 38.16" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">140000</tspan> + </text> + </g> + <g + id="g6423"> + <g + clip-path="url(#clipPath6427)" + id="g6425"> + <path + id="path6431" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:10, 30;stroke-dashoffset:0" + d="m 720,3888.01 4463.98,0" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6433" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,3888.01 40,0" + inkscape:connector-curvature="0" /> + <path + id="path6435" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,3888.01 -40,0" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6437"> + <text + id="text6439" + transform="matrix(1,0,0,-1,24.2656,384.433)"> + <tspan + id="tspan6441" + sodipodi:role="line" + y="0" + x="0 7.632 15.264 22.896 30.528 38.16" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">160000</tspan> + </text> + <text + id="text6443" + transform="matrix(0,1,1,0,19.0938,204.398)"> + <tspan + id="tspan6445" + sodipodi:role="line" + y="0" + x="0 7.6199999 10.956 17.256001" + style="font-size:12px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">Size</tspan> + </text> + </g> + <path + id="path6447" + style="fill:none;stroke:#000000;stroke-width:10;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,3888.01 4463.98,0" + inkscape:connector-curvature="0" /> + <path + id="path6449" + style="fill:none;stroke:#000000;stroke-width:10;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 5183.98,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + <path + id="path6451" + style="fill:none;stroke:#000000;stroke-width:10;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,431.988 4463.98,0" + inkscape:connector-curvature="0" /> + <path + id="path6453" + style="fill:none;stroke:#000000;stroke-width:10;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 720,431.988 0,3456.022" + inkscape:connector-curvature="0" /> + <path + id="path6455" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2693.75,2938.4 2418.24,0 0,877.621 -2418.24,0 0,-877.621 z" + inkscape:connector-curvature="0" /> + <path + id="path6457" + style="fill:none;stroke:#000000;stroke-width:10;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2693.75,2938.4 2418.24,0 0,877.621 -2418.24,0 0,-877.621 z" + inkscape:connector-curvature="0" /> + <path + id="path6459" + style="fill:none;stroke:#0000ff;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2794.57,3701.76 201.6,0" + inkscape:connector-curvature="0" /> + <g + id="g6461"> + <g + clip-path="url(#clipPath6465)" + id="g6463"> + <path + id="path6469" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2794.57,3671.76 c 7.93,0 15.59,3.16 21.21,8.79 5.63,5.62 8.79,13.28 8.79,21.21 0,7.97 -3.16,15.58 -8.79,21.21 -5.62,5.62 -13.28,8.79 -21.21,8.79 -7.97,0 -15.59,-3.17 -21.21,-8.79 -5.63,-5.63 -8.79,-13.24 -8.79,-21.21 0,-7.93 3.16,-15.59 8.79,-21.21 5.62,-5.63 13.24,-8.79 21.21,-8.79" + inkscape:connector-curvature="0" /> + <path + id="path6471" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2794.57,3671.76 c 7.93,0 15.59,3.16 21.21,8.79 5.63,5.62 8.79,13.28 8.79,21.21 0,7.97 -3.16,15.58 -8.79,21.21 -5.62,5.62 -13.28,8.79 -21.21,8.79 -7.97,0 -15.59,-3.17 -21.21,-8.79 -5.63,-5.63 -8.79,-13.24 -8.79,-21.21 0,-7.93 3.16,-15.59 8.79,-21.21 5.62,-5.63 13.24,-8.79 21.21,-8.79 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <g + id="g6473"> + <g + clip-path="url(#clipPath6477)" + id="g6475"> + <path + id="path6481" + style="fill:#0000ff;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2996.17,3671.76 c 7.93,0 15.59,3.16 21.21,8.79 5.63,5.62 8.79,13.28 8.79,21.21 0,7.97 -3.16,15.58 -8.79,21.21 -5.62,5.62 -13.28,8.79 -21.21,8.79 -7.97,0 -15.58,-3.17 -21.21,-8.79 -5.62,-5.63 -8.79,-13.24 -8.79,-21.21 0,-7.93 3.17,-15.59 8.79,-21.21 5.63,-5.63 13.24,-8.79 21.21,-8.79" + inkscape:connector-curvature="0" /> + <path + id="path6483" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2996.17,3671.76 c 7.93,0 15.59,3.16 21.21,8.79 5.63,5.62 8.79,13.28 8.79,21.21 0,7.97 -3.16,15.58 -8.79,21.21 -5.62,5.62 -13.28,8.79 -21.21,8.79 -7.97,0 -15.58,-3.17 -21.21,-8.79 -5.62,-5.63 -8.79,-13.24 -8.79,-21.21 0,-7.93 3.17,-15.59 8.79,-21.21 5.63,-5.63 13.24,-8.79 21.21,-8.79 z" + inkscape:connector-curvature="0" /> + </g> + </g> + <path + id="path6491" + style="fill:none;stroke:#008000;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2794.57,3490.39 201.6,0" + inkscape:connector-curvature="0" /> + <path + id="path6493" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2794.57,3460.39 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path6495" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2794.57,3460.39 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + <path + id="path6497" + style="fill:#008000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2996.17,3460.39 30,60 -60,0" + inkscape:connector-curvature="0" /> + <path + id="path6499" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2996.17,3460.39 30,60 -60,0 30,-60 z" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6501"> + <text + id="text6503" + transform="matrix(1,0,0,-1,315.455,343.999)"> + <tspan + id="tspan6505" + sodipodi:role="line" + y="0" + x="0 9.1295996 18.259199 36.864101 44.366501 48.369701 62.395302 71.539299 75.542503 79.5457 87.465698 96.321701" + style="font-size:14.39999962px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">numsimplices</tspan> + </text> + </g> + <path + id="path6507" + style="fill:none;stroke:#ff0000;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2794.57,3282.93 201.6,0" + inkscape:connector-curvature="0" /> + <path + id="path6509" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2764.57,3252.93 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path6511" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2764.57,3252.93 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path6513" + style="fill:#ff0000;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2966.17,3252.93 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <path + id="path6515" + style="fill:none;stroke:#ff0000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2966.17,3252.93 60,60 m -60,0 60,-60" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6517"> + <text + id="text6519" + transform="matrix(1,0,0,-1,315.455,323.252)"> + <tspan + id="tspan6521" + sodipodi:role="line" + y="0" + x="0 9.1295996 18.259199 32.284801 36.863998 46.007999 50.0112 58.824001 66.744003 75.081596 83.937599 89.856003" + style="font-size:14.39999962px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">num blockers</tspan> + </text> + </g> + <path + id="path6523" + style="fill:none;stroke:#00bfbf;stroke-width:20;stroke-linecap:square;stroke-linejoin:round;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2794.57,3075.47 201.6,0" + inkscape:connector-curvature="0" /> + <path + id="path6525" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2794.57,3105.47 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6527" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2794.57,3105.47 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + <path + id="path6529" + style="fill:#00bfbf;fill-opacity:1;fill-rule:nonzero;stroke:none" + d="m 2996.17,3105.47 -30,-60 60,0" + inkscape:connector-curvature="0" /> + <path + id="path6531" + style="fill:none;stroke:#000000;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1;stroke-dasharray:none" + d="m 2996.17,3105.47 -30,-60 60,0 -30,60 z" + inkscape:connector-curvature="0" /> + <g + transform="scale(10,10)" + id="g6533"> + <text + id="text6535" + transform="matrix(1,0,0,-1,315.455,302.505)"> + <tspan + id="tspan6537" + sodipodi:role="line" + y="0" + x="0 9.1295996 18.259199 32.284801 36.863998 45.993599 54.8064 63.936001 68.515198 77.659203 86.472 95.615997 104.4432 113.5872 117.5904 126.4464 131.0256 140.21297 144.21616 153.02896 160.94896 169.28656 178.14256 184.06096" + style="font-size:14.39999962px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans">num non popable blockers</tspan> + </text> + </g> + <text + style="font-size:120px" + y="-3655.6985" + x="3153.7925" + id="text6487-0" + transform="scale(1,-1)"> + <tspan + id="tspan6489-8" + sodipodi:role="line" + style="font-size:144px;font-variant:normal;font-weight:normal;writing-mode:lr-tb;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;font-family:DejaVu Sans;-inkscape-font-specification:DejaVuSans" + x="3153.7925" + y="-3655.6985">size of the graph</tspan> + </text> + </g> + </g> + </g> +</svg> diff --git a/src/Skeleton_blocker/doc/blockers_curve.png b/src/Skeleton_blocker/doc/blockers_curve.png Binary files differnew file mode 100644 index 00000000..58863ece --- /dev/null +++ b/src/Skeleton_blocker/doc/blockers_curve.png diff --git a/src/Skeleton_blocker/doc/ds_representation.png b/src/Skeleton_blocker/doc/ds_representation.png Binary files differnew file mode 100644 index 00000000..8136621a --- /dev/null +++ b/src/Skeleton_blocker/doc/ds_representation.png diff --git a/src/Skeleton_blocker/doc/ds_representation.svg b/src/Skeleton_blocker/doc/ds_representation.svg new file mode 100644 index 00000000..981b2874 --- /dev/null +++ b/src/Skeleton_blocker/doc/ds_representation.svg @@ -0,0 +1,470 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Created with Inkscape (http://www.inkscape.org/) --> + +<svg + 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:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="434.50912" + height="113.23431" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="ds_representation.svg" + inkscape:export-filename="/home/dsalinas/Documents/CodeSVN/gudhi_depot/trunk/src/Skeleton_blocker/doc/ds_representation.png" + inkscape:export-xdpi="164.24294" + inkscape:export-ydpi="164.24294"> + <defs + id="defs4"> + <inkscape:path-effect + is_visible="true" + id="path-effect4610" + effect="spiro" /> + </defs> + <sodipodi:namedview + id="base" + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1.0" + inkscape:pageopacity="0.0" + inkscape:pageshadow="2" + inkscape:zoom="3.959798" + inkscape:cx="393.78845" + inkscape:cy="51.962328" + inkscape:document-units="px" + inkscape:current-layer="layer1" + showgrid="false" + inkscape:window-width="2560" + inkscape:window-height="1523" + inkscape:window-x="0" + inkscape:window-y="0" + inkscape:window-maximized="1" + fit-margin-top="0" + fit-margin-left="0" + fit-margin-right="0" + fit-margin-bottom="0" /> + <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 + inkscape:label="Layer 1" + inkscape:groupmode="layer" + id="layer1" + transform="translate(775.10425,-319.57102)"> + <path + id="path4432" + d="m -564.66566,372.78112 -22.51977,46.5698 62.69739,-31.00174 z" + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:round;stroke-opacity:1;display:inline" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cccc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0" + d="m -553.17597,345.78586 c 0.75762,1.51523 32.57742,14.89975 32.57742,14.89975" + id="path3125" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -519.08333,361.44322 31.81981,11.8693" + id="path3127" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + inkscape:connector-curvature="0" + id="path14-7" + style="fill:none;stroke:none" + d="m -554.02684,345.73906 29.32107,42.08799 7.736,-39.88821" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-1" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -523.3168,376.08402 34.2525,-51.7575" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -564.28765,372.5549 47.47717,-24.4962 -7.82868,39.90103 37.1231,-14.89975 -29.29442,-25.25382 -37.37564,-2.27284 29.54696,42.42641" + id="path3121" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccccccc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-691.68016,428.25063)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-669.37366,382.75481)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-4" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-630.26652,397.04052)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-1" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-659.37366,354.89767)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-42" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-622.23081,358.64766)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-3" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-593.12367,383.11196)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-7" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + inkscape:connector-curvature="0" + id="path14-1-1" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -378.67395,371.32852 34.2525,-51.7575" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -413.6327,367.61658 37.56127,-20.2544 c 0,0 -4.64286,29.64285 -5.35714,31.42857 -0.71429,1.78571 -32.20413,-11.17417 -32.20413,-11.17417 z" + id="path4091" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccsc" /> + <g + id="g3909"> + <path + sodipodi:nodetypes="ccc" + d="m -409.13145,340.85729 28.31093,41.70918 8.87241,-39.38313" + style="fill:none;fill-opacity:0.41568603999999998;fill-rule:nonzero;stroke:none;opacity:0.13580247" + id="path14-3-5" + inkscape:connector-curvature="0" /> + <path + sodipodi:nodetypes="cccc" + inkscape:connector-curvature="0" + style="opacity:0.13580244;fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:round;stroke-opacity:1;display:inline" + d="m -420.02281,368.02562 -22.51977,46.5698 62.69739,-31.00174 z" + id="path4432-5" /> + <path + sodipodi:nodetypes="cc" + inkscape:connector-curvature="0" + id="path3125-0" + d="m -408.53312,341.03036 c 0.75762,1.51523 32.57742,14.89975 32.57742,14.89975" + style="opacity:0.13580244;fill:none;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:1, 3;stroke-dashoffset:0" /> + <path + sodipodi:nodetypes="cc" + inkscape:connector-curvature="0" + id="path3127-1" + d="m -374.44048,356.68772 31.81981,11.8693" + style="opacity:0.13580244;fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" /> + <path + sodipodi:nodetypes="ccccccc" + inkscape:connector-curvature="0" + id="path3121-0" + d="m -419.6448,367.7994 47.47717,-24.4962 -7.82868,39.90103 37.1231,-14.89975 -29.29442,-25.25382 -37.37564,-2.27284 29.54696,42.42641" + style="opacity:0.13580244;fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" /> + <path + sodipodi:type="arc" + style="opacity:0.13580244;fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + id="path4584-36" + sodipodi:cx="93.972473" + sodipodi:cy="113.9189" + sodipodi:rx="3.4171808" + sodipodi:ry="3.4171808" + d="m 97.389654,113.9189 a 3.4171808,3.4171808 0 1 1 -6.834362,0 3.4171808,3.4171808 0 1 1 6.834362,0 z" + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-547.03731,423.49513)" /> + <path + sodipodi:type="arc" + style="opacity:0.13580244;fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + id="path4584-4-5" + sodipodi:cx="93.972473" + sodipodi:cy="113.9189" + sodipodi:rx="3.4171808" + sodipodi:ry="3.4171808" + d="m 97.389654,113.9189 a 3.4171808,3.4171808 0 1 1 -6.834362,0 3.4171808,3.4171808 0 1 1 6.834362,0 z" + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-524.73081,377.99931)" /> + <path + sodipodi:type="arc" + style="opacity:0.13580244;fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + id="path4584-1-6" + sodipodi:cx="93.972473" + sodipodi:cy="113.9189" + sodipodi:rx="3.4171808" + sodipodi:ry="3.4171808" + d="m 97.389654,113.9189 a 3.4171808,3.4171808 0 1 1 -6.834362,0 3.4171808,3.4171808 0 1 1 6.834362,0 z" + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-485.62367,392.28502)" /> + <path + sodipodi:type="arc" + style="opacity:0.13580244;fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + id="path4584-42-0" + sodipodi:cx="93.972473" + sodipodi:cy="113.9189" + sodipodi:rx="3.4171808" + sodipodi:ry="3.4171808" + d="m 97.389654,113.9189 a 3.4171808,3.4171808 0 1 1 -6.834362,0 3.4171808,3.4171808 0 1 1 6.834362,0 z" + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-514.73081,350.14217)" /> + <path + sodipodi:type="arc" + style="opacity:0.13580244;fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + id="path4584-3-9" + sodipodi:cx="93.972473" + sodipodi:cy="113.9189" + sodipodi:rx="3.4171808" + sodipodi:ry="3.4171808" + d="m 97.389654,113.9189 a 3.4171808,3.4171808 0 1 1 -6.834362,0 3.4171808,3.4171808 0 1 1 6.834362,0 z" + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-477.58796,353.89216)" /> + <path + sodipodi:type="arc" + style="opacity:0.13580244;fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + id="path4584-7-0" + sodipodi:cx="93.972473" + sodipodi:cy="113.9189" + sodipodi:rx="3.4171808" + sodipodi:ry="3.4171808" + d="m 97.389654,113.9189 a 3.4171808,3.4171808 0 1 1 -6.834362,0 3.4171808,3.4171808 0 1 1 6.834362,0 z" + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-448.48082,378.35646)" /> + </g> + <path + style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -370.55894,347.61837 23.42349,19.75458 c 0,0 -28.39286,9.99999 -29.10714,11.78571 -0.71429,1.78571 5.68365,-31.54029 5.68365,-31.54029 z" + id="path4091-7" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccsc" /> + <path + id="path4432-6" + d="m -750.37996,370.16849 -22.51977,46.5698 62.69739,-31.00174 z" + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:round;stroke-opacity:1;display:inline" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cccc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:1, 3;stroke-dashoffset:0" + d="m -738.89027,343.17323 c 0.75762,1.51523 32.57742,14.89975 32.57742,14.89975" + id="path3125-9" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -704.79763,358.83059 31.81981,11.8693" + id="path3127-2" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + inkscape:connector-curvature="0" + id="path14-12" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -750.60027,369.89548 -21.18655,45.87606 60.51647,-29.53414" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-7-8" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -739.74114,343.12643 29.32107,42.08799 7.736,-39.88821" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-8-0" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -702.3655,345.90435 -2.625,13.17237 29.83309,9.73554" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-2-70" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -704.89087,358.7838 -5.27665,26.68316 35.26265,-15.39201" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-3-2" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -739.4886,343.00016 28.31093,41.70918 8.87241,-39.38313" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-1-2" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -709.0311,373.47139 34.2525,-51.7575" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -750.00195,369.94227 47.47717,-24.4962 -7.82868,39.90103 37.1231,-14.89975 -29.29442,-25.25382 -37.37564,-2.27284 29.54696,42.42641" + id="path3121-6" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccccccc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-877.39446,425.638)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-79" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-855.08796,380.14218)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-4-9" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-815.98082,394.42789)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-1-61" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-845.08796,352.28504)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-42-8" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-807.94511,356.03503)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-3-5" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-778.83797,380.49933)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-7-1" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-718.37708" + y="430.86295" + id="text6164-6-56-2" + sodipodi:linespacing="125%" + inkscape:export-xdpi="164.24294" + inkscape:export-ydpi="164.24294" + inkscape:export-filename="/home/dsalinas/Documents/CodeSVN/gudhi_depot/trunk/src/Skeleton_blocker/doc/ds_representation.png"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6" + x="-718.37708" + y="430.86295">Simplicial complex</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-462.22809" + y="430.86295" + id="text6164-6-56-2-3" + sodipodi:linespacing="125%" + inkscape:export-xdpi="164.24294" + inkscape:export-ydpi="164.24294" + inkscape:export-filename="/home/dsalinas/Documents/CodeSVN/gudhi_depot/trunk/src/Skeleton_blocker/doc/ds_representation.png"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9" + x="-462.22809" + y="430.86295">Encoding</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-535.67126" + y="334.7963" + id="text6164-6-56-2-3-0" + sodipodi:linespacing="125%"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9-9" + x="-535.67126" + y="334.7963">Graph</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-389.50018" + y="335.10443" + id="text6164-6-56-2-3-0-3" + sodipodi:linespacing="125%"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9-9-1" + x="-389.50018" + y="335.10443">Blockers</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-470.03345" + y="335.56711" + id="text6164-6-56-2-3-0-36" + sodipodi:linespacing="125%"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9-9-3" + x="-470.03345" + y="335.56711">+</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-618.52417" + y="382.18915" + id="text6164-6-56-2-1" + sodipodi:linespacing="125%" + inkscape:export-xdpi="164.24294" + inkscape:export-ydpi="164.24294" + inkscape:export-filename="/home/dsalinas/Documents/CodeSVN/gudhi_depot/trunk/src/Skeleton_blocker/doc/ds_representation.png"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-4" + x="-618.52417" + y="382.18915">=</tspan></text> + </g> +</svg> diff --git a/src/Skeleton_blocker/doc/ds_scheme.svg b/src/Skeleton_blocker/doc/ds_scheme.svg new file mode 100644 index 00000000..f13a6213 --- /dev/null +++ b/src/Skeleton_blocker/doc/ds_scheme.svg @@ -0,0 +1,477 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Created with Inkscape (http://www.inkscape.org/) --> + +<svg + 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:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="434.50912" + height="113.23431" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="ds_scheme.svg" + inkscape:export-filename="/home/dsalinas/Documents/CodeSVN/gudhi_depot/trunk/src/Skeleton_blocker/doc/ds_representation.png" + inkscape:export-xdpi="164.24294" + inkscape:export-ydpi="164.24294"> + <defs + id="defs4"> + <inkscape:path-effect + is_visible="true" + id="path-effect4610" + effect="spiro" /> + </defs> + <sodipodi:namedview + id="base" + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1.0" + inkscape:pageopacity="0.0" + inkscape:pageshadow="2" + inkscape:zoom="2.8" + inkscape:cx="110.77021" + inkscape:cy="32.991372" + inkscape:document-units="px" + inkscape:current-layer="layer1" + showgrid="false" + inkscape:window-width="2560" + inkscape:window-height="1523" + inkscape:window-x="0" + inkscape:window-y="0" + inkscape:window-maximized="1" + fit-margin-top="0" + fit-margin-left="0" + fit-margin-right="0" + fit-margin-bottom="0" /> + <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 + inkscape:label="Layer 1" + inkscape:groupmode="layer" + id="layer1" + transform="translate(775.10425,-319.57102)"> + <path + id="path4432" + d="m -564.66566,372.78112 -22.51977,46.5698 62.69739,-31.00174 z" + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:round;stroke-opacity:1;display:inline" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cccc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0" + d="m -553.17597,345.78586 c 0.75762,1.51523 32.57742,14.89975 32.57742,14.89975" + id="path3125" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -519.08333,361.44322 31.81981,11.8693" + id="path3127" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + inkscape:connector-curvature="0" + id="path14-7" + style="fill:none;stroke:none" + d="m -554.02684,345.73906 29.32107,42.08799 7.736,-39.88821" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-1" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -523.3168,376.08402 34.2525,-51.7575" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -564.28765,372.5549 47.47717,-24.4962 -7.82868,39.90103 37.1231,-14.89975 -29.29442,-25.25382 -37.37564,-2.27284 29.54696,42.42641" + id="path3121" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccccccc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-691.68016,428.25063)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-669.37366,382.75481)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-4" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-630.26652,397.04052)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-1" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-659.37366,354.89767)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-42" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-622.23081,358.64766)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-3" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-593.12367,383.11196)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-7" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + id="path4432-5" + d="m -420.02281,368.02562 -22.51977,46.5698 62.69739,-31.00174 z" + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:round;stroke-opacity:1;display:inline" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cccc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:1, 3;stroke-dashoffset:0" + d="m -408.53312,341.03036 c 0.75762,1.51523 32.57742,14.89975 32.57742,14.89975" + id="path3125-0" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -374.44048,356.68772 31.81981,11.8693" + id="path3127-1" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + inkscape:connector-curvature="0" + id="path14-79" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -420.24312,367.75261 -21.18655,45.87606 60.51647,-29.53414" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-7-1" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -409.38399,340.98356 29.32107,42.08799 7.736,-39.88821" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-8-6" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -372.00835,343.76148 -2.625,13.17237 29.83309,9.73554" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-2-7" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -374.53372,356.64093 -5.27665,26.68316 35.26265,-15.39201" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-3-5" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -409.13145,340.85729 28.31093,41.70918 8.87241,-39.38313" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-1-1" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -378.67395,371.32852 34.2525,-51.7575" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -419.6448,367.7994 47.47717,-24.4962 -7.82868,39.90103 37.1231,-14.89975 -29.29442,-25.25382 -37.37564,-2.27284 29.54696,42.42641" + id="path3121-0" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccccccc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-547.03731,423.49513)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-36" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-524.73081,377.99931)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-4-5" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-485.62367,392.28502)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-1-6" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-514.73081,350.14217)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-42-0" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-477.58796,353.89216)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-3-9" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-448.48082,378.35646)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-7-0" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -413.6327,367.61658 37.56127,-20.2544 c 0,0 -4.64286,29.64285 -5.35714,31.42857 -0.71429,1.78571 -32.20413,-11.17417 -32.20413,-11.17417 z" + id="path4091" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccsc" /> + <path + style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -370.55894,347.61837 23.42349,19.75458 c 0,0 -28.39286,9.99999 -29.10714,11.78571 -0.71429,1.78571 5.68365,-31.54029 5.68365,-31.54029 z" + id="path4091-7" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccsc" /> + <path + id="path4432-6" + d="m -750.37996,370.16849 -22.51977,46.5698 62.69739,-31.00174 z" + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:round;stroke-opacity:1;display:inline" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cccc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:1, 3;stroke-dashoffset:0" + d="m -738.89027,343.17323 c 0.75762,1.51523 32.57742,14.89975 32.57742,14.89975" + id="path3125-9" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -704.79763,358.83059 31.81981,11.8693" + id="path3127-2" + inkscape:connector-curvature="0" + sodipodi:nodetypes="cc" /> + <path + inkscape:connector-curvature="0" + id="path14-12" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -750.60027,369.89548 -21.18655,45.87606 60.51647,-29.53414" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-7-8" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -739.74114,343.12643 29.32107,42.08799 7.736,-39.88821" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-8-0" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -702.3655,345.90435 -2.625,13.17237 29.83309,9.73554" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-2-70" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -704.89087,358.7838 -5.27665,26.68316 35.26265,-15.39201" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-3-2" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -739.4886,343.00016 28.31093,41.70918 8.87241,-39.38313" + sodipodi:nodetypes="ccc" /> + <path + inkscape:connector-curvature="0" + id="path14-1-2" + style="fill:#575e9c;fill-opacity:0.41568604;fill-rule:nonzero;stroke:none" + d="m -709.0311,373.47139 34.2525,-51.7575" + sodipodi:nodetypes="cc" /> + <path + style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" + d="m -750.00195,369.94227 47.47717,-24.4962 -7.82868,39.90103 37.1231,-14.89975 -29.29442,-25.25382 -37.37564,-2.27284 29.54696,42.42641" + id="path3121-6" + inkscape:connector-curvature="0" + sodipodi:nodetypes="ccccccc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-877.39446,425.638)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-79" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-855.08796,380.14218)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-4-9" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-815.98082,394.42789)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-1-61" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-845.08796,352.28504)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-42-8" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-807.94511,356.03503)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-3-5" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <path + transform="matrix(0.39947101,-0.59295401,0.59295401,0.39947101,-778.83797,380.49933)" + d="m 97.389654,113.9189 c 0,1.88726 -1.529924,3.41718 -3.417181,3.41718 -1.887257,0 -3.417181,-1.52992 -3.417181,-3.41718 0,-1.88726 1.529924,-3.41718 3.417181,-3.41718 1.887257,0 3.417181,1.52992 3.417181,3.41718 z" + sodipodi:ry="3.4171808" + sodipodi:rx="3.4171808" + sodipodi:cy="113.9189" + sodipodi:cx="93.972473" + id="path4584-7-1" + style="fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:0.99118668;stroke-linecap:butt;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline" + sodipodi:type="arc" /> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-718.37708" + y="430.86295" + id="text6164-6-56-2" + sodipodi:linespacing="125%" + inkscape:export-xdpi="164.24294" + inkscape:export-ydpi="164.24294" + inkscape:export-filename="/home/dsalinas/Documents/CodeSVN/gudhi_depot/trunk/src/Skeleton_blocker/doc/ds_representation.png"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6" + x="-718.37708" + y="430.86295">Simplicial complex</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-462.22809" + y="430.86295" + id="text6164-6-56-2-3" + sodipodi:linespacing="125%" + inkscape:export-xdpi="164.24294" + inkscape:export-ydpi="164.24294" + inkscape:export-filename="/home/dsalinas/Documents/CodeSVN/gudhi_depot/trunk/src/Skeleton_blocker/doc/ds_representation.png"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9" + x="-462.22809" + y="430.86295">Encoding</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-535.67126" + y="334.7963" + id="text6164-6-56-2-3-0" + sodipodi:linespacing="125%"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9-9" + x="-535.67126" + y="334.7963">Graph</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-389.50018" + y="335.10443" + id="text6164-6-56-2-3-0-3" + sodipodi:linespacing="125%"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9-9-1" + x="-389.50018" + y="335.10443">Blockers</tspan></text> + <text + xml:space="preserve" + style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Times New Roman;-inkscape-font-specification:'Times New Roman,'" + x="-470.03345" + y="335.56711" + id="text6164-6-56-2-3-0-36" + sodipodi:linespacing="125%"><tspan + sodipodi:role="line" + id="tspan6166-1-0-6-9-9-3" + x="-470.03345" + y="335.56711">+</tspan></text> + </g> +</svg> diff --git a/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp b/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp index 3f4a9ffc..b1cb281e 100644 --- a/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp +++ b/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp @@ -1,3 +1,25 @@ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <boost/timer/timer.hpp> #include <stdio.h> #include <stdlib.h> diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 1d215984..eff37a18 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker.h - * - * Created on: Jan, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKER_H #define GUDHI_SKELETON_BLOCKER_H @@ -20,5 +34,164 @@ #include "gudhi/Utils.h" //xxx + +/** \defgroup skbl Skeleton-Blocker + +\author David Salinas + +\section Introduction +The Skeleton-Blocker data-structure had been introduced in the two papers +\cite socg_blockers_2011,\cite blockers2012. +It proposes a light encoding for simplicial complexes by storing only an *implicit* representation of its +simplices. +Intuitively, it just stores the 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that +is very small in practice (see next section for a formal definition). +This data-structure handles all simplicial complexes operations such as + as simplex enumeration or simplex removal but operations that are particularly efficient + are operations that do not require simplex enumeration such as edge iteration, link computation or simplex contraction. + + +\section Definitions + +We recall briefly classical definitions of simplicial complexes + \cite Munkres-elementsalgtop1984. +An abstract simplex is a finite non-empty set and its dimension is its number of elements minus 1. +Whenever \f$\tau \subset \sigma\f$ and \f$\tau \neq \emptyset \f$, \f$ \tau \f$ is called a face of +\f$ \sigma\f$ and \f$ \sigma\f$ is called a coface of \f$ \tau \f$ . Furthermore, +when \f$ \tau \neq \sigma\f$ we say that \f$ \tau\f$ is a proper-face of \f$ \sigma\f$. +An abstract simplicial complex is a set of simplices that contains all the faces of their simplices. +The 1-skeleton of a simplicial complex (or its graph) consists of its elements of dimension lower than 2. + +*\image html "ds_representation.png" "Skeleton-blocker representation" width=20cm + + +To encode, a simplicial complex, one can encodes all its simplices. +In case when this number gets too large, +a lighter and implicit version consists of encoding only its graph plus some elements called missing faces or blockers. +A blocker is a simplex of dimension greater than 1 +that does not belong to the complex but whose all proper faces does. + + +Remark that for a clique complex (i.e. a simplicial complex whose simplices are cliques of its graph), the set of blockers +is empty and the data-structure is then particularly sparse. +One famous example of clique-complex is the Rips complex which is intensively used +in topological data-analysis. +In practice, the set of blockers of a simplicial complex +remains also small when simplifying a Rips complex with edge contractions +but also for most of the simplicial complexes used in topological data-analysis such as Delaunay, Cech or Witness complexes. +For instance, the numbers of blockers is depicted for random 3 dimensional spheres embedded into \f$R^4\f$ +in figure X. + + +*\image html "blockers_curve.png" "Number of blockers of random triangulations of 3-spheres" width=10cm + + + + +\section API + +\subsection Overview + +Four classes are implemented for simplicial complex in this representation namely : + +\li Skeleton_blocker_complex : a simplicial complex with basic operations such as vertex/edge/simplex enumeration and construction +\li Skeleton_blocker_link_complex : the link of a simplex in a parent complex. It is represented as a sub complex +of the parent complex +\li Skeleton_blocker_simplifiable_complex : a simplicial complex with simplification operations such as edge contraction or simplex collapse +\li Skeleton_blocker_geometric_complex : a simplifiable simplicial complex who has access to geometric points in \f$R^d\f$ + +The two last classes are derived classes from the <Code>Skeleton_blocker_complex</Code> class. The class <Code>Skeleton_blocker_link_complex</Code> inheritates from a template passed parameter +that may be either <Code>Skeleton_blocker_complex</Code> or <Code>Skeleton_blocker_geometric_complex</Code> (a link may store points coordinates or not). +Most user will just need to use Skeleton_blocker_geometric_complex. + +\subsection Visitor + +The class <Code>Skeleton_blocker_complex</Code> has a visitor that is called when usual operations such as adding an edge or remove a vertex are called. +You may want to use this visitor to compute statistics or to update another data-structure (for instance this visitor is heavily used in the +<Code>Contraction</Code> package). + + + + +\section Example + + +\subsection s Iterating through vertices, edges, blockers and simplices + +Iteration through vertices, edges, simplices or blockers is straightforward with c++11 for range loops. +Note that simplex iteration with this implicit data-structure just takes +a few more time compared to iteration via an explicit representation +such as the Simplex Tree. The following example computes the Euler Characteristic +of a simplicial complex. + + \code{.cpp} + typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; + typedef Complex::Vertex_handle Vertex_handle; + typedef Complex::Simplex_handle Simplex; + + const int n = 15; + + // build a full complex with 10 vertices and 2^n-1 simplices + Complex complex; + for(int i=0;i<n;i++) + complex.add_vertex(); + for(int i=0;i<n;i++) + for(int j=0;j<i;j++) + //note that add_edge adds the edge and all its cofaces + complex.add_edge(Vertex_handle(i),Vertex_handle(j)); + + // this is just to illustrate iterators, to count number of vertices + // or edges, complex.num_vertices() and complex.num_edges() are + // more appropriated! + unsigned num_vertices = 0; + for(auto v : complex.vertex_range()){ + ++num_vertices; + } + + unsigned num_edges = 0; + for(auto e : complex.edge_range()) + ++num_edges; + + unsigned euler = 0; + unsigned num_simplices = 0; + // we use a reference to a simplex instead of a copy + // value here because a simplex is a set of integers + // and copying it cost time + for(const Simplex & s : complex.simplex_range()){ + ++num_simplices; + if(s.dimension()%2 == 0) + euler += 1; + else + euler -= 1; + } + std::cout << "Saw "<<num_vertices<<" vertices, "<<num_edges<<" edges and "<<num_simplices<<" simplices"<<std::endl; + std::cout << "The Euler Characteristic is "<<euler<<std::endl; + \endcode + + +\verbatim +./SkeletonBlockerIteration +Saw 15 vertices, 105 edges and 32767 simplices +The Euler Characteristic is 1 + 0.537302s wall, 0.530000s user + 0.000000s system = 0.530000s CPU (98.6%) +\endverbatim + + + +\subsection Acknowledgements +The author wishes to thank Dominique Attali and AndrĂ© Lieutier for +their collaboration to write the two initial papers about this data-structure + and also Dominique for leaving him use a prototype. + + +\copyright GNU General Public License v3. +\verbatim Contact: David Salinas, david.salinas@inria.fr \endverbatim +*/ +/** @} */ // end defgroup + + + #endif + + diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h index 4475afcc..3afd4cc7 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h @@ -1,10 +1,24 @@ -/* - * ComplexVisitor.h - * - * Created on: Dec 11, 2013 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_COMPLEXVISITOR_H_ #define GUDHI_COMPLEXVISITOR_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h index 864ee6ac..4e1c5178 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h @@ -1,11 +1,24 @@ -/* - * Skeleton_blocker_link_superior.h - * - * Created on: Feb 19, 2014 - * Author: David Salinas - * Copyright 2013 INRIA. All rights reserved - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKER_LINK_SUPERIOR_H_ #define GUDHI_SKELETON_BLOCKER_LINK_SUPERIOR_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h index 369635e5..fd44fba5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h @@ -1,30 +1,24 @@ -/* - * Skeleton_blocker_off_io.h - * Created on: Nov 28, 2014 - * 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): David Salinas - * - * Copyright (C) 2014 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/>. - * - */ - - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 SKELETON_BLOCKER_OFF_IO_H_ #define SKELETON_BLOCKER_OFF_IO_H_ @@ -34,6 +28,9 @@ namespace Gudhi { namespace skbl { +/** + *@brief Off reader visitor that can be passed to Off_reader to read a Skeleton_blocker_complex. + */ template<typename Complex> class Skeleton_blocker_off_visitor_reader{ Complex& complex_; @@ -71,6 +68,9 @@ public: } }; +/** +*@brief Class that allows to load a Skeleton_blocker_complex from an off file. +*/ template<typename Complex> class Skeleton_blocker_off_reader{ public: diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h index 79a8e7aa..a24bea25 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_simple_geometric_traits.h - * - * Created on: Feb 11, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_SIMPLE_GEOMETRIC_TRAITS_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLE_GEOMETRIC_TRAITS_H_ @@ -16,8 +30,12 @@ namespace Gudhi{ namespace skbl{ + /** * @extends SkeletonBlockerGeometricDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerGeometricDS and + * can be passed as a template argument to Skeleton_blocker_geometric_complex */ template<typename GeometryTrait> struct Skeleton_blocker_simple_geometric_traits : public skbl::Skeleton_blocker_simple_traits { @@ -35,6 +53,7 @@ public: template<class ComplexGeometricTraits> friend class Skeleton_blocker_geometric_complex; private: Point point_; + Point& point(){ return point_; } const Point& point() const { return point_; } }; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h index 3975bb46..e17ea9b5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_simple_traits.h - * - * Created on: Feb 11, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_SIMPLE_TRAITS_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLE_TRAITS_H_ @@ -18,11 +32,14 @@ namespace skbl { /** * @extends SkeletonBlockerDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerDS and + * can be passed as a template argument to Skeleton_blocker_complex */ struct Skeleton_blocker_simple_traits{ /** - * @brief global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. - * In gross, vertices are stored in a vector. + * @brief Global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. + * Vertices are stored in a vector. * For the root simplicial complex, the local and global descriptors are the same. * For a subcomplex L and one of its vertices 'v', the local descriptor of 'v' is its position in * the vertex vector of the subcomplex L whereas its global descriptor is the position of 'v' diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h index 5593a5a8..fb3d9470 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h @@ -1,3 +1,25 @@ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKER_SIMPLEX_H #define GUDHI_SKELETON_BLOCKER_SIMPLEX_H diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h index 5ca8e9af..9b4253d1 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -1,3 +1,25 @@ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKER_SUB_COMPLEX_H #define GUDHI_SKELETON_BLOCKER_SUB_COMPLEX_H @@ -11,7 +33,7 @@ namespace skbl { /** * @brief Simplicial subcomplex of a complex represented by a skeleton/blockers pair. - * + * @extends Skeleton_blocker_complex * @details Stores a subcomplex of a simplicial complex. * To simplify explanations below, we will suppose that : * - K is the root simplicial complex @@ -136,13 +158,13 @@ public: * Constructs the restricted complex of 'parent_complex' to * vertices of 'simplex'. */ - friend void make_restricted_complex(const ComplexType & parent_complex, const Simplex_handle& simplex, Skeleton_blocker_sub_complex & result){ - result.clear(); + void make_restricted_complex(const ComplexType & parent_complex, const Simplex_handle& simplex){ + this->clear(); // add vertices to the sub complex for (auto x : simplex){ assert(parent_complex.contains_vertex(x)); - auto x_local = result.add_vertex(parent_complex[x].get_id()); - result[x_local] = parent_complex[x]; + auto x_local = this->add_vertex(parent_complex[x].get_id()); + (*this)[x_local] = parent_complex[x]; } // add edges to the sub complex @@ -152,7 +174,7 @@ public: parent_complex.add_neighbours(x, x_neigh, true); x_neigh.intersection(simplex); for (auto y : x_neigh){ - result.add_edge(parent_complex[x].get_id(), parent_complex[y].get_id()); + this->add_edge(parent_complex[x].get_id(), parent_complex[y].get_id()); } } @@ -161,8 +183,8 @@ public: // check if it is the first time we encounter the blocker if (simplex.contains(*blocker)){ Root_simplex_handle blocker_root(parent_complex.get_id(*(blocker))); - Simplex_handle blocker_restr(*result.get_simplex_address(blocker_root)); - result.add_blocker(new Simplex_handle(blocker_restr)); + Simplex_handle blocker_restr(*(this->get_simplex_address(blocker_root))); + this->add_blocker(new Simplex_handle(blocker_restr)); } } } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h index 0d870f1a..32538f38 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h @@ -1,10 +1,24 @@ -/* - * Top_faces.h - * - * Created on: Oct 23, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 TOP_FACES_H_ #define TOP_FACES_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h index 21091d10..f6f2c955 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_blockers_iterators.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h index 82025a1c..918e3473 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_iterators_out.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_ITERATORS_EDGES_H_ #define GUDHI_SKELETON_BLOCKERS_ITERATORS_EDGES_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h index cf827705..20a94734 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_iterators.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h index 5ac0f21e..0681d5da 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_simplices_iterators.h - * - * Created on: Sep 26, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_KELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h index 4b66ced5..1fdbdfc9 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_triangles_iterators.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h index 875e915a..4c90ee51 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_iterators_out.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h index b4c1cd9e..81ff0231 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -1,8 +1,23 @@ -/* - * Skeleton_blocker_complex.h +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. * - * Created on: Jan, 2014 - * Author: dsalinas + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKER_COMPLEX_H @@ -42,21 +57,7 @@ namespace skbl { /** *@class Skeleton_blocker_complex *@brief Abstract Simplicial Complex represented with a skeleton/blockers pair. - * - * A simplicial complex is completely defined by : - * - the graph of its 1-skeleton; - * - its set of blockers. - * - * The graph is a boost graph templated with SkeletonBlockerDS::Graph_vertex and SkeletonBlockerDS::Graph_edge. - * - * One can accesses to vertices via SkeletonBlockerDS::Vertex_handle, to edges via Skeleton_blocker_complex::Edge_handle and - * simplices via Skeleton_blocker_simplex<Vertex_handle>. - * - * The SkeletonBlockerDS::Root_vertex_handle serves in the case of a subcomplex (see class Skeleton_blocker_sub_complex) - * to access to the address of one vertex in the parent complex. - * - * @todo TODO Simplex_handle are not classic handle - * + *@ingroup skbl */ template<class SkeletonBlockerDS> class Skeleton_blocker_complex @@ -73,19 +74,35 @@ class Skeleton_blocker_complex public: - + /** + * @brief The type of stored vertex node, specified by the template SkeletonBlockerDS + */ typedef typename SkeletonBlockerDS::Graph_vertex Graph_vertex; + + /** + * @brief The type of stored edge node, specified by the template SkeletonBlockerDS + */ typedef typename SkeletonBlockerDS::Graph_edge Graph_edge; typedef typename SkeletonBlockerDS::Root_vertex_handle Root_vertex_handle; + + /** + * @brief The type of an handle to a vertex of the complex. + */ typedef typename SkeletonBlockerDS::Vertex_handle Vertex_handle; typedef typename Root_vertex_handle::boost_vertex_handle boost_vertex_handle; + /** + * @brief A ordered set of integers that represents a simplex. + */ typedef Skeleton_blocker_simplex<Vertex_handle> Simplex_handle; typedef Skeleton_blocker_simplex<Root_vertex_handle> Root_simplex_handle; + /** + * @brief Handle to a blocker of the complex. + */ typedef Simplex_handle* Blocker_handle; @@ -117,12 +134,12 @@ protected: public: /** - * Handle to an edge of the complex. + * @brief Handle to an edge of the complex. */ typedef typename boost::graph_traits<Graph>::edge_descriptor Edge_handle; - +protected: typedef std::multimap<Vertex_handle,Simplex_handle *> BlockerMap; typedef typename std::multimap<Vertex_handle,Simplex_handle *>::value_type BlockerPair; typedef typename std::multimap<Vertex_handle,Simplex_handle *>::iterator BlockerMapIterator; @@ -149,7 +166,6 @@ protected: //todo remove!!! -public: /** Each vertex can access to the blockers passing through it. */ BlockerMap blocker_map_; @@ -163,9 +179,12 @@ public: ///////////////////////////////////////////////////////////////////////////// - /** @name Constructors / Destructors / Initialization + /** @name Constructors, Destructors */ //@{ + /** + *@brief constructs a simplicial complex with a given number of vertices and a visitor. + */ Skeleton_blocker_complex(int num_vertices_ = 0,Visitor* visitor_=NULL):visitor(visitor_){ clear(); for (int i=0; i<num_vertices_; ++i){ @@ -277,10 +296,9 @@ private: public: /** - * @brief Constructor with a list of simplices + * @brief Constructor with a list of simplices. * @details The list of simplices must be the list - * of simplices of a simplicial complex. - *todo rewrite as iterators + * of simplices of a simplicial complex. */ Skeleton_blocker_complex(std::list<Simplex_handle>& simplices,Visitor* visitor_=NULL): num_vertices_(0),num_blockers_(0), @@ -315,7 +333,6 @@ public: } - // We cannot use the default copy constructor since we need // to make a copy of each of the blockers Skeleton_blocker_complex(const Skeleton_blocker_complex& copy){ @@ -331,6 +348,8 @@ public: } } +/** +*/ Skeleton_blocker_complex& operator=(const Skeleton_blocker_complex& copy){ clear(); visitor = NULL; @@ -354,7 +373,7 @@ public: } /** - * Clears the simplicial complex. After a call to this function, + * @details Clears the simplicial complex. After a call to this function, * blockers are destroyed. The 1-skeleton and the set of blockers * are both empty. */ @@ -371,6 +390,9 @@ public: skeleton.clear(); } +/** +*@brief allows to change the visitor. +*/ void set_visitor(Visitor* other_visitor){ visitor = other_visitor; } @@ -397,11 +419,19 @@ public: return *local; } + /** + * @brief Return the vertex node associated to local Vertex_handle. + * @remark Assume that the vertex is present in the complex. + */ Graph_vertex& operator[](Vertex_handle address){ assert(0<=address.vertex && address.vertex< boost::num_vertices(skeleton)); return skeleton[address.vertex]; } + /** + * @brief Return the vertex node associated to local Vertex_handle. + * @remark Assume that the vertex is present in the complex. + */ const Graph_vertex& operator[](Vertex_handle address) const{ assert(0<=address.vertex && address.vertex< boost::num_vertices(skeleton)); return skeleton[address.vertex]; @@ -425,7 +455,8 @@ public: /** * @brief Remove a vertex from the simplicial complex - * @remark In fact, it just deactivates the vertex. + * @remark It just deactivates the vertex with a boolean flag but does not + * remove it from vertices from complexity issues. */ void remove_vertex(Vertex_handle address){ assert(contains_vertex(address)); @@ -437,17 +468,15 @@ public: if (visitor) visitor->on_remove_vertex(address); } - /** - * @return true iff the simplicial complex contains the vertex u - */ +/** +*/ bool contains_vertex(Vertex_handle u) const{ if (u.vertex<0 || u.vertex>=boost::num_vertices(skeleton)) return false; return (*this)[u].is_active(); } - /** - * @return true iff the simplicial complex contains the vertex u - */ +/** +*/ bool contains_vertex(Root_vertex_handle u) const{ boost::optional<Vertex_handle> address = get_address(u); return address && (*this)[*address].is_active(); @@ -465,9 +494,8 @@ public: } /** - * Given an Id return the address of the vertex having this Id in the complex. - * For a simplicial complex, the address is the id but it may not be the case for a SubComplex. - * + * @brief Given an Id return the address of the vertex having this Id in the complex. + * @remark For a simplicial complex, the address is the id but it may not be the case for a SubComplex. */ virtual boost::optional<Vertex_handle> get_address(Root_vertex_handle id) const{ boost::optional<Vertex_handle> res; @@ -487,10 +515,14 @@ public: /** + * @brief Convert an address of a vertex of a complex to the address in + * the current complex. + * @details * If the current complex is a sub (or sup) complex of 'other', it converts * the address of a vertex v expressed in 'other' to the address of the vertex * v in the current one. - * @remark this methods uses Root_vertex_handle to identify the vertex + * @remark this methods uses Root_vertex_handle to identify the vertex and + * assumes the vertex is present in the current complex. */ Vertex_handle convert_handle_from_another_complex( const Skeleton_blocker_complex& other,Vertex_handle vh_in_other) const{ @@ -499,7 +531,9 @@ public: return *vh_in_current_complex; } - + /** + * @brief return the graph degree of a vertex. + */ int degree(Vertex_handle local) const{ assert(0<=local.vertex && local.vertex< boost::num_vertices(skeleton)); return degree_[local.vertex]; @@ -526,24 +560,40 @@ public: return res; } + /** + * @brief returns the stored node associated to an edge + */ Graph_edge& operator[](Edge_handle edge_handle){ return skeleton[edge_handle]; } + /** + * @brief returns the stored node associated to an edge + */ const Graph_edge& operator[](Edge_handle edge_handle) const{ return skeleton[edge_handle]; } + /** + * @brief returns the first vertex of an edge + * @details it assumes that the edge is present in the complex + */ Vertex_handle first_vertex(Edge_handle edge_handle) const{ return source(edge_handle,skeleton); } + /** + * @brief returns the first vertex of an edge + * @details it assumes that the edge is present in the complex + */ Vertex_handle second_vertex(Edge_handle edge_handle) const{ return target(edge_handle,skeleton); } /** * @brief returns the simplex made with the two vertices of the edge + * @details it assumes that the edge is present in the complex + */ Simplex_handle get_vertices(Edge_handle edge_handle) const{ auto edge((*this)[edge_handle]); @@ -551,7 +601,7 @@ public: } /** - * @brief Adds an edge between vertices a and b + * @brief Adds an edge between vertices a and b and all its cofaces. */ Edge_handle add_edge(Vertex_handle a, Vertex_handle b){ assert(contains_vertex(a) && contains_vertex(b)); @@ -573,7 +623,7 @@ public: } /** - * @brief Adds all edges of simplex sigma to the simplicial complex. + * @brief Adds all edges and their cofaces of a simplex to the simplicial complex. */ void add_edges(const Simplex_handle & sigma){ Simplex_handle_iterator i, j; @@ -583,7 +633,8 @@ public: } /** - * @brief Removes edge ab from the simplicial complex. + * @brief Removes an edge from the simplicial complex and all its cofaces. + * @details returns the former Edge_handle representing the edge */ virtual Edge_handle remove_edge(Vertex_handle a, Vertex_handle b){ bool found; @@ -602,7 +653,7 @@ public: /** - * @brief Removes edge from the simplicial complex. + * @brief Removes edge and its cofaces from the simplicial complex. */ void remove_edge(Edge_handle edge){ assert(contains_vertex(first_vertex(edge))); @@ -660,23 +711,10 @@ public: /** @name Blockers operations */ //@{ - /** - * Adds the 2-blocker abc - */ - void add_blocker(Vertex_handle a, Vertex_handle b, Vertex_handle c){ - add_blocker(Simplex_handle(a,b,c)); - } /** - * Adds the 3-blocker abcd - */ - void add_blocker(Vertex_handle a, Vertex_handle b, Vertex_handle c, Vertex_handle d){ - add_blocker(Simplex_handle(a,b,c,d)); - } - - /** - * Adds the simplex blocker_pt to the set of blockers and - * returns a Blocker_handle toward it if was not present before. + * @brief Adds the simplex to the set of blockers and + * returns a Blocker_handle toward it if was not present before and 0 otherwise. */ Blocker_handle add_blocker(const Simplex_handle& blocker){ if (contains_blocker(blocker)) @@ -700,7 +738,7 @@ public: protected: /** - * Adds the simplex s to the set of blockers + * @brief Adds the simplex to the set of blockers */ void add_blocker(Blocker_handle blocker){ if (contains_blocker(*blocker)) @@ -744,8 +782,8 @@ protected: public: /** - * Removes the simplex sigma from the set of blockers. - * sigma has to belongs to the set of blockers + * @brief Removes the simplex from the set of blockers. + * @remark sigma has to belongs to the set of blockers */ void remove_blocker(const Blocker_handle sigma){ for (auto vertex : *sigma){ @@ -758,7 +796,7 @@ public: /** - * Remove all blockers, in other words, it expand the simplicial + * @brief Remove all blockers, in other words, it expand the simplicial * complex to the smallest flag complex that contains it. */ void remove_blockers(){ @@ -850,17 +888,9 @@ private: - - ///////////////////////////////////////////////////////////////////////////// - /** @name Neighbourhood access - */ - //@{ - -public: +protected: /** - * @brief Adds to simplex n the neighbours of v: - * \f$ n \leftarrow n \cup N(v) \f$. - * + * @details Adds to simplex the neighbours of v e.g. \f$ n \leftarrow n \cup N(v) \f$. * If keep_only_superior is true then only vertices that are greater than v are added. */ virtual void add_neighbours(Vertex_handle v, Simplex_handle & n,bool keep_only_superior=false) const{ @@ -876,34 +906,25 @@ public: } /** - * @brief Add to simplex res all vertices which are + * @details Add to simplex res all vertices which are * neighbours of alpha: ie \f$ res \leftarrow res \cup N(alpha) \f$. * * If 'keep_only_superior' is true then only vertices that are greater than alpha are added. - * * todo revoir * */ virtual void add_neighbours(const Simplex_handle &alpha, Simplex_handle & res,bool keep_only_superior=false) const{ res.clear(); - // ---------------------------- - // Compute vertices in the link - // we compute the intersection of N(alpha_i) and store it in n - // ---------------------------- auto alpha_vertex = alpha.begin(); add_neighbours(*alpha_vertex,res,keep_only_superior); for (alpha_vertex = (alpha.begin())++ ; alpha_vertex != alpha.end() ; ++alpha_vertex) - { keep_neighbours(*alpha_vertex,res,keep_only_superior); - } } /** - * @brief Eliminates from simplex n all vertices which are - * not neighbours of v: \f$ res \leftarrow res \cap N(v) \f$. - * + * @details Remove from simplex n all vertices which are + * not neighbours of v e.g. \f$ res \leftarrow res \cap N(v) \f$. * If 'keep_only_superior' is true then only vertices that are greater than v are keeped. - * */ virtual void keep_neighbours(Vertex_handle v, Simplex_handle& res,bool keep_only_superior=false) const{ Simplex_handle nv; @@ -912,32 +933,26 @@ public: } /** - * @brief Eliminates from simplex n all vertices which are - * neighbours of v: \f$ res \leftarrow res \setminus N(v) \f$. - * + * @details Remove from simplex all vertices which are + * neighbours of v eg \f$ res \leftarrow res \setminus N(v) \f$. * If 'keep_only_superior' is true then only vertices that are greater than v are added. - * */ virtual void remove_neighbours(Vertex_handle v, Simplex_handle & res,bool keep_only_superior=false) const{ Simplex_handle nv; add_neighbours(v,nv,keep_only_superior); res.difference(nv); } - //@} - ///////////////////////////////////////////////////////////////////////////// - /** @name Operations on the simplicial complex - */ - //@{ public: /** * @brief Compute the local vertices of 's' in the current complex * If one of them is not present in the complex then the return value is uninitialized. * - * xxx rename get_address et place un using dans sub_complex + * */ + //xxx rename get_address et place un using dans sub_complex boost::optional<Simplex_handle> get_simplex_address(const Root_simplex_handle& s) const { boost::optional<Simplex_handle> res; @@ -1002,8 +1017,9 @@ public: /* * @brief returns the number of edges in the complex. - * todo in O(n), cache the value + * @details currently in O(n) */ + // todo cache the value int num_edges() const{ return boost::num_edges(skeleton); } @@ -1031,22 +1047,6 @@ public: return boost::connected_components(this->skeleton,&component[0]) - num_vert_collapsed; } - - //todo remove - // do - void keep_only_largest_cc(){ - std::vector<unsigned> component(skeleton.vertex_set().size()); - boost::connected_components(this->skeleton,&component[0]); - auto maxCC = min_element(component.begin(),component.end()); - for (unsigned i = 0; i != component.size(); ++i){ - if(component[i]!=*maxCC){ - if(this->contains_vertex(Vertex_handle(i))) - this->remove_vertex(Vertex_handle(i)); - } - } - } - - /** * @brief %Test if the complex is a cone. * @details Runs in O(n) where n is the number of vertices. @@ -1154,6 +1154,7 @@ private: public: typedef Triangle_around_vertex_iterator<Skeleton_blocker_complex,Superior_link> Superior_triangle_around_vertex_iterator; + typedef boost::iterator_range < Triangle_around_vertex_iterator<Skeleton_blocker_complex,Link> > Complex_triangle_around_vertex_range; /** @@ -1222,6 +1223,9 @@ public: typedef boost::iterator_range < Complex_simplex_iterator > Complex_simplex_range; + /** + * @brief Returns a Complex_simplex_range over all the simplices of the complex + */ Complex_simplex_range simplex_range() const { Complex_simplex_iterator end(this,true); @@ -1264,7 +1268,9 @@ private: public: - + /** + * @brief Returns a range of the blockers of the complex passing through a vertex + */ Complex_blocker_around_vertex_range blocker_range(Vertex_handle v) { auto begin = Complex_blocker_around_vertex_iterator(blocker_map_.lower_bound(v)); @@ -1273,7 +1279,7 @@ public: } /** - * @brief Returns a Complex_blocker_around_vertex_range over all blockers of the complex adjacent to the vertex v. + * @brief Returns a range of the blockers of the complex passing through a vertex */ Const_complex_blocker_around_vertex_range const_blocker_range(Vertex_handle v) const { @@ -1309,7 +1315,9 @@ private: public: - + /** + * @brief Returns a range of the blockers of the complex + */ Complex_blocker_range blocker_range() { auto begin = Complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end() ); @@ -1317,7 +1325,9 @@ public: return Complex_blocker_range(begin,end); } - + /** + * @brief Returns a range of the blockers of the complex + */ Const_complex_blocker_range const_blocker_range() const { auto begin = Const_complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end() ); @@ -1339,6 +1349,7 @@ public: */ //@{ public: + std::string to_string() const{ std::ostringstream stream; stream<<num_vertices()<<" vertices:\n"<<vertices_to_string()<<std::endl; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h index 924b653c..4dbabd60 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_geometric_complex.h - * - * Created on: Feb 11, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ #define SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ @@ -22,7 +36,7 @@ namespace skbl { /** * @brief Class that represents a geometric complex that can be simplified. * The class allows access to points of vertices. - * + * @ingroup skbl */ template<typename SkeletonBlockerGeometricDS> class Skeleton_blocker_geometric_complex : public Skeleton_blocker_simplifiable_complex<SkeletonBlockerGeometricDS> @@ -46,9 +60,10 @@ public: /** * @brief Add a vertex to the complex with its associated point. */ - void add_vertex(const Point& point){ + Vertex_handle add_vertex(const Point& point){ Vertex_handle ad = SimplifiableSkeletonblocker::add_vertex(); (*this)[ad].point() = point; + return ad; } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h index 29c0691b..f3ebfa60 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_link_complex.h - * - * Created on: Feb 7, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_LINK_COMPLEX_H_ #define GUDHI_SKELETON_BLOCKERS_LINK_COMPLEX_H_ @@ -22,6 +36,7 @@ template<class ComplexType> class Skeleton_blocker_sub_complex; * \brief Class representing the link of a simplicial complex encoded by a skeleton/blockers pair. * It inherits from Skeleton_blocker_sub_complex because such complex is a sub complex of a * root complex. + * \ingroup skbl */ template<typename ComplexType> class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex<ComplexType> diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h index 4f9060ef..1a51e709 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_simplifiable_complex.h - * - * Created on: Feb 4, 2014 - * Author: dsalinas - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_SKELETON_BLOCKERS_SIMPLIFIABLE_COMPLEX_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLIFIABLE_COMPLEX_H_ @@ -17,6 +31,8 @@ namespace skbl { /** * \brief Class that allows simplification operation on a simplicial complex represented * by a skeleton/blockers pair. + * \ingroup skbl + * @extends Skeleton_blocker_complex */ template<typename SkeletonBlockerDS> class Skeleton_blocker_simplifiable_complex : public Skeleton_blocker_complex<SkeletonBlockerDS> diff --git a/src/Skeleton_blocker/test/TestSimplifiable.cpp b/src/Skeleton_blocker/test/TestSimplifiable.cpp index 9f802463..2dafda52 100644 --- a/src/Skeleton_blocker/test/TestSimplifiable.cpp +++ b/src/Skeleton_blocker/test/TestSimplifiable.cpp @@ -1,9 +1,24 @@ -/* - * TestSimplifiable.cxx - * - * Created on: Feb 4, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <stdio.h> @@ -59,8 +74,8 @@ bool test_contraction1(){ Complex complex(n); build_complete(n,complex); complex.remove_edge(Vertex_handle(b),Vertex_handle(z)); - complex.add_blocker(Vertex_handle(a),Vertex_handle(x),Vertex_handle(y)); - complex.add_blocker(Vertex_handle(b),Vertex_handle(x),Vertex_handle(y)); + complex.add_blocker(Simplex_handle(Vertex_handle(a),Vertex_handle(x),Vertex_handle(y))); + complex.add_blocker(Simplex_handle(Vertex_handle(b),Vertex_handle(x),Vertex_handle(y))); // Print result cerr << "complex before complex"<< complex.to_string()<<endl; @@ -121,7 +136,7 @@ bool test_link_condition1(){ Complex complex(0); // Build the complexes build_complete(4,complex); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); // Print result @@ -168,7 +183,7 @@ bool test_collapse2(){ complex.add_edge(Vertex_handle(1),Vertex_handle(4)); complex.add_edge(Vertex_handle(2),Vertex_handle(4)); complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_blocker(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4)); + complex.add_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4))); // Print result cerr << "initial complex :\n"<< complex.to_string(); cerr <<endl<<endl; @@ -191,7 +206,7 @@ bool test_collapse3(){ complex.add_edge(Vertex_handle(1),Vertex_handle(4)); complex.add_edge(Vertex_handle(2),Vertex_handle(4)); complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_blocker(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4)); + complex.add_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4))); // Print result cerr << "initial complex:\n"<< complex.to_string(); cerr <<endl<<endl; diff --git a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp b/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp index c89f84e2..f7bf289a 100644 --- a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp +++ b/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp @@ -1,3 +1,24 @@ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <stdio.h> #include <stdlib.h> #include <string> @@ -203,7 +224,7 @@ bool test_iterator_triangles(){ complex.add_vertex(); complex.add_edge(Vertex_handle(4),Vertex_handle(7)); complex.add_edge(Vertex_handle(3),Vertex_handle(7)); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(6)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(6))); num_triangles_seen=0; TEST("triangles (should be 6 of them):"); @@ -234,7 +255,7 @@ bool test_iterator_simplices(){ complex.add_edge(Vertex_handle(4),Vertex_handle(5)); complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_blocker(Vertex_handle(2),Vertex_handle(3),Vertex_handle(4),Vertex_handle(5)); + complex.add_blocker(Simplex_handle(Vertex_handle(2),Vertex_handle(3),Vertex_handle(4),Vertex_handle(5))); bool correct_number_simplices = true; @@ -301,7 +322,7 @@ bool test_iterator_simplices3(){ complex.add_edge(Vertex_handle(0),Vertex_handle(1)); complex.add_edge(Vertex_handle(1),Vertex_handle(2)); complex.add_edge(Vertex_handle(2),Vertex_handle(0)); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); unsigned num_simplices = 0 ; @@ -449,7 +470,7 @@ bool test_link2(){ for (int j=i+1;j<15;j++) complex.add_edge(Vertex_handle(i),Vertex_handle(j)); } - complex.add_blocker(Vertex_handle(10),Vertex_handle(11),Vertex_handle(13)); + complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(11),Vertex_handle(13))); alpha = Simplex_handle(Vertex_handle(12),Vertex_handle(14)); Skeleton_blocker_link_complex<Complex> L(complex,alpha); // Complexes built @@ -487,7 +508,7 @@ bool test_link3(){ for (int j=i+1;j<15;j++) complex.add_edge(Vertex_handle(i),Vertex_handle(j)); } - complex.add_blocker(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12)); + complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12))); alpha = Simplex_handle(Vertex_handle(12),Vertex_handle(14)); Skeleton_blocker_link_complex<Complex> L(complex,alpha); // Complexes built @@ -519,7 +540,7 @@ bool test_link4(){ for (int j=i+1;j<15;j++) complex.add_edge(Vertex_handle(i),Vertex_handle(j)); } - complex.add_blocker(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12),Vertex_handle(13)); + complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12),Vertex_handle(13))); Simplex_handle alpha(Vertex_handle(12),Vertex_handle(14)); Skeleton_blocker_link_complex<Complex> L(complex,alpha); // Complexes built @@ -544,7 +565,7 @@ bool test_link5(){ Complex complex(0,new Print_complex_visitor<Vertex_handle>()); // Build the complexes build_complete(4,complex); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2),Vertex_handle(3)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); Simplex_handle alpha(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); @@ -564,7 +585,7 @@ bool test_link6(){ Complex complex(0,new Print_complex_visitor<Vertex_handle>()); // Build the complexes build_complete(4,complex); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); Simplex_handle alpha(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); @@ -593,8 +614,8 @@ bool test_link7(){ complex.add_edge(Vertex_handle(i),Vertex_handle(7)); } complex.add_edge(Vertex_handle(6),Vertex_handle(7)); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); - complex.add_blocker(Vertex_handle(3),Vertex_handle(4),Vertex_handle(5)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); + complex.add_blocker(Simplex_handle(Vertex_handle(3),Vertex_handle(4),Vertex_handle(5))); Simplex_handle alpha(Vertex_handle(3),Vertex_handle(4),Vertex_handle(5)); diff --git a/src/common/doc/Gudhi_banner.jpg b/src/common/doc/Gudhi_banner.jpg Binary files differnew file mode 100644 index 00000000..ebd3d8af --- /dev/null +++ b/src/common/doc/Gudhi_banner.jpg diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index 4e36066f..b640ea7b 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -1,20 +1,38 @@ /** \mainpage +\image html "Gudhi_banner.jpg" "" width=20cm + The Gudhi library (Geometric Understanding in Higher Dimensions) is a generic C++ library for -computational topology. Its goal is to provide robust, efficient, flexible and easy to use +topological analysis of high-dimensional data whose goal is to provide robust, efficient, flexible and easy to use implementations of -state-of-the-art algorithms and data structures for computational topology. We refer to +state-of-the-art algorithms and data structures for computational topology. + +The current release of the library allows to use several data-structures for simplicial complexes : +simplex tree, Hasse diagram or skeleton-blocker. Several operations can then be done on top of these +representations such a spersistent homology computation or simplification. + +All data-structures are generic and several of their aspects (such as stored elements, policies) +can be parametrized via template classes. + +We refer to \cite gudhilibrary_ICMS14 for a detailed description of the design of the library. -The current release of the library allows the user to construct representations of simplicial complexes -- -simplex tree or Hasse diagram -- from a point -cloud (Rips complex) or -a list of simplices, and to compute their persistent homology with coefficients in a field -\f$\mathbb{Z}/p\mathbb{Z}\f$ (for an arbitrary prime \f$p\f$), or simultaneously with coefficients -in a family of fields (multi-field persistent homology). +\section Compiling + +The library uses c++11 and requires Boost with version 1.48.0 or more recent : http://www.boost.org/. +Some packages require additional libraries : +\li the multi-field persistent homology algorithm has an optional dependency with GMP +\li Qt demos require CGAL, Qt4 and QGLViewer + +The procedure to install these packages according to your operating system is +detailled here http://doc.cgal.org/latest/Manual/installation.html + +The library compiles in Linux and Mac OSX. + +\section d Demos and Examples To build the library, run the following in a terminal: @@ -26,27 +44,13 @@ cmake -DCMAKE_BUILD_TYPE=Release .. make \endverbatim -The library has dependencies with Boost 1.48.0 or more recent (required): http://www.boost.org/ -and with GMP: https://gmplib.org/ The dependency with GMP is optional, and is used only for the -multi-field persistent homology algorithm. - - -We provide example files: run these examples with -h for details on their use, and read the README file. - -\li <CODE>rips_persistence.cpp</CODE> computes the Rips complex of a point cloud and its persistence diagram. -\li <CODE>rips_multifield_persistence.cpp</CODE> computes the Rips complex of a point cloud and its persistence diagram -with a family of field coefficients. -\li <CODE>performance_rips_persistence.cpp</CODE> provides timings for the construction of the Rips complex on a set of -points sampling a Klein bottle in \f$\mathbb{R}^5\f$ with a simplex tree, its conversion to a -Hasse diagram and the computation of persistent homology and multi-field persistent homology for the -different representations. \details \copyright GNU General Public License v3. -\verbatim Contact: ClĂ©ment Maria, clement.maria@inria.fr \endverbatim +\verbatim Contact: gudhi-devel@lists.gforge.inria.fr \endverbatim */
\ No newline at end of file diff --git a/src/common/include/gudhi/Clock.h b/src/common/include/gudhi/Clock.h index ea21659e..08096c05 100644 --- a/src/common/include/gudhi/Clock.h +++ b/src/common/include/gudhi/Clock.h @@ -1,9 +1,24 @@ -/* - * Clock.h - * - * Created on: Jun 17, 2014 - * Author: dsalinas - */ + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_CLOCK_H_ #define GUDHI_CLOCK_H_ diff --git a/src/common/include/gudhi/Off_reader.h b/src/common/include/gudhi/Off_reader.h index a9c64f97..e29218d8 100644 --- a/src/common/include/gudhi/Off_reader.h +++ b/src/common/include/gudhi/Off_reader.h @@ -1,8 +1,8 @@ /* * Off_reader.h * Created on: Nov 28, 2014 - * This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ + * 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): David Salinas @@ -21,7 +21,7 @@ * * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. - * + * */ @@ -113,18 +113,26 @@ private: bool is_off_file = (line.find("OFF") != std::string::npos); bool is_noff_file = (line.find("nOFF") != std::string::npos); - if(!is_off_file && !is_noff_file) return false; + if(!is_off_file && !is_noff_file) { + std::cerr << line<<std::endl; + std::cerr << "missing off header\n"; + return false; + } if(!goto_next_uncomment_line(line)) return false; std::istringstream iss(line); if(is_off_file){ off_info_.dim = 3; - if(!(iss >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)) + if(!(iss >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)){ + std::cerr << "incorrect number of vertices/faces/edges\n"; return false; + } } else - if(!(iss >> off_info_.dim >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)) + if(!(iss >> off_info_.dim >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)){ + std::cerr << "incorrect number of vertices/faces/edges\n"; return false; + } off_visitor.init(off_info_.dim,off_info_.num_vertices,off_info_.num_faces,off_info_.num_edges); return true; @@ -134,7 +142,7 @@ private: uncomment_line.clear(); do std::getline(stream_, uncomment_line); - while(uncomment_line[0] == '%'); + while(uncomment_line[0] == '%');// || uncomment_line.empty()); return (uncomment_line.size()>0 && uncomment_line[0] != '%'); } @@ -171,6 +179,19 @@ private: }; +template<typename OFFVisitor> +void read_off(const std::string& name_file_off,OFFVisitor& vis){ + std::ifstream stream(name_file_off); + if(!stream.is_open()) + std::cerr <<"could not open file \n"; + else{ + Off_reader off_reader(stream); + off_reader.read(vis); + } +} + + + } // namespace Gudhi diff --git a/src/common/include/gudhi/Utils.h b/src/common/include/gudhi/Utils.h index cef361dc..1626a0bf 100644 --- a/src/common/include/gudhi/Utils.h +++ b/src/common/include/gudhi/Utils.h @@ -1,17 +1,31 @@ -/* - * Utils.h - * - * Created on: 13 juin 2013 - * Author: salinasd - */ - + /* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 GUDHI_UTILS_H_ #define GUDHI_UTILS_H_ #define PRINT(a) std::cerr << #a << ": " << (a) << " (DISP)"<<std::endl -//#define DBG_VERBOSE +#define DBG_VERBOSE #ifdef DBG_VERBOSE #define DBG(a) std::cerr << "DBG: " << (a)<<std::endl #define DBGMSG(a,b) std::cerr << "DBG: " << a<<b<<std::endl diff --git a/src/common/include/gudhi/iofile.h b/src/common/include/gudhi/iofile.h deleted file mode 100644 index b939d45b..00000000 --- a/src/common/include/gudhi/iofile.h +++ /dev/null @@ -1,236 +0,0 @@ -//todo remove and use off_reader instead - -#ifndef GUDHI_IOFILE_H_ -#define GUDHI_IOFILE_H_ - -#include <iostream> -#include <fstream> -#include <sstream> -#include <vector> -#include <cstdio> -#include <cstring> -#include <list> -#include <cassert> - - - -//todo use my new visitor based off instead -/** - * @brief OFF reader, save the content of the file (vertices and maximal faces) in 'complex'. - * The class Complex has to handle the following operations: - * - void add_vertex(double[dim],int dim) - * - void add_face(int dimension ,int[dimension] vertices) - * Source from : http://www.holmes3d.net/graphics/offfiles/OFFLoading.txt - * - * @todo todo ignore comments in the file -> # comment - */ -template<typename Complex> inline -bool general_read_off_file(const std::string & file_name, Complex& complex){ - // Declare temporary variables to read data into. - // If the read goes well, we'll copy these into - // our class variables, overwriting what used to - // be there. If it doesn't, we won't have messed up - // our previous data structures. - int tempNumPoints = 0; // Number of x,y,z coordinate triples - int tempNumFaces = 0; // Number of polygon sets - int tempNumEdges = 0; // Unused, except for reading. - int tempDimPoints = 0; - double** tempPoints = NULL; // An array of x,y,z coordinates. - int** tempFaces = NULL; // An array of arrays of point - // pointers. Each entry in this - // is an array of integers. Each - // integer in that array is the - // index of the x, y, and z - // coordinates in the corresponding - // arrays. - int* tempFaceSizes = NULL; // An array of polygon point counts. - // Each of the arrays in the tempFaces - // array may be of different lengths. - // This array corresponds to that - // array, and gives their lengths. - int i; // Generic loop variable. - bool goodLoad = true; // Set to false if the file appears - // not to be a valid OFF file. - char tempBuf[128]; // A buffer for reading strings - // from the file. - - // Create an input file stream for the file the CArchive - // is connected to. This allows use of the overloaded - // extraction operator for conversion from string - // data to doubles and ints. - std::ifstream ifs (file_name.c_str(), std::ios::in); - if(!ifs.is_open()) { - std::cerr << "Unable to open file " << file_name << std::endl; - return false; - } - - // Grab the first string. If it's "OFF", we think this - // is an OFF file and continue. Otherwise we give up. - ifs >> tempBuf; - if (strcmp(tempBuf, "OFF") != 0) { - goodLoad = false; - std::cerr << "No OFF preambule\n"; - } - - // Read the sizes for our two arrays, and the third - // int on the line. If the important two are zero - // sized, this is a messed up OFF file. Otherwise, - // we setup our temporary arrays. - if (goodLoad) { - ifs >> tempNumPoints >> tempNumFaces >> tempNumEdges; - if (tempNumPoints < 1 || tempNumFaces < 0) { - // If either of these were negative, we make - // sure that both are set to zero. This is - // important for later deleting our temporary - // storage. - goodLoad = false; - std::cerr << "tempNumPoints < 1 || tempNumFaces < 0\n"; - tempNumPoints = 0; - tempNumFaces = 0; - } else { - tempPoints = new double*[tempNumPoints]; - tempFaces = new int*[tempNumFaces]; - tempFaceSizes = new int[tempNumFaces]; - } - } - - if (goodLoad) { - // Load all of the points. - - // we start by loading the first one - // the case is difference because then we dont know the dimension by advance - // we discover the point dimension by reading the first line - std::string lineFirstPoint; - std::getline(ifs, lineFirstPoint); - while(lineFirstPoint.size()<3){ - std::getline(ifs, lineFirstPoint); - } - - // we store the first point in a temporary list - std::istringstream lineFirstPointStream(lineFirstPoint); - std::list<double> firstTempPoint; - double coord; - while(lineFirstPointStream>>coord){ - firstTempPoint.push_back(coord); - ++tempDimPoints; - } - // we store the point in our points array - tempPoints[0]=new double[tempDimPoints]; - for( int j = 0 ; j<tempDimPoints; ++j){ - tempPoints[0][j] = firstTempPoint.front(); - firstTempPoint.pop_front(); - } - - // now, we know the dimension and can read safely other points - for (i = 1; i < tempNumPoints; i++) { - tempPoints[i] = new double[tempDimPoints]; - for (int j = 0 ; j<tempDimPoints ; ++j){ - ifs>>tempPoints[i][j]; - } - } - - // Load all of the faces. - for (i = 0; i < tempNumFaces; i++) { - // This tells us how many points make up - // this face. - ifs >> tempFaceSizes[i]; - // So we declare a new array of that size - tempFaces[i] = new int[tempFaceSizes[i]]; - // And load its elements with the vertex indices. - for (int j = 0; j < tempFaceSizes[i]; j++) { - ifs >> tempFaces[i][j]; - } - // Clear out any face color data by reading up to - // the newline. 128 is probably considerably more - // space than necessary, but better safe than - // sorry. - ifs.getline(tempBuf, 128); - } - } - - // Here is where we copy the data from the temp - // structures into our permanent structures. We - // probably will do some more processing on the - // data at the same time. This code you must fill - // in on your own. - if (goodLoad) { - // we save vertices first in the complex - for (i = 0; i < tempNumPoints; i++) - complex.add_vertex(tempPoints[i],tempDimPoints); - - // we save faces - for (i = 0; i < tempNumFaces; i++) { - for (int j = 0; j < tempFaceSizes[i]; j++) - complex.add_face(tempFaceSizes[i],tempFaces[i]); - } - } - - // Now that we're done, we have to make sure we - // free our dynamic memory. - for (i = 0; i < tempNumPoints; i++) { - delete []tempPoints[i]; - } - delete []tempPoints; - - for (i = 0; i < tempNumFaces; i++) { - delete tempFaces[i]; - } - delete []tempFaces; - delete []tempFaceSizes; - - // Clean up our ifstream. The MFC framework will - // take care of the CArchive. - ifs.close(); - - return goodLoad; -} - - -template<typename Complex> -class Geometric_flag_complex_wrapper{ - Complex& complex_; - typedef typename Complex::Vertex_handle Vertex_handle; - typedef typename Complex::Point Point; - - const bool load_only_points_; - -public: - Geometric_flag_complex_wrapper(Complex& complex,bool load_only_points = false): - complex_(complex), - load_only_points_(load_only_points) -{} - - - void add_vertex(double* xyz,int dim){ - Point p(dim); - for(int i=0;i<dim;++i) - p[i] = xyz[i]; - complex_.add_vertex(p); - } - - void add_face(int dimension ,int* vertices){ - if (!load_only_points_){ - for (int i = 0; i<dimension ; ++i) - for (int j = i+1; j<dimension ; ++j) - complex_.add_edge(Vertex_handle(vertices[i]),Vertex_handle(vertices[j])); - } - } -}; - - - - -/** - * @brief Read a mesh into a OFF file - * load_only_points should be true if only the points have to be loaded. - */ -template<typename Complex> -bool read_off_file(std::string file_name,Complex &complex,bool load_only_points = false){ - complex.clear(); - Geometric_flag_complex_wrapper<Complex> complex_wrapper(complex,load_only_points); - return general_read_off_file(file_name,complex_wrapper); - -} - - -#endif |
