MASON-INTEREST-L Archives

September 2013

MASON-INTEREST-L@LISTSERV.GMU.EDU

Options: Use Monospaced Font
Show Text 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:
Mon, 30 Sep 2013 10:19:29 -0400
Content-Type:
text/plain
Parts/Attachments:
text/plain (104 lines)
Yes, getOtherNode.  Someone's sleepy.

Sean

On Sep 30, 2013, at 5:14 AM, Beth Kar wrote:

> Thank you Sean, I tried your approach and so far it works fine for me.
> However, currently I only work on a relatively small network of agents (15).
> However, since there is no method getOtherEdge(from) I guess you meant
> getOtherNode(from), right?
> 
> So, the code I used is:
> 
> public Edge getEdge(Network network, Object from, Object to){
> 		Bag b = network.getEdgesOut(from);
> 				
> 		for (int i=0; i<b.size(); i++){
> 			
> 			Edge e = (Edge)(b.get(i));
> 		
> 			if(e.getOtherNode(from).equals(to)){
> 				return e;
> 			}
> 			
> 		}
> 		
> 		return null;
> 	}
> 
> and then:
> 
> if(getedge(AgentA, AgentB) == null){
> 	network.addEdge(AgentA, AgentB, null);
> }
> 
> Beth.
> 
> 
> On Fri, 27 Sep 2013 22:09:31 -0400, Sean Luke <[log in to unmask]> wrote:
> 
>> 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