Faces recognition in Planar Graphs

[Andrei Daletski]

Dera OGDF Community,
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 give the sample of the code, the planar graph I processing, and the 2dim points assigned to the graph.

This code says there is 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)



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

Or:

#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;
}