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

From: Janek Kozicki (janek_listy_at_[hidden])
Date: 2007-07-18 13:53:27

Ok, 

I managed to find a good example, so it will be easier to get the
picture. (because previous email doesn't seem too clear ;)
But still when I write it I assume that you looked at "class Model"
from parent post.

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

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)

I need to:
- iterate on all interactions no. -2, answer: -5 -6 -7
- iterate on all bodies in interaction -2, answer: 1 2 3 4 5 (accidentally all bodies)
- iterate on all bodies in interaction -6. answer: 2,3,4
- iterate on all interactions from group -2 that involve body 4, answer: -6 -7
- iterate on all interactions that involve body 1, answer: -5 -8 -11, -2 -3 -4
- check if there is an interaction from group -2, that involves bodies 2 and 4, 
      answer: yes it is -6

that's it. The interaction container will heavily rely on information
stored in 'groups' container to answer all the queries.

Most of all, I really would like to have a constant answer time
(regardless of container size), because I'm going to simulate 10'000
of bodies. If some other solution would be faster for 500 bodies I
don't care, I need constant (possibly longer) time.

PS: gravity in different way: You noticed that in fact only ground is
an "emitter" of gravity, why the magnets are only receivers. I would
need to distinguish the emitter/receiver somehow. But that's even a
more different story. First I want to crunch the problem above :)

-- 
Janek Kozicki