[Boost-users] BGL -- adjacency_matrix, graph concepts

Subject: [Boost-users] BGL -- adjacency_matrix, graph concepts
From: Raymond Wan (r.wan_at_[hidden])
Date: 2009-10-06 02:06:54

Hi all,

I have a basic question about BGL, but I'm a bit too new with templating 
to understand some of the terms used in the documentation...  :-(

I'd like to build a graph using an adjacency matrix and the 
edge_iterator_constructor of the graph (or anything faster than repeated 
add_edge's).  In the docs, I found this for adjacency_list:

template <class EdgeIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
                vertices_size_type n,
                edges_size_type m = 0,
                const GraphProperty& p = GraphProperty())

but the closest I found for adjacency_matrix is:

template <typename EdgeIterator>
adjacency_matrix(EdgeIterator first,
                  EdgeIterator last,
                  vertices_size_type n,
                  const GraphProperty& p = GraphProperty())

It's not the same because of "typename"?  As a toy example, I've taken 
the MST example and have modified it a lot to get this:

-----
#include <boost/config.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

int main () {
   using namespace boost;
   typedef adjacency_matrix < undirectedS, no_property, property < 
edge_weight_t, int > > Graph;
   typedef graph_traits < Graph >::edge_descriptor Edge;
   typedef graph_traits < Graph >::vertex_descriptor Vertex;
   typedef std::pair<int, int> E;

   const int num_nodes = 5;
   E edges[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
     E(3, 4), E(4, 0)
   };
   int weights[] = { 1, 1, 2, 7, 3, 1, 1 };
   std::size_t num_edges = sizeof(edges) / sizeof(E);

   Graph g1 (num_nodes);
   for (unsigned int i = 0; i < num_edges; i++) {
     add_edge (edges[i].first, edges[i].second, g1);
   }
   print_graph (g1);

   Graph g2 (num_nodes);
//   Graph g2 (edges, edges + num_edges, weights, num_nodes);
   print_graph (g2);

   return EXIT_SUCCESS;
}
-----

The 5th line from the end is what is causing me problems.  It seemed to 
work with an adjacency_list.  (I'd also would like to add weights, but I 
guess add_edge could support that...I just think that this way is faster 
based on the "Quick Tour of the BGL" page in the docs.)

I looked in my examples directory [1.39] and simply grepped for 
"adjacency_matrix" and came up with only one file:  adjacency_matrix.cpp 
.  Other than the pros/cons of adjacency matrices and lists, is there 
something wrong with adjacency matrices; any reason for its absence in 
the examples directory?

One final question -- in the documentation, it lists various graph 
concepts 
(http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/graph_concepts.html) 
such as BidirectionalGraph, VertexAndEdgeListGraph, AdjacencyMatrix, 
etc.  Are these concepts relevant to BGL or only in a general sense? 
What I mean is what is their relationship with adjacency_list and 
adjacency_matrix?  Any pointers would be appreciated...

Thank you!

Ray