[Boost-users] [graph] VertexList type boost::vecS and boost::listS

Subject: [Boost-users] [graph] VertexList type boost::vecS and boost::listS
From: Christoph (c_p_at_[hidden])
Date: 2011-10-14 09:27:04

Hi,

I have some Questions concerning the Boost Graph Library graph template
selector VertexList type. In the docs at
http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_adjacency_list.html
I just found the two types documented.

1. How do i use the printed_graph (...) with a graph type that uses
boost::listS instead of boost::vecS? 

I read that by using boost::vecS there is automatically an internal
property for each Vertex created, which is the index of the vertex. I
assume this is the reason why 'add_edge (1,2,g);' and 
'print_graph (g,get(boost::vertex_index, g));' work for a graph g with a
boost::vecS VertexList.

However i cannot simply do 'add_edge (1,2,g);' or 'print_graph
(g,get(boost::vertex_index, g));' vor a graph g with a VertexList type
listS. 

How do i specify a vertex_index property for VertexList listS graph
type, so that i can somehow use print_graph (g,something);?

How are vertices internally identified when using listS? Are there any
documentations about the function 'vertex()'? I think it is missing in
Table 1: Summary of boost graph concepts in
http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/graph_concepts.html

Look at the difference in using add_edge for the two different graph
types and what happens if i try to insert an edge with one vertex not
yet being part of the vertex set.

Here is an example:
//begin code
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

typedef boost::adjacency_list < boost::listS,
                                boost::vecS,
                                boost::bidirectionalS>
link_graph_vertex_vec;

typedef boost::adjacency_list < boost::listS,
                                boost::listS,
                                boost::bidirectionalS>
link_graph_vertex_list;

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

        link_graph_vertex_vec 	g1(3);
        std::cout << "Number of vertices in g1: " << num_vertices (g1) <<
std::endl;	
        add_edge (0,1,g1);
        std::cout << "Number of vertices in g1: " << num_vertices (g1) <<
std::endl;
        add_edge (1,2,g1);
        std::cout << "Number of vertices in g1: " << num_vertices (g1) <<
std::endl;
        add_edge (2,10,g1);
        std::cout << "Number of vertices in g1: " << num_vertices (g1) <<
std::endl;
        print_graph (g1, get(boost::vertex_index, g1));
        
        link_graph_vertex_list 	g2(3);
        std::cout << "Number of vertices in g2: " << num_vertices (g2) <<
std::endl;	
        add_edge (vertex(0,g2), vertex(1,g2), g2);//add_edge (0,1,g2);
        std::cout << "Number of vertices in g2: " << num_vertices (g2) <<
std::endl;
        add_edge (vertex(1,g2), vertex(2,g2), g2);//add_edge (1,2,g2);
        std::cout << "Number of vertices in g2: " << num_vertices (g2) <<
std::endl;
        //add_edge (vertex(2,g2), vertex(3,g2), g2);//add_edge (2,3,g2);
        //vertex(3,g2) // what is the return type, why does the program exit?
        std::cout << "Number of vertices in g2: " << num_vertices (g2) <<
std::endl;
        
    return 0;
}
//end code

I have to decide whether to use boost::listS or boost::vecS for the
VertexList type. The 'interface' of the vecS type graph operations are
much easier for me to understand and to use. But on the other hand the
listS type has the faster remove and insert operations.

best regards
Christoph