breadth_first_search on labeled_graph

Question

How should breadth_first_search be called using labeled_graph assuming the following setup? - results in 2 errors:

binary '[' : no operator found which takes a right-hand operand of type 'Vertex' (or there is no acceptable conversion)

Error 2 left of '.id' must have class/struct/union

#include<iostream>
#include<boost/graph/adjacency_list.hpp>
#include<boost/graph/breadth_first_search.hpp>
#include <boost/graph/labeled_graph.hpp>

using namespace boost;

struct NodeInfo{int id;};
struct EdgeInfo{};

typedef boost::labeled_graph< boost::adjacency_list<
    boost::vecS, boost::vecS, boost::undirectedS, NodeInfo, EdgeInfo>,
    std::string> Graph;

typedef boost::graph_traits<Graph>::vertex_descriptor GridVertex;

class Topology 
{
public:

    Graph grid;
    std::map<std::string, GridVertex> vertices; //_id to Edge

    struct custom_visitor : public boost::default_bfs_visitor
    {
        Graph& grid;

        custom_visitor(Graph& grid) :grid(grid)  {}

        template <typename Vertex, typename Graph>
        void discover_vertex(Vertex v, const Graph& g)
        {

            //vertex(...) in breadth_first_search is causing: 
            //binary '[' : no operator found which takes a right-hand operand of 
            //type 'Vertex' (or there is no acceptable conversion)  
            //left of .id must have class...
            int m = grid[v].id;

        }
    };

    void GetShortestPath(std::string s_id, std::string t_id)
    {
        custom_visitor vis(grid);

        //vertex(...) causes error
        breadth_first_search(grid.graph(), vertex(vertices[s_id],grid.graph()), visitor(vis));
    }

    void BuildNet()
    {
        Graph g;
        GridVertex v;

        v = add_vertex("A", NodeInfo(), g);
        vertices["A"] = v;

        v = add_vertex("B", NodeInfo(), g);
        vertices["B"] = v;

        add_edge_by_label("A", "B", EdgeInfo(), g);
    }
};


int main()
{
    Topology net;
    net.GetShortestPath("A", "B");
    return 0;
}

score 2 · Accepted Answer · answered Mar 09 '16 at 08:01

2

Why are you using labeled_graph?

Labeled graph has a different interface from just adjacency_list. This is not surprising, because, what would be the point otherwise :)

So, if vertex(...) causes error use grid.vertex(s_id):

breadth_first_search(grid.graph(), grid.vertex(s_id), visitor(vis));

In the visitor, use the actual graph so you can use its operator[]:

int m = grid.graph()[v].id;

Or, in fact why not use the second parameter which exists for the purpose:

void discover_vertex(Vertex v, const Graph& g) {
    int m = g[v].id;
}

An effort to make a sensible example from the code: Live On Coliru

answered Mar 09 '16 at 08:01

sehe

374,641
47
450
633

Thanks @sehe. Somehow labeled_graph seems very intuitive with ids read directly from a database. – Tims Mar 09 '16 at 16:25
1

Ok. As you've probably found out it's not a well supported part of the library and I would rate it a rather [Leaky Abstraction](http://www.joelonsoftware.com/articles/LeakyAbstractions.html). Consider using the Graph models directly for a while - until you'd be comfortable writing the labeled adapter yourself, basically. This could improve the learning curve – sehe Mar 09 '16 at 16:29
Sure, will plan for a transition – Tims Mar 09 '16 at 16:46
1

Cheers. Rest assured, I have learned about labeled_graph the hard way. Frankly I was a bit shocked at [the state of maintenance](http://stackoverflow.com/a/35640105/85371) it is in. It's probably easier to write some more verbose code than grappling with the leaky abstraction. Of course, you are free to judge it for yourself. If you keep using it, perhaps you can improve it! – sehe Mar 09 '16 at 16:50

breadth_first_search on labeled_graph

1 Answers1

Linked