graph no longer static

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1790 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: 6bbb8dfaffd09a81ccafac6919e073ed74b9c7e6

5 files changed, 56 insertions, 80 deletions

diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h
index bb0a13d2..52de30be 100644
--- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h
+++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h
@@ -31,14 +31,14 @@ namespace bottleneck_distance {
 
 template<typename Persistence_diagram1, typename Persistence_diagram2>
 double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) {
-    G::initialize(diag1, diag2, 0.);
-    std::vector<double> sd(G::sorted_distances());
+    Persistence_graph g(diag1, diag2, 0.);
+    std::vector<double> sd(g.sorted_distances());
     int idmin = 0;
     int idmax = sd.size() - 1;
-    // alpha can be modified, this will change the complexity
+    // alpha can change the complexity
     double alpha = pow(sd.size(), 0.25);
-    Graph_matching m;
-    Graph_matching biggest_unperfect;
+    Graph_matching m(g);
+    Graph_matching biggest_unperfect(g);
     while (idmin != idmax) {
         int step = static_cast<int>((idmax - idmin) / alpha);
         m.set_r(sd.at(idmin + step));
@@ -64,14 +64,14 @@ template<typename Persistence_diagram1, typename Persistence_diagram2>
 double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e=0.) {
     if(e == 0.)
         return compute_exactly(diag1, diag2);
-    G::initialize(diag1, diag2, e);
-    int in = G::diameter()/e + 1;
+    Persistence_graph g(diag1, diag2, e);
+    int in = g.diameter_bound()/e + 1;
     int idmin = 0;
     int idmax = in;
-    // alpha can be modified, this will change the complexity
-    double alpha = pow(in, 0.25);
-    Graph_matching m;
-    Graph_matching biggest_unperfect;
+    // alpha can change the complexity
+    double alpha = pow(in, 0.10);
+    Graph_matching m(g);
+    Graph_matching biggest_unperfect(g);
     while (idmin != idmax) {
         int step = static_cast<int>((idmax - idmin) / alpha);
         m.set_r(e*(idmin + step));
diff --git a/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h b/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h
deleted file mode 100644
index 0959dd03..00000000
--- a/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h
+++ /dev/null
@@ -1,42 +0,0 @@
-/*    This file is part of the Gudhi Library. The Gudhi library
- *    (Geometric Understanding in Higher Dimensions) is a generic C++
- *    library for computational topology.
- *
- *    Author:       Francois Godi
- *
- *    Copyright (C) 2015  INRIA (France)
- *
- *    This program is free software: you can redistribute it and/or modify
- *    it under the terms of the GNU General Public License as published by
- *    the Free Software Foundation, either version 3 of the License, or
- *    (at your option) any later version.
- *
- *    This program is distributed in the hope that it will be useful,
- *    but WITHOUT ANY WARRANTY; without even the implied warranty of
- *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *    GNU General Public License for more details.
- *
- *    You should have received a copy of the GNU General Public License
- *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-#ifndef SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_
-#define SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_
-
-#include <gudhi/Internal_point.h>
-
-namespace CGAL {
-
-typedef Gudhi::bottleneck_distance::Internal_point Internal_point;
-
-struct Construct_coord_iterator {
-    typedef  const double* result_type;
-    const double* operator()(const Internal_point& p) const
-    { return p.vec; }
-    const double* operator()(const Internal_point& p, int)  const
-    { return p.vec+2; }
-};
-
-} //namespace CGAL
-
-#endif  // SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_
diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h
index fa20b2a2..10b7073a 100644
--- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h
+++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h
@@ -36,7 +36,7 @@ namespace bottleneck_distance {
 class Graph_matching {
 public:
     /** \internal \brief Constructor constructing an empty matching. */
-    explicit Graph_matching();
+    explicit Graph_matching(Persistence_graph &g);
     /** \internal \brief Copy operator. */
     Graph_matching& operator=(const Graph_matching& m);
     /** \internal \brief Is the matching perfect ? */
@@ -47,6 +47,7 @@ public:
     void set_r(double r);
 
 private:
+    Persistence_graph& g;
     double r;
     /** \internal \brief Given a point from V, provides its matched point in U, null_point_index() if there isn't. */
     std::vector<int> v_to_u;
@@ -61,13 +62,14 @@ private:
     void update(std::vector<int> & path);
 };
 
-inline Graph_matching::Graph_matching()
-    : r(0.), v_to_u(G::size(), null_point_index()), unmatched_in_u() {
-    for (int u_point_index = 0; u_point_index < G::size(); ++u_point_index)
+inline Graph_matching::Graph_matching(Persistence_graph& g)
+    : g(g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u() {
+    for (int u_point_index = 0; u_point_index < g.size(); ++u_point_index)
         unmatched_in_u.emplace_back(u_point_index);
 }
 
 inline Graph_matching& Graph_matching::operator=(const Graph_matching& m) {
+    g = m.g;
     r = m.r;
     v_to_u = m.v_to_u;
     unmatched_in_u = m.unmatched_in_u;
@@ -83,7 +85,7 @@ inline bool Graph_matching::multi_augment() {
         return false;
     Layered_neighbors_finder layered_nf(layering());
     int max_depth = layered_nf.vlayers_number()*2 - 1;
-    double rn = sqrt(G::size());
+    double rn = sqrt(g.size());
     // verification of a necessary criterion in order to shortcut if possible
     if (max_depth <0 || (unmatched_in_u.size() > rn && max_depth >= rn))
         return false;
@@ -130,10 +132,10 @@ inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u
 inline Layered_neighbors_finder Graph_matching::layering() const {
     std::list<int> u_vertices(unmatched_in_u);
     std::list<int> v_vertices;
-    Neighbors_finder nf(r);
-    for (int v_point_index = 0; v_point_index < G::size(); ++v_point_index)
+    Neighbors_finder nf(g, r);
+    for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index)
         nf.add(v_point_index);
-    Layered_neighbors_finder layered_nf(r);
+    Layered_neighbors_finder layered_nf(g, r);
     for(int layer = 0; !u_vertices.empty(); layer++) {
         // one layer is one step in the BFS
         for (auto it1 = u_vertices.cbegin(); it1 != u_vertices.cend(); ++it1) {
diff --git a/src/Bottleneck_distance/include/gudhi/Internal_point.h b/src/Bottleneck_distance/include/gudhi/Internal_point.h
index 78aad470..1a050d48 100644
--- a/src/Bottleneck_distance/include/gudhi/Internal_point.h
+++ b/src/Bottleneck_distance/include/gudhi/Internal_point.h
@@ -35,7 +35,7 @@ struct Internal_point {
     double vec[2];
     int point_index;
     Internal_point() {}
-    Internal_point(double x, double y, int p_i = null_point_index()) { vec[0]=x; vec[1]=y; point_index = p_i; }
+    Internal_point(double x, double y, int p_i) { vec[0]=x; vec[1]=y; point_index = p_i; }
     double x() const { return vec[ 0 ]; }
     double y() const { return vec[ 1 ]; }
     double& x() { return vec[ 0 ]; }
@@ -44,7 +44,7 @@ struct Internal_point {
     {
         return point_index==p.point_index;
     }
-    bool  operator!=(const Internal_point& p) const { return ! (*this == p); }
+    bool  operator!=(const Internal_point& p) const { return !(*this == p); }
 };
 
 inline int null_point_index() {
@@ -55,4 +55,18 @@ inline int null_point_index() {
 
 }  // namespace Gudhi
 
+namespace CGAL {
+
+typedef Gudhi::bottleneck_distance::Internal_point Internal_point;
+
+struct Construct_coord_iterator {
+    typedef  const double* result_type;
+    const double* operator()(const Internal_point& p) const
+    { return p.vec; }
+    const double* operator()(const Internal_point& p, int)  const
+    { return p.vec+2; }
+};
+
+} //namespace CGAL
+
 #endif  // INTERNAL_POINT_H_
diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h
index f2d9abb2..f28e21a2 100644
--- a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h
+++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h
@@ -31,8 +31,8 @@
 #include <CGAL/Weighted_Minkowski_distance.h>
 #include <CGAL/Search_traits.h>
 
-#include <gudhi/Persistence_diagrams_graph.h>
-#include <gudhi/Construct_coord_iterator.h>
+#include <gudhi/Persistence_graph.h>
+#include <gudhi/Internal_point.h>
 
 #include <unordered_set>
 
@@ -57,7 +57,7 @@ class Neighbors_finder {
 
 public:
     /** \internal \brief Constructor taking the near distance definition as parameter. */
-    Neighbors_finder(double r);
+    Neighbors_finder(const Persistence_graph& g, double r);
     /** \internal \brief A point added will be possibly pulled. */
     void add(int v_point_index);
     /** \internal \brief Returns and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */
@@ -66,6 +66,7 @@ public:
     std::vector<int> pull_all_near(int u_point_index);
 
 private:
+    const Persistence_graph& g;
     const double r;
     Kd_tree kd_t;
     std::unordered_set<int> projections_f;
@@ -81,7 +82,7 @@ private:
 class Layered_neighbors_finder {
 public:
     /** \internal \brief Constructor taking the near distance definition as parameter. */
-    Layered_neighbors_finder(double r);
+    Layered_neighbors_finder(const Persistence_graph& g, double r);
     /** \internal \brief A point added will be possibly pulled. */
     void add(int v_point_index, int vlayer);
     /** \internal \brief Returns and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */
@@ -90,43 +91,44 @@ public:
     int vlayers_number() const;
 
 private:
+    const Persistence_graph& g;
     const double r;
     std::vector<std::shared_ptr<Neighbors_finder>> neighbors_finder;
 };
 
-inline Neighbors_finder::Neighbors_finder(double r) :
-    r(r), kd_t(), projections_f() { }
+inline Neighbors_finder::Neighbors_finder(const Persistence_graph& g, double r) :
+    g(g), r(r), kd_t(), projections_f() { }
 
 inline void Neighbors_finder::add(int v_point_index) {
-    if (G::on_the_v_diagonal(v_point_index))
+    if (g.on_the_v_diagonal(v_point_index))
         projections_f.emplace(v_point_index);
     else
-        kd_t.insert(G::get_v_point(v_point_index));
+        kd_t.insert(g.get_v_point(v_point_index));
 }
 
 inline int Neighbors_finder::pull_near(int u_point_index) {
     int tmp;
-    int c = G::corresponding_point_in_v(u_point_index);
-    if (G::on_the_u_diagonal(u_point_index) && !projections_f.empty()){
+    int c = g.corresponding_point_in_v(u_point_index);
+    if (g.on_the_u_diagonal(u_point_index) && !projections_f.empty()){
         //Any pair of projection is at distance 0
         tmp = *projections_f.cbegin();
         projections_f.erase(tmp);
     }
-    else if (projections_f.count(c) && (G::distance(u_point_index, c) <= r)){
+    else if (projections_f.count(c) && (g.distance(u_point_index, c) <= r)){
         //Is the query point near to its projection ?
         tmp = c;
         projections_f.erase(tmp);
     }
     else{
         //Is the query point near to a V point in the plane ?
-        Internal_point u_point = G::get_u_point(u_point_index);
+        Internal_point u_point = g.get_u_point(u_point_index);
         std::vector<double> w = {1., 1.};
         K_neighbor_search search(kd_t, u_point, 0., true, Distance(0, 2, w));
         auto it = search.begin();
-        if(it==search.end() || G::distance(u_point_index, it->first.point_index) > r)
+        if(it==search.end() || g.distance(u_point_index, it->first.point_index) > r)
             return null_point_index();
         tmp = it->first.point_index;
-        kd_t.remove(G::get_v_point(tmp));
+        kd_t.remove(g.get_v_point(tmp));
     }
     return tmp;
 }
@@ -141,12 +143,12 @@ inline std::vector<int> Neighbors_finder::pull_all_near(int u_point_index) {
     return all_pull;
 }
 
-inline Layered_neighbors_finder::Layered_neighbors_finder(double r) :
-    r(r), neighbors_finder() { }
+inline Layered_neighbors_finder::Layered_neighbors_finder(const Persistence_graph& g, double r) :
+    g(g), r(r), neighbors_finder() { }
 
 inline void Layered_neighbors_finder::add(int v_point_index, int vlayer) {
     for (int l = neighbors_finder.size(); l <= vlayer; l++)
-        neighbors_finder.emplace_back(std::shared_ptr<Neighbors_finder>(new Neighbors_finder(r)));
+        neighbors_finder.emplace_back(std::shared_ptr<Neighbors_finder>(new Neighbors_finder(g, r)));
     neighbors_finder.at(vlayer)->add(v_point_index);
 }