Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
[Altklausur - SS15] 5 - DAG
Hallo,
im Folgenden handelt es sich um die Teilaufgabe a).
Ich würde diese Aufgabe mit einem Breitensuche-Algorithmus bearbeiten.
“Für die Tiefensuche bräuchte man einen Markierschritt, der bei dieser Aufgabe nicht realisierbar wäre.”
- Liege ich mit dieser Aussage richtig?
Ist mein Ansatz richtig oder laufe ich Richtung Wand?
Ich vermute, Aufgabe 5 (Seite 8, https://www2.cs.fau.de/teaching/WS2015/AuD/organisation/oldexams/secure/15-07-30_klausur.pdf) ist eigentlich gemeint.
Allgemein zu Tiefensuche in DAGs: Warum markiert man Knoten? Ist das bei einem gerichteten azyklischen Graph überhaupt ein Problem?
Konkret zu der Aufgabe: Hier suchst du doch eigentlich nichts, sondern sollst nur so lange den Graph ablaufen (welche Kanten du nimmst, sagt dir die übergebene HashMap) und zurückgeben, ob du damit bei TRUE oder FALSE landest.
1 „Gefällt mir“
Vielen Dank für den Tipp. Ich habe auch den Titel geändert.
Ich habe hoffentlich alles richtig verstanden und eine Lösung gefunden:
String thisString = this.v;
if(this == TRUE){
return true;
}else if(this == FALSE){
return false;
}
if(tv.contains(thisString)){
tv.remove(thisString);
return this.trueC.eval(tv);
}else if(tv.contains("!" + thisString)){
tv.remove(thisString);
return this.falseC.eval(tv);
}else{
return false;
}“Testcase” laut Angabe (einfach in main einfügen):
BDD a = new BDD(); a.v = "a";
a.trueC = new BDD(); a.trueC.v = "c";
a.trueC.falseC = TRUE;
BDD b = new BDD(); b.v = "b";
a.falseC = new BDD(); a.falseC.v = "c";
b.trueC = FALSE;
b.falseC = TRUE;
a.trueC.trueC = b;
a.falseC.falseC = b;
a.falseC.trueC = FALSE;
HashSet<String> test = new HashSet<String>();
test.add("!a");
test.add("!b");
test.add("c");
System.out.println("ERGEBNIS: " + a.eval(test));Falls der Code richtig sein sollte, darf er gerne als Musterlösung bei den Altklausuren gepostet werden.
Hast du auch noch einen Tipp für die b).
Ich habe folgendes:
if(p.contains(this)){
return true;
}
p.add(this);
if(this.trueC != null){
return this.trueC.isDAG(p);
}
if(this.falseC != null){
return this.falseC.isDAG(p);
}
return false;Das funktioniert natürlich nicht, weil ich erst das falseC aufrufe, wenn trueC schon durchgelaufen ist.
Normalerweise würde ich das ja in einer Schleife schreiben, nur leider weiß ich nicht wie ich das mit den Nachfolgern löse,
da diese hier trueC und falseC sind und nicht in einem Array o.ä.
Ich würde ggf. “==” durch equals ersetzen, in denen du nicht etwas auf null prüfst. Wobei hier sollte “==” und equals keine Unterschiede liefern.
Warum möchtest du Elemente aus dem übergebenen HashSet löschen? Die Variablenbelegung ändert sich doch nicht. Außerdem schließt die Aufgabenstellung nicht aus, dass sie selbe Variable von unterschiedlichen Knoten ausgewertet wird.
Warum ein Ausrufezeichen vorne an den String anhängen?
„!v“ ist keine Variable.
Sieht doch nicht schlecht aus, nur sind soweit ich das auf die Schnelle sehe true und false konsequent vertauscht. Zum ersten if: Wenn du den Knoten im aktuellen Durchlauf schon mal gesehen hast, hast du doch einen Zyklus gefunden und es ist kein DAG.
Wenn es dir hilft, dass es ein Array ist, dann bau dir doch eins mit [m]new BDD {this.trueC, this.falseC}[/m]. Wie würdest du es damit lösen? Danach kannst du dir überlegen wie du dieses Array wieder los wirst.
Warum? Hier wird kein [m]equals[/m] implementiert, damit verhält es sich genau wie [m]==[/m]. Und die dass [m]TRUE[/m] und [m]FALSE[/m] als [m]static final[/m] deklariert sind, ist doch ein starker Hinweis dafür, dass es jeweils sowieso nur ein Objekt davon gibt.
Die Implementierung von AverageGuy hat meines Erachtens noch einen weiteren Fehler. Wenn der trueChild mal nicht null ist, wird sofort etwas zurückgegeben. Der falseChild-Zweig wird damit gar nicht erst durchlaufen. Ist also erst im falseChild-Zweig ein Kreis vorhanden, so wird dieser nicht detektiert. Den Codeabschnitt
if(this.trueC != null){
return this.trueC.isDAG(p);
}sollte man daher imo. durch
if(this.trueC != null && !this.trueC.isDAG(p)){
return false;
}ersetzen.
@izibi
Teilaufgabe a): habe ich anscheinend falsch verstanden. Ich bin von dieser Art der Variablenbelegung ausgegangen: z.B. {“a”, “!b”, “c”}.
Teilaufgabe b): Besser als das bekomme ich es nicht hin. Ich glaube ich bin an den Grenzen meiner Fähigkeiten angelangt…
Ich weiß einfach nicht, wie ich es schaffe, dass ich nicht nur die trueC’s durchlaufe.
Ich habe den Tiefensuche-Code eigentlich 1:1 aus den Folien genommen und auf mein Problem angewandt: Ohne Erfolg wie du siehst.
if(p.contains(this)){
return false;
}
p.add(this);
BDD[] run = new BDD[]{this.trueC, this.falseC};
for(BDD child : run){
if(child == null){
continue;
}
if(!p.contains(child)){
return child.isDAG(p);
}else{
return false;
}
}
return true;Ich bin mit der Aufgabe / Aufgabenstellung auch nicht glücklich, mein Ansatz zur a):
(nur eine Skizze)
boolean eval(HashSet<String> tv) {
if (tv.isEmpty()) {
return true;
} else {
if (tv.contains(this.v)) {
tv.remove(this.v);
return this.eval(tv);
} else {
boolean t1 = false;
boolean t2 = false;
if (trueC != null) {
t1 = trueC.eval(tv);
}
if (falseC != null) {
t2 = falseC.eval(tv);
}
return t1 || t2;
}
}
}Wann ist der Teilgraph, der vom aktuellen Knoten ausgeht, denn azyklisch? Zum einen darfst du den aktuellen Knoten nicht schon mal besucht haben (das passt in deinem Code), zum anderen darf weder das true-Kind, noch das false-Kind Zyklen enthalten, oder anders ausgedrückt: beide Kinder müssen selbst DAGs sein. Also eigentlich, willst du da etwas wie [m]return trueC.isDAG() && falseC.isDAG();[/m], nur dass es auch [m]null[/m] sein könnte.
Wenn du grob bei deinem Code mit der Schleife bleiben willst oder den Code später so umschreiben willst, dass für jedes Kind ein if da steht: du willst nur returnen, wenn dein Kind kein DAG ist, dann weißt du sicher, dass der komplette Graph kein DAG ist. Sonst willst du noch das andere Kind überprüfen.
(Im wesentlichen steht der Code dafür ja sowieso schon im Post von ic97usop.)
Dieses if ist redundant, das fragt genau ab, was [m]child.isDAG(p)[/m] dann gleich als erstes nochmal prüft.
Das sieht nach einem Versuch aus, rekursiv auf dem übergebenen HashSet zu arbeiten. Das ist aber doch die Variablenbelegung, die über die komplette Auswertung konstant bleibt. Es darf daraus nichts entfernt werden. Das hier (Code ungetestet und nur schnell hingeschrieben) ist ein gültiger BDD (niemand sagt, dass eine Variable nicht doppelt ausgewertet werden darf):
BDD a = new BDD(), b = new BDD();
a.v = "x";
a.trueC = b;
a.falseC = b;
b.v = "x";
b.trueC = BDD.TRUE;
b.falseC = BDD.FALSE;Also ein Knoten, der x auswertet und unabhängig von dessen Wert in einen zweiten Knoten übergeht, der nochmal x auswertet und dann in TRUE oder FALSE geht. Wenn [m]a.eval(tv)[/m] nun ein [m]tv.remove(„x“);[/m] macht, verfälscht das das Ergebnis.
Bei Aufgabe a) soll Rekursion nur auf dem BDD betrieben werden und die einzige Methode, die man vom übergebenen HashSet braucht, ist contains.
Da ich mich beim Lernen auf DSP auch mal ablenken will, habe ich mich auch mal an der Aufgabe versucht.
import java.util.*;
public class BDD {
static final BDD TRUE = new BDD();
static final BDD FALSE = new BDD();
BDD trueC, falseC;
String v;
/*************************************************************
* Task 5.a: Function to evaluate a boolean expression *
* @param tv: given expression *
* @return true iff the given graph satisfies the expression *
*************************************************************/
boolean eval(HashSet<String> tv){
/** Sanity check that the hashset is not null. **/
if(tv == null){
return false;
}
/** Base cases **/
if(this.equals(TRUE)){
return true;
}
if(this.equals(FALSE)){
return false;
}
/**********************************************
* Recursion cases. *
* Please note that some sanity checks might *
* be removed due to assumptions of the task. *
**********************************************/
if(!tv.contains(v) && this.falseC != null && this.falseC.eval(tv)){
return true;
}
if(!tv.contains('!' + v) && this.trueC != null && this.trueC.eval(tv)){
return true;
}
return false;
}
/*********************************************
* Task 5.b: A recursive function to check *
* whether the given graph is a DAG *
* @return true iff the given graph is a DAG *
*********************************************/
boolean isDAG(){
return isDAG(new HashSet<BDD>());
}
/************************************************
* Helping function for task 5.b *
* @param p set of visited nodes *
* @return false iff the graph contains a cycle *
************************************************/
boolean isDAG(HashSet<BDD> p){
/** Just a sanity check since this function is not private. **/
if(p == null){
return false;
}
/** Base cases. **/
if(this.equals(TRUE) || this.equals(FALSE)){
return true;
}
if(p.contains(this)){
return false;
}
/** Mark the current element as visited. **/
p.add(this);
/** Recursion cases. **/
if(this.trueC != null && !this.trueC.isDAG(p)){
return false;
}
if(this.falseC != null && !this.falseC.isDAG(p)){
return false;
}
/************************************************
* Now mark the current element as unvisited *
* to ensure that we still can revisit it later *
* from a different tree branch. *
************************************************/
p.remove(this);
return true;
}
/** Tests for task 5.a **/
public static void testEval1(){
BDD a = new BDD();
a.v = "a";
BDD b = new BDD();
b.v = "b";
BDD c1 = new BDD();
c1.v = "c";
BDD c2 = new BDD();
c2.v = "c";
a.trueC = c1;
a.falseC = c2;
c1.trueC = b;
c1.falseC = TRUE;
c2.trueC = FALSE;
c2.falseC = b;
b.trueC = FALSE;
b.falseC = TRUE;
HashSet<String> tv = new HashSet<String>();
tv.add("a");
tv.add("!b");
tv.add("c");
assert a.eval(tv) : "Error at eval test 1";
System.out.println("Eval test 1: OK");
}
public static void testEval2(){
BDD a = new BDD();
a.v = "x";
BDD b = new BDD();
b.v = "x";
a.trueC = b;
a.falseC = b;
b.trueC = TRUE;
b.falseC = FALSE;
HashSet<String> tv = new HashSet<String>();
tv.add("!x");
assert !a.eval(tv) : "Error at eval test 2";
System.out.println("Eval test 2: OK");
}
/** Tests for task 5.b **/
public static void testDAG1(){
BDD a = new BDD();
a.v = "a";
BDD b = new BDD();
b.v = "b";
BDD c1 = new BDD();
c1.v = "c";
BDD c2 = new BDD();
c2.v = "c";
a.trueC = c1;
a.falseC = c2;
c1.trueC = b;
c1.falseC = TRUE;
c2.trueC = FALSE;
c2.falseC = b;
b.trueC = FALSE;
b.falseC = TRUE;
assert a.isDAG() : "Error at DAG test 1.";
System.out.println("DAG test 1: OK");
}
public static void testDAG2(){
BDD a = new BDD();
a.v = "a";
a.trueC = a;
a.falseC = FALSE;
assert !a.isDAG() : "Error at DAG test 2.";
System.out.println("DAG test 2: OK");
}
/***************************************
* Main function for testing purposes. *
* Do not forget to enable assertions. *
* @param args not needed here *
***************************************/
public static void main(String[] args){
testEval1();
testEval2();
testDAG1();
testDAG2();
}
}@ic97usop, damit läuft du nur dann weiter, wenn in tv eine Variable der Form “v” oder “!”+v auftaucht, aber nicht bis zu einem Endknoten hier TRUE oder FALSE gekommen bist, die du auf jeden Fall erreichen musst.
Dein Code ist fast richtig und die Aufgabe ist eig. simpler: if(tv.contains(this.v)) nehme die true Kante, sonst nehme die andere Kante. (natürlich nur, insofern eine Kante existiert), rekursion
Ist bspw. dein HashSet leer würdest du sicher immer die false Kante nehmen.
Ich habe meinen Code etwas geändert. Allerdings muss man imo. beide Zweige abprüfen, wenn weder v noch !v in tv enthalten sind.
Wenn tv.contains(v) => nimm nur trueC
Wenn tv.contains(!v) => nimm nur falseC
Sonst => nimm beides
Ist die Hashset außerdem leer, verstehe ich aus der Aufgabenstellung nicht, ob die Bedingung „wahr“ oder „falsch“ ist. Ich habe das für den Fall „wahr“ implementiert.
Wenn das HashSet leer ist, haben alle Variablen den Wert false.
([m]tv.contains(„v“)[/m] => v = true) und ([m]!tv.contains(„v“)[/m] => v = false)
Aber gut, wenn wir schon anfangen, mehr oder weniger richtigen Code zu posten (wieder mal ungetestet, so wie man das in der Klausur halt auch hätte, sollte aber passen):
boolean eval(HashSet<String> tv) {
if (this == BDD.TRUE) return true;
if (this == BDD.FALSE) return false;
return tv.contains(v) ? trueC.eval(tv) : falseC.eval(tv);
}
boolean isDAG(HashSet<BDD> p) {
if (p.contains(this)) return false;
p.add(this);
boolean ret = (trueC == null || trueC.isDAG(p)) && (falseC == null || falseC.isDAG(p));
p.remove(this);
return ret;
}
1 „Gefällt mir“
@izibi: Dein Code erkennt leider auch beim Graphen “b ← a ← c” den Knoten a als Wurzel eines DAGs an.
[code=java]public static void main (String[] args) throws java.lang.Exception
{
// b=TRUE ← a ← c
// a is not the root of the DAG!
BDD a = new BDD();
BDD b = BDD.TRUE;
BDD c = new BDD();
c.trueC = a;
a.v = "a";
c.v = "c";
System.out.println("b=TRUE <-- a <-- c: failed? " + (a.isDAG() ? "yes" : "no"));
}[/code]
→ http://ideone.com/3uvNOr
Ich wüsste nicht, wie man prüfen soll, ob irgendein Objekt auf einen zeigt, wenn man keine Liste von allen Knoten besitzt.
[quote=Marcel[Inf]]
@izibi: Dein Code erkennt leider auch beim Graphen “b ← a ← c” den Knoten a als Wurzel eines DAGs an.
[/quote]
a ist hier auch Wurzel eines DAGs, nämlich von b ← a. Die Aufgabenstellung nimmt ja Knotentypen als Graphtypen. Somit wird implizit ein Graph von allen Knoten aufgespannt, die von seinem definierenden Knoten (in dem Fall a) aus sichtbar sind (in dem Fall a und b).
[quote=bulsa:1457967662]a ist hier auch Wurzel eines DAGs, nämlich von b ← a. Die Aufgabenstellung nimmt ja Knotentypen als Graphtypen. Somit wird implizit ein Graph von allen Knoten aufgespannt, die von seinem definierenden Knoten (in dem Fall a) aus sichtbar sind (in dem Fall a und b).
[/quote]
Klingt logisch, Danke 
Interessehalber würde mich interessieren, wie denn eine iterative Variante von isDAG() (also iterative Tiefensuche + Zyklenerkennung) aussieht.
In der rekursiven Fassung hat man in “p” die Knoten gespeichert, die sich auf dem aktuellen Pfad befindet haben.
Beim Aufstieg entfernte man dann immer wieder den eigenen Knoten. Wie kann ich in der iterateiven Version feststellen, wann ich aufsteige?
[code=java]boolean isDAG(HashSet p){
Deque stack = new ArrayDeque<>();
Set visited = new HashSet<>();
visited.add(this);
stack.push(this);
while (!stack.isEmpty()) {
BDD cur = stack.pop();
if (cur.trueC != null && !visited.contains(cur.trueC)) {
stack.push(cur.trueC);
visited.add(cur.trueC);
}
if (cur.falseC != null && !visited.contains(cur.falseC)) {
stack.push(cur.falseC);
visited.add(cur.falseC);
}
}
return true;
}[/code]