Source code for sfepy.base.resolve_deps

"""
Functions for resolving dependencies.
"""
from __future__ import absolute_import
import itertools as it

from sfepy.base.base import basestr
import six
from six.moves import range

[docs] def get_nums(deps): """ Get number of prerequisite names for each name in dependencies. """ nums = {} for key, val in six.iteritems(deps): nums[key] = len(val) return nums
[docs] def solvable(deps, names): """ Return True if `names` form a solvable block, i.e. the set of names equals to the set of their prerequisites. """ if not names: return False # Missing self-reference. dep_names = set() for name in names: dep_names.update(deps[name]) return dep_names == set(names)
[docs] def remove_known(deps, known): """ Remove known names from dependencies. """ if isinstance(known, basestr): out = {} for key, val in six.iteritems(deps): if key == known: continue out[key] = [ii for ii in val if ii != known] return out else: out = deps for ii in known: out = remove_known(out, ii) return out
[docs] def try_block(deps, num): """ Return generator of lists of solvable blocks of the length `num`. """ keys = list(deps.keys()) for ic in it.combinations(keys, num): if solvable(deps, ic): yield sorted(ic)
[docs] def resolve(deps): """ Resolve dependencies among equations so that smaller blocks are solved first. The dependencies are given in terms of variable names. Parameters ---------- deps : dict The dependencies as a dictionary with names as keys and sets of prerequisite names as values. Returns ------- order : list The list of blocks in the order of solving. Each block is a list of names. """ order = [] if not(len(deps)): return order nums = get_nums(deps) ib0 = min(nums.values()) for ib in range(ib0, len(deps) + 1): blocks = [ii for ii in try_block(deps, ib)] if len(blocks): new_deps = remove_known(deps, blocks[0]) order.extend([blocks[0]] + resolve(new_deps)) if len(list(it.chain(*order))) == len(deps): break return order