Re: [Repast-developer] Topology Notes

[Laszlo G. <gu...@la...>]

Hi Tom and all,

I'm very excited that we got to talking about this! ;-)
Obviously, most of your comments and concerns are true.
I've been thinking along some of these lines, too, back in
November. Let me see what I can remember from those thoughts...

At 09:55 AM 1/22/2003 -0600, Thomas R. Howe wrote:
>[...]
>First, I see a problem with conclusion in our previous discussions that
>metric spaces can unify the space library.  Metric spaces only apply to
>symmetric relationships, d(x,y) =3D=3D d(y,x).  The network library has
>complete support for asymmetric relationships: d(x,y) !=3D d(y,x) or
>d(y,x) =3D=3D null.  In fact this is the most general case.  Symmetric
>networks are the special case (albeit a rather substantial one). So it
>seems that, at least for that part of the space library, metrics don't
>apply.  Now it seems totally reasonable to unify, at least, all of the
>grid type spaces, and perhaps even symmetric networks, using the metric
>approach.

You're absolutely right here. (Even though, one could imagine and
implement a  'distance function' that is not symmetric; it should never
be called a 'metric'.) But this is really just a side-note.


>Gulya, Nick and I were talking about the relation stuff you came up with
>yesterday.  That is a super neat way to unify the network stuff with the
>spatial stuff.  I have some concerns, (I'm sure you can guess what they
>are).  The first is performance, both memory and computation.  If there
>is a large grid, the set of edges created by a Moore neighborhood will
>be huge.  Computationally, I'm concerned about the update method in the
>contexts.

My intention with the current implementation was to be a 'proof-of-concept'
thing. Also, I figured that a particular relation type can always be=20
implemented
in a 'smart way'. Meaning that the functionality defined in RelNode can=
 always
be overridden to capitalize on the additional information known about the=20
space.
This could mean a class 'between' RelNode and the class of the actual=
 relation.

According to this scenario, if the modeler (or the programmer) knows a=
 better
data structure/algorithm to store the edges and reproduce them upon request
(e.g., when getRelatedTo() is called) than the naive set of HashMaps used in
RelNode, and it s/he thinks it worths the effort in that particular=20
project, then
s/he should definitely implement it that way. If s/he decides otherwise, the
project can still fall back on the standard implementation.

Now, with spaces provided by Repast itself, it's obviously a bit different.
I always imagined that grid spaces would be based on matrices in the=
 background
(It's hard to imagine anything more efficient.) But, the same time, they=
 would
respond to the same set of methods. That is, it's much like the current=20
'getNeighbors()'
thing, except that it comes from a standard set applicable to more general=
=20
spaces.
And that it would return Edges or Nodes...

Obviously, this would come at the price of actually storing the space twice
(once in the matrix, and once in the graph). :(

Also, I might be overlooking something. For example, I always thought edges
could be generated 'on the fly' (e.g., when the actual method is called).=20
And, I am
sure, this is true for most cases. Still, one never knows when the user=
 might
feel like starting, say, a breadth-first graph-search. And then, s/he would=
=20
fail
miserably if not all edges are generated yet...

>If agents are moving, and constantly changing their
>neighborhoods, the update method (where relations are updated) will be
>extremely expensive.

Yes. But if the setup I outlined above works, it might not be. On the other=
=20
hand,
I would implement the scenario you describe above as having a 'spatial=
 context'
that defines what location is a neighbor to what other location. That's=20
obviously
static. Then I'd have a '"partner" context', which would define the agent's
'partners'. This latter's implementation would be based on the 'spatial=20
context'.
That is, it'd simply query the former to get the actual neighbors.

Now, it might be, again, bending the model towards the implementation=20
artifacts...

>My second concern is that all agents will have to
>extend some base class (DefaultNode, RelNode, etc.).  This eliminates
>some of the flexibility people could use to extend other classes.  This
>has been a concern for both Nick and I and is one reason why we so
>desparately want to use aspects.

True, and I know about this concern. To some extend I share it, too.
My main reason for going with the base class solution was clarity.
I guess, the whole framework could be implemented based on interfaces, too,
(I never tried, though), but I wanted to keep the benefits of having a clean
notation and a clean model code in the end.

That is to say, I won't necessarily fight for this design... Again, I might
be overlooking something. It's been a while (2 months) that I worked on
this...


>The third concern I have has to do
>with the Range operator.  I guess this falls under computational
>expense, but it is a little different.  If someone needs to do a range
>query, the agent would need to find the shortest path to each of the
>other objects.  That would be prohibitively expensive.
>I wonder, do you have any thoughts on how to get around this problem?

This is true and this is something I did not think about before. Still,
if we could keep the option of plugging in 'smart implementations'
then this one, too, goes away. I mean, then it boils down to the
common trade-off between putting in more efforts during the implementation
phase or spending more time on completing the experiments.

I don't know if this helps anything, but these are my thoughts now.
I am happy to continue the discussion (hopefully, with shorter delays on
my side).

Take care!

Gulya


>On Thu, 2002-11-21 at 22:52, Laszlo Gulyas wrote:
> > Hi Guys,
> >
> > I'm sorry for taking so long reacting, but there's so many things
> > going on right now. (Not excluding selling the furniture and the car
> > in preparation to moving back to Europe.) So, my schedule was and
> > is a bit hectic. Fortunately, though, both Anita (my wife) and I have
> > saved up some days off, so we're gonna take off for a last vacation
> > soon. Hopefully, I get back for the last couple of days much more
> > relaxed/productive...
> >
> > However, I wanted to get back to you on this before that happens.
> > I think, Mike has summarized our discussion rather well. The only
> > thing remained to say is about displaying these things. In principle,
> > the Drawable interface works well: it basically maps an agent into
> > a 2D coordinate system, plus provides a way for it to draw itself.
> > This should be general enough.
> >
> > Except that it kind of makes it hard for an agent to participate in
> > several [switchable] 'spaces' or to display itself on different
> > displays
> > of the same [possibly N-dimensional] space. Now, I don't necessarily
> > think that it is time now [just before 2.0] to blow up the whole gui
> > package.
> > However, I've been doing some experimentation and created my
> > own ContextMapping (well, I call them contexts, but they are, kind
> > of, generalized topologies) interface whose methods take an agent and
> > - map it into an (X,Y) /screen/ coordinate,
> > - return its Dimension,
> > - draw it on the screen.
> >
> > I just thought I'd share this with you. (See the attachment.)
> > Please, do not look at its performance yet! On the other hand,
> > it's kind of complex, so I won't blame you not want to start
> > with it right now.
> >
> > - - - - -
> >
> > OK. In this model, I've taken the 'space/topology' issue a step
> > further. (?) [Don't think I'm suggesting you should start implementing
> > any of this. Rather, I just want to share my crazy visions with you.]
> >
> > Now I think that the bottom line of all these 'space/topology'
> > issues is the concept of a Relation. It is really nothing else, but an
> > Edge
> > on a network, so one nice thing about this approach is that it
> > provides
> > a natural way to unify the 'grid-based' and the network models.
> >
> > OK, so I call them relations, not Edges, what's the difference?
> > Technically, my implementation is nothing more than providing
> > ways to sort out edges according to their types. This way, I have
> > general methods to say, "Give me the related nodes according to
> > relation R", R being a parameter.
> >
> > My 'contexts' create and update the relations and all the Model/Agent
> > do is to query and use them, via these general methods. This way, by
> > replacing the context, you can place the agents into vastly different
> > environments, as long as they all define the same relations.
> >
> > From this point of view, the topologies/spaces just define special,
> > perhaps
> > parametrized [with distance] 'neighborhood' or 'close-to' relations.
> > Storing
> > the agents on a grid internally is just an efficient way of
> > implementing this.
> > (Naturally, it is debatable whether the relations/edges define special
> > kinds
> > of topologies, or the other way around, but this time, I just went
> > with the
> > latter option.)
> >
> > Well, let me know what do you think. Note, however, that I'll be out
> > of
> > town till December 3. So, don't get mad at me if I won't answer them
> > immediately. (Well, that's kind of usual from me, sadly enough.)
> >
> > Take care!
> >
> > Gulya
> >
> > PS: I can't resist to put this in here: as a long shot off the
> > 'relation burble':
> > this could, in fact, finally lead to the 'DB-based' simulation I've
> > been
> > 'visioning' for a while. I mean, if relations are a central concept in
> > the
> > architecture, and the model's and the agents' logic is formulated
> > according
> > to this, it could be possible to actually implement them by storing
> > them
> > in a relational DB. Then, in principle, one could do cool stuff, like
> > defining 'dynamic relationships' via joints, or creating triggers,
> > etc.
> > I'm not sure if it's necessarily more efficient, but wouldn't it be
> > cool?! ;-)
> > [Enough of me now! :-)]
> >
> > At 07:15 PM 11/15/2002 -0600, North, Michael wrote:
> >
> > > Tom:
> > >
> > >
> > >
> > > The topology issues that we discussed might be represented as
> > > follows:
> > >
> > >
> > >
> > > 1.)   An abstract Topology class or interface can be defined:
> > >
> > > a.      The class has a method, getDistance(Object o1, Object o2),
> > > that returns the distance between any two objects.
> > >
> > > b.     The Topology class has appropriate methods to get neighbors
> > > within a certain range such as getNeighbors(Object o1, double range)
> > > .
> > >
> > > 2.)   Three or more concrete Topology implementation classes can
> > > then be defined:
> > >
> > > a.      An implementation for Moore neighborhoods, von Neumann
> > > neighborhoods, and hexagonal neighborhoods based on the current grid
> > > implementation can be defined.  This would use the current
> > > array-based grid storage and maintain backward compatibility.  Since
> > > it is essentially the current implementation, it would run as fast
> > > as the current code.
> > >
> > > b.     An implementation for metric spaces can be defined that uses
> > > trees to store objects and find neighbors.  This can be done since
> > > the rules of a metric space allow tree storage.  For example see
> > > http://www.vldb.org/conf/1997/P426.PDF. Other implementations are
> > > also available, especially for large lists.  For example, see
> > > http://portal.acm.org/citation.cfm?id=3D328959&dl=3DACM&coll=3Dportal.
> > > This implementation would run slower than the current code but it
> > > would still be reasonable for most problems.  The price of slower
> > > execution is made up for by the added flexibility.
> > >
> > > c.      An implementation for completely abstract (i.e. non-metric)
> > > spaces can be defined that uses a simple list to store objects and a
> > > na=EFve all pairs matching algorithm to find neighbors.  The algorithm
> > > will simply test the distance between each object to find
> > > neighbors.  This implementation will be much slower than the current
> > > code for large lists but the slower execution will be made up for by
> > > the increased flexibility, at least for initial testing.  Users that
> > > find they need a particularly abstract notion of space are free to
> > > develop optimized versions of the Topology class as they see fit.
> > >
> > > 3.)   Users select the fastest concrete implementation class that
> > > supports their model's notion of space.  Of course, users are also
> > > free to extend or add to the existing concrete classes.
> > >
> > >
> > >
> > > Mike
> > >
> > >
> > >
> > >
>--
>Tom Howe
>Social Science Research Computing
>University of Chicago