7

I have used a python library to generate the following GraphViz .dot file.

http://pastebin.com/mL7ck9Zp

I want to now read it into C++'s Boost::Graph so I can use Boost::Graph's library algorithms on it.

However, I need to do some preprocessing. In particular, I want to create a bundled property with a string constructor and have read_graphviz() pass the string in the label field in the dot file into the string constructor.

How do I go about doing this?

avak
  • 189
  • 1
  • 11
  • The constructor thing cannot be granted. The algorithm specifically requires the properties to be default constructible (hey, the docs not _that_ bad :)). _(You might parse into a temp graph, and build a clone from that in your preferred graph type)_ – sehe Apr 07 '15 at 21:43

1 Answers1

20

First thing to realize is that Boost documentation samples almost always refer to/are generated from the actual samples: libs/graph/example/read_graphviz.cpp

Second thing to realize is that BGL is highly generic. Highly. And it achieves much of this genericity on the concepts of Boost Property Maps.

Finally, observe that parsing from "free-form" (at least dynamically/untyped text form) into some kind of generic MutableGraph model is pushing the limits.

This explains how you would have to read important parts of the documentation under the docs for property_map.

Anyhow, since indeed the sample seems a bit dated, allow me to demonstrate:

  1. Include the implementation of the parser into one translation unit:

    #include <libs/graph/src/read_graphviz_new.cpp>

    This way BGL remains a header-only library.

  2. Prefer bundled properties these days:

    struct Vertex {
    std::string name, label, shape;
};

struct Edge {
    std::string label;
    double weight; // perhaps you need this later as well, just an example
};

typedef property<graph_name_t, std::string> graph_p;
typedef adjacency_list<vecS, vecS, directedS, Vertex, Edge, graph_p> graph_t;

    We will be filling label, shape, name for vertices and edges.

  3. The dynamic property maps are where the magic happens:

    dynamic_properties dp/*(ignore_other_properties)*/;

    This class provides type-erased access to a variety of underlying property maps identified by (name, typeid(key_type)).

    This means you can register the bundled properties, and map them to the graphviz attribute names:

    int main() {
    // Construct an empty graph and prepare the dynamic_property_maps.
    graph_t graph(0);

    dynamic_properties dp(ignore_other_properties);
    dp.property("node_id", get(&Vertex::name,  graph));
    dp.property("label",   get(&Vertex::label, graph));
    dp.property("shape",   get(&Vertex::shape, graph));
    dp.property("label",   get(&Edge::label,   graph));

    That's really all there is to it. (Read up on the magic of Bundled Properties, found via the page for the adjacency_list template).

    Though we don't need it, let's throw the graph property in the mix too (as in the documentation sample):

        // Use ref_property_map to turn a graph property into a property map
    boost::ref_property_map<graph_t *, std::string> gname(get_property(graph, graph_name));
    dp.property("name",    gname);

  4. Now all that's left is reading the graph.

    Well. Okay then. And let's write it back out too, but with a new graph name, then:

    std::ifstream dot("input.dot");

if (read_graphviz(dot, graph, dp/*, "node_id"*/)) {
    std::cout << "Graph name: '" << get_property(graph, graph_name) << "'\n";
    get_property(graph, graph_name) = "Let's give it a name";
    write_graphviz_dp(std::cout, graph, dp/*, "node_id"*/);
}

  5. Don't forget to link to Boost Regex

Full Demo

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/dynamic_property_map.hpp>
#include <libs/graph/src/read_graphviz_new.cpp>
#include <boost/graph/graph_utility.hpp>

using namespace boost;

struct Vertex {
    std::string name, label, shape;
};

struct Edge {
    std::string label;
    double weight; // perhaps you need this later as well, just an example
};

typedef property<graph_name_t, std::string> graph_p;
typedef adjacency_list<vecS, vecS, directedS, Vertex, Edge, graph_p> graph_t;

int main() {
    // Construct an empty graph and prepare the dynamic_property_maps.
    graph_t graph(0);

    dynamic_properties dp/*(ignore_other_properties)*/;
    dp.property("node_id", get(&Vertex::name,  graph));
    dp.property("label",   get(&Vertex::label, graph));
    dp.property("shape",   get(&Vertex::shape, graph));
    dp.property("label",   get(&Edge::label,   graph));

    // Use ref_property_map to turn a graph property into a property map
    boost::ref_property_map<graph_t *, std::string> gname(get_property(graph, graph_name));
    dp.property("name",    gname);

    std::ifstream dot("input.dot");

    if (read_graphviz(dot, graph, dp/*, "node_id"*/)) {
        std::cout << "Graph name: '" << get_property(graph, graph_name) << "'\n";
        get_property(graph, graph_name) = "Let's give it a name";
        write_graphviz_dp(std::cout, graph, dp/*, "node_id"*/);
    }
}

Prints (note the empty name before, and the updated graph name attribute, after):

Graph name: ''
digraph G {
name="Let's give it a name";
n0 [label="A9\n", shape=box];
n1 [label="- [0.48%,19.42%]", shape=ellipse];
n11 [label="+ [0%,0%]", shape=ellipse];
n12 [label="- [0%,0.75%]", shape=ellipse];
n13 [label="+ [0.03%,1.33%]", shape=ellipse];
n14 [label="- [0%,0.75%]", shape=ellipse];
n15 [label="+ [0%,0%]", shape=ellipse];
n16 [label="+ [0%,0%]", shape=ellipse];
n17 [label="A14\n", shape=box];
n18 [label="+ [0.03%,2.51%]", shape=ellipse];
n19 [label="A15\n", shape=box];
n2 [label="A15\n", shape=box];
n20 [label="A6\n", shape=box];
n21 [label="A2\n", shape=box];
n22 [label="- [0%,1.11%]", shape=ellipse];
n23 [label="+ [0%,1%]", shape=ellipse];
n25 [label="- [0%,2.18%]", shape=ellipse];
n26 [label="+ [0%,1.79%]", shape=ellipse];
n27 [label="- [0%,1%]", shape=ellipse];
n28 [label="- [0%,0%]", shape=ellipse];
n29 [label="- [0%,0%]", shape=ellipse];
n3 [label="A11\n", shape=box];
n30 [label="- [0%,0%]", shape=ellipse];
n31 [label="- [0%,0%]", shape=ellipse];
n32 [label="- [0%,1%]", shape=ellipse];
n33 [label="A13\n", shape=box];
n34 [label="+ [0%,1%]", shape=ellipse];
n35 [label="- [0%,0%]", shape=ellipse];
n36 [label="- [0.01%,1.21%]", shape=ellipse];
n38 [label="A12\n", shape=box];
n39 [label="- [0%,1%]", shape=ellipse];
n4 [label="A4\n", shape=box];
n40 [label="+ [0%,1.17%]", shape=ellipse];
n42 [label="- [0%,0%]", shape=ellipse];
n43 [label="A12\n", shape=box];
n44 [label="+ [0%,1.11%]", shape=ellipse];
n45 [label="- [0%,1%]", shape=ellipse];
n47 [label="- [0%,0%]", shape=ellipse];
n49 [label="+ [0%,1.17%]", shape=ellipse];
n5 [label="+ [0%,0%]", shape=ellipse];
n52 [label="+ [0%,0.75%]", shape=ellipse];
n54 [label="A13\n", shape=box];
n55 [label="A14\n", shape=box];
n56 [label="- [0.03%,2.5%]", shape=ellipse];
n57 [label="+ [0.01%,2.27%]", shape=ellipse];
n59 [label="- [0%,0%]", shape=ellipse];
n6 [label="A7\n", shape=box];
n60 [label="+ [0%,1%]", shape=ellipse];
n63 [label="A15\n", shape=box];
n64 [label="+ [0.05%,1.34%]", shape=ellipse];
n65 [label="A15\n", shape=box];
n66 [label="- [0%,1%]", shape=ellipse];
n67 [label="+ [0.02%,2.44%]", shape=ellipse];
n7 [label="A14\n", shape=box];
n71 [label="+ [0.21%,3.83%]", shape=ellipse];
n8 [label="+ [0%,1.57%]", shape=ellipse];
n9 [label="- [0.01%,1.22%]", shape=ellipse];
n0->n1  [label=f];
n0->n2  [label=t];
n17->n18  [label="<=110"];
n17->n19  [label=">110"];
n19->n20  [label="<=8"];
n19->n49  [label=">8"];
n2->n3  [label="<=228"];
n2->n71  [label=">228"];
n20->n21  [label=aa];
n20->n25  [label=c];
n20->n26  [label=cc];
n20->n27  [label=d];
n20->n28  [label=e];
n20->n29  [label=ff];
n20->n30  [label=i];
n20->n31  [label=j];
n20->n32  [label=k];
n20->n33  [label=m];
n20->n38  [label=q];
n20->n42  [label=r];
n20->n43  [label=w];
n20->n47  [label=x];
n21->n22  [label="<=41"];
n21->n23  [label=">41"];
n3->n4  [label="<=3"];
n3->n63  [label=">3"];
n33->n34  [label=g];
n33->n35  [label=p];
n33->n36  [label=s];
n38->n39  [label=f];
n38->n40  [label=t];
n4->n5  [label=l];
n4->n6  [label=u];
n4->n54  [label=y];
n43->n44  [label=f];
n43->n45  [label=t];
n54->n55  [label=g];
n54->n59  [label=p];
n54->n60  [label=s];
n55->n56  [label="<=204"];
n55->n57  [label=">204"];
n6->n7  [label=bb];
n6->n11  [label=dd];
n6->n12  [label=ff];
n6->n13  [label=h];
n6->n14  [label=j];
n6->n15  [label=n];
n6->n16  [label=o];
n6->n17  [label=v];
n6->n52  [label=z];
n63->n64  [label="<=4"];
n63->n65  [label=">4"];
n65->n66  [label="<=5"];
n65->n67  [label=">5"];
n7->n8  [label="<=164"];
n7->n9  [label=">164"];
}
sehe
  • 374,641
  • 47
  • 450
  • 633
  • Wow! Let me remove the comment about the documentation. I'm not a programmer and it was frustrating trying to get this to work. – avak Apr 07 '15 at 21:50
  • 1
    @avak Oh, I do realize I have the "unfair" advantage of having read through these docs many a time before (even so, I found it worth noting that I found the docs for property bundles only through the page for `adjacency_list`, e.g.). Cheers – sehe Apr 07 '15 at 21:52
  • I try this example in a similar graph but when I want to read the dot file I get this error: `Attempt to put a value into a const property map`, anyone knows what I am doing wrong? – Bruce Nov 08 '17 at 16:00
  • @Bruce I don't have my crystal ball polished, but a good guess is when your map doesn't model an [LvaluePropertyMap](http://www.boost.org/doc/libs/1_65_1/libs/property_map/doc/LvaluePropertyMap.html) where one is required. Feel free to post a question if you can't make it work – sehe Nov 08 '17 at 16:14
  • 3
    @sehe Ahh, I know what was the problem, I was using: `vertex_index` as `node_id` `dp.property ("node_id", get (boost::vertex_index, graph));` the put method of propertymap couldn't put vertex_index in the property map, by changinh it to another property such as string it works. – Bruce Nov 08 '17 at 16:15
  • @Bruce Thanks for the comment, I was having the same issue. I am using a std::string label in my bundled Vertex to workaround about this, as suggested. It works, but I would like to avoid it (having an unused data member, just to be able to read a graph). Is there another way to avoid that error? – phcerdan Aug 01 '19 at 15:54
  • 1
    @phcerdan You can fake it by modelling the LValuePropertyMap concept manually and feeding it (you may make it so the `put` operation throws?). – sehe Aug 05 '19 at 11:08
  • 1
    @phcerdan Ah. Another day where google tells me I've answered a very similar question before https://stackoverflow.com/a/27238425/85371 (it looks like you don't even have to bother with the missing `put` operation: it's not an issue if the code doesn't use that part of the concept interface) – sehe Aug 05 '19 at 11:08