Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW
Created March 18, 2024 19:55
Show Gist options
  • Save Hermann-SW/fc6ce25be40b72579c4ff05a38a9a30a to your computer and use it in GitHub Desktop.
Save Hermann-SW/fc6ce25be40b72579c4ff05a38a9a30a to your computer and use it in GitHub Desktop.
Using C++ Boost lib "read_graphviz()" to convert a graph int LEDA graph format
//=======================================================================
// 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=dot2leda
g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f -lboost_graph
cpplint --filter=-legal/copyright,-build/namespaces $f.cpp
cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config
*/
//=======================================================================
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
using namespace std;
int main(int argc, char *argv[]) {
assert(argc == 2);
typedef adjacency_list< vecS, vecS, undirectedS,
property< vertex_name_t, string > > graph_t;
graph_t graph(0);
dynamic_properties dp;
property_map< graph_t, vertex_name_t >::type vname
= get(vertex_name, graph);
dp.property("node_id", vname);
ifstream gvgraph(argv[1]);
assert(read_graphviz(gvgraph, graph, dp, "node_id"));
cout << "LEDA.GRAPH" << "\n";
cout << "string" << "\n";
cout << "int" << "\n";
cout << num_vertices(graph) << "\n";
BOOST_FOREACH(graph_t::vertex_descriptor v, vertices(graph)) {
cout << get("node_id", dp, v) << "\n";
}
cout << num_edges(graph) << "\n";
BOOST_FOREACH(graph_t::edge_descriptor e, edges(graph)) {
cout << 1+source(e, graph) << " " << 1+target(e, graph)
<< " " << 0 << "\n";
}
return 0;
}
@Hermann-SW
Copy link
Author

Building and checking according to top comment instructions:

$ f=dot2leda
$ g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f -lboost_graph
$ cpplint --filter=-legal/copyright,-build/namespaces $f.cpp
Done processing dot2leda.cpp
$ cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config
Checking dot2leda.cpp ...
$ 

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 18, 2024

read_graphviz() has to be adapted to all properties that might occur in Graphviz .dot file.
leda2graph does simple transformation for example C60.dot fullerene:

$ curl -s https://stamm-wilbrandt.de/C60.dot | head -3
strict graph "60-fullerene" {
  A1 -- B1 -- C1 -- D1 -- E1 -- A1 
  A2 -- B2 -- C2 -- D2 -- E2 -- F2 -- G2 -- H2 -- I2 -- J2 -- K2 -- L2 -- M2 -- N2 -- O2 -- A2 
$ 
$ curl -s https://stamm-wilbrandt.de/C60.dot | tail -3
  J4 -- D5
  M4 -- E5
}
$ 

Angel brackets require "subgraph" before each opening "{".
But read_graphviz() does not read graph correctly.
This is planar graph K5-{4--5}, which works with graphviz (complete graph on 5 nodes without one edge):

graph { 1 -- {2 -- {3 -- {4 5}}} }

Even after adding "subgraph"s

graph { 1 -- subgraph {2 -- subgraph {3 -- subgraph {4 5}}} }

that also works fro graphviz, read_graphviz() does not read a single edge, so previous comment C60.dot has all angel brackets removed.

C60.dot is originally from this 2015 tweet:
https://twitter.com/HermannSW/status/554820349117091840

dot2leda in action:

$ ./dot2leda <(curl -s https://stamm-wilbrandt.de/C60.dot) | head -6
LEDA.GRAPH
string
int
60
A1
A2
$ ./dot2leda <(curl -s https://stamm-wilbrandt.de/C60.dot) | tail -3
31 15 0
40 20 0
49 25 0
$ 

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 18, 2024

Together with straight_line_graphviz.cpp and GraphvizFiddle.py gists allows to display planar straight line drawing in browser (layout is done by straight_line_graphviz.cpp, neato only used to display graph, does no layout itself):

$ GraphvizFiddle.py chromium-browser <(../straight_line_graphviz <(./dot2leda <(curl -s https://stamm-wilbrandt.de/C60.dot)))
$ 

Result is this planar straight line drawing of C60 fullerene in browser.

Layout is a bit big; after manually adding size="10,200" at bottom of editor and pressing Draw button you get below. The bold edges belong to C60, the dotted edges are part of the triangulation needed because of straight_line_drawing algorithm only working on maximal planar graph:
BGL C60 planar_straight_line_drawing

You might know C60 well, it is called "football fullerene" as well (it has twenty 6-gons and twelve 5-gons):
https://en.wikipedia.org/wiki/Buckminsterfullerene
image

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 19, 2024

After

sudo apt install libboost-doc
cd
cp -r /usr/share/doc/libboost1.74-doc/examples/libs/graph/example .
cd example

many of the examples making use of read_graphviz() do not even compile:

$ head -14 scc.cpp | tail -6
/*
   IMPORTANT!!!
   ~~~~~~~~~~~~
   This example uses interfaces that have been deprecated and removed from
   Boost.Grpah. Someone needs to update it, as it does NOT compile.
*/
$ 

This demo works, and was the basis I started with for ending in this gist code:

$ g++ graph-thingie.cpp -lboost_graph
$ ./a.out 
graph GRAPH (CX2A1Z)

vertex a (NODE_A)
vertex b (NODE_B)
vertex c ()
$

This is the demo input graph:

$ head -89 graph-thingie.cpp | tail -12
    const char* dot = "digraph \
{ \
  graph [name=\"GRAPH\", identifier=\"CX2A1Z\"] \
    \
    a [label=\"NODE_A\", root=\"1\"] \
    b [label=\"NODE_B\", root=\"0\"] \
 \
 a -> b [label=\"EDGE_1\"] \
 b -> c [label=\"EDGE_2\"] \
}";

    istringstream gvgraph(dot);
$ 

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment