Re: [Repast-developer] Topology Notes

[Thomas R. H. <th...@sr...>]

On Fri, 2003-01-24 at 20:46, Laszlo Gulyas wrote:
> 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) == d(y,x).  The network library has
> >complete support for asymmetric relationships: d(x,y) != d(y,x) or
> >d(y,x) == 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.
> 

Yeah, it's a side-note, but I think it is a fairly important semantic
point.

[...]
> 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). 
> 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 
> fail
> miserably if not all edges are generated yet...
> 


Yeah, I thought about generating these edges on the fly, also.  Seems
like this doesn't provide much of an advantage.  I suppose it allows you
to maintain the getOutEdges or getRelations, so that might be useful. 
But it forces the user to create those methods, when they might never
need them.  For example, in the situation like a grid, it seems rare
that a user would call getOutEdges, but it would still need to exist to
maintain the interface contract.  Perhaps I'm not seeing something
here.  Obviously, it wouldn't be difficult to handle the grid example,
but I'm thinking more about when people create their own spaces.


[...]
> 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 
> 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 
> 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 
> artifacts...
> 

If I understand what you mean here, I think this has a lot of
potential.  Basically, the network (or context) acts as a set of
containers that can hold agents (at least in a spatial context). 
Basically a square lattice of buckets.  Then the agents query that to
determine their own edges.  This is actually what I was thinking about
when we were first having these discussions, but I never quite settled
on it.  But it makes sense.  If we assume that the network represents
the agents' relationships (which your model certainly does), then the
spatial relationships, would be somewhat exterior to the agent.  Spatial
relationships are exogenous to the actors afterall.  I think that this
could work with a limited overhead, because, as you say, the agents can
still be accessed using the matrix structure.  In this situation, I
would think that we would encourage users to use the getTo/getFrom Node
type methods, with added getVonNuemannNodes, etc.  As long as people
used these methods, they could swap spaces with no problem.  It may be
bending the model, but it does make sense to me.  I still think the
semantics of a spatial model are different, but I think that if users
want space swapability(sic from myself), they will have to use these
kinds of abstractions.

I would say, though, that I think it should be a "neighbor" context, not
a partner context.  

> >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.

I still have concerns about this, but our network stuff has a base agent
class, so. . .  The other thing is that if people want to use the
network as a set of containers for agents (since a spatial network like
a grid will be static), then this doesn't apply because, they can put
any class in a node on the network.

> 
> >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


Like you say, as long as we have concrete space classes that have range
operators, this shouldn't be a problem.  It just won't be abstracted
out.


Having said all this, I think that there is a semantic argument still to
made here.  I think that your identification of spaces as contexts is
particularly important.  IF we think of them as spaces, this will never
be consistent. (A social network is different than a grid).  But if they
are contexts, which can be layered and represent different kinds of
relationships, then the semantic difference is eliminated.  Some
contexts are static others are dynamic.  I think that this has potential
to be the way forward.  What do others think?

-Tom


> >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=328959&dl=ACM&coll=portal.
> > > > 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ïve 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
> 
> 
> 
> 
> -------------------------------------------------------
> This SF.NET email is sponsored by:
> SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See!
> http://www.vasoftware.com
> _______________________________________________
> Repast-developer mailing list
> Rep...@li...
> https://lists.sourceforge.net/lists/listinfo/repast-developer
-- 
Tom Howe
Social Science Research Computing
University of Chicago