7

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.

Emil Lundberg
  • 7,268
  • 6
  • 37
  • 53
sunky
  • 73
  • 1
  • 4

1 Answers1

6

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: '
'
sehe
  • 374,641
  • 47
  • 450
  • 633
  • Aha, that's a sleek way to do text phrasing! But for more generic purposes, I'd like to use the adjacent_list class so that I can utilize most of the graph concept and achieve maximum flexibility. thus I'd like to treat the node id as a property of the vertex instead of the vertex descriptor. but also I'd like to use node id to visit the vertex descriptor too. It seems the property map class can only map the descriptor to property of the descriptor. I don't know how to do it the other way around. – sunky Mar 22 '14 at 04:28
  • Hmm. Those are completely different questions. Also, I don't see the contradiction (why "But for"). Years of experience make me pretty confident that I can easily adapt the parsing to your graph type. If you have unrelated questions about adjacency_list you should consider asking a new question. – sehe Mar 22 '14 at 08:02
  • Finally, BGL uses vertex as the term for nodes. So the node id is the vertex ID _by definition_. You just want to store it differently. I think BGL calls that Bundled Properties? – sehe Mar 22 '14 at 08:05
  • The following error is raised, when I try to compile on a system. `error: 'istream_iterator' is not a member of 'boost::spirit'` – sAguinaga May 29 '16 at 14:25
  • To @user8793459 that posted [this follow-up](https://stackoverflow.com/q/46802313/85371); using Spirit was a bit of a joke because this question was so unconstrained and basically showed no prior effort. Here's a pure C++ standard-library approach that isn't even much more complicated: http://coliru.stacked-crooked.com/a/3ef8b37871333756 – sehe Oct 19 '17 at 16:04
  • @sunky And for the adjacency list, here's my take on it too: http://coliru.stacked-crooked.com/a/97088f1ae555e054 – sehe Oct 19 '17 at 16:16