Graphenproblem - Martins Label Setting Algorithmus

[KingK58]

Guten Tag Community,
ich bin neu im Forum und absoluter Neuling im Programmieren.
Folgendes Problem. Ich habe mich ein wenig übernommen. Als ich meine Masterarbeit angemeldet habe, dachte ich bei meinem Thema nicht, dass ich ein vollständiges Programm allein schreiben muss, aber nun steh ich davor. Ich muss ein Programm schreiben, womit ich einen multikriteriellen kürzesten Weg bestimmen kann. Leider scheitere ich schon am Ansatz. Falls irgendjemand eine Idee hat, so möge er sich bitte bei mir melden. Ich wäre euch sehr sehr dankbar.
Bitte nicht falsch verstehen. Ich verlange keine fertige Lösung. Wenn ich wenigstens mal nen Ansatz finden könnte, hoffe ich mal, dass ich den Rest hin bekomme.
Ich muss den "Martins Label Setting Algorithmus" implementieren. Bei bedarf kann ich hierzu weitere Informationen geben, samt Pseudocode
Lg

[mobby]

Was soll dein Progamm denn überhaupt können? Und wieso entscheidest du dich dabei für die Programmiersprache Python? Soll es eine Oberfläche besitzen usw. Das wäre Infos die benötigt würden, um dich an entsprechenden Tutorials weiterzuleiten.

[KingK58]

Mein Professor beharrt auf Python:)
Folgendes soll es können. Ich muss in einem Graphen einen kürzesten Weg finden.
Hier ist der Pseudocode den ich rein theoretisch implementieren muss: http://s14.directupload.net/images/140716/flh4r4ol.png

eine oberfläche wird erstmal nicht benötigt

[MagBen]

Musst Du den Algorithmus Zeile für Zeile in Python implementieren oder reicht es wenn Du den Algorithmus aus anderen fertigen Lösungen zusammenbaust?
Im letzteren Fall schau Dir mal https://wiki.python.org/moin/PythonGraphApi. Ab der Überschrift "Preliminary ideas" kommt eine Liste mit Python Bibliotheken, die alle was mit Graphen zu tun haben.

Außerdem solltest Du Python lernen, es gibt Leute die meinen das geht an einem Nachmittag, es gibt Leute die meinen das dauert länger: http://norvig.com/21-days.html

[KingK58]

Das Programm muss am Ende einfach funktionieren, egal wie:) Ob ich nun eigene Gedanken einbaue oder eins zu eins implementiere ist mir überlassen.
Ein Tutorial für Python habe ich schon durchgearbeitet. Ich schaue mir heute abend mal die Links an die du mir geschickt hast. Vielen Dank.

[MagBen]

Ein Tutorial für Python habe ich schon durchgearbeitet.

Dann kannst Du hier ja auch Code posten und ganz konkret was fragen. Auf konkrete Fragen gibt's hier meistens bessere Antworten als auf die allgemeinen Fragen.

Ich schaue mir heute abend mal die Links an die du mir geschickt hast.

Ich muss dazu aber noch sagen, dass ich bei einem konkreten Problem auch nur das gemacht habe (Liste durchgeschaut) und dann aber keine der Bibliotheken benutzt habe, sondern es völlig anders realisiert habe (Numpy + Metis).

[pillmuncher]

Das Programm muss am Ende einfach funktionieren, egal wie:) Ob ich nun eigene Gedanken einbaue oder eins zu eins implementiere ist mir überlassen.

MagBens Frage beantwortet das irgendwie nicht. Musst du den Algorithmus selber implementieren oder kannst du eine fertige Funktion einer bestehenden Bibliothek (sofern es die gibt) verwenden?

Außerdem: falls du es selber implementieren musst, hast du denn Probleme damit, den Algorithmus zu verstehen, oder damit, wie man ihn in Python umsetzen würde? Welche Datenstrukturen bzw. welche Operationen auf diesen man verwenden kann/soll? Gibt es irgendwelche Einschränkungen in Bezug auf das Format, in dem Ein- oder Ausgabe vorliegen sollen?

[KingK58]

MagBens Frage beantwortet das irgendwie nicht. Musst du den Algorithmus selber implementieren oder kannst du eine fertige Funktion einer bestehenden Bibliothek (sofern es die gibt) verwenden?

Falls es eine solche Bibliothek geben sollte, so kann ich diese selbstverständlich auch verwenden, habe allerdings noch nichts passendes dazu gefunden.

Außerdem: falls du es selber implementieren musst, hast du denn Probleme damit, den Algorithmus zu verstehen, oder damit, wie man ihn in Python umsetzen würde? Welche Datenstrukturen bzw. welche Operationen auf diesen man verwenden kann/soll? Gibt es irgendwelche Einschränkungen in Bezug auf das Format, in dem Ein- oder Ausgabe vorliegen sollen?

Den Algorithmus an sich hab ich verstanden. Mein größtes Problem liegt darin, wie ich den einzelnen Knoten unterschiedliche Labels zuweisen soll bei Python. Erstmal gehen wir von einem beliebigem Graph mit mehr als einem Kantenattribut aus und versuchen erst einmal dafür ein Programm zu schreiben. Je nach Art des Programms werden wir dann später unser Ein- und Ausgabeformat festlegen.

[pillmuncher]

Den Algorithmus an sich hab ich verstanden.

Ich dagegen irgendwie nicht... oder doch? Zuerst dachte ich, es würden für jeden Knoten nur die Kante zum Vorgängerknoten mit den geringsten Kosten übrigbleiben, dann bräuchte man nur von jedem Knoten aus über den Vorgänger zurückzugehen bis zum Ausgangspunkt. Statt dessen werden die Kosten für alle Kanten entlang aller Pfade berechnet, woraus man sich dann den besten Pfad zusammensetzen kann, indem man sich den jeweils günstigsten Vorgängerknoten heraussucht. Aber, wie gesagt, vielleicht habe ich auch was verkehrt verstanden / programmiert. Hier jedenfalls meine (unoptimierte) Implementierung von Martins' Algorithmus:

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()

Ergebnis:

Code: Alles auswählen

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

Ein paar Anmerkungen zum besseren Verständnis:

my_graph bildet alle Knoten auf Adjazenzlisten ab. Jeder Eintrag dort ist ein Nachfolgeknoten, so dass dies hier die Nachfolgerelation ist:

Code: Alles auswählen

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

Den verlinkten Pseudocode habe ich mehr oder weniger 1:1 umgesetzt, allerdings habe ich ein paar Sachen nicht recht verstanden. Was sind zB. l, k und t? Die habe ich weggelassen und statt dessen zu jedem Label auch den Nachfolgeknoten hinzugefügt.

cost_function() berechnet zu jedem Knoten die Anzahl der Hops vom Ausgangsknoten. Somit ist sie natürlich nur ein Dummy und muss durch was gescheites (multi-kriterielles) ersetzt werden.

Die Funktion dominates(a, b) berechnet, ob a eine pareto-optimale Verbesserung ggü. b darstellt.

Man sollte sich evtl. noch einige bessere Datenstrukturen ausdenken. So, wie es dasteht, ist es wohl nicht optimal performant.