CODEWITHSUNDEEP
graph-theorynetlogo
Bryan Head
Bryan Head

Reputation: 12580

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?

Upvotes: 6

Views: 1010

Answers (1)

Nicolas Payette
Nicolas Payette

Reputation: 14972

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

Upvotes: 7

Related Questions