MASON-INTEREST-L Archives

September 2013

MASON-INTEREST-L@LISTSERV.GMU.EDU

Options: Use Monospaced Font
Show Text Part by Default
Condense Mail Headers

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

Print Reply
Mime-Version:
1.0
Sender:
MASON Multiagent Simulation Toolkit <[log in to unmask]>
Subject:
From:
Beth Kar <[log in to unmask]>
Date:
Mon, 30 Sep 2013 05:14:30 -0400
Content-Transfer-Encoding:
8bit
Content-Type:
text/plain; charset="windows-1252"
Reply-To:
MASON Multiagent Simulation Toolkit <[log in to unmask]>
Parts/Attachments:
text/plain (98 lines)
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