1

The question is about the Boost Graph Library (there is no such label unfortunately).

Suppose that I have associated a Widget instance with each vertex of a graph by using the bundled property feature of the Boost Graph Library. The class Widget implements operator== and all widgets associated with vertices are distinct (i.e., for any pair of vertices, widget1 != widget2 holds for the widgets associated with these vertices).

Does the graph maintain a reverse mapping, i.e. can I easily retrieve a vertex descriptor that corresponds to a given object? In particular, suppose that I have objects widget1 and widget2 and the corresponding vertices have been added into the graph. How can I add an edge between the two objects (i.e. between the corresponding vertices)?

AlwaysLearning
  • 7,257
  • 4
  • 33
  • 68
  • Please have a look here: http://stackoverflow.com/questions/32296206/bgl-indexing-a-vertex-by-keys/32296688#32296688 the ***[Bimap suggestion](http://stackoverflow.com/questions/26697477/cut-set-of-a-graph-boost-graph-library/26699982#26699982)*** could actually work for you – sehe Nov 15 '15 at 19:59

1 Answers1

1

I suspect that BGL itself cannot provide a mapping from a vertex attribute to the corresponding vertex descriptor because the mapping is m:1 many to one, in general. Many vertices/descriptors can correspond to the same attribute. Even though in your case, you know that different vertices must have different attribute, BGL generally has no way of knowing that.

You can probably maintain this mapping (e.g. vd_map) yourself when you create the graph e.g. using std:map. When you insert each vertex with its attribute (Widget in this case), insert a corresponding entry:

vd_map[widget] = desc;
thor
  • 21,418
  • 31
  • 87
  • 173
  • If I understand correctly, vertex descriptors can get invalidated. So, wouldn't this solution mean that I can never delete a vertex? – AlwaysLearning Nov 15 '15 at 18:36
  • 2
    I am not sure what your code is trying to do. I guess if you need to delete a vertex, you can always delete the entry from this reverse lookup map beforehand. – thor Nov 15 '15 at 19:20
  • You are right! If I use listS, then all is fine, since only one descriptor gets invalidated upon vertex deletion! – AlwaysLearning Nov 15 '15 at 21:53