src/nepi/util/rmatcher.py

   1 #
   2 #    NEPI, a framework to manage network experiments
   3 #    Copyright (C) 2013 INRIA
   4 #
   5 #    This program is free software: you can redistribute it and/or modify
   6 #    it under the terms of the GNU General Public License version 2 as
   7 #    published by the Free Software Foundation;
   8 #
   9 #    This program is distributed in the hope that it will be useful,
  10 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 #    GNU General Public License for more details.
  13 #
  14 #    You should have received a copy of the GNU General Public License
  15 #    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16 #
  17 # Author: Alina Quereilhac <alina.quereilhac@inria.fr>
  18
  19 def match_tags(box, all_tags, exact_tags):
  20     """ returns True if box has required tags """
  21     tall = set(all_tags)
  22     texact = set(exact_tags)
  23
  24     if texact and box.connections == texact:
  25         return True
  26
  27     if tall and tall.issubset(box.connections):
  28         return True
  29
  30     return False
  31
  32 def find_boxes(box, all_tags = None, exact_tags = None, max_depth = 1):
  33     """ Look for the connected boxes with the required tags, doing breath-first
  34     search, until max_depth ( max_depth = None will traverse the entire graph ).
  35     """
  36     if not all_tags and not exact_tags:
  37         msg = "No matching criteria for resources."
  38         raise RuntimeError(msg)
  39
  40     queue = set()
  41     # enqueue (depth, box)
  42     queue.add((0, box))
  43
  44     traversed = set()
  45     traversed.add(box)
  46
  47     depth = 0
  48
  49     result = set()
  50
  51     while len(q) > 0:
  52         (depth, a) = queue.pop()
  53         if match_tags(a, all_tags, exact_tags):
  54             result.add(a)
  55
  56         if not max_depth or depth <= max_depth:
  57             depth += 1
  58             for b in sorted(a.connections):
  59                 if b not in traversed:
  60                     traversed.add(b)
  61                     queue.add((depth, b))
  62
  63     return result