Boost logo

Boost Users :

Subject: [Boost-users] Using BGL with mutexes
From: Kelvin Chung (kelvSYC_at_[hidden])
Date: 2012-01-03 00:47:05


I wish to use multiple threads to build a graph, and to topologically
sort it. It would appear that the easiest way is to construct a graph
adapter like so:

template <class T>
class Graph {
        boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, T>
internalGraph;
        boost::shared_mutex mutex; // read-write lock enabler
        
        // Add other suitable adapter methods here
};

I'm wondering whether this is the better idea over using the PBGL,
since it seems that the PBGL is more complicated.

My specific scenario is that T is a functor type whose operation is
expensive, and may depend on calling a similar functor (determining the
dependent functors needed is cheap); thus, I'm trying to obtain all of
the functors and then ordering them so that all dependent functors are
always evaluated before the functor itself is evaluated. Thus, each
thread would do something like this:

Graph<T>& dependencyGraph = ...; // shared graph
std::deque<T> tasks; // initially populated list
while (!tasks.empty()) {
        T task = tasks.front();
        tasks.pop_front();

        std::list<T> dependents = task.getDependents();
        for (std::list<T>::const_iterator it = dependents.begin(); it !=
dependents.end(); ++it) {
                dependencyGraph.addEdge(task, *it); // Creates a new vertex if either
vertex does not exist
                tasks.push_back(*it);
        }
}

No vertices or edges are ever removed from the graph, unless the whole
graph is being destroyed. Would bundling a mutex and a graph be a good
idea for this purpose?


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net