# Source code for pacman.utilities.vertex_sorter

```
# Copyright (c) 2017-2019 The University of Manchester
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# 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 <http://www.gnu.org/licenses/>.
import sys
from spinn_utilities.default_ordered_dict import DefaultOrderedDict
[docs]class ConstraintOrder(object):
""" A constraint order definition for sorting.
"""
__slots__ = [
# The class of the constraint
"_constraint_class",
# The order of the constraint relative to other constraints to be
# sorted
"_relative_order",
# Properties of the constraint instances that must not be None for
# the constraint to match this ordering
"_required_optional_properties"
]
def __init__(
self, constraint_class, relative_order,
required_optional_properties=None):
"""
:param type constraint_class: The class of the constraint
:param int relative_order:
The order of the constraint relative to other constraints to be\
sorted
:param required_optional_properties:
Properties of the constraint instances that must not be None for\
the constraint to match this ordering
:type required_optional_properties: list(str) or None
"""
self._constraint_class = constraint_class
self._relative_order = relative_order
self._required_optional_properties = required_optional_properties
@property
def constraint_class(self):
""" the constraint class
:rtype: type
"""
return self._constraint_class
@property
def relative_order(self):
""" the relative order
:rtype: int
"""
return self._relative_order
@property
def required_optional_properties(self):
""" the required optional properties
:rtype: list(str) or None
"""
return self._required_optional_properties
[docs]class VertexSorter(object):
""" Sorts vertices based on constraints with given criteria.
"""
__slots__ = [
# Group constraints based on the class
"_constraints"
]
def __init__(self, constraint_order):
"""
:param list(ConstraintOrder) constraint_order:
The order in which the constraints are to be sorted
"""
# Group constraints based on the class
self._constraints = DefaultOrderedDict(list)
for c in constraint_order:
self._constraints[c.constraint_class].append(
(c.relative_order, c.required_optional_properties))
# Sort each list of constraint by the number of optional properties,
# largest first
for constraints in self._constraints.values():
constraints.sort(key=len, reverse=True)
[docs] def sort(self, vertices):
""" Sort the given set of vertices by the constraint ordering
:param list(AbstractVertex) vertices: The vertices to sort
:return: The sorted list of vertices
:rtype: list(AbstractVertex)
"""
vertices_with_rank = list()
for vertex in vertices:
# Get all the ranks of the constraints
ranks = [sys.maxsize]
for c in vertex.constraints:
# If the constraint is one to sort by
if c.__class__ in self._constraints:
current_ranks = self._constraints[c.__class__]
for (rank, required_param) in current_ranks:
if self._matches(c, required_param):
ranks.append(rank)
# Sort and store the ranks for overall ordering
ranks.sort()
vertices_with_rank.append((vertex, ranks))
# Sort the vertices - because ranks is a list, things with the same
# min rank will be sorted by the next highest rank and so on
vertices_with_rank.sort(key=lambda thing: thing[1])
# Strip the ranks from the sorted list
return [vertex for vertex, _ in vertices_with_rank]
@staticmethod
def _matches(constraint, opts):
""" Determines if the constraint matches the given optional required\
parameters
:param AbstractConstraint constraint:
:param opts:
:type opts: list(str) or None
:rtype: bool
"""
if opts is None:
return True
return all(getattr(constraint, opt) is not None
for opt in opts)
```