sdgaw erzswer sdgaw erzswer -4 years ago 145
C++ Question

Constructing a Boost graph from a file (Adjacency list)

I'm trying to get started with the very good Boost graph library.

The first step is reading a graph from a file, where each line contains edges separated by spaces.

I can't seem to get it done right. My current code looks like this:

..include stuff..
using namespace boost;

typedef boost::adjacency_list<listS, vecS, undirectedS> Graph;

Graph get_graph(char* str1){

Graph g;

std::ifstream infile(str1);
std::string line;
int e1;
int e2;

//std::map<int,g> VertexList;

while (std::getline(infile, line)){

std::istringstream iss(line);

//std::cout<<line<<"\n";

std::vector<std::string> strs;
split(strs, line, is_any_of(" "));


//std::cout<<" Adding edge: " << strs[0]<< " to " << strs[1] << "\n";

std::istringstream ss(strs[0].substr(0,5));
ss >> e1;

std::istringstream s2(strs[1].substr(0,5));
s2 >> e2;


//ADD e1 and e2 to a graph and connect them with an edge somehow!



// VertexList[123]=boost::add_vertex(g);

//Graph::vertex_descriptor v2 = boost::add_vertex(g);

//add individual vertices to the graph..
//e1 = add_vertex(g);
//e2 = add_vertex(g);

//add the corresponding edge..


}

std::cout<<num_vertices(g)<<std::endl;



return g;

}

int main(int argc, char *argv[]){

Graph g = get_graph(argv[1]);


//degree_vec(g);

return 0;

}


File example:

214328887 34428380
17116707 28465635
380580781 18996905
221036078 153460275
107830991 17868918
151338729 222261763
19705747 34428380
222261763 88323281
19933035 149538028
158419434 17434613


Things I tried and kind of worked:


  • Using boost graph library: how to create a graph by reading edge lists from file, but it reads Edge lists, which do not help me as I can not call functions, bound to Adjacency lists (or can I?)

  • Using
    add_edge(e1,e2,g)
    did not work, as in this case
    e1
    and
    e2
    can only be unsigned integers of length 1 (?), It threw some weird results if I used
    add_edge(123,32,g)
    for example. (like when I counted vertices, there were 122, instead of 1)

  • Using
    vertex_descriptors
    , for e.g.
    Graph::vertex_descriptor e1 = boost::add_vertex(g);
    and then adding edges using these descriptors, but I can't seem to make it work (as I said, this is relatively new to me)


Answer Source

Using add_edge(e1,e2,g)

Sure it does! Your assumptions about how adjacency_list<..., vecS,... > should work are wrong. The vertex-descriptor IS the vertex index in that case and vertices are random-access (due to vecS).

If you want to make the numbers as read "just" an ID, make them a property of your vertex, instead of directly using them as the vertex index. Most likely you will want to use some node-based container selector for the vertex container (so instead of vecS e.g. listS). Next, you probably want an id or name property associated with each vertex. May I suggest a bundled property:

struct VertexProperty {
    int id;
};

typedef boost::adjacency_list<listS, vecS, undirectedS, VertexProperty> Graph;

std::istringstream iss(line);
if (iss >> e1 >> e2) {
    // find or insert v1 and v2, e.g. insert by:
    auto v1 = add_vertex(VertexProperty { e1 }, g);
    auto v2 = add_vertex(VertexProperty { e2 }, g);

    add_edge(v1, v2, g);
}

Notes:

BONUS: labeled_graph demo

As a bonus, here's an example using labeled_graph adaptor:

Live On Coliru

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

using namespace boost;

typedef boost::adjacency_list<listS, vecS, undirectedS> AdjList;
typedef boost::labeled_graph<AdjList, size_t, mapS> Graph;

Graph get_graph(char* str1){

    Graph g; 

    std::ifstream infile(str1);
    std::string line;

    while (std::getline(infile, line)) {

        std::istringstream iss(line);

        size_t vid1, vid2;
        if (iss >> vid1 >> vid2) {
            auto v1 = add_vertex(vid1, g);
            auto v2 = add_vertex(vid2, g);

            add_edge(v1, v2, g);
        } else {
            std::cerr << "Skipped invalid line '" << line << "'\n";
        }

    }

    std::cout << num_vertices(g) << std::endl;
    return g;
}

int main(int argc, char *argv[]){ 
    if (argc<2) return 255;
    Graph g = get_graph(argv[1]);
}

Which prints (for the example input):

18

Which is correct since 222261763 and 34428380 occur twice in the input of 10 lines (10x2 - 2 == 18 vertices).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download