summaryrefslogtreecommitdiff
path: root/src/Collapse
diff options
context:
space:
mode:
authorROUVREAU Vincent <vincent.rouvreau@inria.fr>2020-04-05 09:00:44 +0200
committerROUVREAU Vincent <vincent.rouvreau@inria.fr>2020-04-05 09:00:44 +0200
commit44090f837b402941b345631a2ef92b3f9c88a738 (patch)
tree06e1b9d82cd5977fd4210124c58a69011b920964 /src/Collapse
parentc23490a73bca4208af68f741d1e3e0a505f22411 (diff)
Some cleanup
Diffstat (limited to 'src/Collapse')
-rw-r--r--src/Collapse/include/gudhi/FlagComplexSpMatrix.h433
1 files changed, 5 insertions, 428 deletions
diff --git a/src/Collapse/include/gudhi/FlagComplexSpMatrix.h b/src/Collapse/include/gudhi/FlagComplexSpMatrix.h
index ac02a46f..20db7fae 100644
--- a/src/Collapse/include/gudhi/FlagComplexSpMatrix.h
+++ b/src/Collapse/include/gudhi/FlagComplexSpMatrix.h
@@ -116,16 +116,6 @@ class FlagComplexSpMatrix {
*/
MapVertexToIndex vertexToRow;
- //! Stores the number of vertices in the original Simplicial Complex.
- /*!
- This stores the count of vertices (which is also the number of rows in the Matrix).
- */
- std::size_t rows;
-
- std::size_t numOneSimplices;
-
- std::size_t numDomEdge;
-
//! Stores the Sparse matrix of double values representing the Original Simplicial Complex.
/*!
\code
@@ -167,155 +157,23 @@ class FlagComplexSpMatrix {
// Stores the indices from the sorted filtered edge vector.
// std::set<std::size_t> recurCriticalCoreIndcs;
- //! Stores <I>true</I> if the current row is inserted in the queue <B>rowIterator<B> otherwise its value is
- //! <I>false<I>.
+ //! Stores the number of vertices in the original Simplicial Complex.
/*!
- Initialised to a boolean vector of length equal to the value of the variable <B>rows</B> with all <I>true</I>
- values. Subsequent removal/addition of a row from <B>rowIterator<B> is reflected by concerned entries changing to
- <I>false</I>/<I>true</I> in this vector.
+ This stores the count of vertices (which is also the number of rows in the Matrix).
*/
- boolVector rowInsertIndicator; //(current iteration row insertion indicator)
+ std::size_t rows;
- //! Map that stores the Reduction / Collapse of vertices.
- /*!
- \code
- Map = std::unordered_map<Vertex,Vertex>
- \endcode
- This is empty to begin with. As and when collapses are done (let's say from dominated vertex <I>v</I> to dominating
- vertex <I>v'</I>) : <br> <B>ReductionMap</B>[<I>v</I>] = <I>v'</I> is entered into the map. <br> <I>This does not
- store uncollapsed vertices. What it means is that say vertex <I>x</I> was never collapsed onto any other vertex.
- Then, this map <B>WILL NOT</B> have any entry like <I>x</I> -> <I>x</I>. Basically, it will have no entry
- corresponding to vertex <I>x</I> at all. </I>
- */
- Map ReductionMap;
+ std::size_t numOneSimplices;
- bool vertexCollapsed;
bool edgeCollapsed;
- // Variable to indicate if filtered-edge-collapse has to be performed.
- int expansion_limit;
void init() {
- rowToVertex.clear();
- vertexToRow.clear();
- oneSimplices.clear();
- ReductionMap.clear();
-
- vertDomnIndicator.clear();
- rowInsertIndicator.clear();
- rowIterator.push(0);
- rowIterator.pop();
-
- filteredEgdeIter.push({{0, 0}, 0});
- filteredEgdeIter.pop();
- fEgdeVector.clear();
-
rows = 0;
- numDomEdge = 0;
numOneSimplices = 0;
- expansion_limit = 2;
-
- vertexCollapsed = false;
edgeCollapsed = false;
}
- //! Function for computing the sparse-matrix corresponding to the core of the complex. It also prepares the working
- //!list filteredEgdeIter for edge collapses
- void after_vertex_collapse() {
- sparse_colpsd_adj_Matrix = new sparseRowMatrix(rows, rows); // Just for debugging purpose.
- oneSimplices.clear();
- if (not filteredEgdeIter.empty()) {
- std::cout << "Working list for edge collapses are not empty before the edge-collapse." << std::endl;
- }
- for (std::size_t rw = 0; rw < rows; ++rw) {
- if (not vertDomnIndicator[rw]) // If the current column is not dominated
- {
- auto nbhrs_to_insert = closed_neighbours_row_index(rw); // returns row indices of the non-dominated vertices.
- for (auto& v : nbhrs_to_insert) {
- sparse_colpsd_adj_Matrix->insert(rw, v) = 1; // This creates the full matrix
- if (rw < v) {
- oneSimplices.push_back({rowToVertex[rw], rowToVertex[v]});
- filteredEgdeIter.push({{rw, v}, 1});
- // if(rw == v)
- // std::cout << "Pushed the edge {" << rw << ", " << v << "} " << std::endl;
- }
- }
- }
- }
- // std::cout << "Total number of non-zero elements before domination check are: " <<
- // sparse_colpsd_adj_Matrix->nonZeros() << std::endl; std::cout << "Total number of edges for domination check are:
- // " << filteredEgdeIter.size() << std::endl;
- // std::cout << *sparse_colpsd_adj_Matrix << std::endl;
- return;
- }
-
- //! Function to fully compact a particular vertex of the ReductionMap.
- /*!
- It takes as argument the iterator corresponding to a particular vertex pair (key-value) stored in the ReductionMap.
- <br> It then checks if the second element of this particular vertex pair is present as a first element of some other
- key-value pair in the map. If no, then the first element of the vertex pair in consideration is fully compact. If
- yes, then recursively call fully_compact_this_vertex() on the second element of the original pair in consideration
- and assign its resultant image as the image of the first element of the original pair in consideration as well.
- */
- void fully_compact_this_vertex(Map::iterator iter) {
- Map::iterator found = ReductionMap.find(iter->second);
- if (found == ReductionMap.end()) return;
-
- fully_compact_this_vertex(found);
- iter->second = ReductionMap[iter->second];
- }
-
- //! Function to fully compact the Reduction Map.
- /*!
- While doing strong collapses, we store only the immediate collapse of a vertex. Which means that in one round,
- vertex <I>x</I> may collapse to vertex <I>y</I>. And in some later round it may be possible that vertex <I>y</I>
- collapses to <I>z</I>. In which case our map stores : <br> <I>x</I> -> <I>y</I> and also <I>y</I> -> <I>z</I>. But
- it really should store : <I>x</I> -> <I>z</I> and <I>y</I> -> <I>z</I>. This function achieves the same. <br> It
- basically calls fully_compact_this_vertex() for each entry in the map.
- */
- void fully_compact() {
- Map::iterator it = ReductionMap.begin();
- while (it != ReductionMap.end()) {
- fully_compact_this_vertex(it);
- it++;
- }
- }
-
- void sparse_strong_vertex_collapse() {
- complete_vertex_domination_check(
- rowIterator, rowInsertIndicator,
- vertDomnIndicator); // Complete check for rows in rowIterator, rowInsertIndicator is a list of boolean
- // indicator if a vertex is already inserted in the working row_queue (rowIterator)
- if (not rowIterator.empty())
- sparse_strong_vertex_collapse();
- else
- return;
- }
-
- void complete_vertex_domination_check(doubleQueue& iterator, boolVector& insertIndicator, boolVector& domnIndicator) {
- double k;
- doubleVector nonZeroInnerIdcs;
- while (not iterator.empty()) // "iterator" contains list(FIFO) of rows to be considered for domination check
- {
- k = iterator.front();
- iterator.pop();
- insertIndicator[k] = false;
- if (not domnIndicator[k]) // Check if is already dominated
- {
- nonZeroInnerIdcs = closed_neighbours_row_index(k);
- for (doubleVector::iterator it = nonZeroInnerIdcs.begin(); it != nonZeroInnerIdcs.end(); it++) {
- int checkDom = vertex_domination_check(k, *it); // "true" for row domination comparison
- if (checkDom == 1) // row k is dominated by *it, k <= *it;
- {
- setZero(k, *it);
- break;
- } else if (checkDom == -1) // row *it is dominated by k, *it <= k;
- setZero(*it, k);
- }
- }
- }
- }
-
bool check_edge_domination(Edge e) // Edge e is the actual edge (u,v). Not the row ids in the matrixs
{
auto u = std::get<0>(e);
@@ -456,22 +314,6 @@ class FlagComplexSpMatrix {
std::cout << "The total number of non-critical edges is: " << totEdges - criticalCoreEdges.size() << std::endl;
}
- int vertex_domination_check(double i, double j) // True for row comparison, false for column comparison
- {
- if (i != j) {
- doubleVector Listi = closed_neighbours_row_index(i);
- doubleVector Listj = closed_neighbours_row_index(j);
- if (Listj.size() <= Listi.size()) {
- if (std::includes(Listi.begin(), Listi.end(), Listj.begin(), Listj.end())) // Listj is a subset of Listi
- return -1;
- }
-
- else if (std::includes(Listj.begin(), Listj.end(), Listi.begin(), Listi.end())) // Listi is a subset of Listj
- return 1;
- }
- return 0;
- }
-
doubleVector closed_neighbours_row_index(double indx) // Returns list of non-zero columns of the particular indx.
{
doubleVector nonZeroIndices;
@@ -510,89 +352,13 @@ class FlagComplexSpMatrix {
return common;
}
- void setZero(double dominated, double dominating) {
- for (auto& v : closed_neighbours_row_index(dominated))
- if (not rowInsertIndicator[v]) // Checking if the row is already inserted
- {
- rowIterator.push(v);
- rowInsertIndicator[v] = true;
- }
- vertDomnIndicator[dominated] = true;
- ReductionMap[rowToVertex[dominated]] = rowToVertex[dominating];
-
- vertexToRow.erase(rowToVertex[dominated]);
- vertices.erase(rowToVertex[dominated]);
- rowToVertex.erase(dominated);
- }
-
- vertexVector closed_neighbours_vertex_index(double rowIndx) // Returns list of non-zero "vertices" of the particular
- // colIndx. the difference is in the return type
- {
- vertexVector colmns;
- for (auto& v : closed_neighbours_row_index(rowIndx)) // Iterate over the non-zero columns
- colmns.push_back(rowToVertex[v]);
- std::sort(colmns.begin(), colmns.end());
- return colmns;
- }
-
- vertexVector vertex_closed_active_neighbours(
- double rowIndx) // Returns list of all non-zero "vertices" of the particular colIndx which are currently active.
- // the difference is in the return type.
- {
- vertexVector colmns;
- for (auto& v : closed_neighbours_row_index(rowIndx)) // Iterate over the non-zero columns
- if (not contractionIndicator[v]) // Check if the row corresponds to a contracted vertex
- colmns.push_back(rowToVertex[v]);
- std::sort(colmns.begin(), colmns.end());
- return colmns;
- }
-
- vertexVector closed_all_neighbours_row_index(
- double rowIndx) // Returns list of all non-zero "vertices" of the particular colIndx whether dominated or not.
- // the difference is in the return type.
- {
- vertexVector colmns;
- for (rowInnerIterator itCol(sparseRowAdjMatrix, rowIndx); itCol; ++itCol) // Iterate over the non-zero columns
- colmns.push_back(rowToVertex[itCol.index()]); // inner index, here it is equal to it.row()
- std::sort(colmns.begin(), colmns.end());
- return colmns;
- }
-
- void swap_rows(const Vertex& v,
- const Vertex& w) { // swap the rows of v and w. Both should be members of the skeleton
- if (membership(v) && membership(w)) {
- auto rw_v = vertexToRow[v];
- auto rw_w = vertexToRow[w];
- vertexToRow[v] = rw_w;
- vertexToRow[w] = rw_v;
- rowToVertex[rw_v] = w;
- rowToVertex[rw_w] = v;
- }
- }
-
public:
- //! Default Constructor
- /*!
- Only initialises all Data Members of the class to empty/Null values as appropriate.
- One <I>WILL</I> have to create the matrix using the Constructor that has an object of the Simplex_tree class as
- argument.
- */
-
- FlagComplexSpMatrix() { init(); }
-
- FlagComplexSpMatrix(std::size_t expRows) {
- init();
- sparseRowAdjMatrix = sparseRowMatrix(
- expansion_limit * expRows,
- expansion_limit * expRows); // Initializing sparseRowAdjMatrix, This is a row-major sparse matrix.
- }
-
//! Main Constructor
/*!
Argument is an instance of Filtered_sorted_edge_list. <br>
This is THE function that initialises all data members to appropriate values. <br>
<B>rowToVertex</B>, <B>vertexToRow</B>, <B>rows</B>, <B>cols</B>, <B>sparseRowAdjMatrix</B> are initialised here.
- <B>vertDomnIndicator</B>, <B>rowInsertIndicator</B> ,<B>rowIterator<B> are initialised by init() function which is
+ <B>vertDomnIndicator</B> ,<B>rowIterator<B> are initialised by init() function which is
called at the begining of this. <br>
*/
FlagComplexSpMatrix(const size_t& num_vertices, const Filtered_sorted_edge_list& edge_t) {
@@ -616,84 +382,19 @@ class FlagComplexSpMatrix {
*/
~FlagComplexSpMatrix() {}
- //! Function for performing strong collapse.
- /*!
- calls sparse_strong_vertex_collapse(), and
- Then, it compacts the ReductionMap by calling the function fully_compact().
- */
- double strong_vertex_collapse() {
- auto begin_collapse = std::chrono::high_resolution_clock::now();
- sparse_strong_vertex_collapse();
- vertexCollapsed = true;
- auto end_collapse = std::chrono::high_resolution_clock::now();
-
- auto collapseTime = std::chrono::duration<double, std::milli>(end_collapse - begin_collapse).count();
- // std::cout << "Time of Collapse : " << collapseTime << " ms\n" << std::endl;
-
- // Now we complete the Reduction Map
- fully_compact();
- // Post processing...
- after_vertex_collapse();
- return collapseTime;
- }
-
// Performs edge collapse in a decreasing sequence of the filtration value.
Filtered_sorted_edge_list filtered_edge_collapse() {
critical_core_edges();
- vertexCollapsed = false;
edgeCollapsed = true;
return criticalCoreEdges;
}
- // double strong_vertex_edge_collapse() {
- // auto begin_collapse = std::chrono::high_resolution_clock::now();
- // strong_vertex_collapse();
- // strong_edge_collapse();
- // // strong_vertex_collapse();
- // auto end_collapse = std::chrono::high_resolution_clock::now();
-
- // auto collapseTime = std::chrono::duration<double, std::milli>(end_collapse- begin_collapse).count();
- // return collapseTime;
- // }
-
- bool membership(const Vertex& v) {
- auto rw = vertexToRow.find(v);
- if (rw != vertexToRow.end())
- return true;
- else
- return false;
- }
-
- bool membership(const Edge& e) {
- auto u = std::get<0>(e);
- auto v = std::get<1>(e);
- if (membership(u) && membership(v)) {
- auto rw_u = vertexToRow[u];
- auto rw_v = vertexToRow[v];
- if (rw_u <= rw_v)
- for (auto x : closed_neighbours_row_index(rw_v)) { // Taking advantage of sorted lists.
- if (rw_u == x)
- return true;
- else if (rw_u < x)
- return false;
- }
- else
- for (auto x : closed_neighbours_row_index(rw_u)) { // Taking advantage of sorted lists.
- if (rw_v == x)
- return true;
- else if (rw_v < x)
- return false;
- }
- }
- return false;
- }
void insert_vertex(const Vertex& vertex, double filt_val) {
auto rw = vertexToRow.find(vertex);
if (rw == vertexToRow.end()) {
sparseRowAdjMatrix.insert(rows, rows) =
filt_val; // Initializing the diagonal element of the adjency matrix corresponding to rw_b.
vertDomnIndicator.push_back(false);
- rowInsertIndicator.push_back(true);
contractionIndicator.push_back(false);
rowIterator.push(rows);
vertexToRow.insert(std::make_pair(vertex, rows));
@@ -725,128 +426,4 @@ class FlagComplexSpMatrix {
std::size_t num_vertices() const { return vertices.size(); }
- //! Function for returning the ReductionMap.
- /*!
- This is the (stl's unordered) map that stores all the collapses of vertices. <br>
- It is simply returned.
- */
-
- Map reduction_map() const { return ReductionMap; }
- std::unordered_set<Vertex> vertex_set() const { return vertices; }
- sparseRowMatrix collapsed_matrix() const { return *sparse_colpsd_adj_Matrix; }
-
- sparseRowMatrix uncollapsed_matrix() const { return sparseRowAdjMatrix; }
-
- edge_list all_edges() const { return oneSimplices; }
-
- vertexVector active_neighbors(const Vertex& v) {
- vertexVector nb;
- auto rw_v = vertexToRow.find(v);
- if (rw_v != vertexToRow.end()) {
- nb = vertex_closed_active_neighbours(rw_v->second);
- }
- return nb;
- }
-
- vertexVector neighbors(const Vertex& v) {
- vertexVector nb;
- auto rw_v = vertexToRow.find(v);
- if (rw_v != vertexToRow.end()) nb = closed_neighbours_vertex_index(rw_v->second);
-
- return nb;
- }
-
- vertexVector active_relative_neighbors(const Vertex& v, const Vertex& w) {
- std::vector<Vertex> diff;
- if (membership(v) && membership(w)) {
- auto nbhrs_v = active_neighbors(v);
- auto nbhrs_w = active_neighbors(w);
- std::set_difference(nbhrs_v.begin(), nbhrs_v.end(), nbhrs_w.begin(), nbhrs_w.end(),
- std::inserter(diff, diff.begin()));
- }
- return diff;
- }
-
- void contraction(const Vertex& del, const Vertex& keep) {
- if (del != keep) {
- bool del_mem = membership(del);
- bool keep_mem = membership(keep);
- if (del_mem && keep_mem) {
- doubleVector del_indcs, keep_indcs, diff;
- auto row_del = vertexToRow[del];
- auto row_keep = vertexToRow[keep];
- del_indcs = closed_neighbours_row_index(row_del);
- keep_indcs = closed_neighbours_row_index(row_keep);
- std::set_difference(del_indcs.begin(), del_indcs.end(), keep_indcs.begin(), keep_indcs.end(),
- std::inserter(diff, diff.begin()));
- for (auto& v : diff) {
- if (v != row_del) {
- sparseRowAdjMatrix.insert(row_keep, v) = 1;
- sparseRowAdjMatrix.insert(v, row_keep) = 1;
- }
- }
- vertexToRow.erase(del);
- vertices.erase(del);
- rowToVertex.erase(row_del);
- // setZero(row_del->second, row_keep->second);
- } else if (del_mem && not keep_mem) {
- vertexToRow.insert(std::make_pair(keep, vertexToRow.find(del)->second));
- rowToVertex[vertexToRow.find(del)->second] = keep;
- vertices.emplace(keep);
- vertices.erase(del);
- vertexToRow.erase(del);
-
- } else {
- std::cerr << "The first vertex entered in the method contraction() doesn't exist in the skeleton." << std::endl;
- exit(-1);
- }
- }
- }
-
- void relable(const Vertex& v, const Vertex& w) { // relable v as w.
- if (membership(v) and v != w) {
- auto rw_v = vertexToRow[v];
- rowToVertex[rw_v] = w;
- vertexToRow.insert(std::make_pair(w, rw_v));
- vertices.emplace(w);
- vertexToRow.erase(v);
- vertices.erase(v);
- // std::cout<< "Re-named the vertex " << v << " as " << w << std::endl;
- }
- }
-
- // Returns the contracted edge. along with the contracted vertex in the begining of the list at {u,u} or {v,v}
-
- void active_strong_expansion(const Vertex& v, const Vertex& w, double filt_val) {
- if (membership(v) && membership(w) && v != w) {
- // std::cout << "Strong expansion of the vertex " << v << " and " << w << " begins. " << std::endl;
- auto active_list_v_w = active_relative_neighbors(v, w);
- auto active_list_w_v = active_relative_neighbors(w, v);
- if (active_list_w_v.size() <
- active_list_v_w.size()) { // simulate the contraction of w by expanding the star of v
- for (auto& x : active_list_w_v) {
- active_edge_insertion(v, x, filt_val);
- // std::cout << "Inserted the edge " << v << " , " << x << std::endl;
- }
- swap_rows(v, w);
- // std::cout << "A swap of the vertex " << v << " and " << w << "took place." << std::endl;
- } else {
- for (auto& y : active_list_v_w) {
- active_edge_insertion(w, y, filt_val);
- // std::cout << "Inserted the edge " << w << ", " << y << std::endl;
- }
- }
- auto rw_v = vertexToRow.find(v);
- contractionIndicator[rw_v->second] = true;
- }
- if (membership(v) && !membership(w)) {
- relable(v, w);
- }
- }
- void active_edge_insertion(const Vertex& v, const Vertex& w, double filt_val) {
- insert_new_edges(v, w, filt_val);
- // update_active_indicator(v,w);
- }
-
- void print_sparse_skeleton() { std::cout << sparseRowAdjMatrix << std::endl; }
}; \ No newline at end of file