class Property:
    def __init__(self, value):
        self._value = value
    
    def getValue(self):
        return self._value
    
    def setValue(self, value):
        self._value = value

    def getOtherEnds(self):
        if self._value is not None:
            return (self._value,)
        else:
            return ()

class AbstractAssociation:
    def __init__(self, object):
        self._object = object
    
    def object(self):
        return self._object

class SingleBidiAssociation(AbstractAssociation):
    def __init__(self, object):
        AbstractAssociation.__init__(self, object)
        self._other = None
    
    def getOtherAssociation(self):
        return self._other
    
    def getOtherEnd(self):
        x = self.getOtherAssociation()
        if x is None:
            return None
        return x.object()
    
    def unregister(self, other):
        if self._other is not None:
            self._other = None
    
    def register(self, other):
        if self._other is not None:
            self._other.unregister(self)
            self._other = other
        elif other is not None:
            self._other = other
    
    def connectTo(self, other):
        if other is not self._other:
            self.register(other)
            if other is not None:
                other.register(self)

class WiredSingleAssociation(SingleBidiAssociation):
    def __init__(self, otherEnd, object):
        SingleBidiAssociation.__init__(self, object)
        self.otherEnd = otherEnd
    
    def connect(self, to):
        self.connectTo(getattr(to, self.otherEnd))

class AbstractMultiAssociation(AbstractAssociation):
    pass

class MultiAssociationSet(AbstractMultiAssociation):
    def __init__(self, object):
        AbstractMultiAssociation.__init__(self, object)
        self._elements = set()

    def register(self, element):
        self._elements.add(element)

    def getOtherEnds(self):
        # Does not remove duplicates
        for e in self._elements:
            yield e.object()

class XAssociation:
    def __init__(self, edge, weightedEdge, object):
        self.edge = edge
        self.weightedEdge = weightedEdge
        self.object = object
    
    def edges(self):
        return getattr(self.object, self.edge).getOtherEnds()
    
    def otherEnd(self, edge):
        return getattr(edge, self.weightedEdge).otherEnd(self.object)
    
    def weight(self, edge):
        return getattr(edge, self.weightedEdge).getWeight()

    def getOtherEnds(self):
        edgeNodes = getattr(self.object, self.edge).getOtherEnds()
        for e in edgeNodes:
            edge = getattr(e, self.weightedEdge)
            yield edge.otherEnd(self.object)

class Graph:
    def directSuccessors(self):
        return self.directSuccessorsOf(self.object())
    
    def successors(self):
        result = set()
        self.accumulateSuccessors(self.object(), result)
        return result

    def accumulateSuccessors(self, object, accumulator):
        for succ in self.directSuccessorsOf(object):
            if succ not in accumulator:
                accumulator.add(succ)
                self.accumulateSuccessors(succ, accumulator)
    
    def predecessorOf(self, object):
        return object in self.successors()

class WiredGraph(Graph):
    def __init__(self, connections, object):
        self.connections = connections
        self._object = object
    
    def object(self):
        return self._object
    
    def directSuccessorsOf(self, object):
        for conn in self.connections:
            # Note: does not avoid duplicates
            for succ in getattr(object, conn).getOtherEnds():
                yield succ

class WeightedAssociation:
    def __init__(self, start, end, weight, edge):
        self.start = start
        self.end = end
        self.weight = weight
        self.edge = edge
    
    def getWeight(self):
        return getattr(self.edge, self.weight).getValue()
    
    def otherEnd(self, vertex):
        startVertex = getattr(self.edge, self.start).getOtherEnd()
        if startVertex is vertex:
            return getattr(self.edge, self.end).getOtherEnd()
        else:
            return startVertex

class WeightedDigraph(WiredGraph):
    def __init__(self, outgoing, object):
        WiredGraph.__init__(self, outgoing, object)
        self.outgoing = outgoing
    
    def shortestDistanceTo(self, targetVertex):
        import heapq
        import itertools
        done = set()
        distances = []
        counter = itertools.count(0)
        def push(distance, vertex):
            heapq.heappush(distances, (distance, next(counter), vertex))
        def pop():
            distance, _, vertex = heapq.heappop(distances)
            return distance, vertex
        push(0, self.object())
        while distances:
            distance, vertex = pop()
            if vertex is targetVertex:
                return distance
            if vertex not in done:
                done.add(vertex)
                for outAssocName in self.outgoing:
                    outAssoc = getattr(vertex, outAssocName)
                    for edge in outAssoc.edges():
                        target = outAssoc.otherEnd(edge)
                        if target not in done:
                            newDistance = distance + outAssoc.weight(edge)
                            push(newDistance, target)

