Re: [Boost-Users] Bandwidth Optimization using RCM (reverse Cuthill-Mckee)

From: Martin Okrslar (okrslar_at_[hidden])
Date: 2003-04-03 02:28:50

Bulent Nedim Alemdar wrote:

>Hi
>
>I am a very fresh user of Boost library. While I was searching the internet
>for a bandwidth optimization algorithm, I found Boost Graph Library.
>
>The library supports an RCM algorithm (cuthill_mckee_ordering) and I have
>checked the example given at this address:
>http://www.boost.org/libs/graph/example/cuthill_mckee_ordering.cpp
>
>It seems like the used vertex numbers given in this example is sequential
>and starts form 0:   vertex list:  0, 1, 2, 3, 4, 5, 6, 7,8, 9
>and a edge list is constructed from these vertex numbers.
>
>Do I have to define such a sequential order and always start from 0? 
>
I'm not a BGL pro either, but I think that the sequential order is 
mandatory. If you just need other labels than those given by the 
sequential order, you can define an internal map, like here:

 typedef boost::adjacency_list<
    boost::vecS, //edges
    boost::vecS, //nodes
    boost::undirectedS,

    //vertex properties
    boost::property<boost::vertex_name_t, std::int> //your custom label

    // no edge properties
    > Graph;

You can access the map as follows:

    Graph g(10);
   
    typedef boost::property_map<Graph, boost::vertex_name_t>::type 
Graph_namemap_t;
    Graph_namemap_t namemap = get(boost::vertex_name,g);

This gives you a map of BGLnodes to your label; I don't know if this is 
enough for you, because adding edges still requires to use the BGL 
nodes. Note: Adding an internal property to your graph changes the type 
of BGLnodes from int to an other type.

Hope this is at least a bit helpful.
 Martin

>What if
>I define vertex numbers such as : 1, 6, 9, 10, 11, 13, 21, 25, 26, 30,
>and define a valid edge like: ( 1,10), (1,13), (6,21), (6,30), (6,11),
>(6,9), (10,13), (10,26), (10,9), (13,21), (21,25), (9,11), (13,35)
>
>The above vertex list is a relabed list of the one given in the example code
>and I defined the same edge (connectivity) list.
>
>In fact, I tried it but the returned ordered list is not valid. Unless I use
>the vertex numbers starting from 0 and goes up to 9 like given on the
>example,  the returned ordered is wrong.
>
>I really appreciate your comments and helps on this
>
>thanks
>bulent
>
>
>
>
>
>Info: <http://www.boost.org>
>Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
>Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
> 
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
>
>
>  
>

-- 
-----------------------------------------------------------------------------
Martin Okrslar
MPI for Molecular Genetics          phone: ++ 49 + 30 / 8413-1166
Computational Molecular Biology     Fax:   ++ 49 + 30 / 8413-1152
Ihnestrasse 73                      email: okrslar_at_[hidden]
D-14195 Berlin                      URL:   http://cmb.molgen.mpg.de
-----------------------------------------------------------------------------