23 #ifndef GRAPH_MATCHING_H_ 24 #define GRAPH_MATCHING_H_ 26 #include <gudhi/Neighbors_finder.h> 29 #include <unordered_set> 34 namespace persistence_diagram {
40 class Graph_matching {
43 explicit Graph_matching(Persistence_graph &g);
52 Persistence_graph* gp;
55 std::vector<int> v_to_u;
57 std::unordered_set<int> unmatched_in_u;
60 Layered_neighbors_finder layering()
const;
62 bool augment(Layered_neighbors_finder & layered_nf,
int u_start_index,
int max_depth);
64 void update(std::vector<int> & path);
67 inline Graph_matching::Graph_matching(Persistence_graph& g)
68 : gp(&g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u(g.size()) {
69 for (
int u_point_index = 0; u_point_index < g.size(); ++u_point_index)
70 unmatched_in_u.insert(u_point_index);
73 inline bool Graph_matching::perfect()
const {
74 return unmatched_in_u.empty();
77 inline bool Graph_matching::multi_augment() {
80 Layered_neighbors_finder layered_nf(layering());
81 int max_depth = layered_nf.vlayers_number()*2 - 1;
82 double rn = sqrt(gp->size());
84 if (max_depth < 0 || (unmatched_in_u.size() > rn && max_depth >= rn))
86 bool successful =
false;
87 std::vector<int> tries(unmatched_in_u.cbegin(), unmatched_in_u.cend());
88 for (
auto it = tries.cbegin(); it != tries.cend(); it++)
90 successful = augment(layered_nf, *it, max_depth) || successful;
94 inline void Graph_matching::set_r(
double r) {
98 inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf,
int u_start_index,
int max_depth) {
100 std::vector<int> path;
101 path.emplace_back(u_start_index);
103 if (static_cast<int> (path.size()) > max_depth) {
109 path.emplace_back(layered_nf.pull_near(path.back(),
static_cast<int> (path.size()) / 2));
110 while (path.back() == null_point_index()) {
116 path.emplace_back(layered_nf.pull_near(path.back(), path.size() / 2));
118 path.emplace_back(v_to_u.at(path.back()));
119 }
while (path.back() != null_point_index());
126 inline Layered_neighbors_finder Graph_matching::layering()
const {
127 std::vector<int> u_vertices(unmatched_in_u.cbegin(), unmatched_in_u.cend());
128 std::vector<int> v_vertices;
129 Neighbors_finder nf(*gp, r);
130 for (
int v_point_index = 0; v_point_index < gp->size(); ++v_point_index)
131 nf.add(v_point_index);
132 Layered_neighbors_finder layered_nf(*gp, r);
133 for (
int layer = 0; !u_vertices.empty(); layer++) {
135 for (
auto it1 = u_vertices.cbegin(); it1 != u_vertices.cend(); ++it1) {
136 std::vector<int> u_succ(nf.pull_all_near(*it1));
137 for (
auto it2 = u_succ.begin(); it2 != u_succ.end(); ++it2) {
138 layered_nf.add(*it2, layer);
139 v_vertices.emplace_back(*it2);
145 for (
auto it = v_vertices.cbegin(); it != v_vertices.cend(); it++)
146 if (v_to_u.at(*it) == null_point_index())
150 u_vertices.emplace_back(v_to_u.at(*it));
159 inline void Graph_matching::update(std::vector<int>& path) {
161 unmatched_in_u.erase(path.front());
162 for (
auto it = path.cbegin(); it != path.cend(); ++it) {
165 v_to_u[*(++it)] = tmp;
174 #endif // GRAPH_MATCHING_H_ Definition: SimplicialComplexForAlpha.h:26