Herve Bronnimann ha scritto:

Cosimo: if you've got one thread that reads and one that modifies your adjacency list, you must protect your graph with a (per vertex) Mutex. If you insist that you are not accessing the same edges at the same time, you still must. If you insist you are not accessing the adj lists at the same time, then maybe (but I doubt you can make that guarantee and the fact you crash means that you probably aren't).

If you go all listS (both tmpl args) you still must use a mutex unless you somehow hack BGL to use lockfree lists. I doubt anyone has ever done that.

You seem to think the crash is because of invalidation of iterators. It isn't. It's because of the lack of synchronization between your threads.

Hi Herve, Thanks for your contribute, but I'm not sure I understand what you've said: each vertex must have a mutex? So, I'm trying to implementing a sync_adjacency_list module, a graph adaptor similar to filtered_graph and reverse_graph; I've reimplemented every function required by the concepts modeled by the adjacency_list; each function has synchronized with the others by the same mutex, so every function that works on a sync_adjacency_list is atomic. I've implemented every graph traversal concept without problems, like this: template <typename G> typename sync_adjacency_list<G>::edges_size_type num_edges(const sync_adjacency_list<G>& g) { interprocess::scoped_lock<interprocess::interprocess_mutex> lock( sync_adjacency_list_mutex ); return num_edges(g.m_g); } Now I'm trying to implement the EdgeMutableGraph concept, in order to obtain the add_edge() support, but I've a problem. template <typename G> std::pair<typename sync_adjacency_list<G>::edge_descriptor, bool> add_edge(const typename sync_adjacency_list<G>::vertex_descriptor u, const typename sync_adjacency_list<G>::vertex_descriptor v, const sync_adjacency_list<G>& g) { interprocess::scoped_lock<interprocess::interprocess_mutex> lock( sync_adjacency_list_mutex ); return add_edge(u, v, g.m_g); } When I try to use it with G = adjacency_list< listS, vecS, directedS, vertexs_properties, edges_properties >, I'm obtaining the follow compile error message: "error C2665: 'boost::add_edge' : none of the 2 overloads could convert all the argument types" It seems that the compiler can't find the right implementation of add_edge(). It's strange, because I'm sure that the add_edge() exists for adjacency_list<...>. The add_edge() version I've implementated is only a wrapper of it. Where I'm wrong? Is it a MSVC 2005 function resolution bug? Thanks in advance, Cosimo Calabrese.

Cosimo, you might also consider using a snapshot of the graph (i.e copy) in each explorer thread. This might well outperform a mutexed solution when the number of concurrent accesses to edges is high. The only thing to be synchronized then is generating a copy of the graph. Best regards, Christoph On Fri, Sep 18, 2009 at 2:47 PM, Cosimo Calabrese <cosimo.calabrese@tellus.it> wrote:

...

Now I'm trying to implement the EdgeMutableGraph concept, in order to obtain the add_edge() support, but I've a problem.

template <typename G> std::pair<typename sync_adjacency_list<G>::edge_descriptor, bool> add_edge(const typename sync_adjacency_list<G>::vertex_descriptor u,         const typename sync_adjacency_list<G>::vertex_descriptor v,         const sync_adjacency_list<G>& g) {  interprocess::scoped_lock<interprocess::interprocess_mutex>  lock( sync_adjacency_list_mutex );  return add_edge(u, v, g.m_g); }

When I try to use it with G = adjacency_list< listS, vecS, directedS, vertexs_properties, edges_properties >, I'm obtaining the follow compile error message:

"error C2665: 'boost::add_edge' : none of the 2 overloads could convert all the argument types"

It seems that the compiler can't find the right implementation of add_edge(). It's strange, because I'm sure that the add_edge() exists for adjacency_list<...>. The add_edge() version I've implementated is only a wrapper of it.

Where I'm wrong? Is it a MSVC 2005 function resolution bug?

I've found the add_edge() problem: I've defined 'const' the internal graph reference of sync_adjacency_list... without const, it works. This is the adaptor (the 'const' is now commented):

template <typename Graph> class sync_adjacency_list {  typedef graph_traits<Graph> Traits;  typedef sync_adjacency_list<Graph> self; public:  typedef Graph graph_type;  sync_adjacency_list( /*const*/ Graph& g) : m_g(g) { }

 // .....

 /*const*/ Graph& m_g; }

Now, I'll test it...

Cosimo Calabrese.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Cosimo, Here are some ideas: Do you need all of the properties in the explorer threads? maybe you can construct a somewhat cheap copy of the graph of just vertices, edges and weights? When each explorer thread runs an instance of Dijkstra you might consider a parallel version of Dijkstra [1,2] working on disjoint graph regions? That might allow you to cut the graph into pieces and assigning a 'local' version of the graph to each explorer thread and joining them later on? [1] http://www.mcs.anl.gov/~itf/dbpp/text/node35.html [2] J. McHugh, Algorithmic Graph Theory Unfortunately I'm not used to Boost.BGL so I don't know if any of the suggested methods will work. Best regards, Christoph On Sun, Sep 20, 2009 at 4:50 PM, Cosimo Calabrese <cosimo.calabrese@tellus.it> wrote:

Christoph,

unfortunately my graph has about 5 million of vertices and 10 million of edges large, with many properties attached to them. A single graph takes about 1 Gb of RAM. The "copy solution" is the one I've used till now.

But now: - the copy time is heavy, so with a shared graph I would resolve this problem; - every explorer thread has need of a different view of the graph, so with a single shared graph and with the filtered_graph adaptor, I would resolve this problem too; - the thread number specific of my application is increasing, so the copy of the graph is too much onerous.

