Face recognition in planar graphs using OGDF library

Question

It's been almost 2 weeks since I started to think about solution to that problem, as u probably see, without success ;)

Recently I was experimenting with OGDF function for planar graphs, such as "computeFaces" in "ConstCombinatorialEmbedding" or finding "PlanarStraightLayout" for planar graphs too. The second seems to work well, but the first isn't. Below I provide the sample of the code, the planar graph I'm processing, and the 2dim points assigned to the graph.

This code says there are two faces in that graph, "0 1 4 0 3 6 2 5 3 0 2 6 5 2" and "0 4 1 0 6 3 5 6", which, obviously, isn't true. So my question is, are there some bugs in the OGDF code that produces that output, or am I not using it correctly? Documentation, as typical, says nothing :/

Thank you all a lot for your time and response!

I'm using the latest version of OGDF (Dogwood)

planar graph representation by OGDF

The edges:
1 2
1 3
1 4
2 5
1 5
4 6
3 6
6 7
7 3
7 4
7 1

Sample code:
https://ideone.com/VzX0De

Or:
https://pastebin.com/PC0MwMy8

#include <iostream>
#include <ogdf/basic/Graph.h>
#include <ogdf/planarlayout/PlanarStraightLayout.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/GridLayout.h>

int main() {
    // Create a graph
    ogdf::Graph graph;
    auto graphAttributes = ogdf::GraphAttributes(graph);
    // Add nodes to the graph
    //ogdf::node v0 = graph.newNode();
    ogdf::node v1 = graph.newNode();
    ogdf::node v2 = graph.newNode();
    ogdf::node v3 = graph.newNode();
    ogdf::node v4 = graph.newNode();
    ogdf::node v5 = graph.newNode();
    ogdf::node v6 = graph.newNode();
    ogdf::node v7 = graph.newNode();

    // Add edges to the graph
    graph.newEdge(v1,v2);
    graph.newEdge(v1,v3);
    graph.newEdge(v1,v4);
    graph.newEdge(v2,v5);
    graph.newEdge(v1,v5);
    graph.newEdge(v4,v6);
    graph.newEdge(v3,v6);
    graph.newEdge(v6,v7);
    graph.newEdge(v3,v7);
    graph.newEdge(v4,v7);
    graph.newEdge(v1,v7);

    ogdf::PlanarStraightLayout layout;
    layout.call(graphAttributes);
    ogdf::CombinatorialEmbedding combEmbending = ogdf::CombinatorialEmbedding(graph);
    combEmbending.computeFaces();

    auto elem = combEmbending.faces;
    std::vector<std::vector<ogdf::node>> allFaces;
    for (auto &x : elem) {
        auto first = x->firstAdj();
        std::vector <ogdf::node> all;
        for (auto smth : x->entries) {
            auto y = smth;
            all.push_back(y->theNode());
            //std::cout << y->isSource() << ' ';
        }
        allFaces.push_back(all);
    }

    std::cout << "SEE\n";
    for (auto i : allFaces) {
        for (auto j : i) std::cout << j->index() << " ";
        std::cout << '\n';
    }
    std::cout << '\n';

    // Output the coordinates of each node
    std::vector<std::string> arr;
    for (ogdf::node n : graph.nodes) {
        ogdf::DPoint pos = graphAttributes.point(n);
        std::cout << "Node " << n->index() << " Position: (" << pos.m_x << ", " << pos.m_y << ")" << std::endl;
        arr.push_back(std::to_string(pos.m_x) + " " + std::to_string(pos.m_y));
    }
    for (auto &e: graph.edges) {
        auto nodes = e->nodes();
        auto point1 = graphAttributes.point(nodes[0]);
        auto point2 = graphAttributes.point(nodes[1]);
        std::cout << point1.m_x << " " << point1.m_y << " " << point2.m_x << " " << point2.m_y << '\n';
    }
    for (auto i : arr)
        std::cout << i << '\n';
    return 0;
}

Similar code in Boost works well, but I need the easiness of removing edges and nodes from OGDF

Face recognition in planar graphs using OGDF library

0 Answers0