Re: [boost] [multi_index] a more complicated container - good example

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2007-07-19 06:13:43

Hello, Janek, I've studied a bit the scenario you propose and I've
got some questions and proposals related to a possible implementation
with Boost.MultiIndex.

Janek Kozicki ha escrito:
[...]

> Imagine that we want to simulate 4 magnets (eg. from loudspeakers)
> falling down on a ground.
>
> 1. To speed up calculation we decide that magnetic interaction does
> not exist above some defined distance (so we avoid calculating
> magnetic forces between all magnets).
>
> 2. magnets can collide with each other and with the ground
>
> 3. we say that ground can collide with the mangnets, and also emits
> gravity to all of them with unlimited distance.
>
> 5. ground doesn't move.
>
> Ok, so let's crank it out. First we name the bodies and the
> interactions using "bimap<id,std::string> names;". So it will be
> easier for humans to grasp. Remember that negative number is a group.
>
> names:
>
> id      name
> 1       magnet 1
> 2       magnet 2
> 3       magnet 3
> 4       magnet 4
> 5       ground
> -1      all the magnets
> -2      groups of interactions happening through collision
> -3      groups of interactions happening through magnetic forces
> -4      groups of interactions happening through gravity

Why do you assign positive IDs to bodies and negative IDs to groups
and groups of interactions? As far as I can see there's no need to use
this kind of loose type checking, since IDs for different classes of
entities are handled separately.

