Pretty print vertex and edges structs via boost::dynamic_properties

Question

I'm trying to make a nice print of the verticies proprieties of both Bidder and Item. This is my structure.

struct Graph{
    std::vector<int>bidder2item;
    std::vector<int>item2bidder;
};

namespace Nodes {
    struct Bidder {
        int id;
        int best_item = -1;
        double val_first_best_item = -1.;
        double val_second_best_item = -1.;
    };

    struct Item {
        int id;
        double cost = 0.;
        int high_bidder = -1;
        double high_bid = -1.;
    };

    static inline std::ostream& operator<<(std::ostream& os, Bidder const& b) {
        return os << "BIDDER: id:\t" << b.id << "\tbest_item:\t" << b.best_item << "\tval_first_best_item:\t" << b.val_first_best_item << "\tval_second_best_item\t" << b.val_second_best_item;
    }
    static inline std::ostream& operator<<(std::ostream& os, Item const& i) {
        return os << "BIDDER: id:\t" << i.id << "\cost:\t" << i.cost << "\high_bidder:\t" << i.high_bidder << "\high_bid\t" << i.high_bid;
    }
}

struct Edge {
    double weight;
};

using Nodes::Bidder;
using Nodes::Item;

using Vertex = boost::variant<Bidder, Item>;
using UndirectedGraph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex, Edge, Graph>; // Vertex Graph
using edge_iterator = boost::graph_traits<UndirectedGraph>::edge_iterator;
using vertex_iterator = boost::graph_traits<UndirectedGraph>::vertex_iterator;

The next function is used to randomly generate a bipartite graph an the second one is to visualize the vertices proprieties.

UndirectedGraph return_graph(std::vector<std::vector<float>> *cost_matrix, const int *n_bidders_items) {

    std::uniform_real_distribution<float> distribution(0., 20.);

    UndirectedGraph random_graph;

    for (int i = 0; i < *n_bidders_items * 2; ++i) {
        if (i < *n_bidders_items) boost::add_vertex(Bidder{i}, random_graph);
        else boost::add_vertex(Item{i}, random_graph);
    }

    random_graph[boost::graph_bundle].bidder2item = *new std::vector<int>(*n_bidders_items, -1);
    random_graph[boost::graph_bundle].item2bidder = *new std::vector<int>(*n_bidders_items, -1);


    // Every left nodes has a connection to every right nodes
    for (int i = 0; i < *n_bidders_items; ++i) {
        for (int j = *n_bidders_items; j < *n_bidders_items * 2; ++j) {
            if (i != j) {
                float value = float(distribution(generator));
                (*cost_matrix)[i][j % (* n_bidders_items)] = value;
                boost::add_edge(i, j, Edge{value}, random_graph);
            }
        }
    }
    printGraph(&random_graph);
    return random_graph;
}

void printGraph(UndirectedGraph const *g) {
    boost::dynamic_properties dp;

    using V = UndirectedGraph::vertex_descriptor;
    using E = UndirectedGraph::edge_descriptor;

    using VertexFilter = std::function<bool(V)>;
    using EdgeFilter = std::function<bool(E)>;
    using FMap = boost::filtered_graph<UndirectedGraph, EdgeFilter, VertexFilter>;


    EdgeFilter any_interconnect = boost::keep_all{};
    VertexFilter bidders = [&g](V v) -> bool { return boost::get<Bidder>(&(*g)[v]); };
    VertexFilter items = [&g](V v) -> bool { return boost::get<Item>(&(*g)[v]); };

    FMap map_bidder = FMap(*g, any_interconnect, bidders);
    FMap map_items = FMap(*g, any_interconnect, items);

    dp.property("map_bidder", map_bidder);
    dp.property("map_items", map_items);
    boost::write_graphviz_dp(std::cout, *g, dp);

}

I have taken ispiration from the following previous posts:

• Make a boost filtered_graph by vertex label property
• Adding custom properties to vertex of a grid in Boost Graph Library

But I coudn't figure out how to make thigs work.

I would like to have something like so:

Bidder: ...proprieties... Edge Weight: weight Item: ...proprieties...

Answer 1

There's a big problem here:

using FMap = boost::filtered_graph<UndirectedGraph, EdgeFilter, VertexFilter>;

No matter what you call FMap, a filtered graph does not become a property map. That's why

dp.property("map_bidder", map_bidder);
dp.property("map_items", map_items);

makes no sense.

If you just want to print the bundle types, no need to complicate with filters:

void printGraph(Graph* g) {
    boost::dynamic_properties dp;
    dp.property("node_id", get(boost::vertex_index,  *g));
    dp.property("label",   get(boost::vertex_bundle, *g));
    dp.property("weight",  get(&EdgeProp::weight,    *g));
    boost::write_graphviz_dp(std::cout, *g, dp);
}

Now there are some warts because dynamic_properties requires that the maps are read & write, so we have to complete the set of IO operations to make things compile:

