#
# NEPI, a framework to manage network experiments
# Copyright (C) 2013 INRIA
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License version 2 as
# published by the Free Software Foundation;
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see .
#
# Author: Alina Quereilhac
def match_tags(box, all_tags, exact_tags):
""" returns True if box has required tags """
tall = set(all_tags)
texact = set(exact_tags)
if texact and box.connections == texact:
return True
if tall and tall.issubset(box.connections):
return True
return False
def find_boxes(box, all_tags = None, exact_tags = None, max_depth = 1):
""" Look for the connected boxes with the required tags, doing breath-first
search, until max_depth ( max_depth = None will traverse the entire graph ).
"""
if not all_tags and not exact_tags:
msg = "No matching criteria for resources."
raise RuntimeError(msg)
queue = set()
# enqueue (depth, box)
queue.add((0, box))
traversed = set()
traversed.add(box)
depth = 0
result = set()
while len(q) > 0:
(depth, a) = queue.pop()
if match_tags(a, all_tags, exact_tags):
result.add(a)
if not max_depth or depth <= max_depth:
depth += 1
for b in sorted(a.connections):
if b not in traversed:
traversed.add(b)
queue.add((depth, b))
return result