Last active
July 21, 2024 22:16
-
-
Save Hermann-SW/99d151a273d290ee0d843c79b2da26a8 to your computer and use it in GitHub Desktop.
Boost make_"connected / biconnected_planar / maximal_planar"+straight_line_drawing demos made create graphviz graph with fixed coordinates
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//======================================================================= | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
/* | |
f=straight_line_graphviz | |
g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f | |
cpplint --filter=-legal/copyright,-build/namespaces $f.cpp | |
cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config | |
*/ | |
//======================================================================= | |
#include <cassert> | |
#include <cstring> | |
#include <iostream> | |
#include <fstream> | |
#include <vector> | |
#include <boost/graph/adjacency_list.hpp> | |
#include <boost/graph/properties.hpp> | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/property_map/property_map.hpp> | |
#include <boost/ref.hpp> | |
#include <boost/graph/make_connected.hpp> | |
#include <boost/graph/make_biconnected_planar.hpp> | |
#include <boost/graph/make_maximal_planar.hpp> | |
#include <boost/graph/planar_face_traversal.hpp> | |
#include <boost/graph/boyer_myrvold_planar_test.hpp> | |
#include <boost/graph/planar_canonical_ordering.hpp> | |
#include <boost/graph/is_straight_line_drawing.hpp> | |
#include <boost/graph/chrobak_payne_drawing.hpp> | |
// This example shows how to start with a connected planar graph | |
// and add edges to make the graph maximal planar (triangulated.) | |
// Any maximal planar simple graph on n vertices has 3n - 6 edges and | |
// 2n - 4 faces, a consequence of Euler's formula. | |
using namespace boost; | |
// a class to hold the coordinates of the straight line embedding | |
struct coord_t { | |
std::size_t x; | |
std::size_t y; | |
}; | |
int main(int argc, char** argv) { | |
typedef adjacency_list< vecS, vecS, undirectedS, | |
property< vertex_index_t, int >, property< edge_index_t, int > > | |
graph; | |
int n, m, dbg; | |
char line[200]; | |
assert((argc >> 1) == 1); | |
std::ifstream in(argv[1]); | |
assert(in); | |
dbg = (argc == 3); | |
in >> line; | |
in >> line; | |
in >> line; | |
in >> n; | |
graph g(n+1); | |
for (int i=1; i <= n; ++i) { | |
in >> line; | |
} | |
in >> m; | |
for (int i=1; i <= m; ++i) { | |
int s, t, v; | |
in >> s >> t >> v; | |
add_edge(s, t, g); | |
} | |
int edge_count_input = num_edges(g); | |
make_connected(g); | |
// Initialize the interior edge index | |
property_map< graph, edge_index_t >::type e_index = get(edge_index, g); | |
graph_traits< graph >::edges_size_type edge_count = 0; | |
graph_traits< graph >::edge_iterator ei, ei_end; | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
put(e_index, *ei, edge_count++); | |
// Test for planarity; compute the planar embedding as a side-effect | |
typedef std::vector< graph_traits< graph >::edge_descriptor > vec_t; | |
std::vector< vec_t > embedding2(num_vertices(g)); | |
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = &embedding2[0])); | |
make_biconnected_planar(g, &embedding2[0]); | |
// Re-initialize the edge index, since we just added a few edges | |
edge_count = 0; | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
put(e_index, *ei, edge_count++); | |
// Test for planarity again; compute the planar embedding as a side-effect | |
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = &embedding2[0])); | |
make_maximal_planar(g, &embedding2[0]); | |
// Re-initialize the edge index, since we just added a few edges | |
edge_count = 0; | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
put(e_index, *ei, edge_count++); | |
// Test for planarity one final time; compute the planar embedding as a | |
// side-effect | |
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = &embedding2[0])); | |
typedef std::vector< std::vector< graph_traits< graph >::edge_descriptor > > | |
embedding_storage_t; | |
typedef boost::iterator_property_map< embedding_storage_t::iterator, | |
property_map< graph, vertex_index_t >::type > | |
embedding_t; | |
// Create the planar embedding | |
embedding_storage_t embedding_storage(num_vertices(g)); | |
embedding_t embedding(embedding_storage.begin(), get(vertex_index, g)); | |
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = embedding)); | |
// Find a canonical ordering | |
std::vector< graph_traits< graph >::vertex_descriptor > ordering; | |
planar_canonical_ordering(g, embedding, std::back_inserter(ordering)); | |
// Set up a property map to hold the mapping from vertices to coord_t's | |
typedef std::vector< coord_t > straight_line_drawing_storage_t; | |
typedef boost::iterator_property_map< | |
straight_line_drawing_storage_t::iterator, | |
property_map< graph, vertex_index_t >::type > | |
straight_line_drawing_t; | |
straight_line_drawing_storage_t straight_line_drawing_storage( | |
num_vertices(g)); | |
straight_line_drawing_t straight_line_drawing( | |
straight_line_drawing_storage.begin(), get(vertex_index, g)); | |
// Compute the straight line drawing | |
chrobak_payne_straight_line_drawing( | |
g, embedding, ordering.begin(), ordering.end(), straight_line_drawing); | |
// Verify that the drawing is actually a plane drawing | |
assert(is_straight_line_drawing(g, straight_line_drawing)); | |
std::cout << "graph {" << std::endl; | |
std::cout << " layout=neato" << std::endl; | |
std::cout << " node [shape=none]" << std::endl; | |
// get the property map for vertex indices | |
typedef property_map<graph, vertex_index_t>::type IndexMap; | |
IndexMap index = get(vertex_index, g); | |
graph_traits< graph >::vertex_iterator vi, vi_end; | |
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { | |
if (index[*vi] == 0) continue; | |
coord_t coord(get(straight_line_drawing, *vi)); | |
std::cout << " " << *vi << " [pos=\"" << coord.x << "," << coord.y | |
<< "!\""; | |
if (dbg) | |
std::cout << " label=\"" << *vi - 1 <<"\""; | |
std::cout << "]" << std::endl; | |
} | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { | |
if (index[source(*ei, g)] == 0) continue; | |
if (index[target(*ei, g)] == 0) continue; | |
std::cout << " " << index[source(*ei, g)] | |
<< "--" << index[target(*ei, g)] | |
<< "[style=" << (edge_count_input-- > 0 ? "bold" : "dotted") | |
<< "]" << std::endl; | |
} | |
std::cout << "}" << std::endl; | |
return 0; | |
} |
The randomgraph application described before allows to output random maximal planar graphs.
Even more, it creates random maximal planar combinatorial embeddings.
When "-o" output file has a ".a" suffix, the combinatorial embedding is in the written adjacency lists:
hermann@7600x:~$ NOSTAT=1 randomgraph 8 -o x.a -s 123456 && cat x.a
[[1,7,3,5,2,4],[0,4,2,3,6,7],[0,5,3,1,4],[0,7,6,1,2,5],[2,1,0],[3,2,0],[3,7,1],[6,3,0,1]]
hermann@7600x:~$
But the vertices in this representation are 0-based and not 1-based as in LEDA graph format.
New "dbg" option for straight_line_drawing.cpp allows to reduce the graphviz vertex labels by 1 to match the adjacency list output for easy visual inspection of the embedding ordering at any given vertex. For example for vertex 3
its adjacency list [0,7,6,1,2,5]
can be verified easily when displayed with GraphvizFiddle.py, as ordered counterclockwise traversal of the edges at vertex 3
:
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Associated forum thread:
https://forums.raspberrypi.com/viewtopic.php?t=367391
C60 fullerene was drawn as example graph:
![BGL C60 planar_straight_line_drawing](https://private-user-images.githubusercontent.com/12639134/326284463-0f7f3c09-bcd3-4b49-a938-eccbb7fd27e4.jpg?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjE4MDkxMjUsIm5iZiI6MTcyMTgwODgyNSwicGF0aCI6Ii8xMjYzOTEzNC8zMjYyODQ0NjMtMGY3ZjNjMDktYmNkMy00YjQ5LWE5MzgtZWNjYmI3ZmQyN2U0LmpwZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA3MjQlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwNzI0VDA4MTM0NVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWNiYWFjNjYzMzA2ODFhOGI4YzRjZjgwNGJiYTMxZGNmY2ZmNDk2ZDUxMjFiNmZjNDFlZTNiNjI4YjE5ZTliOGYmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.QbFSflYrcxKeSwUOC6xsjpjU981pLNbwIWYdL6SNAFU)
https://forums.raspberrypi.com/viewtopic.php?t=367391#p2204504
It is also called "football fullerene", consists of 20 hexagons and 12 pentagons.
Here is C60 spherical embedding you most likely know:
![Football_Pallo_valmiina-cropped](https://private-user-images.githubusercontent.com/12639134/326284971-9dc69284-5e3f-4501-bb3e-7be096636ae1.jpg?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjE4MDkxMjUsIm5iZiI6MTcyMTgwODgyNSwicGF0aCI6Ii8xMjYzOTEzNC8zMjYyODQ5NzEtOWRjNjkyODQtNWUzZi00NTAxLWJiM2UtN2JlMDk2NjM2YWUxLmpwZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA3MjQlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwNzI0VDA4MTM0NVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWU4MjVkYWQ2YjFlNWZjNjE2MzY3YTRmOTNkNWIyMDNjNGMyYjA3MmE2YzVmMDUzNDkyYWRjNDg0M2FhOWYwMWQmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.Wk4Tx86JHQ30MxS96RXXyx-bbCHAbRtm5wEhRxiQgTQ)