using VertexProp = boost::variant<Bidder, Item>;
static inline std::istream& operator>>(std::istream& is, VertexProp&) { return is; }

see boost::dynamic_properties and immutable graph object and Boost::Graph: how to import graphviz with custom Vertex class for more background

That should already be enough:

graph G {
0 [label="BIDDER: id:   0       best_item:      -1      val_first_best_item:    -1      val_second_best_item    -1"];
1 [label="BIDDER: id:   1       best_item:      -1      val_first_best_item:    -1      val_second_best_item    -1"];
2 [label="BIDDER: id:   2       best_item:      -1      val_first_best_item:    -1      val_second_best_item    -1"];
3 [label="BIDDER: id:   3       best_item:      -1      val_first_best_item:    -1      val_second_best_item    -1"];
4 [label="BIDDER: id:   4       best_item:      -1      val_first_best_item:    -1      val_second_best_item    -1"];
5 [label="BIDDER: id:   0       cost:   0       high_bidder:    -1      high_bid        -1"];
6 [label="BIDDER: id:   1       cost:   0       high_bidder:    -1      high_bid        -1"];
7 [label="BIDDER: id:   2       cost:   0       high_bidder:    -1      high_bid        -1"];
8 [label="BIDDER: id:   3       cost:   0       high_bidder:    -1      high_bid        -1"];
9 [label="BIDDER: id:   4       cost:   0       high_bidder:    -1      high_bid        -1"];
0--5  [weight=7.42609];
0--6  [weight=6.42883];
0--7  [weight=1.64521];
0--8  [weight=15.1427];
0--9  [weight=13.3676];
1--5  [weight=17.7843];
1--6  [weight=18.2666];
1--7  [weight=2.03375];
1--8  [weight=15.3638];
1--9  [weight=14.0291];
2--5  [weight=15.3731];
2--6  [weight=15.6312];
2--7  [weight=16.2417];
2--8  [weight=14.2055];
2--9  [weight=15.9913];
3--5  [weight=13.4127];
3--6  [weight=18.6377];
3--7  [weight=18.6832];
3--8  [weight=9.63378];
3--9  [weight=4.45048];
4--5  [weight=2.89091];
4--6  [weight=16.1538];
4--7  [weight=17.5303];
4--8  [weight=10.4171];
4--9  [weight=10.4213];
}

OTHER ISSUES

• Don't write the memory leak operator (*new X)

• In fact don't write new or delete

• Also, stop using pointers instead references

• the condition i != j was never true. This was the result of your overcomplicated index-calculations, simplify and use readable names:

   for (int bidder = 0; bidder < N; ++bidder) {
       for (int item = 0; item < N; ++item) {
           if (bidder != item) {
               float value = distribution(generator);
  
               data.cost_matrix[bidder][item] = value;
               boost::add_edge(bidder, N + item, EdgeProp{value}, g);
           }
       }
   }
  

• a function named return_graph is poorly named, prefer generateRandomGraph or something

• a function named generateGraph should not be printing a graph. What use is the printGraph function then?

   return_graph(...); // also prints the graph by the way
  

  Should be

   auto g = generateGraph();
   // ...
   printGraph(g);
  

• The generation function "takes" a const_matrix. But in reality it returns all the values. Instead of burdening the caller with creating the matrix ahead of time, and making sure the n_bidders_items matches its dimensions (!), just return both!

   using Matrix = std::vector<std::vector<float>>;
   struct Data {
       Matrix cost_matrix;
       Graph  graph;
   };
  
  Data generateData(int N) {
       Data data;
       auto& [cm, g] = data;
  
       data.cost_matrix.assign(N, Matrix::value_type(N, 0));
       std::uniform_real_distribution<float> distribution(0., 20.);
  
       for (int i = 0; i < N; ++i)
           add_vertex(Bidder{i}, g);
       for (int i = 0; i < N; ++i)
           add_vertex(Item{N + i}, g);
  
       GraphProp& gp = g[boost::graph_bundle];
       gp.bidder2item.assign(N, -1);
       gp.item2bidder.assign(N, -1);
  
       // Every left nodes has a connection to every right nodes
       for (int bidder = 0; bidder < N; ++bidder) {
           for (int item = 0; item < N; ++item) {
               if (bidder != item) {
                   float value = distribution(generator);
  
                   data.cost_matrix[bidder][item] = value;
                   add_edge(bidder, N + item, EdgeProp{value}, g);
               }
           }
       }
  
       return data;
   }
  

I address all the above in my version below. Things I did not address:

• It looks a bit like you're on two minds about the type of graph. On the one hand you chose to model as an undirected adjacency_list, but then the use of the properties suggests that the model could actually be an adjacency_matrix or even a grid_graph

Full Demo

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/variant.hpp>
#include <random>

static std::mt19937 generator{std::random_device{}()};

namespace Nodes {
    struct Bidder {
        int    id;
        int    best_item            = -1;
        double val_first_best_item  = -1.;
        double val_second_best_item = -1.;
    };

    struct Item {
        int    id;
        double cost        = 0.;
        int    high_bidder = -1;
        double high_bid    = -1.;
    };

    static inline std::ostream& operator<<(std::ostream& os, Bidder const& b) {
        return os << "BIDDER: id:\t" << b.id << "\tbest_item:\t" << b.best_item
                << "\tval_first_best_item:\t" << b.val_first_best_item
                << "\tval_second_best_item\t" << b.val_second_best_item;
    }
    static inline std::ostream& operator<<(std::ostream& os, Item const& i) {
        return os << "BIDDER: id:\t" << i.id << "\tcost:\t" << i.cost
                << "\thigh_bidder:\t" << i.high_bidder << "\thigh_bid\t"
                << i.high_bid;
    }
    struct EdgeProp {
        double weight;
    };

    using VertexProp = boost::variant<Bidder, Item>;
    static inline std::istream& operator>>(std::istream& is, VertexProp&) { return is; }
} // namespace Nodes

using Nodes::Bidder;
using Nodes::Item;
using Nodes::EdgeProp;
using Nodes::VertexProp;

struct GraphProp {
    std::vector<int> bidder2item;
    std::vector<int> item2bidder;
};

using Graph = boost::adjacency_list<               //
    boost::listS, boost::vecS, boost::undirectedS, //
    VertexProp, EdgeProp, GraphProp>;

using Matrix = std::vector<std::vector<float>>;
struct Data {
    Matrix cost_matrix;
    Graph  graph;
};

Data generateData(int N) {
    Data data;
    auto& [cm, g] = data;

    data.cost_matrix.assign(N, Matrix::value_type(N, 0));
    std::uniform_real_distribution<float> distribution(0., 20.);

    for (int i = 0; i < N; ++i)
        add_vertex(Bidder{i}, g);
    for (int i = 0; i < N; ++i)
        add_vertex(Item{N + i}, g);

    GraphProp& gp = g[boost::graph_bundle];
    gp.bidder2item.assign(N, -1);
    gp.item2bidder.assign(N, -1);

    // Every left nodes has a connection to every right nodes
    for (int bidder = 0; bidder < N; ++bidder) {
        for (int item = 0; item < N; ++item) {
            if (bidder != item) {
                float value = distribution(generator);

                data.cost_matrix[bidder][item] = value;
                add_edge(bidder, N + item, EdgeProp{value}, g);
            }
        }
    }

    return data;
}

void printGraph(Graph& g) {
    boost::dynamic_properties dp;
    dp.property("node_id", get(boost::vertex_index,  g));
    dp.property("label",   get(boost::vertex_bundle, g));
    dp.property("weight",  get(&EdgeProp::weight,    g));
    write_graphviz_dp(std::cout, g, dp);
}

int main() {
    auto [cost_matrix, graph] = generateData(5);
    printGraph(graph);
}

Printed:

graph G {
0 [label="BIDDER: id:   0   best_item:  -1  val_first_best_item:    -1  val_second_best_item    -1"];
1 [label="BIDDER: id:   1   best_item:  -1  val_first_best_item:    -1  val_second_best_item    -1"];
2 [label="BIDDER: id:   2   best_item:  -1  val_first_best_item:    -1  val_second_best_item    -1"];
3 [label="BIDDER: id:   3   best_item:  -1  val_first_best_item:    -1  val_second_best_item    -1"];
4 [label="BIDDER: id:   4   best_item:  -1  val_first_best_item:    -1  val_second_best_item    -1"];
5 [label="BIDDER: id:   5   cost:   0   high_bidder:    -1  high_bid    -1"];
6 [label="BIDDER: id:   6   cost:   0   high_bidder:    -1  high_bid    -1"];
7 [label="BIDDER: id:   7   cost:   0   high_bidder:    -1  high_bid    -1"];
8 [label="BIDDER: id:   8   cost:   0   high_bidder:    -1  high_bid    -1"];
9 [label="BIDDER: id:   9   cost:   0   high_bidder:    -1  high_bid    -1"];
0--6  [weight=5.00229];
0--7  [weight=18.2496];
0--8  [weight=15.024];
0--9  [weight=2.74795];
1--5  [weight=2.54128];
1--7  [weight=5.28732];
1--8  [weight=19.3544];
1--9  [weight=15.8096];
2--5  [weight=1.76579];
2--6  [weight=4.12413];
2--8  [weight=12.156];
2--9  [weight=8.35624];
3--5  [weight=12.4344];
3--6  [weight=1.87166];
3--7  [weight=18.5511];
3--9  [weight=13.3363];
4--5  [weight=6.61118];
4--6  [weight=1.03358];
4--7  [weight=17.1966];
4--8  [weight=2.37933];
}