361 lines
18 KiB
C++
Executable File
361 lines
18 KiB
C++
Executable File
#include "trianglepattterntopology.hpp"
|
|
#include <boost/graph/biconnected_components.hpp>
|
|
#include <boost/graph/connected_components.hpp>
|
|
#include <numeric>
|
|
|
|
FlatPatternTopology::FlatPatternTopology() {}
|
|
|
|
FlatPatternTopology::FlatPatternTopology(const std::vector<size_t> &numberOfNodesPerSlot,
|
|
const std::vector<vcg::Point2i> &edges)
|
|
: numberOfNodesPerSlot(numberOfNodesPerSlot)
|
|
{
|
|
pattern = BoostGraph(
|
|
std::accumulate(numberOfNodesPerSlot.begin(), numberOfNodesPerSlot.end(), 0));
|
|
isAdjacentTo.resize(boost::num_vertices(pattern),
|
|
std::vector<bool>(boost::num_vertices(pattern), false));
|
|
for (const vcg::Point2i &e : edges) {
|
|
boost::add_edge(e[0], e[1], pattern);
|
|
isAdjacentTo[e[0]][e[1]] = true;
|
|
isAdjacentTo[e[1]][e[0]] = true;
|
|
}
|
|
|
|
constructNodeToSlotMap();
|
|
constructSlotToNodeMap();
|
|
constructCorresponginNodeMap();
|
|
}
|
|
|
|
bool FlatPatternTopology::containsArticulationPoints(std::vector<int> &articulationPointsVi) const
|
|
{
|
|
assert(numberOfNodesPerSlot.size() == 7 && numberOfNodesPerSlot[4] < 2 && !nodeToSlot.empty()
|
|
&& !correspondingNode.empty());
|
|
BoostGraph copyOfPattern(pattern);
|
|
// std::cout << std::endl;
|
|
// std::vector<int> componentsBefore(boost::num_vertices(copyOfPattern));
|
|
// size_t num_components = boost::connected_components(copyOfPattern, &componentsBefore[0]);
|
|
// std::cout << "Number of cc before:" << num_components << std::endl;
|
|
// printGraph(copyOfPattern);
|
|
|
|
copyOfPattern = constructRotationallySymmetricPattern(copyOfPattern,
|
|
slotToNode,
|
|
nodeToSlot,
|
|
correspondingNode);
|
|
// // Remove edges connected to the bottom edge node
|
|
// assert(slotToNode.find(4) != slotToNode.end());
|
|
// std::unordered_set<size_t> bottomEdgeNodeSet =
|
|
// (slotToNode.find(4))->second;
|
|
// size_t bottomEdgeNodeIndex = *bottomEdgeNodeSet.begin();
|
|
// boost::clear_vertex(bottomEdgeNodeIndex, copyOfPattern);
|
|
|
|
// std::vector<int> componentsAfter(boost::num_vertices(copyOfPattern));
|
|
// num_components = boost::connected_components(copyOfPattern, &componentsAfter[0]);
|
|
// std::cout << "Number of cc after:" << num_components << std::endl;
|
|
// printGraph(copyOfPattern);
|
|
|
|
// Compute articulation points on the edited graph
|
|
std::vector<vertex_t> articulationPoints;
|
|
boost::articulation_points(copyOfPattern, std::back_inserter(articulationPoints));
|
|
for (const auto apVi : articulationPoints) {
|
|
articulationPointsVi.push_back(static_cast<int>(apVi));
|
|
}
|
|
// std::cout << "Found " << articulationPoints.size()
|
|
// << " articulation points.\n";
|
|
// size_t numberOfNonValidArticulationPoints = 0;
|
|
// for (std::size_t i = 0; i < articulationPoints.size(); ++i) {
|
|
// std::cout << articulationPoints[i] << std::endl;
|
|
// if (boost::out_degree(articulationPoints[i], copyOfPattern) < 3) {
|
|
// numberOfNonValidArticulationPoints++;
|
|
// }
|
|
// }
|
|
// if (numberOfNonValidArticulationPoints == articulationPoints.size()) {
|
|
// return false;
|
|
// }
|
|
return !articulationPoints.empty();
|
|
}
|
|
|
|
void FlatPatternTopology::constructNodeToSlotMap(
|
|
const std::vector<size_t> &numberOfNodesPerSlot,
|
|
std::unordered_map<size_t, size_t> &nodeToSlot) {
|
|
const size_t numberOfNodes = std::accumulate(numberOfNodesPerSlot.begin(),
|
|
numberOfNodesPerSlot.end(), 0);
|
|
assert(numberOfNodes != 0 && nodeToSlot.empty() &&
|
|
numberOfNodesPerSlot.size() == 7);
|
|
std::vector<size_t> maxNodeIndexPerSlot(numberOfNodesPerSlot.size());
|
|
for (size_t i = 0; i < maxNodeIndexPerSlot.size(); ++i) {
|
|
maxNodeIndexPerSlot[i] = std::accumulate(
|
|
numberOfNodesPerSlot.begin(), numberOfNodesPerSlot.begin() + i + 1, 0);
|
|
}
|
|
|
|
for (size_t nodeIndex = 0; nodeIndex < numberOfNodes; nodeIndex++) {
|
|
const size_t slotIndex =
|
|
std::distance(maxNodeIndexPerSlot.begin(),
|
|
std::upper_bound(maxNodeIndexPerSlot.begin(),
|
|
maxNodeIndexPerSlot.end(), nodeIndex));
|
|
nodeToSlot[nodeIndex] = slotIndex;
|
|
}
|
|
}
|
|
|
|
void FlatPatternTopology::constructNodeToSlotMap() {
|
|
constructNodeToSlotMap(numberOfNodesPerSlot, nodeToSlot);
|
|
}
|
|
|
|
void FlatPatternTopology::constructSlotToNodeMap() {
|
|
constructSlotToNodeMap(nodeToSlot, slotToNode);
|
|
}
|
|
|
|
void FlatPatternTopology::constructSlotToNodeMap(
|
|
const std::unordered_map<size_t, size_t> &nodeToSlot,
|
|
std::unordered_map<size_t, std::unordered_set<size_t>> &slotToNode) {
|
|
assert(!nodeToSlot.empty());
|
|
for (size_t nodeIndex = 0; nodeIndex < nodeToSlot.size(); nodeIndex++) {
|
|
slotToNode[nodeToSlot.at(nodeIndex)].insert(nodeIndex);
|
|
}
|
|
}
|
|
|
|
// TODO: The function expects that the numberOfNodesPerSlot follows a
|
|
// specific format and that the vertex container was populated in a
|
|
// particular order.
|
|
void FlatPatternTopology::constructCorresponginNodeMap() {
|
|
assert(!nodeToSlot.empty() && correspondingNode.empty() &&
|
|
numberOfNodesPerSlot.size() == 7);
|
|
|
|
for (size_t nodeIndex = 0; nodeIndex < boost::num_vertices(pattern);
|
|
nodeIndex++) {
|
|
const size_t slotIndex = nodeToSlot[nodeIndex];
|
|
if (slotIndex == 1) {
|
|
correspondingNode[nodeIndex] = nodeIndex + 1;
|
|
} else if (slotIndex == 2) {
|
|
correspondingNode[nodeIndex] = nodeIndex - 1;
|
|
} else if (slotIndex == 3) {
|
|
const size_t numberOfNodesBefore =
|
|
nodeIndex - std::accumulate(numberOfNodesPerSlot.begin(),
|
|
numberOfNodesPerSlot.begin() + 3, 0);
|
|
correspondingNode[nodeIndex] =
|
|
std::accumulate(numberOfNodesPerSlot.begin(),
|
|
numberOfNodesPerSlot.begin() + 6, 0) -
|
|
1 - numberOfNodesBefore;
|
|
} else if (slotIndex == 5) {
|
|
const size_t numberOfNodesAfter =
|
|
std::accumulate(numberOfNodesPerSlot.begin(),
|
|
numberOfNodesPerSlot.begin() + 6, 0) -
|
|
1 - nodeIndex;
|
|
correspondingNode[nodeIndex] =
|
|
numberOfNodesAfter + std::accumulate(numberOfNodesPerSlot.begin(),
|
|
numberOfNodesPerSlot.begin() + 3,
|
|
0);
|
|
}
|
|
}
|
|
}
|
|
|
|
bool FlatPatternTopology::pathExists(int src, int dest) const
|
|
{
|
|
const int N = boost::num_vertices(pattern);
|
|
std::vector<bool> visited(N, false);
|
|
visited[src] = true;
|
|
std::stack<int> next;
|
|
next.push(src);
|
|
|
|
while (!next.empty()) {
|
|
int cv = next.top();
|
|
next.pop();
|
|
|
|
for (int nv = 0; nv < N; ++nv) {
|
|
if (!visited[nv] && isAdjacentTo[cv][nv] == 1) {
|
|
visited[nv] = true;
|
|
next.push(nv);
|
|
}
|
|
}
|
|
}
|
|
// dest was reached from src?
|
|
return visited[dest];
|
|
}
|
|
|
|
/*
|
|
* In this function I create an "extended" pattern of the one in the base
|
|
* triangle by:
|
|
* 1)copying the edges from left edge to the right edge and vice versa
|
|
* 2)I label all nodes that lay on the boarder of the base triangle as
|
|
* "external" and add edges connecting them to each other (this is wrong in the
|
|
* case in which all "external" nodes are connected via a single node!))
|
|
* */
|
|
|
|
BoostGraph FlatPatternTopology::constructRotationallySymmetricPattern(
|
|
const BoostGraph &pattern,
|
|
const std::unordered_map<size_t, std::unordered_set<size_t>> &slotToNodes,
|
|
const std::unordered_map<size_t, size_t> &nodeToSlot,
|
|
const std::unordered_map<size_t, size_t> &correspondingNode) const
|
|
{
|
|
BoostGraph rotationallySymmetricPattern(pattern);
|
|
|
|
// for (const std::pair<size_t, size_t> &correspondingPair : correspondingNode) {
|
|
// const auto v0 = boost::vertex(correspondingPair.first, pattern);
|
|
// const auto v1 = boost::vertex(correspondingPair.second, pattern);
|
|
// if (boost::degree(v0, pattern) != 0 || boost::degree(v1, pattern) != 0) {
|
|
// boost::add_edge(v0, v1, rotationallySymmetricPattern);
|
|
// }
|
|
// }
|
|
|
|
boost::graph_traits<BoostGraph>::out_edge_iterator ei, ei_end;
|
|
// Copy edges that lay on the left edge to the right edge
|
|
const auto slot3NodesPairIt = slotToNodes.find(3);
|
|
if (slot3NodesPairIt != slotToNodes.end()) {
|
|
for (const size_t &nodeIndex : slot3NodesPairIt->second) {
|
|
for (boost::tie(ei, ei_end) = boost::out_edges(nodeIndex, pattern); ei != ei_end; ++ei) {
|
|
auto vt = boost::target(*ei, pattern);
|
|
const auto vtNodeSlotPairIt = nodeToSlot.find(vt);
|
|
assert(vtNodeSlotPairIt != nodeToSlot.end());
|
|
const size_t vtSlot = vtNodeSlotPairIt->second;
|
|
if (vtSlot == 3 || vtSlot == 1 || vtSlot == 0) {
|
|
// Connect the corresponding nodes on the opposite edge
|
|
auto correspondingNodeIndexIt = correspondingNode.find(nodeIndex);
|
|
assert(correspondingNodeIndexIt != correspondingNode.end());
|
|
auto correspondingVtIt = correspondingNode.find(vt);
|
|
assert(correspondingVtIt != correspondingNode.end() || vtSlot == 0);
|
|
const size_t &correspondingNodeIndex = correspondingNodeIndexIt->second;
|
|
size_t correspondingVt = 0;
|
|
if (correspondingVtIt != correspondingNode.end()) {
|
|
correspondingVt = correspondingVtIt->second;
|
|
}
|
|
boost::add_edge(correspondingNodeIndex,
|
|
correspondingVt,
|
|
rotationallySymmetricPattern);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// // Copy edges that lay on the right edge to the left edge
|
|
const auto slot5NodesPairIt = slotToNodes.find(5);
|
|
if (slot5NodesPairIt != slotToNodes.end()) {
|
|
for (const size_t &nodeIndex : slot5NodesPairIt->second) {
|
|
for (boost::tie(ei, ei_end) = boost::out_edges(nodeIndex, pattern); ei != ei_end; ++ei) {
|
|
auto vt = boost::target(*ei, pattern);
|
|
const auto vtNodeSlotPairIt = nodeToSlot.find(vt);
|
|
assert(vtNodeSlotPairIt != nodeToSlot.end());
|
|
const size_t vtSlot = vtNodeSlotPairIt->second;
|
|
if (vtSlot == 5 || vtSlot == 2 || vtSlot == 0) {
|
|
// Connect the corresponding nodes on the opposite edge
|
|
auto correspondingNodeIndexIt = correspondingNode.find(nodeIndex);
|
|
assert(correspondingNodeIndexIt != correspondingNode.end());
|
|
auto correspondingVtIt = correspondingNode.find(vt);
|
|
assert(correspondingVtIt != correspondingNode.end() || vtSlot == 0);
|
|
const size_t &correspondingNodeIndex = correspondingNodeIndexIt->second;
|
|
size_t correspondingVt = 0;
|
|
if (correspondingVtIt != correspondingNode.end()) {
|
|
correspondingVt = correspondingVtIt->second;
|
|
}
|
|
boost::add_edge(correspondingNodeIndex,
|
|
correspondingVt,
|
|
rotationallySymmetricPattern);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// NOTE: The problem with that approach is that I connect !all! "external"
|
|
// nodes with each other, which might not be entirely true. If the number of
|
|
// cc of the tilled configuration is not 1 this might not label patterns as
|
|
// having an articulation node although they might have one. Create set of
|
|
// nodes connected with "external" edges
|
|
std::unordered_set<size_t> externallyConnectedNodes;
|
|
// Mark the star node as external
|
|
const auto slot0NodesPairIt = slotToNodes.find(0);
|
|
if (slot0NodesPairIt != slotToNodes.end()) {
|
|
externallyConnectedNodes.insert(slot0NodesPairIt->second.begin(),
|
|
slot0NodesPairIt->second.end());
|
|
}
|
|
// Mark all bottom nodes as external since they are allways connected to the
|
|
// south-neighbouring pattern
|
|
const auto slot4NodesPairIt = slotToNodes.find(4);
|
|
if (slot4NodesPairIt != slotToNodes.end()) {
|
|
externallyConnectedNodes.insert(slot4NodesPairIt->second.begin(),
|
|
slot4NodesPairIt->second.end());
|
|
}
|
|
// Add all slot3 nodes that have a connection to the "inside"
|
|
if (slot3NodesPairIt != slotToNodes.end()) {
|
|
externallyConnectedNodes.insert(slot3NodesPairIt->second.begin(),
|
|
slot3NodesPairIt->second.end());
|
|
for (const size_t &nodeIndex : slot3NodesPairIt->second) {
|
|
auto correspondingNodePairIt = correspondingNode.find(nodeIndex);
|
|
// for (boost::tie(ei, ei_end) = boost::out_edges(nodeIndex, pattern); ei != ei_end; ++ei) {
|
|
// auto vt = boost::target(*ei, pattern);
|
|
// const auto vtNodeSlotPairIt = nodeToSlot.find(vt);
|
|
// assert(vtNodeSlotPairIt != nodeToSlot.end());
|
|
// const size_t vtSlot = vtNodeSlotPairIt->second;
|
|
// if (vtSlot != 3) {
|
|
// assert(correspondingNodePairIt != correspondingNode.end());
|
|
// externallyConnectedNodes.insert(correspondingNodePairIt->second);
|
|
// // boost::add_edge(correspondingNodePairIt->second,
|
|
// // vt,
|
|
// // rotationallySymmetricPattern);
|
|
// // boost::add_edge(nodeIndex, vt, rotationallySymmetricPattern);
|
|
// }
|
|
// }
|
|
boost::add_edge(correspondingNodePairIt->second,
|
|
nodeIndex,
|
|
rotationallySymmetricPattern);
|
|
}
|
|
}
|
|
// Add all slot5 nodes that have a connection to the "inside"
|
|
if (slot5NodesPairIt != slotToNodes.end()) {
|
|
for (const size_t &nodeIndex : slot5NodesPairIt->second) {
|
|
auto correspondingNodePairIt = correspondingNode.find(nodeIndex);
|
|
// for (boost::tie(ei, ei_end) = boost::out_edges(nodeIndex, pattern); ei != ei_end; ++ei) {
|
|
// auto vt = boost::target(*ei, pattern);
|
|
// const auto vtNodeSlotPairIt = nodeToSlot.find(vt);
|
|
// assert(vtNodeSlotPairIt != nodeToSlot.end());
|
|
// const size_t vtSlot = vtNodeSlotPairIt->second;
|
|
// if (vtSlot != 5) {
|
|
// assert(correspondingNodePairIt != correspondingNode.end());
|
|
// externallyConnectedNodes.insert(correspondingNodePairIt->second);
|
|
// boost::add_edge(correspondingNodePairIt->second,
|
|
// vt,
|
|
// rotationallySymmetricPattern);
|
|
// }
|
|
// }
|
|
boost::add_edge(correspondingNodePairIt->second,
|
|
nodeIndex,
|
|
rotationallySymmetricPattern);
|
|
}
|
|
externallyConnectedNodes.insert(slot5NodesPairIt->second.begin(),
|
|
slot5NodesPairIt->second.end());
|
|
}
|
|
|
|
// connecting all is wrong. Maybe I should check whether the external nodes
|
|
// are connected via a single node? If so this node is an articulation point.
|
|
// I could test this by checking if it filters out only the falsely labeled
|
|
// pattern 2367
|
|
const size_t &n = externallyConnectedNodes.size();
|
|
const size_t numberOfExternalEdges = n * (n - 1) / 2;
|
|
// Connect all external nodes with each other
|
|
for (size_t edgeIndex = 0; edgeIndex < numberOfExternalEdges; edgeIndex++) {
|
|
const int sei0 = n - 2
|
|
- std::floor(std::sqrt(-8 * edgeIndex + 4 * n * (n - 1) - 7) / 2.0 - 0.5);
|
|
const int sei1 = edgeIndex + sei0 + 1 - n * (n - 1) / 2 + (n - sei0) * ((n - sei0) - 1) / 2;
|
|
const size_t ni0 = *std::next(externallyConnectedNodes.begin(), sei0);
|
|
const size_t ni1 = *std::next(externallyConnectedNodes.begin(), sei1);
|
|
if (correspondingNode.contains(ni0) || correspondingNode.contains(ni1)) {
|
|
if (correspondingNode.contains(ni0) && correspondingNode.contains(ni1)
|
|
&& pathExists(correspondingNode.at(ni0), correspondingNode.at(ni1))) {
|
|
boost::add_edge(ni0, ni1, rotationallySymmetricPattern);
|
|
} else if (!correspondingNode.contains(ni0) && correspondingNode.contains(ni1)
|
|
&& pathExists(ni0, correspondingNode.at(ni1))) {
|
|
boost::add_edge(ni0, ni1, rotationallySymmetricPattern);
|
|
} else if (correspondingNode.contains(ni0) && !correspondingNode.contains(ni1)
|
|
&& pathExists(correspondingNode.at(ni0), ni1)) {
|
|
boost::add_edge(ni0, ni1, rotationallySymmetricPattern);
|
|
}
|
|
}
|
|
}
|
|
|
|
return rotationallySymmetricPattern;
|
|
}
|
|
|
|
void FlatPatternTopology::printGraph(const BoostGraph &g)
|
|
{
|
|
boost::graph_traits<BoostGraph>::edge_iterator ei, ei_end;
|
|
for (boost::tie(ei, ei_end) = boost::edges(g); ei != ei_end; ++ei)
|
|
std::cout << (char) (boost::source(*ei, g) + 'A') << " -- "
|
|
<< (char) (boost::target(*ei, g) + 'A');
|
|
std::cout << std::endl;
|
|
}
|