MASON-INTEREST-L Archives

September 2013

MASON-INTEREST-L@LISTSERV.GMU.EDU

Options: Use Proportional Font
Show HTML Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Subject:
From:
Sean Luke <[log in to unmask]>
Reply To:
MASON Multiagent Simulation Toolkit <[log in to unmask]>
Date:
Fri, 27 Sep 2013 22:09:31 -0400
Content-Type:
text/plain
Parts/Attachments:
text/plain (51 lines)
The implementations discussed so far have some problems.  So some notes on people's implementations.  First Tony's:

> public boolean areNeighbors(Network network, Object agentA, Object agentB) {
>     Bag edges = network.getEdges(agentA, null);
>     Iterator<Edge> iter = edges.iterator();    
>     while (iter.hasNext()) {                
>             Edge e = iter.next();
>             if (e.getOtherNode(agentA)==agentB)
>                 return true;
>         }
>     return false;              
> }

The problem with this approach is threefold.  First, it searches the entire network looking for an edge between two nodes -- this is O(E), which is *extremely* slow, particularly when Network has an O(1) lookup for this!  Second, if agentA isn't on either end of an edge, then getOtherNode(agentA) will return a node -- and in theory that node could be agentB.  So using it like this will have bugs.  Third, using == is probably not preferable to using .equals(...) since Network uses hash lookups (which use .equals(...) internally).

Beth's approach:

> Bag edges = mynetwork.getEdges(agentA, null);
> int length = edges.size();
> boolean exists = false;
> 		
> for (int node=0; node<len; node++) {
>     Edge e = (Edge)(edges.get(node));
>     if(e.getOtherNode(agentA) == agentB) exists = true;
>     else continue;
> }
> 
> if (!exists) mynetwork.addEdge(agentA, agentB, null);

This has the same three issues.

I suggest instead doing this.  Let the two objects be "from" and "to" instead of agentA and agentB.  If your graph is undirected, it doesn't matter which is from and which is to.

public Edge getEdge(Network network, Object from, Object to) 
	{
    	Bag b = network.getEdgesOut(from);  // will never be null
    	for(int i = 0; i < b.size(); i++)
    		{
    		Edge e = (Edge)(b.get(i));
    		if (e.getOtherEdge(from).equals(to))
    			return e;
    		}
    	return null;
    	}

If an edge exists, this method returns it, else it returns null.  This should be a gazillion times faster for large networks.

I've not tested this to see if it works, but if it doesn't, it should be a simple bugfix.  If we can get some verification, I'll add a similar method to Network proper.

Sean, embarrassed that this wasn't here in the first place...

ATOM RSS1 RSS2