Class SortingNetwork

examples/ga/sortingnetwork.py:19–121

Sorting network class. From Wikipedia : A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sort the values by outputting the smaller value to one wire, an

from itertools import product

class SortingNetwork(list):
    """Sorting network class.

    From Wikipedia : A sorting network is an abstract mathematical model
    of a network of wires and comparator modules that is used to sort a
    sequence of numbers. Each comparator connects two wires and sort the
    values by outputting the smaller value to one wire, and a larger
    value to the other.
    """
    def __init__(self, dimension, connectors = []):
        self.dimension = dimension
        for wire1, wire2 in connectors:
            self.addConnector(wire1, wire2)

    def addConnector(self, wire1, wire2):
        """Add a connector between wire1 and wire2 in the network."""
        if wire1 == wire2:
            return

        if wire1 > wire2:
            wire1, wire2 = wire2, wire1

        index = 0
        for level in reversed(self):
            if self.checkConflict(level, wire1, wire2):
                break
            index -= 1

        if index == 0:
            self.append([(wire1, wire2)])
        else:
            self[index].append((wire1, wire2))

    def checkConflict(self, level, wire1, wire2):
        """Check if a connection between `wire1` and `wire2` can be 
        added on this `level`."""
        for wires in level:
            if wires[1] >= wire1 and wires[0] <= wire2:
                return True

    def sort(self, values):
        """Sort the values in-place based on the connectors in the network."""
        for level in self:
            for wire1, wire2 in level:
                if values[wire1] > values[wire2]:
                    values[wire1], values[wire2] = values[wire2], values[wire1]

    def assess(self, cases=None):
        """Try to sort the **cases** using the network, return the number of
        misses. If **cases** is None, test all possible cases according to
        the network dimensionality.
        """
        if cases is None:
            cases = product((0, 1), repeat=self.dimension)

        misses = 0
        ordered = [[0]*(self.dimension-i) + [1]*i for i in range(self.dimension+1)]
        for sequence in cases: