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