TTK
Loading...
Searching...
No Matches
GabowTarjan.h
Go to the documentation of this file.
1#pragma once
2
3#include <Debug.h>
5
6#include <algorithm>
7#include <iostream>
8#include <map>
9#include <queue>
10#include <vector>
11
12namespace ttk {
13
14 class GabowTarjan : public Debug {
15
16 struct Edge {
17 int v1{};
18 int v2{};
19 double weight{};
20
21 Edge(int p1, int p2, double w) : v1{p1}, v2{p2}, weight{w} {
22 }
23
24 bool operator<(const Edge &other) const {
25 return weight < other.weight;
26 }
27 };
28
29 public:
31 this->setDebugMsgPrefix("Gabow-Tarjan");
32 }
33
34 double Distance();
35
37
38 int run(std::vector<MatchingType> &matchings);
39
40 inline void setInput(int rowSize_,
41 int colSize_,
42 std::vector<std::vector<double>> *C_) {
43 Cptr = C_;
44
45 Size1 = (unsigned int)rowSize_ - 1;
46 Size2 = (unsigned int)colSize_ - 1;
47 if(Size1 <= 0 || Size2 <= 0) {
48 this->printMsg("One or more empty diagram(s).");
49 }
50
51 MaxSize = Size1 + Size2;
52 Edges.clear();
53
54 // Connect diagonal points.
55 for(unsigned int i = Size1; i < MaxSize; ++i)
56 for(unsigned int j = MaxSize + Size2; j < 2 * MaxSize; ++j)
57 Edges.emplace_back(Edge(i, j, (double)0));
58
59 // Connect real points.
60 for(unsigned int i = 0; i < Size1; ++i) {
61 unsigned int k = MaxSize;
62 for(unsigned int j = 0; j < Size2; ++j) {
63 auto val = (*C_)[i][j];
64 Edges.emplace_back(Edge(i, k++, val));
65 }
66 }
67
68 // Connect real points with their diagonal.
69 for(unsigned int i = 0; i < Size1; ++i) {
70 auto val = (*C_)[i][Size2];
71 Edges.emplace_back(Edge(i, MaxSize + Size2 + i, val));
72 }
73
74 for(unsigned int j = 0, k = MaxSize; j < Size2; ++j, ++k) {
75 auto val = (*C_)[Size1][j];
76 Edges.emplace_back(Edge(Size1 + (k - MaxSize), k, val));
77 }
78
79 std::sort(Edges.begin(), Edges.end());
80 }
81
82 inline void clear() {
83 MaxSize = 0;
84 Size1 = 0;
85 Size2 = 0;
86 Edges.clear();
87 Pair.clear();
88 Connections.clear();
89 Layers.clear();
90 }
91
92 private:
93 // Original cost matrix.
94 std::vector<std::vector<double>> *Cptr;
95
96 /*
97 * Total number of persistencePairs
98 */
99 unsigned int MaxSize;
100 unsigned int Size1;
101 unsigned int Size2;
102
103 /*
104 * Edges between all nodes given by
105 * persistencePairs in both persistence diagrams
106 */
107 std::vector<Edge> Edges;
108
109 /*
110 * Pairing between vertices in persistence diagrams,
111 * -1 means the vertex is not paired to any other vertex.
112 * Non negative number, index of the vertex to
113 * which the given vertex is paired.
114 */
115 std::vector<int> Pair;
116
117 /*
118 * Connection matrix, gives edges between
119 * vertices in the first and second diagram
120 */
121 std::vector<std::vector<int>> Connections;
122
123 /*
124 * Layers used in the Hopcroft-Karp algorithm
125 * The layer information is required for a NIL vertex
126 * and all vertices in PersistencePairs1
127 * Hence 0 slot is used for NIL and all the vertices
128 * in PersistencePairs1 are shifted by one.
129 * So to read layer of the vertex 0 we access Layers[1]
130 */
131 std::vector<int> Layers;
132
133 bool DFS(int v);
134 bool BFS();
135
136 // Hopcroft-Karp algorithm: find a maximal matching
137 void HopcroftKarp(unsigned int &matching);
138 };
139
140} // namespace ttk
Minimalist debugging class.
Definition: Debug.h:88
void setDebugMsgPrefix(const std::string &prefix)
Definition: Debug.h:364
int printMsg(const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const
Definition: Debug.h:118
int run(std::vector< MatchingType > &matchings)
void printCurrentMatching()
void setInput(int rowSize_, int colSize_, std::vector< std::vector< double > > *C_)
Definition: GabowTarjan.h:40
The Topology ToolKit.