BGL -- adjacency_matrix, graph concepts
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
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@gmail.com
Hi Andrew, Andrew Sutton wrote:
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.
I see -- then the fact that one says "class" and the other says "typename" is merely a typo? Or is there a difference, but based on my elementary level, that difference is unimportant? (I'm guessing the latter...)
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?
Sorry for not being clear! I thought what i did was "so" wrong, that my mistake was obvious (i.e., that constructor does not exist, etc.). The error I'm getting is a compiler error (below). Is the error telling me (from "candidates are...") that it only works with directed graphs? (Sorry for the strange characters...my g++ is printing them out and I don't know why...it looks like I'm using colorgcc in the wrong terminal, but I don't think that's the case.) ----- sample.cpp: In function âint main()â: sample.cpp:34: error: no matching function for call to âboost::adjacency_matrix<boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, std::allocator<bool> >::adjacency_matrix(main()::E [7], main()::E*, int [7], const int&)â /usr/local/boost_1_39_0/include/boost/graph/adjacency_matrix.hpp:601: note: candidates are: boost::adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>::adjacency_matrix(typename std::vector<typename boost::mpl::if_<typename boost::has_property<typename boost::detail::retag_property_list<boost::edge_bundle_t, EdgeProperty>::type>::type, std::pair<bool, typename boost::detail::retag_property_list<boost::edge_bundle_t, EdgeProperty>::type>, char>::type, typename Allocator::rebind<typename boost::mpl::if_<typename boost::has_property<typename boost::detail::retag_property_list<boost::edge_bundle_t, EdgeProperty>::type>::type, std::pair<bool, typename boost::detail::retag_property_list<boost::edge_bundle_t, EdgeProperty>::type>, char>::type>::other>::size_type) [with Directed = boost::undirectedS, VertexProperty = boost::no_property, EdgeProperty = boost::property<boost::edge_weight_t, int, boost::no_property>, GraphProperty = boost::no_property, Allocator = std::allocator<bool>] /usr/local/boost_1_39_0/include/boost/graph/adjacency_matrix.hpp:474: note: boost::adjacency_matrix<boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, std::allocator<bool> > ::adjacency_matrix(const boost::adjacency_matrix<boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, std::allocator<bool> >&) -----
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.
I see. Is that the only reason? I was worried that maybe there's a problem with adjacency_matrix (hence the compiler errors I was getting above).
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.
I see. In other words, BidirectionalGraph, etc. are "abstract views" and there is no way one would call a "BidirectionalGraph constructor" -- there's no such thing? For example, in the documentation, one might say that a problem requires a "BidirectionalGraph". This is short-hand for both the authors and the readers that the problem requires some data structure, types, etc.? Thank you for your help! Ray
AMDG Raymond Wan wrote:
Andrew Sutton wrote:
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.
I see -- then the fact that one says "class" and the other says "typename" is merely a typo? Or is there a difference, but based on my elementary level, that difference is unimportant? (I'm guessing the latter...)
class and typename are equivalent in this context. In Christ, Steven Watanabe
Hi Steven, Steven Watanabe wrote:
AMDG
Raymond Wan wrote:
Andrew Sutton wrote: I see -- then the fact that one says "class" and the other says "typename" is merely a typo? Or is there a difference, but based on my elementary level, that difference is unimportant? (I'm guessing the latter...)
class and typename are equivalent in this context.
Ok -- thanks for the clarification! Ray
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.)
Is the error telling me (from "candidates are...") that it only works with directed graphs? (Sorry for the strange characters...my g++ is printing them out and I don't know why...it looks like I'm using colorgcc in the wrong terminal, but I don't think that's the case.)
----- sample.cpp: In function âint main()â:
sample.cpp:34: error: no matching function for call to âboost::adjacency_matrix<boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, std::allocator<bool> >::adjacency_matrix(main()::E [7], main()::E*, int [7], const int&)â
Hmmm... I wonder if the compiler is having trouble telling the difference between edges and edges + num_edges. You might try passing edges as &edges[0] to force the compiler to treat it as a pointer. Maybe? Andrew Sutton andrew.n.sutton@gmail.com
Hi Andrew, Andrew Sutton wrote:
sample.cpp: In function âint main()â:
sample.cpp:34: error: no matching function for call to âboost::adjacency_matrix<boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, std::allocator<bool> >::adjacency_matrix(main()::E [7], main()::E*, int [7], const int&)â
Hmmm... I wonder if the compiler is having trouble telling the difference between edges and edges + num_edges. You might try passing edges as &edges[0] to force the compiler to treat it as a pointer. Maybe?
Unfortunately, no luck... And I didn't have this problem with adjacency_list (sorry for not saying this explicitly before!) and the same compiler (g++ v4.3.2). I guess that made me wonder if maybe this constructor does not exist? Or maybe I need to #include something more besides just "adjacency_matrix.hpp"? Hmmmm, I hope this is not too much to ask, but can you or someone else check if the sample code I posted before compiles (with the offending line uncommented)? I should compile as-is... Just to check if I'm going nuts... :-) Here it is again below [with the line commented out, so this should compile]. Thank you! Ray ----- #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[0], edges + num_nodes, weights, num_nodes); print_graph (g2); return EXIT_SUCCESS; }
Unfortunately, no luck... And I didn't have this problem with adjacency_list (sorry for not saying this explicitly before!) and the same compiler (g++ v4.3.2). I guess that made me wonder if maybe this constructor does not exist? Or maybe I need to #include something more besides just "adjacency_matrix.hpp"?
Hmmmm, I hope this is not too much to ask, but can you or someone else check if the sample code I posted before compiles (with the offending line uncommented)? I should compile as-is... Just to check if I'm going nuts... :-) Here it is again below [with the line commented out, so this should compile].
After looking, that constructor may not exist in Boost 1.39. It exists in trunk, but it seems to be causing problems (can't find add_edge). Your best bet is to construct the matrix over n vertices and then manually populate the graph with edges. Andrew Sutton andrew.n.sutton@gmail.com
Hi Andrew, Andrew Sutton wrote:
Hmmmm, I hope this is not too much to ask, but can you or someone else check if the sample code I posted before compiles (with the offending line uncommented)? I should compile as-is... Just to check if I'm going nuts... :-) Here it is again below [with the line commented out, so this should compile]. After looking, that constructor may not exist in Boost 1.39. It exists in trunk, but it seems to be causing problems (can't find add_edge).
Your best bet is to construct the matrix over n vertices and then manually populate the graph with edges.
Ah, thank you for looking into it for me! I'll do what you suggest then; thanks! By the way, is this something that should be added into the Boost bug database (or feature request)? Ray
Hi Andrew, Andrew Sutton wrote:
After looking, that constructor may not exist in Boost 1.39. It exists in trunk, but it seems to be causing problems (can't find add_edge).
Your best bet is to construct the matrix over n vertices and then manually populate the graph with edges.
I'm not 100% sure, but it seems like I can't add_edge () with edge weights for adjacency_matrix -- perhaps that function doesn't exist also? In my toy example, this works: typedef adjacency_list < vecS, vecS, undirectedS, no_property, property < edge_weight_t, int > > Graph; ... add_edge (edges[i].first, edges[i].second, weights[i], g1); But when I change the typedef to: typedef adjacency_matrix < undirectedS, no_property, property < edge_weight_t, int > > Graph; I get a compiler error at the add_edge line (without the weight is ok): sample.cpp:35: error: no matching function for call to add_edge(int&, int&, int&, main()::Graph&) Or maybe there is something special I have to do for adjacency_matrix? If this form of add_edge () doesn't exist, then my next option is to add edges first and then update the properties in a separate step? Thanks! Ray
I see. In other words, BidirectionalGraph, etc. are "abstract views" and there is no way one would call a "BidirectionalGraph constructor" -- there's no such thing? For example, in the documentation, one might say that a problem requires a "BidirectionalGraph". This is short-hand for both the authors and the readers that the problem requires some data structure, types, etc.?
"View" isn't quite the right word - more like "contract" - but otherwise, that's a fairly accurate description :) Andrew Sutton andrew.n.sutton@gmail.com
Hi again Andrew, Andrew Sutton wrote:
I see. In other words, BidirectionalGraph, etc. are "abstract views" and there is no way one would call a "BidirectionalGraph constructor" -- there's no such thing? For example, in the documentation, one might say that a problem requires a "BidirectionalGraph". This is short-hand for both the authors and the readers that the problem requires some data structure, types, etc.?
"View" isn't quite the right word - more like "contract" - but otherwise, that's a fairly accurate description :)
Ah, thank you for this -- the docs make a bit more sense now! I'll stop looking for a BidirectionalGraph constructor, then... :-) Ray
participants (3)
-
Andrew Sutton -
Raymond Wan -
Steven Watanabe