> Now we examine the simulation at some particular point in time. Let's
> see what interactions are happenning here. We have some bodies
> colliding with each other (also a three body collision). We have some
> magnets close enough interacting through magnetic force. Let's say
> that bodies 2 and 4 are currently too far to interact megnetically.
>
> bodies_involved  group   group_of_groups      Interaction* instance
> 1,2              -5      -2                   ... (collision)
> 2,3,4            -6      -2                   ... (collision)
> 4,5              -7      -2                   ... (collision with ground)
> 1,2              -8      -3                   ... (magnetic interaction)
> 2,3              -9      -3                   ... (magnetic interaction)
> 3,4              -10     -3                   ... (magnetic interaction)
> 1,2,3,4,5        -11(*)  -4                   ... (gravity)
>
> (*) -10 is in fact not necessary, because it duplicates information in -4.
>
> During my calculations I must iterate separetely over all "collision"
> interactions, all "magnetic" interactions, and that (single) gravity
> interaction. Becuase different formulas govern collisions (Hooke's
> law), other magnetism (Maxwell's equations), others gravity (Newton's
> law).
>
> (in fact gravity is so special that currently I do it differently,
> but let's now try it that way)
>
> Also, my employer told me that "magnet 4" is really special, and I
> must answer if it will be damaged in this simulation, while others
> are not important. I must iterate over every interaction where
> "magnet 4" takes part to calculate something to see if it breaks.
> But it is simpler to iterate *first* over all "collision" interactions
> involving "magnet 4". because it's a different mathematical formula
> that will say if it will break or not. Then iterate over *other*
> categories with other formula. Also let's say that "magnet 2" is
> really dangerous for "magnet 4" if they touch each other I must
> instantly know this.
>
> Now, the point is, that I think (not sure!) is that I should compress
> this information, to make it simpler (for the computer, not me :-).
>
> So I will use that 'groups' container about which I started this

> thread. It contains information already written above.
>
> "bimap<id,group_id> groups;":
>
> id      groups it belongs to
> 1       -1 -5 -8 -11
> 2       -1 -5 -6 -8  -9 -11
> 3       -1 -6 -9 -10 -11
> 4       -1 -6 -7 -10 -11
> 5       -7 -11
> -5      -2
> -6      -2
> -7      -2
> -8      -3
> -9      -3
> -10     -3
> -11     -4
>
> And finally the interaction container will use just one index to
> identify things (the last column "group_of_groups"):
>
> group_of_groups      Interaction*
> -2                   ... (collision)
> -2                   ... (collision)
> -2                   ... (collision with ground)
> -3                   ... (magnetic interaction)
> -3                   ... (magnetic interaction)
> -3                   ... (magnetic interaction)
> -4                   ... (gravity)

OK, here's one possible realization. Note that there are some divergences
with respect to some initial assumptions you made, please verify whether
they're acceptable:

Say bodies are implemented like this:

  struct body
  {
    body(int id):id(id){}
    ...
    int id;
  };

and what you call groups of interactions I'll simply call interactions and model
them like this:

  struct interaction
  {
    interaction(int id,int type):id(id),type(type){}
    ...
    int id;
    int type;
  };

where id is self-explanatory and type codes what you call "groups of
groups", using for instance some mnemonic enum:

  enum{collision=0,magnetic=1,gravitational=2};
  interaction  i5(5,collision);

Now, all the relationships between interactions and bodies can be represented
as a multi-index container over pairs of (body*,interaction*):

  typedef std::pair<
    body*,
    interaction*
  > body_interaction_value_type;

  typedef multi_index_container<
    body_interaction_value_type,
    indexed_by<
      hashed_non_unique<body_id_extractor>,
      hashed_non_unique<interaction_id_extractor>,
      ordered_non_unique<interaction_type_extractor>
    >
  > body_interaction;

where the custom key extractors (which are defined in the complete
program attached) do what their names suggest. So, body_interaction has
indices on body ID, interaction ID and type of interaction. Some remarks:

* Unlike your approach, mine does not create any kind of entities for
"groups of groups": instead, the type of each interaction is just an
attribute of that entity. I don't see any need for having groups of groups
assigned IDs as if they were interactions.
* Indices are hashed so as to provide constant time lookup complexities.
This works best under the following assumptions:
  - Each interaction does not involve many bodies (with the possible
  exception of gravity, which nonetheless can be dealt with with special
  methods, namely via index #2.)
  - Each body is not involved in many interactions.
As always, only real measurements can tell whether this model can really
scale up.

In the following examples, assume we've got a container of type
body_interaction called bi.

> I need to:
> - iterate on all interactions no. -2, answer: -5 -6 -7

  accumulate(
      acc,bi.get<2>().equal_range(collision),interaction_id_extractor());

This uses index #2 (grouping by type of interaction); note that each interaction
will we visited as many times as bodies it involves: to eliminate duplicates a
O(1)-complecity consists in accumulating the entries into a unique hashed set,
which is what accumulate does (see the code attached for more details.)

> - iterate on all bodies in interaction -2, answer: 1 2 3 4 5 (accidentally all bodies)

    accumulate(
      acc,bi.get<2>().equal_range(collision),body_id_extractor());

As the previous, but we extract body IDs instead of interaction IDs.

> - iterate on all bodies in interaction -6. answer: 2,3,4

    print(bi.get<1>().equal_range(6),body_id_extractor());

We look for all entries with interaction IDs 6 (in O(1) time)
and lists their associated body IDs.

> - iterate on all interactions from group -2 that involve body 4, answer: -6 -7

    print(
      bi.equal_range(4),interaction_id_extractor(),
      is_interaction_type(collision));

We (efficiently) list the interactions in whicj voy 4 is involved and filter
according to the type of collision. This works on the assumption that body 4
is not involved in many interactions, as explained above.

> - iterate on all interactions that involve body 1, answer: -5 -8 -11, -2 -3 -4

    print(bi.equal_range(1),interaction_id_extractor());

> - check if there is an interaction from group -2, that involves bodies 2 and 4,
>       answer: yes it is -6

    print(
      bi.equal_range(2),interaction_id_extractor(),
      bll::bind(is_interaction_type(collision),bll::_1)&&
      bll::bind(does_interaction_affect_body(4,bi),bll::_1));

We look up the interactions in which body 2 is involved and filter as
appropriate.

I don't really know if this approaches what you've got in mind. Depending
on the type of queries you're going to make, it might be benefficial to
include more indices, but looks to me like your basic needs could be
covered with the model I propose.

Complete example attached, compiled under GCC 3.2

HTH,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo