[BGL, Graph] choose the correct container to handle graph with a property
Hello, I have a graph representing the Network topology and I want to replace it by a BGL graph. My problem is that I need to find a vertex by its IP address (an internal property), but I think we can only find a vertex with its vertex_descriptor. A solution is to maintain a map from IP address to vertex_descriptor. But removing a vertex with vecS for VertexList invalidates all vertex descriptors. Unfortunately, I need some efficiently to find a vertex, so listS seems not appropriated. Finally, I try to use setS for VertexList (and it works IMHO), but in the documentation: "The container must model Sequence or RandomAccessContainer." Hence, my questions are: - Can I use setS for VertexList ? And if I can't, why ? - Is there a better solution to find vertex by an internal property that handle an exterior map ? Cheers, -- Johan
Johan Oudinet ha escrito:
Hello, I have a graph representing the Network topology and I want to replace it by a BGL graph. My problem is that I need to find a vertex by its IP address (an internal property), but I think we can only find a vertex with its vertex_descriptor. A solution is to maintain a map from IP address to vertex_descriptor. But removing a vertex with vecS for VertexList invalidates all vertex descriptors. Unfortunately, I need some efficiently to find a vertex, so listS seems not appropriated.
[...]
Hence, my questions are: - Can I use setS for VertexList ? And if I can't, why ?
[...] I think a multi_index_container would be a perfect fit here, because it can provide a sequenced index as the VertexList interface and additional ordered indices for lookup. Unfortunately, this cannot be made to work without some serious hacking, unless BGL provided additional guarantees on some internal details of adjacency_list. The complete story can be read at http://thread.gmane.org/gmane.comp.lib.boost.devel/116970 where you can find the efforts of a guy called Alexander to blend BGL and Boost.MultiIndex. In the end he succeeded, but only at the expense of relying on the internal implementation of adjacency_list. 100% unsafe. Of course, it this a recurrent need I think it'd be great if adjacency_list can be extended/overspecified so as to work with multi_index_containers. My hunch is that little actual work would be needed. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On 11/21/05, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
Johan Oudinet ha escrito:
[...]
I think a multi_index_container would be a perfect fit here, because it can provide a sequenced index as the VertexList interface and additional ordered indices for lookup. Unfortunately, this cannot be made to work without some serious hacking, unless BGL provided additional guarantees on some internal details of adjacency_list. The complete story can be read at
http://thread.gmane.org/gmane.comp.lib.boost.devel/116970
where you can find the efforts of a guy called Alexander to blend BGL and Boost.MultiIndex. In the end he succeeded, but only at the expense of relying on the internal implementation of adjacency_list. 100% unsafe.
Thanks for the URL, it was an interresting experience but too long and unsafe for me :-(
Of course, it this a recurrent need I think it'd be great if adjacency_list can be extended/overspecified so as to work with multi_index_containers. My hunch is that little actual work would be needed.
I agree with you and I hope this work will be soon (so I can use it without doing the Alexander's work :-p) I used a mapping from IP address to vertex_descriptor until BGL provides multi_index_containers. Cheers, -- Johan
participants (4)
-
Joaquín Mª López Muñoz -
Johan Oudinet