PlanarSubgraphTriangles.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/DisjointSets.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/planarity/PlanarSubgraphModule.h>
 
namespace ogdf {
 
 
template<typename TCost>
class PlanarSubgraphTriangles : public PlanarSubgraphModule<TCost> {
public:
 
    PlanarSubgraphTriangles(bool onlyTriangles = false) : m_onlyTriangles(onlyTriangles) { }
 
    virtual PlanarSubgraphTriangles* clone() const override {
        return new PlanarSubgraphTriangles(m_onlyTriangles);
    }
 
protected:
    virtual Module::ReturnType doCall(const Graph& graph, const List<edge>&, List<edge>& delEdges,
            const EdgeArray<TCost>* pCost, bool preferredImplyPlanar = false) override {
        OGDF_ASSERT(isConnected(graph));
        OGDF_ASSERT(isSimpleUndirected(graph));
 
        delEdges.clear();
        GraphCopy copy(graph);
        List<edge> edges;
        copy.allEdges(edges);
        EdgeArray<bool> includeEdges(copy, false);
 
        // sort weighted edges
        if (pCost != nullptr) {
            GenericComparer<edge, TCost, false> edgeCmp(
                    [&](edge e) { return (*pCost)[copy.original(e)]; });
            GenericComparer<adjEntry, TCost, false> adjCmp(
                    [&](adjEntry a) { return (*pCost)[copy.original(a->theEdge())]; });
            edges.quicksort(edgeCmp);
 
            for (node v : copy.nodes) {
                List<adjEntry> newOrder;
                v->allAdjEntries(newOrder);
                newOrder.quicksort(adjCmp);
                copy.sort(v, newOrder);
            }
        }
 
        DisjointSets<> components(copy.numberOfNodes());
        NodeArray<int> set(copy);
        for (node v : copy.nodes) {
            set[v] = components.makeSet();
        }
 
        if (!m_onlyTriangles) {
            // First step: Find as many diamonds as we can.
            for (edge currentEdge : edges) {
                // Skip if we already include this edge
                if (includeEdges[currentEdge]) {
                    continue;
                }
 
                // We assume this edge to be the cord of our diamond. This means we have to find two
                // distinct triangles to make a diamond, and we will try to prefer ones with higher
                // weights given by our pCost parameter
 
                node source = currentEdge->source();
                node target = currentEdge->target();
 
                edge triangleEdge1 = nullptr, triangleEdge2 = nullptr;
                node triangleNode = nullptr;
                int triangleSet = -1;
 
                findTriangle(copy, currentEdge, pCost, components, set, [&](node v, edge e1, edge e2) {
                    // Only use the found triangle if none of the nodes are in the same component.
                    // We know that each individually found triangle does not have two nodes in the
                    // same component, so we only have to check the opposite ones.
                    int potentialSet = components.find(set[v]);
                    if (potentialSet == triangleSet) {
                        return false; // This is not a triangle we can use, keep looking!
                    }
 
                    if (triangleNode == nullptr) {
                        // We don't have a triangle yet, mark this one down as the best we can find from this edge.
                        triangleNode = v;
                        triangleEdge1 = e1;
                        triangleEdge2 = e2;
                        triangleSet = potentialSet;
                        return false; // continue searching for a second triangle to make our diamond
                    } else {
                        // We already found a triangle before, so this is the second-best triangle we can find,
                        // making a diamond.
                        includeEdges[currentEdge] = includeEdges[triangleEdge1] =
                                includeEdges[triangleEdge2] = includeEdges[e1] = includeEdges[e2] =
                                        true;
 
                        // Link up diamond nodes' components. These cannot be on the same connected subgraph yet.
                        int sourceSet = components.find(set[source]);
                        int targetSet = components.find(set[target]);
                        components.link(
                                components.link(components.link(sourceSet, targetSet), triangleSet),
                                potentialSet);
                        return true; // stop looking
                    }
                });
            }
        }
 
        // Second step: Find as many triangles as we can.
        for (edge currentEdge : edges) {
            if (includeEdges[currentEdge]) {
                continue;
            }
 
            node source = currentEdge->source();
            node target = currentEdge->target();
 
            findTriangle(copy, currentEdge, pCost, components, set, [&](node v, edge e1, edge e2) {
                includeEdges[currentEdge] = includeEdges[e1] = includeEdges[e2] = true;
                int potentialSet = components.find(set[v]);
                int sourceSet = components.find(set[source]);
                int targetSet = components.find(set[target]);
                components.link(components.link(sourceSet, targetSet), potentialSet);
                return true;
            });
        }
 
        // Third step: Link unconnected sub graphs
        for (edge currentEdge : edges) {
            node source = currentEdge->source();
            node target = currentEdge->target();
            int sourceSet = components.find(set[source]);
            int targetSet = components.find(set[target]);
            if (sourceSet != targetSet) {
                includeEdges[currentEdge] = true;
                components.link(sourceSet, targetSet);
            }
 
            if (!includeEdges[currentEdge]) {
                delEdges.pushBack(copy.original(currentEdge));
            }
        }
 
        return Module::ReturnType::Feasible;
    }
 
 
private:
    bool m_onlyTriangles; 
 
 
    edge searchEdge(node target, node source, internal::GraphIterator<adjEntry> connectionIterator) {
        while (connectionIterator != source->adjEntries.end()) {
            if ((*connectionIterator)->twinNode() == target) {
                return (*connectionIterator)->theEdge();
            }
            connectionIterator++;
        }
        return nullptr;
    }
 
 
    void findTriangle(GraphCopy& copy, edge currentEdge, const EdgeArray<TCost>* pCost,
            DisjointSets<>& components, NodeArray<int>& set,
            std::function<bool(node, edge, edge)> callback) {
        node source = currentEdge->source();
        node target = currentEdge->target();
        auto sourceIt = source->adjEntries.begin();
        auto targetIt = target->adjEntries.begin();
        int sourceSet = components.find(set[source]);
        int targetSet = components.find(set[target]);
        // Our nodes cannot be in the same set.
        if (sourceSet == targetSet) {
            return;
        }
 
        while (sourceIt != source->adjEntries.end() && targetIt != target->adjEntries.end()) {
            if ((*sourceIt)->theEdge() == currentEdge) {
                sourceIt++;
                continue; // re-check loop condition
            }
            if ((*targetIt)->theEdge() == currentEdge) {
                targetIt++;
                continue; // re-check loop condition
            }
 
            // Look for a triangle, starting with the edge with next highest weight
            // If no weights are given, it does not matter which edge we start with
            adjEntry potentialConnector;
            node potentialConnection;
            internal::GraphIterator<adjEntry> potentialConnectionIterator;
            if (pCost == nullptr
                    || (*pCost)[copy.original((*sourceIt)->theEdge())]
                            > (*pCost)[copy.original((*targetIt)->theEdge())]) {
                potentialConnector = *sourceIt;
                potentialConnection = target;
                potentialConnectionIterator = targetIt;
                sourceIt++;
            } else {
                potentialConnector = *targetIt;
                potentialConnection = source;
                potentialConnectionIterator = sourceIt;
                targetIt++;
            }
            // Note: sourceIt and targetIt may be invalid until next loop
 
            node potentialNode = potentialConnector->twinNode();
            int potentialSet = components.find(set[potentialNode]);
 
            // Only use this edge if it doesn't connect back to one of the components
            if (potentialSet != sourceSet && potentialSet != targetSet) {
                edge potentialEdge =
                        searchEdge(potentialNode, potentialConnection, potentialConnectionIterator);
                if (potentialEdge != nullptr) {
                    // We found a triangle.
                    // If our callback returns true, it's signalling that we're done and don't
                    // want to look for another triangle.
                    // If it returns false, we continue looking.
                    if (callback(potentialNode, potentialEdge, potentialConnector->theEdge())) {
                        return;
                    }
                }
            }
        }
    }
};
 
}