I think that with this task list, I'm practically obliged to having an only one shared graph. The graph is too much large. What do you think about?

Thanks in advance, Cosimo Calabrese.

Christoph Heindl ha scritto:

...

Cosimo,

you might also consider using a snapshot of the graph (i.e copy) in each explorer thread. This might well outperform a mutexed solution when the number of concurrent accesses to edges is high. The only thing to be synchronized then is generating a copy of the graph.

Best regards, Christoph

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Sep 21, 2009, at 10:59 AM, Cosimo Calabrese wrote:

...

Here are some ideas: Do you need all of the properties in the explorer threads? maybe you can construct a somewhat cheap copy of the graph of just vertices, edges and weights?

Unfortunately no, my graph has 5 million of vertices and 10 million of edges, and the properties RAM cost is very lower confronted to the graph structure. The graph structure takes approximately the same RAM quantity of the graph + properties. Moreover I've tried to make a graph copy, but it takes about 30 seconds on my machine (Pentium D 2.8GHz, 3Gb RAM, WinXP); it's too much confronted to the Dijkstra's time (about 6-7 seconds).

...

When each explorer thread runs an instance of Dijkstra you might consider a parallel version of Dijkstra [1,2] working on disjoint graph regions? That might allow you to cut the graph into pieces and assigning a 'local' version of the graph to each explorer thread and joining them later on?

These arguments are relatively new to me... do you think that's the way?

I've take a look to PBGL and MTGL:

https://software.sandia.gov/trac/mtgl/ http://www.osl.iu.edu/research/pbgl/

Maybe I can use them to resolve my problem?

Having written significant portions of one and used/hacked on the other I can say with some certainty that neither one of them will solve your problems out-of-the-box (at least not in the way I propose). Firstly, the problem seems somewhat ill defined so I've got a few questions to nail down the particulars: 1. When does the shortest paths solution have to be correct (i.e. match the graph exactly)? 2. Are there any constraints as to when your 'integrator' thread can call add_edge() (this relates to 1. pretty directly) Now the solution I propose, since you have a monotonically increasing edge set you can actually compute an incremental solution to the SSSP problem rather than completely re-running Dijkstra. Basically you can patch up the SSSP solution when you do the edge addition in O(N) time (expected time should be much lower but depends on parameters of your graph that I don't have so I won't try to explain in detail). Either way this is either somewhat better, or much better than O(N log N) to re-run Dijkstra. All you do is push the new weight onto the Dijkstra queue and run Dijkstra as normal. The key question is does your SSSP solution have to be exact? If not you can simply spin off the 'patching up the SSSP' work to the 'Explorer' thread and get a solution that's reasonably likely to be accurate, otherwise it should be faster than completely re-running Dijkstra to patch up the solution. If you really do need concurrent access to the adjacency list then I'd just wrap a readers-writers lock around each vertex's adjacencies. I'm actually working on incremental algorithms in parallel and will likely end up adding some sequential counterparts as well. Dijkstra is a pretty simple one so if you get a hold of me with the particulars of your problem and it fits with the stuff I was going to do anyway I may be able to write what you need fairly quickly. On the 'partitioning/distributing the graph' note, if you want to go that route there's a lot of support for it in PBGL. You'd probably want to rip out all the MPI stuff and put in a shared memory process group. You could run MPI over SM, but if the preliminary data I've run on the matter is any indication performance will be abysmal and memory consumption will go way up. Also, you're still going to have to deal with the concurrent access to the adjacency-list issue. I've adopted the general rule that partitioning data structures is only appropriate when 1. you don't have a shared address space, or 2. you have hideous contention and no other way to alleviate it. That's just my $0.02 though, and subject to change at any time. Cheers, Nick

Thanks, Cosimo Calabrese.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Tue, 22 Sep 2009, Cosimo Calabrese wrote:

...

1. When does the shortest paths solution have to be correct (i.e. match the graph exactly)?

Well, I always need the exact solution.

...

2. Are there any constraints as to when your 'integrator' thread can call add_edge() (this relates to 1. pretty directly)

No, there aren't. The add_edge() can be called at any moment.

It looks like (from your description that I snipped out) that you are really creating a new graph for every thread that is a copy of the original graph plus some new, thread-specific edges. I would not recommend having a single graph for all of this because of the issues you are having. What about the following: 1. Create a union_graph adapter that takes two graphs with the same number of vertices and merges their edge sets (concatenating the out_edges and in_edges for each vertex implicitly). Properties would also need to be handled (or indexes for external properties). 2. For every thread, create a new graph with just that thread's new edges and run Dijkstra's algorithm on the union_graph of that piece and the original graph. 3. Throw away the temporary, thread-specific graph when the thread is done. That should remove all of your locking (except in the memory allocator), and the filtered_graph, and greatly simplify (and probably speed up) the code. Do you think this will work? -- Jeremiah Willcock

On Wed, 23 Sep 2009, Cosimo Calabrese wrote:

...

It looks like (from your description that I snipped out) that you are really creating a new graph for every thread that is a copy of the original graph plus some new, thread-specific edges. I would not recommend having a single graph for all of this because of the issues you are having. What about the following:

Well, I've really a single, unique, huge istance of an adjacency_list in my application. I've called the initial form of that graph: 'original graph'. There aren't other graphs in memory. Every thread creates a filtered_graph object, that takes a reference of the original graph, but it's not a memory copy of it, it's only an adaptor. The thread adds the new edges and vertices using a reference of the original graph, and explores the filtered graph. The original graph has about 5 million of vertices and 10 million of edges. It takes about 1 Gb of RAM, I can't replicate it.

I know you were not doing that literally, but it seemed like the combined effect of your graph addition, filtering, and deletion meant that each run of Dijkstra's algorithm was in effect on a graph built this way.

