Hausübung 5 Aufgabe 7 Graphen

[kechler]

Hallo zusammen,

ich habe mal ne Frage zur oben genannten Aufgabe:

Kann ich davon ausgehen, dass bei get-distance immer nur Weglängen abgefragt werden, ausgehend von einem Knoten der höher im Graphen steht als der Zielknoten?! Mit anderen Worten ist nur so etwas erlaubt:

(get-distance 'E 'G mygraph)

oder soll unsre Prozedur auch diese Abfrage abarbeiten können:
(get-distance 'G 'E mygraph)

Bei der letzten Abfrage ist nämlich das Problem, dass ich durch meinen rekursiven Durchlauf des Listen-Graphen diesen Weg nicht finden kann, da er ja nicht weiss, wenn er bei G angelangt ist, dass über ihm Knoten stehen, die auch zu E führen.

Sonst kann das ganze beliebig ekelhaft werden, da ich mir meinen Graphen nochmal in einen Akkumulator speichern und diesen danach nochmal überprüfen müsste.

Danke im voraus

[MisterD123]

steht doch in der aufgabe, kein weg => -1 zurückgeben, startknoten=zielknoten => 0 zurückgeben, sonst die länge des gefundenen wegs eben.

[Robert]

er meint was anderes .. es gibt in dem gegebenen graphen sowohl einen weg von E nach G wie auch einen Weg von G nach E

dein Programm sollte auch BEIDE Wege finden können.
Wenn dein Prog. das nicht kann ist es falsch. Das Problem was du beschreibst macht dein Programm praktisch nutzlos da es Glückssache ist ob ein Weg gefunden wird oder nicht.

Ein Graph ist durch seine Kanten beschrieben und die beiden Graphen:

(list (make-edge 'A 1 'B)
(make-edge 'B 1 'C)
(make-edge 'C 1 'A))

(list (make-edge 'B 1 'C)
(make-edge 'A 1 'B)
(make-edge 'C 1 'A))

sind gleich .. oder besser gesagt äquivalent. (man spricht auch von isomorph)
ob dein Programm einen weg von A nach C findet ist dann von der Reihenfolge abhängig, das kanns nicht sein da es in dem Graphen von jedem Knoten zu jedem anderen einen Weg gibt.

Schaut mal auf das Bild im Attachment. Alle wege welche ihr per Hand finden könnt in dem Graphen sollte euer Prog auch finden (check aber bitte vorher das ich mich nicht vertan hab beim erstellen der grafik)

[Drudge]

Ist mit Nachbarknoten wirklich Nachbarknoten gemeint oder doch Nachfolgerknoten? Da es sich um einen gerichteten Graphen handelt macht dies ja einen Unterschied.
Nachbarknoten d(V) ist die Vereinigung der Menge der Vorgängerknoten d+(V) und der Menge der Nachfolgerknoten d-(V). So ähnlich habe ich das jedenfalls gelernt.

[Robert]

es ist in der Vorlage für die hausübung ja ein Beispiel gegeben. Dieses Bsp. ist korrekt! - Das sollte deine Frage beantworten

.. ich will euch noch nen Tip geben .. welche art von Nachbarknoten ist denn sinnvoller? ... denkt mal darüber nach wie man die nachbarfunktion so für die nächste Aufgabe nutzen könnte ..

[Pill]

Hey kann mir mal einer helfen? Es geht um die 7.2 Ich bin glaube ich nah dran, nur funktioniert der Akkumulator noch nicht, bzw. ist vielleicht an der falschen Stelle:

(define-struct edge (start length end))

(define mygraph
(list (make-edge 'B 2 'I)
(make-edge 'B 3 'C)
(make-edge 'I 3 'J)
(make-edge 'J 3 'B)
))

(define (neighbors node mygraph)
(cond
[(empty? mygraph) empty]
[(not (symbol? node)) 'kein_Knoten]
[(symbol=? (edge-start (first mygraph)) node) (cond
[(equal? (edge-start (first mygraph)) (edge-end (first mygraph)))(neighbors node (rest mygraph))]
[else(cons (edge-end (first mygraph)) (neighbors node (rest mygraph)))])]
[else (neighbors node (rest mygraph))]
)
)

(define (find-route orgination destination mygraph)
(local(
(define (find-route1 orgination destination mygraph accu)
(cond
[(equal? orgination destination) (list destination)]
[else (local((define possible-route (find-route2 (neighbors orgination mygraph) destination mygraph (cons orgination accu))))
(cond
[(boolean? possible-route) false]
[(contains? orgination accu) 'keine_Route_moeglich]
[else (cons orgination possible-route)]))]
))

(define (find-route2 lo-Os destination mygraph accu)
(cond
[(empty? lo-Os) false]
[else (local((define possible-route (find-route1 (first lo-Os) destination mygraph accu)))
(cond
[(boolean? possible-route) (find-route2 (rest lo-Os) destination mygraph accu)]
[else possible-route]))]
))
)

(find-route1 orgination destination mygraph empty)))

Wär cool, wenn sich einer mal das anschauhen könnte. contains? hab ich jetzt mal weggelassen. Bin ich denn nah drann? Den ganzen rest hab ich schon, es kommt nur noch auf diese Funktion an.

Phil

[MisterD123]

du darfst nur nich abbrechen wenn du ne schleife gefunden hast (da wo du das contains ansetzt). Du musst an der Stelle mit dem nächsten nachbarknoten weiterprobieren. ich denke da ist das problem.

[citta]

Dürfen wir für "reachable?" eigentlich find-route benutzen, oder müssen wir dafür dediziert neuen Code schreiben? Mit find-route wäre das doch zu einfach oder täusche ich mich?

[Robert]

gegenfrage .. würde der neue code wesentlich anders aussehen als der von find route? ... würdest du irgendwas neues dabei lernen? .. falls ja dann schreibs neu .. falls nein dann benutze find route