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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-04-05 11:46:55

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<FirstSetData, SecondSetData>.

   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<vertex_index_t, Graph>::const_type 
VertexIndexMap;
       VertexIndexMap index_map = get(vertex_index, g);
       iterator_property_map<FirstSetData*, VertexIndexMap> 
first_set_data(&first_set_data_vec[0], index_map);
       iterator_property_map<SecondSetData*, VertexIndexMap> 
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