...

1. Create a union_graph adapter that takes two graphs with the same number of vertices and merges their edge sets (concatenating the out_edges and in_edges for each vertex implicitly). Properties would also need to be handled (or indexes for external properties).

2. For every thread, create a new graph with just that thread's new edges and run Dijkstra's algorithm on the union_graph of that piece and the original graph.

3. Throw away the temporary, thread-specific graph when the thread is done.

It seems a very, very good idea. I like it very much. If it works, I always access to the 'original' graph in read-only modality, that is the only shared object; I don't need to add any vertex or edge to any existing graph, but each thread only needs to create another, completly new graph, which isn't shared with other threads. So the thread explore the union adaptor in read-only modality. Exciting.

Now I must take a look on some 'graph arithmetic'... This adaptor needs only to model the traversal graph concepts. The two graph type in input to the union adaptor must be the same. So all the adaptor types required by the concepts are the same of the input graphs. Now I need a moment to think about the concept funcions (out_edges(), out_degree(), ... ). I'll tell you about the state of the adaptor very soon.

Those should be fairly simple, except that I do not believe Boost.Iterator has a concatenation iterator like the old View Template Library had. If you write a generic concatenate-two-sequences iterator, you might want to consider contributing it to Boost.Iterator. Otherwise, you should just be able to concatenate edge sets (in edge sets, out edge sets) and add degrees together. Various properties and vertex/edge index computation might be tougher.

...

That should remove all of your locking (except in the memory allocator),

Yes.

...

and the filtered_graph,

Mmmmh, no, not yet. There is one thing of my project I've not mentioned, it's difficult to explain all of it... The graph elements have many properties. Each thread needs to explore not all the graph, but only a particular view of it, that must change dependently by the specific request. So, I need the filter_adaptor. But if you think that I haven't understood something about this point, please... tell me.

OK. So you mean that you're filtering on more than just the thread ID? In that case, you might still need a filter.

...

and greatly simplify (and probably speed up) the code. Do you think this will work?

Yes, I'm hopeful. I'll tell you soon. Thanks for the great idea.

But beyond the Jeremiah's idea, no one can explain what happens in my application? I'm referring to the memory corruption. Surely it depends on the contemporary reading and writing by different thread at the same moment, but I would to know why it happens, even if I've locked all the functions.

I do not know -- adjacency_list I believe has out edge (and possibly in edge) sets for each vertex, plus I think there's a total edge list. That second one might be getting corrupted even if you change unrelated vertices. Also, anytime the documentation says that some operation corrupts iterators into the graph, that means it might move the location of some internal data structure and thus cause conflicts with multiple threads. I have not looked specifically at the behavior you are seeing, though. -- Jeremiah Willcock

Well, I've implemented the union_iterator, that takes 2 iterator ranges and create and unique view of them. But now I've some doubt about the union_graph adapter. Please, try to think the following questions in a Dijkstra's context:

[1] Why the 2 graphs in the union_graph must have the same vertex number? Is it a vertex index issue? I think it is because when I call a function that takes a vertex_descriptor argument, I must query both the graphs on the same vertex_descriptor. Isn't it? In my initial problem I added some new vertexes on the original graph. So with the union_graph, the new vertexes in the 'little graph' aren't in the 'original graph'. I can't know a priori how much vertexes I will add in an elaboration. I must add some 'free' vertex on the original graph, to use in the elaboration?

Basically, yes on your first question. Also, edges in the two graphs need to refer to the same vertices (or be converted). For your last question, that might be a good way to do it; remember that the same single vertex can work for all of your unioned graphs. If you are using numbers as vertex_descriptors (as in CSR and some versions of adjacency_list), you can have more vertices in one graph than the other as long as your functions always return the max vertex count; in that case, vertex numbers up to the min of the two graphs will be common to the two graphs. You would be able to avoid an extra vertex in the original graph that way.

[2] When I add an edge on a graph, the graph assigns to the edge an edge_descriptor. When I add some edges to the two graphs, they can have the same edge_descriptor for different edges. So, when I call a function that takes an edge_descriptor argument, e.g. source() or target(), how can distinguish the two edge with the same edge_descriptor on two different graphs?

See my reply to your later email about this.

[3] This relates to [2] directly: when I call out_edges() on a vertex, the union_graph calls out_edges() on the same vertex_descriptor in both the graphs; I obtain two ranges of edge_iterators, that I join with union_iterator adaptor, but in the two range I can find the same edge_descriptor.

This relates to the "overlapping edge descriptor" issue as well; see the other email. -- Jeremiah Willcock

On Thu, 1 Oct 2009, Cosimo Calabrese wrote:

I've just looked to the edge_descriptor definition. An edge_descriptor is equal to another edge_descriptor if and only if they have the same source and target (from edge_base definition) and the same pointer to a property (from the edge_desc_impl definition).

If the 'original graph' doesn't never involve the free vertexes, and the 'little graph' necessary involves the free vertexes, so an edge_descriptor of the original graph will not be never the same of an edge_descriptor of the little graph.

If I'm sure to distinguish the edges of both the graphs, I think that I can implement the union_graph shortly.

What do you think about it?

I think that should work. You might really want a tagged union type, though (boost::variant with some guarantee that the edge descriptor types of the two graphs are different is an example). You would need to do wrapping of each graph's descriptors in the union iterator then, though. That would remove the restrictions on edges that you gave above. I don't know what you need as far as properties; those might need to be combined as well. -- Jeremiah Willcock

On Mon, 5 Oct 2009, Cosimo Calabrese wrote:

Jeremiah Willcock ha scritto:

...

