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

Subject: Re: [Boost-users] BGL -- adjacency_matrix, graph concepts
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-10-06 08:34:24

> 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,
>
> template <typename EdgeIterator>
> adjacency_matrix(EdgeIterator first,
>
> 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:
>

They're basically the same constructor. The extra int (m) in adjacency_list
is only used to disambiguate the signature from another constructor. The
value is effectively ignored, IIRC.

  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.)
>

You need to be more specific when you say, "causing me problems". If there's
a compiler error, what it is it? Is there a runtime error?

> 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?
>

They don't seem to be used as frequently, so don't get as much attention.

> 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...
>

These concepts describe the interface (functions, types, and semantics) used
to interact with graphs by the generic algorithms in the BGL. The
adjacency_list and adjacency_matrix are data structures that conform to the
requirements of the concepts.

Andrew Sutton
andrew.n.sutton_at_[hidden]