Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Get all links connecting turtles in a turtle-set efficiently in NetLogo

Given a turtle-set nodes, I want to find all links that have both ends in nodes. The best I've come up with so far is:

link-set [ my-links with [ member? other-end nodes ] ] of nodes

This does exactly what I want. However, since member? runs in linear time for non-breed sets, this is O(n*n*d) (where d is the max degree of the nodes and n is the number of nodes). I could improve it using a hash set, but that would require either abusing the table extension, finding a third-party extension, or making my own. I could also create a sorted list of the who numbers of the nodes, and then perform binary search on it to get down to O(n * log(n) * d), but I'm hoping for a simpler answer. Any ideas?

like image 305
Bryan Head Avatar asked Aug 15 '14 19:08

Bryan Head


1 Answers

Here is a wacky idea:

links-own [ i ]

to-report links-between [ nodes ]
  ask links [ set i 0 ]
  ask nodes [ ask my-links [ set i i + 1 ] ]
  report links with [ i = 2 ]
end

It's not the most elegant thing in the world, but it is simple enough and, I believe, only O(n*d).

like image 58
Nicolas Payette Avatar answered Sep 21 '22 06:09

Nicolas Payette