Using boost graph library: how to create a graph by reading edge lists from file

Question

I'm new to boost graph library and I'd like to create a graph by reading edge lists from a file.

A sample of the edge_list.dat file is this:

...
123 445
4535 343
3432 454
123 345
123 566
...

Each line of the file represents an edge of the graph, and the two numbers in each line are the nodes' ids corresponding to the edge. Now I'd like to create a graph from the file edge_list.dat using boost graph library.

However, I don't know the size of the graph in advance. I need to add the vertex into the graph along the way. However it is not practical to create a vertex descriptor for each vertex like this:

Graph::vertex_descriptor v0 = boost::add_vertex(g);
Graph::vertex_descriptor v1 = boost::add_vertex(g);

And I'd like to access the vertex through the vertex id. I don't really know how to do this. For now the solution that I come up with is to create a map for which the key is the id and the value is the vertex_descriptor:

std::map<int,Graph::vertex_descriptor> VertexList;
VertexList[123]=boost::add_vertex(g);

However is there a way that I can do this without creating the map?

Thanks in advance.

Answer 1

Soooo. Ambitious, huh :)

Boost Graph library. And text parsing. Let's see what we can do: Boost Graph + Boost Spirit Qi = nice teamwork.

See it Live On Coliru

#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/graph/edge_list.hpp>
#include <fstream>

typedef std::pair<int,int> Edge;
typedef std::vector<Edge> EdgeList;
typedef boost::edge_list<EdgeList::iterator> Graph;

namespace qi = boost::spirit::qi;

int main()
{
    std::ifstream ifs("input.txt");
    ifs >> std::noskipws;

    boost::spirit::istream_iterator f(ifs), l;

    std::vector<Edge> edges;
    bool parse_ok = qi::phrase_parse(f, l, (qi::int_ >> qi::int_) % qi::eol, qi::blank, edges);

    Graph g(edges.begin(), edges.end());

    if (parse_ok)
    {
        std::cout << "Graph parsed with " << num_edges(g) << " edges\n";
    } else
        std::cout << "Parse error\n";

    if (f!=l)
        std::cout << "Remaining unparsed input: '" << std::string(f,l) << "'\n";
}

Prints (for the valid input lines above):

Graph parsed with 5 edges
Remaining unparsed input: '
'