class Subobject:
    def __init__(self, info, klass):
        self.info, self.klass = info, klass

def subobject(**info):
    return lambda klass: Subobject(info, klass)

def withSubobjects(outerClass):
    def addSubobject(subobjectName, info, subobjectClass):
        static_args = tuple(info.get('args', []))
        overrides, exports = info.get('overrides', {}), info.get('exports', {})
        def mk(self, *args):
            subobj = subobjectClass(*(static_args + args))
            subobj.outer = self
            def delegator(name):
                return lambda *args, **namedArgs: getattr(self, name)(*args, **namedArgs)
            for override in overrides:
                subobj.__dict__[overrides[override]] = delegator(override)
            for export in exports:
                subobj.__dict__[exports[export]] = delegator(export)
            self.__dict__[subobjectName] = subobj
        setattr(outerClass, "mk_" + subobjectName, mk)
        def aliasDelegator(target):
            return lambda self, *args, **namedArgs: \
                getattr(subobjectClass, target)(getattr(self, subobjectName), *args, **namedArgs)
        for export in exports:
            setattr(outerClass, export, aliasDelegator(exports[export]))
    for name, value in outerClass.__dict__.items():
        if type(value) is Subobject:
            delattr(outerClass, name)
            addSubobject(name, value.info, value.klass)
    return outerClass

@withSubobjects
class City:
    @subobject(exports={'getName': 'getValue'})
    class name(Property):
        pass
    
    @subobject()
    class roads(MultiAssociationSet):
        pass
    
    @subobject(args=['roads', 'weightedEdge'])
    class cityToCity(XAssociation):
        pass
    
    @subobject(args=[['cityToCity']], exports={'reachables': 'successors', 'canReach': 'predecessorOf', 'distanceTo': 'shortestDistanceTo'})
    class graph(WeightedDigraph):
        pass
    
    def __init__(self, myName):
        self.mk_name(myName)
        self.mk_roads(self)
        self.mk_cityToCity(self)
        self.mk_graph(self)

@withSubobjects
class Road:
    @subobject(exports={'getLength': 'getValue'})
    class length(Property):
        pass
    
    @subobject(
        args=['roads'],
        exports={'setStart': 'connect', 'getStart': 'getOtherEnd'})
    class start(WiredSingleAssociation):
        pass
    
    @subobject(
        args=['roads'],
        exports={'setEnd': 'connect', 'getEnd': 'getOtherEnd'})
    class end(WiredSingleAssociation):
        pass
    
    @subobject(args=['start', 'end', 'length'])
    class weightedEdge(WeightedAssociation):
        pass

    def __init__(self, length, start, end):
        self.mk_length(length)
        self.mk_start(self)
        self.mk_end(self)
        self.mk_weightedEdge(self)
        self.setStart(start)
        self.setEnd(end)

leuven = City("Leuven")
lille = City("Lille")
brussels = City("Brussels")
antwerp = City("Antwerp")
dendermonde = City("Dendermonde")
mechelen = City("Mechelen")
lokeren = City("Lokeren")
liege = City("Liege")
namur = City("Namur")
charleroi = City("Charleroi")
ghent = City("Ghent")
ninove = City("Ninove")
oudenaarde = City("Oudenaarde")
kortrijk = City("Kortrijk")
Road(16, brussels, leuven)
Road(40, leuven, liege)
Road(40, leuven, namur)
Road(30, leuven, mechelen)
Road(25, liege, namur)
Road(10, brussels, mechelen)
Road(25, brussels, dendermonde)
Road(20, brussels, ghent)
Road(20, brussels, ninove)
Road(50, brussels, lille)
Road(30, brussels, charleroi)
Road(25, namur, charleroi)
Road(60, lille, charleroi)
Road(35, oudenaarde, ninove)
Road(25, oudenaarde, ghent)
Road(30, oudenaarde, kortrijk)
Road(15, lille, kortrijk)
Road(25, ghent, kortrijk)
Road(10, ghent, lokeren)
Road(30, antwerp, lokeren)
Road(15, dendermonde, lokeren)
Road(10, antwerp, mechelen)
assert leuven.canReach(lille)
assert lille.canReach(leuven)
assert leuven.distanceTo(lille) == 66
assert antwerp.distanceTo(liege) == 76
assert lille.distanceTo(liege) == 106
assert brussels.distanceTo(oudenaarde) == 45
assert lokeren.distanceTo(ninove) == 50
print("Tests succeeded.")