I think that should work. You might really want a tagged union type, though (boost::variant with some guarantee that the edge descriptor types of the two graphs are different is an example). You would need to do wrapping of each graph's descriptors in the union iterator then, though. That would remove the restrictions on edges that you gave above. I don't know what you need as far as properties; those might need to be combined as well.

Hi Jeremiah,

I've readed some days ago your suggestions about using boost::variant, but I ignored what boost::variant is. So I've spent some time to study it, and now I think I understand what you have suggested to me. E.g. the edge_descriptor of union_graph adaptor is a boost::variant, that contains the edge_descriptor of both the graph. When I call the source() function I pass an edge_descriptor to it, but the source() doesn't know if the edge_descriptor belongs to one or another graph. So the source() function use a source_visitor, that distinguish between the edge_descriptors, and call the source() on the right graph.

Can you take a look to the attached code? Is this that you meant? I've writed only the case of the source() function, but at every concept function corresponds a visitor.

I think your code is going in the right direction and is basically what I had in mind. One issue with it is the case where the vertex or edge descriptor types of the two graphs are the same. You need separate types for "thing from graph 1" and "thing from graph 2" (you can use the same wrapper for vertices and edges) to put into the variant. Also, if you don't want a variant visitor, you can use get() to dispatch on the variant type. -- Jeremiah Willcock

On Mon, 5 Oct 2009, Cosimo Calabrese wrote:

Jeremiah Willcock ha scritto:

...

One issue with it is the case where the vertex or edge descriptor types of the two graphs are the same. You need separate types for "thing from graph 1" and "thing from graph 2"

Yes, it's true.

I thought to use a thing that I haven't never used, that is the 6th template parameter of adjacency_list: GraphProperties.

adjacency_list<EdgeList, VertexList, Directed, VertexProperties, EdgeProperties, *GraphProperties*>

I could define two tags:

struct original_graph_tag { }; struct little_graph_tag { };

and pass these types in the 'original' and 'little' graph, respectively. This could be enough to differentiate the two type of graph, and therefore the descriptors.

That only works if both graphs are adjacency_lists and you have control over the graph types. I would personally just make: template <typename T> struct from_first_graph {T data;}; template <typename T> struct from_second_graph {T data;}; and then have my variants be: boost::variant<from_first_graph<graph_traits<First>::vertex_descriptor>, from_second_graph<graph_traits<Second>::vertex_descriptor>

and the same for edge descriptors. This will disambiguate the types for arbitrary graphs. -- Jeremiah Willcock

Cosimo Calabrese ha scritto:

Jeremiah Willcock wrote:

...

That only works if both graphs are adjacency_lists and you have control over the graph types. I would personally just make:

template <typename T> struct from_first_graph {T data;}; template <typename T> struct from_second_graph {T data;};

and then have my variants be:

boost::variant<from_first_graph<graph_traits<First>::vertex_descriptor>, from_second_graph<graph_traits<Second>::vertex_descriptor>

...

and the same for edge descriptors. This will disambiguate the types for arbitrary graphs.

It seems a very good idea to me. I'm trying it. I'll tell you about it ASAP.

