Das deutsche Python-Forum

Code: Alles auswählen

from collections import namedtuple
from itertools import groupby
from operator import itemgetter


Label = namedtuple('Label', 'foo bar source target')


def length(labels, s):
    return 1 + length(labels, labels[s].source) if s else 0


def cost_function(labels, s, t):
    return Label(foo=length(labels, s), bar=0, source=s, target=t)


def dominates(a, b):
    a = a[:-2]
    b = b[:-2]
    return a != b and all(m <= n for m, n in zip(a, b))


def multiobjective_best_paths(digraph, calculate_cost, start):
    labels = {start: Label(foo=0, bar=0, source=0, target=start)}
    temporary = {labels[start]}
    permanent = set()
    while temporary:
        smallest = min(temporary)
        temporary.remove(smallest)
        permanent.add(smallest)
        source = smallest.target
        for target in digraph[source]:
            labels[target] = cost = calculate_cost(labels, source, target)
            temporary.add(cost)
            for label in list(temporary):
                if label.target == target and dominates(cost, label):
                    temporary.remove(label)
            if any(dominates(label, cost) for label in temporary
                    if label.target == target):
                temporary.remove(cost)
    sort_key = itemgetter(3, 0)
    group_key = itemgetter(3)
    edges = {k: next(vs).source for k, vs in groupby(
                sorted(permanent, key=sort_key), key=group_key)}
    for k in edges:
        path = [k]
        while path[-1] != start:
            path.append(edges[k])
            k = edges[k]
        yield path[::-1]


def main():

    my_graph = {
        1: {2, 4, 5},
        2: {3},
        3: {4, 5},
        4: {},
        5: {}
    }

    for path in multiobjective_best_paths(my_graph, cost_function, 1):
        print(path)


if __name__ == '__main__':
    main()

Code: Alles auswählen

[1]
[1, 2]
[1, 2, 3]
[1, 4]
[1, 5]

Code: Alles auswählen

1 --> 2
1 --> 4
1 --> 5
2 --> 3
3 --> 4
3 --> 5