New subject: Relaxed heaps

9 Jul 2008

      Hi guys and girls,

I've got an existing Graph structure, consisting of node and edge
classes.  The graph structure itself is implicit in the sense that
every node contains a list of out edges, and edges know where they
start from and go to.

I'm using Qt's container classes for simplicity mostly, eg. a node has
a QList of successors (QList<Edge*>), and all the nodes and edges get
stored in a Network class using QHash<Node*> etc...

I've been trying to extend this to work with the BGL, following the
LEDA and SGB examples.

As far as I know I can simply use the BGL functions on an instance of
my own Network, ie. no need to recreate the graph.  Is this correct?
It would save a lot of cpu time since the network contains several
thousand nodes and can be very dense.  Thus I haven't implemented any
add_node or add_edge functions, because I really only want to analyse
the graph and not change anything.

Some details of what I've got sofar:

-vertex and edge descriptors are simply pointers corresponding to my own classes
-vertex and edge iterators are simply typedefs of
qhash::const_iterator or qlist::const_iterator

-some source code at the bottom.

So far so good.

Though I've been stuck for 2 days trying to figure out how to get
property maps to play nicely with my classes.  I thought I'd be able
to apply the bundle concept from the adjacency list to my own graph,
but I'm not sure what exactly needs to be implemented to work.

The idea is to create property maps directly from the members of my
classes.  Is this possible?  What would I need to implement for
something like

weight_map(get(&Node::cost, Network))

to work?

*** How about for member functions? ie. If cost were a function
instead of a variable? ***

I couldn't really figure out how the bundles are actually accessed.
Though simply copying the get and put functions from the adjacency
list class seems not to work...

I think the crux of the matter really lies in figuring out how to
access the pointers corresponding to nodes or edges with this T
Bundle::* p that gets passed in.

And what do I need to do when creating an exterior property map for
storing temp data, for instance the distance map used by dijkstra?
This is actually where compilation fails at the moment.

Some source:

//Getters and putters for bundles

    template <typename T, typename Bundle>
    inline typename property_map< Network, T Bundle::*>::type
    get(T Bundle::* p, Network& g)
    {
        typedef typename property_map< Network, T Bundle::*>::type result_type;
        return result_type(&g, p);
    }

    template <typename T, typename Bundle, typename Key>
    inline T
    get(T Bundle::* p, Network const & g, const Key& key)
    {
        return get(get(p, g), key);
    }

    template <typename T, typename Bundle, typename Key>
    inline void
    put(T Bundle::* p, Network& g, const Key& key, const T& value)
    {
        put(get(p, g), key, value);
    }

The basic source, target etc. implementations:

    inline graph_traits< Network >::vertex_descriptor
    source(graph_traits< Network >::edge_descriptor e,
            const Network& g)
    {
        return e->getStart();
    }

    inline graph_traits< Network >::vertex_descriptor
    target(graph_traits< Network >::edge_descriptor e,
            const Network& g)
    {
        return e->getEnd();
    }

    inline std::pair<graph_traits< Network >::out_edge_iterator,
graph_traits< Network >::out_edge_iterator>
    out_edges(graph_traits< Network >::vertex_descriptor u,
            const Network& g)
            {
        typedef graph_traits< Network >::out_edge_iterator Iter;
        return std::make_pair( u->getSucc().constBegin() ,
u->getSucc().constEnd() );
            }

    inline std::pair<graph_traits< Network >::vertex_iterator,
graph_traits< Network >::vertex_iterator>
    vertices(const Network& g)
    {
        typedef graph_traits< Network >::vertex_iterator Iter;
        return std::make_pair( g.getNodes().constBegin(),
g.getNodes().constEnd() );
    }

// property map stuff

    template <>
    struct property_map<Network, vertex_index_t>
    {
        typedef identity_property_map type;
        typedef type const_type;
    };

    inline identity_property_map
    get(vertex_index_t, const Network& g)
    {
        return identity_property_map();
    }

    inline identity_property_map
    get(edge_index_t, const Network& g)
    {
        return identity_property_map();
    }

I really think everything else is working though I just can't get
these silly property maps to play nicely.

If someone could point me in the right direction it would be swell.  I
think once I get everything to work it would make a great example too.
 Though personally I thought something like this would be quite
standard, though I couldn't find anything in the mailing list
archives.

Thanks for reading!

And have a great day,
Christian

[BGL] Extending own Graph type to work with BGL

Christiaan Putter

David Abrahams

Christiaan Putter

Dmitry Bufistov

Line Blander Reinhardt

moritz Hilger

Line Blander Reinhardt

tags

participants (5)