Re: [Boost-users] How to represent bipartite graphs ?

5 Apr 2005

      On Apr 5, 2005, at 2:38 AM, Markus Krosche wrote:
...
Hello together,
in my software I have to represent bipartite graphs, in my case petri
nets (two disjoint sets - the places and the transitions - and only
links between elements of the disjoint sets). I would like to use BGL
for this purpose, but I did not find a "nice" solution for this 
problem.
I am quit new to BGL and the only way I see is representing the two
types of vertices inside a vertex-property. A better way would be to
have two types of vertex properties, but I think this is not possible.
Is there anyone who has a solution or an idea for this kind of problem?
Well, you're probably stuck with one of two solutions:

   1) Have both types of vertices stored inside a vertex property. You 
could make this property a pointer to a base class (e.g., BaseVertex*), 
where the derived class is the data for either the first or second set, 
e.g.,

   struct BaseVertex {
     virtual ~BaseVertex() {}
     // things in common with both sets of vertex
     bool isInFirstSet() const = 0;
   };

   struct SetOneVertex : BaseVertex {
     // things for the first set
   };

   struct SetTwoVertex : BaseVertex {
     // things for the second set
   };

   Or, if you're feeling like trying out more Boost libraries, you could 
use a boost::variant.

   2) Have two separate *external* property maps, one for the first set 
and one for the second set. For instance, the property maps could be 
iterator_property_map instances built from these vectors:

       std::vector<FirstSetData> first_set_data_vec(num_vertices(g));
       std::vector<SecondSetData> second_set_data_vec(num_vertices(g));
       typedef property_map::const_type 
VertexIndexMap;
       VertexIndexMap index_map = get(vertex_index, g);
       iterator_property_map 
first_set_data(&first_set_data_vec[0], index_map);
       iterator_property_map 
second_set_data(&second_set_data_vec[0], index_map);

    Just be careful to only reference first_set_data from vertices in 
the first set and second_set_data from vertices in the second set.

	Doug

Re: [Boost-users] How to represent bipartite graphs ?

Doug Gregor