Print

Print


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