I'm nearly to the end of the work, but I've encountered a problem. I've implemented all the traversal concepts, but I'm in difficulty with the Property concepts, in particular on the get( property, key ) function. I don't understand where I'm wrong. I was inspired by the filtered_graph and reverse_graph adaptor, but without results. Sure, I'm relatively new to Boost, and I haven't understand very well how the property lib works, applied on the BGL. I attach 3 files: - the union_different_iterator, that provides a union view of 2 containers; - the union_graph, that provides a union view of 2 graphs (that uses union_different_iterator); - a main module, that tests the union_graph. Please, can anyone help me? Thanks, Cosimo Calabrese. #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_utility.hpp> #include "union_graph.hpp" using namespace boost; using namespace std; namespace boost { // properties installation enum vertex_originality_t { vertex_originality = 101 }; enum edge_ID_t { edge_ID = 102 }; enum edge_originality_t { edge_originality = 103 }; BOOST_INSTALL_PROPERTY(vertex, originality); BOOST_INSTALL_PROPERTY(edge, ID); BOOST_INSTALL_PROPERTY(edge, originality); } typedef property< vertex_name_t, string, property < vertex_originality_t, bool > > vertexs_properties; typedef property < edge_ID_t, long, property < edge_weight_t, long, property < edge_originality_t, bool > > > edges_properties; typedef adjacency_list< listS, vecS, directedS, vertexs_properties, edges_properties > Graph; typedef property_map< Graph, edge_weight_t >::type edge_weight_map_t; int main() { // Setup Test const long NUM_VERTICES = 10; graph_traits<Graph>::edge_descriptor e; bool inserted; // base hraph Graph baseGraph( NUM_VERTICES ); edge_weight_map_t edge_weight_map_base = get( edge_weight, baseGraph ); for ( long i = 0; i < NUM_VERTICES ; ++i ) { // 0->1, 1->2, 2->3, ... n->n+1 ..., 9->0 tie(e, inserted) = add_edge( i % NUM_VERTICES, (i + 1) % NUM_VERTICES, baseGraph ); if ( inserted ) edge_weight_map_base[ e ] = 1; } cout << "Base graph:" << endl; print_graph( baseGraph ); cout << endl; // little graph Graph littleGraph( NUM_VERTICES ); edge_weight_map_t edge_weight_map_little = get( edge_weight, littleGraph ); tie(e, inserted) = add_edge( 0, 6, littleGraph ); if ( inserted ) edge_weight_map_little[ e ] = 1; cout << "Little graph:" << endl; print_graph( littleGraph ); cout << endl; // union graph //cout << "Union graph:" << endl; //print_graph( make_union_graph( baseGraph, littleGraph ) ); //cout << endl; // union graph, test vertex (0) typedef union_graph<Graph, Graph> UG; UG ug = make_union_graph( baseGraph, littleGraph ); graph_traits<UG>::vertex_descriptor u = WR1<graph_traits<Graph>::vertex_descriptor>( 0 ); // Test 1: out_edges e out_degree { graph_traits<UG>::out_edge_iterator oei, oei_end; for ( tie( oei, oei_end ) = out_edges( u, ug ); oei != oei_end; ++oei ) { graph_traits<UG>::vertex_descriptor t = target( *oei, ug ); cout << "Outer target: "; if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &t ) ) cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( t )._data << endl; else cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( t )._data << endl; } cout << "Out degree: " << out_degree( u, ug ) << endl << endl; } /* // Bidirectionality required for this test // Test 2: in_edges, in_degree e degree { graph_traits<UG>::in_edge_iterator iei, iei_end; for ( tie( iei, iei_end ) = in_edges( u, ug ); iei != iei_end; ++iei ) { graph_traits<UG>::vertex_descriptor s = source( *iei, ug ); if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &s ) ) cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( s )._data << endl; else cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( s )._data << endl; } cout << "In degree: " << in_degree( u, ug ) << endl; cout << "Degree: " << degree( u, ug ) << endl; } */ // Test 3: adjacent_vertices { graph_traits<UG>::adjacency_iterator ai, ai_end; for ( tie( ai, ai_end ) = adjacent_vertices( u, ug ); ai != ai_end; ++ai ) { cout << "Adjacency: "; if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &*ai ) ) cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( *ai )._data << endl; else cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( *ai )._data << endl; } cout << endl; } // Test 4: num_vertices, vertices { cout << "Num vertices: " << num_vertices( ug ) << endl; graph_traits<UG>::vertex_iterator vi, vi_end; for ( tie( vi, vi_end ) = vertices( ug ); vi != vi_end; ++vi ) { cout << "Graph Vertex: "; boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &*vi ); if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &*vi ) ) cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( *vi )._data << endl; else cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( *vi )._data << endl; } cout << endl; } // Test 5: num_edges, edges, source, target { cout << "Num edges: " << num_edges( ug ) << endl; graph_traits<UG>::edge_iterator ei, ei_end; for ( tie( ei, ei_end ) = edges( ug ); ei != ei_end; ++ei ) { cout << "Graph edge: "; graph_traits<UG>::vertex_descriptor s = source( *ei, ug ); graph_traits<UG>::vertex_descriptor t = target( *ei, ug ); if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &s ) ) cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( s )._data; else cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( s )._data; cout << "->"; if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &t ) ) cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( t )._data; else cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( t )._data; cout << endl; } cout << endl; } // Test 6: edge { graph_traits<UG>::vertex_descriptor u = WR2<graph_traits<Graph>::vertex_descriptor>( 0 ); graph_traits<UG>::vertex_descriptor v = WR1<graph_traits<Graph>::vertex_descriptor>( 6 ); graph_traits<UG>::edge_descriptor e; bool exists; tie( e, exists ) = edge( u, v, ug ); cout << ( exists ? "This edge exists" : "This edge doesn't exists" ) << endl << endl; } // Test 7: properties { graph_traits<UG>::vertex_descriptor u = WR1<graph_traits<Graph>::vertex_descriptor>( 0 ); typedef property_map< Graph, vertex_index_t >::type vertex_index_map_t; vertex_index_map_t indexmap = get( vertex_index, ug ); //get( indexmap, ug, u ); } } #ifndef _UNION_DIFFERENT_ITERATOR #define _UNION_DIFFERENT_ITERATOR #include <boost/variant.hpp> #include <iterator> #include <utility> using namespace std; template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B> class union_different_iterator : public std::iterator< forward_iterator_tag, boost::variant< WR_A<typename iterator_traits<FI1>::value_type>, WR_B<typename iterator_traits<FI2>::value_type> > > { public: typedef union_different_iterator<FI1, FI2, WR_A, WR_B> self; typedef typename iterator_traits<FI1>::value_type value_type1; typedef typename iterator_traits<FI2>::value_type value_type2; union_different_iterator() {} union_different_iterator( FI1 begin_a, FI1 end_a, FI2 begin_b, FI2 end_b ) : _begin_a( begin_a ), _end_a( end_a ), _curr_a( begin_a ), _begin_b( begin_b ), _end_b( end_b ), _curr_b( begin_b ) {} union_different_iterator( const self& other ) : _begin_a( other._begin_a ), _end_a( other._end_a ), _curr_a( other._curr_a ), _begin_b( other._begin_b ), _end_b( other._end_b ), _curr_b( other._curr_b ) {} const self& operator=( const self& other ) { _begin_a = other._begin_a; _end_a = other._end_a; _curr_a = other._curr_a; _begin_b = other._begin_b; _end_b = other._end_b; _curr_b = other._curr_b; return(*this); } bool operator==( const self& other ) const { return ( _curr_a == other._curr_a ) && ( _curr_b == other._curr_b ); } bool operator!=( const self& other ) const { return !this->operator == ( other ); } /*const*/ value_type operator*() const { return _curr_a == _end_a ? value_type( WR_B<value_type2>( *_curr_b ) ) : value_type( WR_A<value_type1>( *_curr_a ) ) ; } /* value_type operator*() { return _curr_a == _end_a ? value_type( WR_B<value_type2>( *_curr_b ) ) : value_type( WR_A<value_type1>( *_curr_a ) ) ; } */ /* const pointer operator->() const { return _curr_a == _end_a ? _curr_b.operator->() : _curr_a.operator->(); } pointer operator->() { return _curr_a == _end_a ? _curr_b.operator->() : _curr_a.operator->(); } */ self& operator++() { if ( _curr_a == _end_a ) ++_curr_b; else ++_curr_a; return *this; } self operator++(int) { self tmp = *this; ++( *this ); return tmp; } self& operator--() { if (_curr_b == _begin_b ) --_curr_a; else --_curr_b; return *this; } self operator--(int) { self tmp = *this; --( *this ); return tmp; } template <typename T> bool isTypeOf() { if ( _curr_a == _end_a ) return boost::is_same<WR_B<T>, WR_B<value_type2> >::value; else return boost::is_same<WR_A<T>, WR_A<value_type1> >::value; } private: FI1 _begin_a; FI1 _end_a; FI1 _curr_a; FI2 _begin_b; FI2 _end_b; FI2 _curr_b; }; template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B> inline union_different_iterator<FI1, FI2, WR_A, WR_B> make_union_different_iterator(FI1 begin_a, FI1 end_a, FI2 begin_b, FI2 end_b) { return union_different_iterator<FI1, FI2, WR_A, WR_B>(begin_a, end_a, begin_b, end_b); } template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B> inline union_different_iterator<FI1, FI2, WR_A, WR_B> make_union_different_iterator( pair<FI1, FI1> range_a, pair<FI2, FI2> range_b ) { return union_different_iterator<FI1, FI2, WR_A, WR_B>(range_a.first, range_a.second, range_b.first, range_b.second); } template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B> inline pair< union_different_iterator<FI1, FI2, WR_A, WR_B>, union_different_iterator<FI1, FI2, WR_A, WR_B> > make_union_different_range( FI1 begin_a, FI1 end_a, FI2 begin_b, FI2 end_b ) { return make_pair( make_union_different_iterator<FI1, FI2, WR_A, WR_B>( begin_a, end_a, begin_b, end_b ), make_union_different_iterator<FI1, FI2, WR_A, WR_B>( end_a, end_a, end_b, end_b ) ); } template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B> inline pair< union_different_iterator<FI1, FI2, WR_A, WR_B>, union_different_iterator<FI1, FI2, WR_A, WR_B> > make_union_different_range( pair<FI1, FI1> range_a, pair<FI2, FI2> range_b ) { return make_pair( make_union_different_iterator<FI1, FI2, WR_A, WR_B>( range_a, range_b ), make_union_different_iterator<FI1, FI2, WR_A, WR_B>( range_a.second, range_a.second, range_b.second, range_b.second ) ); } #endif #ifndef BOOST_UNION_GRAPH_HPP #define BOOST_UNION_GRAPH_HPP #include <boost/graph/graph_traits.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/adjacency_iterator.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/graph/exception.hpp> #include <boost/variant.hpp> #include "union_different_iterator.hpp" //=========================================================================== // wrappers template <typename T> class WR1 { public: WR1() : _data( T() ) {} WR1( T data ) : _data( data ) {} const WR1<T> operator=( const WR1<T>& other ) { _data = other._data; return(*this); } bool operator==( const WR1<T>& other ) const { return _data == other._data; } T _data; }; template <typename T> class WR2 { public: WR2() : _data( T() ) {} WR2( T data ) : _data( data ) {} const WR2<T> operator=( const WR2<T>& other ) { _data = other._data; return(*this); } bool operator==( const WR2<T>& other ) const { return _data == other._data; } T _data; }; namespace boost { struct not_same_num_vertices : public bad_graph { not_same_num_vertices() : bad_graph("The two graphs of an union_graph must have the same number of vertices.") { } }; //=========================================================================== // union_graph struct union_graph_tag { }; template <typename Graph1, typename Graph2> class union_graph { typedef union_graph<Graph1, Graph2> self; public: typedef Graph1 graph_type1; typedef Graph2 graph_type2; // Constructor union_graph( const Graph1& g1, const Graph2& g2 ) : m_g1(g1), m_g2(g2) { // TODO: precondition: Traits::directed_category must be the same // TODO: precondition: Traits::Traits::traversal_category be the same // TODO: precondition: Traits::edge_parallel_category be the same if ( num_vertices( g1 ) != num_vertices( g2 ) ) throw not_same_num_vertices(); } // Graph requirements typedef boost::variant<WR1<typename graph_traits<Graph1>::vertex_descriptor>, WR2<typename graph_traits<Graph2>::vertex_descriptor> > vertex_descriptor; typedef typename graph_traits<Graph1>::directed_category directed_category; typedef typename graph_traits<Graph1>::traversal_category traversal_category; typedef typename graph_traits<Graph1>::edge_parallel_category edge_parallel_category; // IncidenceGraph requirements typedef boost::variant<WR1<typename graph_traits<Graph1>::edge_descriptor>, WR2<typename graph_traits<Graph2>::edge_descriptor> >edge_descriptor; typedef union_different_iterator< typename graph_traits<Graph1>::out_edge_iterator, typename graph_traits<Graph2>::out_edge_iterator, WR1, WR2 > out_edge_iterator; typedef typename graph_traits<Graph1>::degree_size_type degree_size_type; // AdjacencyGraph requirements typedef union_different_iterator< typename graph_traits<Graph1>::adjacency_iterator, typename graph_traits<Graph2>::adjacency_iterator, WR1, WR2 > adjacency_iterator; // BidirectionalGraph requirements typedef union_different_iterator< typename graph_traits<Graph1>::in_edge_iterator, typename graph_traits<Graph2>::in_edge_iterator, WR1, WR2 > in_edge_iterator; // VertexListGraph requirements typedef union_different_iterator< typename graph_traits<Graph1>::vertex_iterator, typename graph_traits<Graph2>::vertex_iterator, WR1, WR2 > vertex_iterator; typedef typename graph_traits<Graph1>::vertices_size_type vertices_size_type; // EdgeListGraph requirements typedef union_different_iterator< typename graph_traits<Graph1>::edge_iterator, typename graph_traits<Graph2>::edge_iterator, WR1, WR2 > edge_iterator; typedef typename graph_traits<Graph1>::edges_size_type edges_size_type; typedef typename ::boost::edge_property_type<Graph1>::type edge_property_type; typedef typename ::boost::vertex_property_type<Graph1>::type vertex_property_type; typedef union_graph_tag graph_tag; #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES // Bundled properties support template<typename Descriptor> typename graph::detail::bundled_result<Graph1, Descriptor>::type& operator[](Descriptor x) { return const_cast<Graph1&>(this->m_g1)[x]; } template<typename Descriptor> typename graph::detail::bundled_result<Graph1, Descriptor>::type const& operator[](Descriptor x) const { return this->m_g1[x]; } #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES static vertex_descriptor null_vertex() { return Graph1::null_vertex(); } // private: const Graph1& m_g1; const Graph2& m_g2; }; #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES template<typename Graph1, typename Graph2> struct vertex_bundle_type<union_graph<Graph1, Graph2> > : vertex_bundle_type<Graph1> { }; template<typename Graph1, typename Graph2> struct edge_bundle_type<union_graph<Graph1, Graph2> > : edge_bundle_type<Graph1> { }; #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES //=========================================================================== // Non-member functions for the Filtered Edge Graph // Helper functions template <typename Graph1, typename Graph2> inline union_graph<Graph1, Graph2> make_union_graph(Graph1& g1, Graph2& g2) { return union_graph<Graph1, Graph2>(g1, g2); } template <typename Graph1, typename Graph2> inline union_graph<const Graph1, const Graph2> make_union_graph(const Graph1& g1, const Graph2& g2 ) { return union_graph<const Graph1, const Graph2>(g1, g2); } namespace detail { template <typename Graph1, typename Graph2> std::pair<typename graph_traits<Graph1>::vertex_descriptor, typename graph_traits<Graph2>::vertex_descriptor> get_corresponding_vertices(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; VD1 u1; VD2 u2; if ( boost::get<WR1<VD1> >( &u ) ) { u1 = boost::get<WR1<VD1> >( u )._data; u2 = u1; } else { u2 = boost::get<WR2<VD2> >( u )._data; u1 = u2; } return make_pair( u1, u2 ); } } // IncidenceGraph requirements template <typename Graph1, typename Graph2> std::pair<typename union_graph<Graph1, Graph2>::out_edge_iterator, typename union_graph<Graph1, Graph2>::out_edge_iterator> out_edges(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; typedef graph_traits<Graph1>::out_edge_iterator OEI1; typedef graph_traits<Graph2>::out_edge_iterator OEI2; VD1 u1; VD2 u2; tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u ); return make_union_different_range<OEI1, OEI2, WR1, WR2>( out_edges(u1, g.m_g1), out_edges(u2, g.m_g2) ); } template <typename Graph1, typename Graph2> typename union_graph<Graph1, Graph2>::vertex_descriptor source(const typename union_graph<Graph1, Graph2>::edge_descriptor& e, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; typedef graph_traits<Graph1>::edge_descriptor ED1; typedef graph_traits<Graph2>::edge_descriptor ED2; if ( boost::get<WR1<ED1> >( &e ) ) { return graph_traits<UG>::vertex_descriptor( WR1<VD1>( source( boost::get<WR1<ED1> >( e )._data, g.m_g1 ) ) ); } else { return graph_traits<UG>::vertex_descriptor( WR2<VD2>( source( boost::get<WR2<ED2> >( e )._data, g.m_g2 ) ) ); } } template <typename Graph1, typename Graph2> typename union_graph<Graph1, Graph2>::vertex_descriptor target(const typename union_graph<Graph1, Graph2>::edge_descriptor& e, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; typedef graph_traits<Graph1>::edge_descriptor ED1; typedef graph_traits<Graph2>::edge_descriptor ED2; if ( boost::get<WR1<ED1> >( &e ) ) { return graph_traits<UG>::vertex_descriptor( WR1<VD1>( target( boost::get<WR1<ED1> >( e )._data, g.m_g1 ) ) ); } else { return graph_traits<UG>::vertex_descriptor( WR2<VD2>( target( boost::get<WR2<ED2> >( e )._data, g.m_g2 ) ) ); } } template <typename Graph1, typename Graph2> typename union_graph<Graph1, Graph2>::degree_size_type out_degree(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; VD1 u1; VD2 u2; tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u ); return out_degree(u1, g.m_g1) + out_degree(u2, g.m_g2); } // BidirectionalGraph requirements template <typename Graph1, typename Graph2> std::pair<typename union_graph<Graph1, Graph2>::in_edge_iterator, typename union_graph<Graph1, Graph2>::in_edge_iterator> in_edges(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; typedef graph_traits<Graph1>::in_edge_iterator IEI1; typedef graph_traits<Graph2>::in_edge_iterator IEI2; VD1 u1; VD2 u2; tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u ); return make_union_different_range<IEI1, IEI2, WR1, WR2>( in_edges<Graph1>(u1, g.m_g1), in_edges<Graph2>(u2, g.m_g2) ); } template <typename Graph1, typename Graph2> typename union_graph<Graph1, Graph2>::degree_size_type in_degree(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; VD1 u1; VD2 u2; tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u ); return in_degree(u1, g.m_g1) + in_degree(u2, g.m_g2); } template <typename Graph1, typename Graph2> typename union_graph<Graph1, Graph2>::degree_size_type degree(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u, const union_graph<Graph1, Graph2>& g) { return out_degree(u, g) + in_degree(u, g); } // AdjacencyGraph requirements template <typename Graph1, typename Graph2> std::pair<typename union_graph<Graph1, Graph2>::adjacency_iterator, typename union_graph<Graph1, Graph2>::adjacency_iterator> adjacent_vertices(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; typedef graph_traits<Graph1>::adjacency_iterator AI1; typedef graph_traits<Graph2>::adjacency_iterator AI2; VD1 u1; VD2 u2; tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u ); return make_union_different_range<AI1, AI2, WR1, WR2>( adjacent_vertices(u1, g.m_g1), adjacent_vertices(u2, g.m_g2) ); } // VertexListGraph requirements template <typename Graph1, typename Graph2> typename union_graph<Graph1, Graph2>::vertices_size_type num_vertices(const union_graph<Graph1, Graph2>& g) { return num_vertices(g.m_g1); } template <typename Graph1, typename Graph2> std::pair<typename union_graph<Graph1, Graph2>::vertex_iterator, typename union_graph<Graph1, Graph2>::vertex_iterator> vertices(const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_iterator VI1; typedef graph_traits<Graph2>::vertex_iterator VI2; VI2 vi2 = VI2(); VI2 vi2_end = vi2; return make_union_different_range<VI1, VI2, WR1, WR2>( vertices(g.m_g1), make_pair(vi2, vi2_end) ); } // EdgeListGraph requirements template <typename Graph1, typename Graph2> typename union_graph<Graph1, Graph2>::edges_size_type num_edges(const union_graph<Graph1, Graph2>& g) { return num_edges(g.m_g1) + num_edges(g.m_g2); } template <typename Graph1, typename Graph2> std::pair<typename union_graph<Graph1, Graph2>::edge_iterator, typename union_graph<Graph1, Graph2>::edge_iterator> edges(const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::edge_iterator EI1; typedef graph_traits<Graph2>::edge_iterator EI2; return make_union_different_range<EI1, EI2, WR1, WR2>( edges(g.m_g1), edges(g.m_g2) ); } // AdjacencyMatrix requirements template <typename Graph1, typename Graph2> std::pair<typename union_graph<Graph1, Graph2>::edge_descriptor, bool> edge(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u, const typename union_graph<Graph1, Graph2>::vertex_descriptor& v, const union_graph<Graph1, Graph2>& g) { typedef union_graph<Graph1, Graph2> UG; typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; typedef graph_traits<Graph1>::edge_descriptor ED1; typedef graph_traits<Graph2>::edge_descriptor ED2; VD1 u1, v1; VD2 u2, v2; tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u ); tie( v1, v2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( v ); // g1 check { ED1 e1; bool exists; tie( e1, exists ) = edge(u1, v1, g.m_g1); if ( exists ) return make_pair( graph_traits<UG>::edge_descriptor( WR1<ED1>( e1 ) ), exists ); } // g2 check { ED2 e2; bool exists; tie( e2, exists ) = edge(u2, v2, g.m_g2); return make_pair( graph_traits<UG>::edge_descriptor( WR2<ED2>( e2 ) ), exists ); } } //=========================================================================== // Property map namespace detail { struct union_graph_property_selector { template <class UnionGraph, class Property, class Tag> struct bind_ { typedef typename UnionGraph::graph_type Graph; typedef property_map<Graph, Tag> Map; typedef typename Map::type type; typedef typename Map::const_type const_type; }; }; } // namespace detail template <> struct vertex_property_selector<union_graph_tag> { typedef detail::union_graph_property_selector type; }; template <> struct edge_property_selector<union_graph_tag> { typedef detail::union_graph_property_selector type; }; template <typename Graph1, typename Graph2, typename Property> typename property_map<Graph1, Property>::type get(Property p, union_graph<Graph1, Graph2>& g) { return get(p, const_cast<Graph1&>(g.m_g1)); } template <typename Graph1, typename Graph2, typename Property> typename property_map<Graph1, Property>::const_type get(Property p, const union_graph<Graph1, Graph2>& g) { return get(p, (const Graph1&)g.m_g1); } /* template <typename Graph1, typename Graph2, typename Property, typename Key> typename property_map_value<Graph1, Property>::type get(Property p, const union_graph<Graph1, Graph2>& g, const Key& k) { return get(p, (const Graph1&)g.m_g1, k); } */ template <typename Graph1, typename Graph2, typename Property> typename property_map_value<Graph1, Property>::type get(Property p, const union_graph<Graph1, Graph2>& g, const typename union_graph<Graph1, Graph2>::vertex_descriptor& u) { typedef graph_traits<Graph1>::vertex_descriptor VD1; typedef graph_traits<Graph2>::vertex_descriptor VD2; VD1 u1; VD2 u2; //tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u ); return get(p, (const Graph1&)g.m_g1, u1); } template <typename Graph1, typename Graph2, typename Property, typename Key, typename Value> void put(Property p, const union_graph<Graph1, Graph2>& g, const Key& k, const Value& val) { put(p, const_cast<Graph1&>(g.m_g1), k, val); } } // namespace boost #endif // BOOST_UNION_GRAPH_HPP

Now, I'll test it...

Now I am testing a sync_graph adaptor that implement all the read-only graph traversing concept and the EdgeMutableGraph concept, in which all the function are synchronized by the same mutex. Only one function at time can takes the graph. I've a doubt: have I must also to synchronize the access methods to the graph properties maps ( get() and put() )? They are Also shared... Thanks in advance, Cosimo Calabrese.