#1 14. Juni 2010 Topologisches Sortieren Hallo, hab ein Problem. Hab 1 Klasse: DirectedGraph, DirectedGraph2 und ein Demo Programm. Wenn ich jetzt im Demo Programm hingehe, mir eine zufällige Matrix erstellen lasse und diese Topologisch sortieren lassen möchte, kommt nur: Sortierung nicht Möglich. Ich bin schon zu fertig, kann mir da vielleicht jemand meine Augen öffnen? Erster Graph Code: public class DirectedGraph{ /*Instanzvariablen*********************************************/ int[][] adjListe = null; /*Konstrukor***************************************************/ public DirectedGraph(boolean[][] a){ if(a.length == 0){ return; } else{ /*pruefen ob Liste quadratisch ist*/ for(int i = 0; i < a.length; i = i + 1){ if (a[i].length != a.length) return; } /*List erstellen*/ adjListe = new int[a.length][]; int[] hilf; int laenge; int x; for(int j = 0; j < a.length; j = j + 1){ laenge = 0; /*Laenge des Arrays:*/ for(int i = 0; i < a[j].length; i = i + 1){ if(a[j][i] == true){ laenge = laenge + 1; } } hilf = new int[laenge]; /*Array befuellen*/ x = 0; for(int i = 0; i < a[j].length; i = i + 1){ if (a[j][i] == true){ hilf[x] = i; x = x + 1; } } adjListe[j] = hilf; } } } /*Methoden*****************************************************/ public int[] adjList(int n){ if (adjListe == null){ return null; } return adjListe[n]; } public int[] path(int from, int to){ if(adjListe == null){ return null; } java.util.LinkedList<Integer> erledigen = new java.util.LinkedList<Integer>(); boolean[] visited = new boolean[adjListe.length]; int[] vorgaenger = new int[adjListe.length]; int[] hilf = {from}; int schritte = 1; int n = 1; /*Anzahl der Schritte, die beim naechsten Knoten bearbeitet werden*/ int k = 0; /*Anzahl der Knoten, die im aktuellen Schritt scho bearbeitet wurden*/ int knoten; int knoten2; erledigen.add(from); visited[from] = true; while(erledigen.size() > 0){ /*Wenn eine Ebene abgeschlossen ist: Wird k wieder auf 0 gesetzt. Wird n gleich der Anzahl der Elemte in der Liste gesetzt.*/ if(k == n){ k = 0; n = erledigen.size(); schritte = schritte + 1; } /*holt ersten Knoten aus der Liste*/ knoten = erledigen.removeFirst(); for(int i = 0; i < adjListe[knoten].length; i = i + 1){ knoten2 = adjListe[knoten][i]; if(visited[knoten2] != true){ visited[knoten2] = true; vorgaenger[knoten2] = knoten; if(knoten2 == to){ hilf = new int[schritte+1]; hilf[hilf.length-1] = to; for (int j = hilf.length-2; j >= 0; j = j - 1){ hilf[j] = vorgaenger[hilf[j+1]]; } return hilf; } erledigen.add(knoten2); } } k = k + 1; } return hilf; } } Zweiter Graph Code: import java.util.*; class DirectedGraph2 extends DirectedGraph { boolean[][] adjMatrix; public DirectedGraph2(boolean[][] a) { super(a); adjMatrix = a; } public int[] topSort() //liefert topologische Sortierung der Knoten 0...n-1 des Graphen, { //gibt es keine solche Sortierung, wird das int-array der Laenge 0 returniert int[] incomingedges = new int[adjListe.length]; LinkedList<Integer> sortiert = new LinkedList<Integer>(); Stack<Integer> noincomingedges = new Stack<Integer>(); int aktNode, adjNode; for (int i=0; i<incomingedges.length; i++) { incomingedges[i] = 0; for (int j=0; j<incomingedges.length; j++) if (adjMatrix[j][i]) incomingedges[i]++; } for (int i=0; i<incomingedges.length; i++) if (incomingedges[i] == 0) noincomingedges.push(i); while (!noincomingedges.isEmpty()) { aktNode = noincomingedges.pop(); sortiert.add(aktNode); for (int i=0; i<adjListe[aktNode].length; i++) { adjNode = adjListe[aktNode][i]; incomingedges[adjNode]--; if (incomingedges[adjNode] == 0) noincomingedges.push(adjNode); } } for (int i=0; i<incomingedges.length; i++) if (incomingedges[i] > 0) return new int[0]; int[] temp = new int[sortiert.size()]; for (int i=0; i<temp.length; i++) temp[i] = sortiert.remove(); return temp; } } Demoprogramm Code: import java.util.Scanner; public class Bsp12{ public static void main(String args[]){ DirectedGraph2 myGraph = null; boolean[][] a = null; char menue; String zeile, x; Scanner myScanner = new Scanner (System.in); do{ System.out.println("Druecke 'r' um einen zufaelligen Graphen zu erstellen."); System.out.println("Druecke 'p' um die Matrix auszudrucken"); System.out.println("Druecke 'l' um eine Adjazenliste auszugeben"); System.out.println("Druecke 's' um eine topologische Sortierung auszugeben"); System.out.println("Druecke 'g' um einen Path anzuzeigen"); System.out.println("Druecke 'f' um das Programm zu beenden"); x = myScanner.next(); menue = x.charAt(0); if(menue == 'r'){ System.out.println("Gib Anzahl der Knoten."); int s = myScanner.nextInt(); System.out.println("Kantenwahrscheinlichkeit eingeben. Zwischen 0 und 1"); double wahrsch = myScanner.nextDouble(); a = new boolean[s][s]; double edge; for (int i = 0; i < a.length; i = i + 1){ for (int j = 0; j < a[i].length; j = j + 1){ edge = Math.random(); if (edge < wahrsch){ a[i][j] = true; } else{ a[i][j] = false; } } } myGraph = new DirectedGraph2(a); System.out.println("Der zufaellige Graph wurde erfolgreich angelegt."); } else if(menue == 'p'){ if(a == null){ System.out.println("Es ist noch kein Graph vorhanden."); continue; } System.out.println("Adjazentenmatrix fuer " + a.length + " Knoten:\n"); if (a.length >= 11) System.out.print(" "); System.out.print(" | "); for(int i = 0; i < a.length; i= i + 1){ System.out.print(i + " "); } System.out.println(); int width = a.length >= 11 ? 4+2*10+3*(a.length-10) : 3+2*a.length; for(int i=0; i<width-1; i++){ System.out.print("-"); } System.out.println(); for(int i = 0; i < a.length; i = i + 1){ if(a.length >= 11) System.out.printf("%2d", i); else System.out.print(i); System.out.print("| "); for(int j = 0; j <a[i].length; j = j + 1){ if(j>=10) System.out.print(" "); if (a[i][j] == true) System.out.print("T "); else System.out.print("F "); } System.out.println(); } System.out.println(); } else if(menue == 's'){ if(a == null){ System.out.println("Es ist noch kein Graph vorhanden."); continue; } int[] sortiert = myGraph.topSort(); System.out.println("topologische Sortierung:"); if (sortiert.length == 0) { System.out.println("Sortierung nicht moeglich."); continue; } for (int i=0; i<sortiert.length-1; i++) System.out.print(sortiert[i] + " > "); System.out.println(sortiert[sortiert.length-1] + "\n"); continue; } else if(menue == 'l'){ if(myGraph == null){ System.out.println("Es ist noch kein Graph vorhanden."); continue; } System.out.println("Welcher Knoten? Knoten muss zwischen 0 und " + (a.length-1) + " liegen."); int s = myScanner.nextInt(); int[] list = myGraph.adjList(s); for(int i = 0; i < list.length - 1; i = i + 1){ System.out.print(list[i] + ","); } if(list.length > 0){ System.out.println(list[list.length-1]); } } else if(menue == 'g'){ if(myGraph == null){ System.out.println("Es ist noch kein Graph vorhanden."); continue; } System.out.println("Welcher Startknoten? Knoten muss zwischen 0 und " + (a.length-1) + " liegen."); int start = myScanner.nextInt(); System.out.println("Welcher Endknoten? Knoten muss zwischen 0 und " + (a.length-1) + " liegen."); int end = myScanner.nextInt(); int[] path = myGraph.path(start, end); System.out.println("\nPfad von " + start + " nach " + end + ":"); for(int i = 0; i < path.length - 1; i= i + 1) System.out.print(path[i] + ","); System.out.println(path[path.length-1]); } else if(menue == 'f'){ return; } }while(menue != 'f'); } } + Multi-Zitat Zitieren
#2 15. Juni 2010 AW: Topologisches Sortieren eines steht fest: deine linkedlist ist leer Code: if (sortiert.length == 0) { System.out.println("Sortierung nicht moeglich."); + Multi-Zitat Zitieren
#3 15. Juni 2010 AW: Topologisches Sortieren Ich hab mal drüber geschaut, es kompiliert und folgendes fiel mir auf, als ich mir den Graph, bzw die Matrix habe printen lassen. Code: | 0 1 2 3 4 5 -------------- 0| F F F T F F 1| F T F F F F 2| T T F F F T 3| F T T T F F 4| T F F F T F 5| F T F F T F Wenn man bei Wikipedia schaut, dann steht dort, dass Graphen nicht sortierbar sind, wenn sie reflexiv sind. Hier würde es aber schon Probleme geben, wenn man sich die STelle 1|1, 3|3 und 4|4 anschaut, da dort jeder Knoten auf sich selbst zeigt. Hier das, was ich meine: Topologische Sortierung – Wikipedia Am besten du konstruierst im Quellcode mal einen Graphen, der sortierbar ist und versuchst es dann damit. Beispiele: Topologische Sortierung – Wikipedia greez //edit: der Beitrag von Calyx ist mehr als sinnfrei... -.- (außerdem ist das Array und nicht die LinkedList leer) //edit2: Okay, ich hatte Recht. Mit dem ersten Graphen von der Wiki Seite geht es: Hier der Code, mit dem ich den Graphen erzeugt habe: PHP: //TEST GRAPH a = new boolean [ 7 ][ 7 ];for ( int i = 0 ; i < a . length ; i ++){ for ( int j = 0 ; j < a [ i ]. length ; j ++){ a [ i ][ j ] = false ; }} a [ 0 ][ 1 ] = true ; a [ 1 ][ 2 ] = true ; a [ 1 ][ 3 ] = true ; a [ 1 ][ 4 ] = true ; a [ 2 ][ 4 ] = true ; a [ 3 ][ 4 ] = true ; a [ 4 ][ 5 ] = true ; a [ 6 ][ 3 ] = true ; //TESTGRAPH ENDE Das war die Ausgabe: Code: Adjazentenmatrix fuer 7 Knoten: | 0 1 2 3 4 5 6 ---------------- 0| F T F F F F F 1| F F T T T F F 2| F F F F T F F 3| F F F F T F F 4| F F F F F T F 5| F F F F F F F 6| F F F T F F F Und das die topologische Sortierung: Code: topologische Sortierung: 6 > 0 > 1 > 3 > 2 > 4 > 5 greez //ein letztes noch: Das bedeutet nun für dich, dass es grundsätzlich richtig funktioniert, nur dürfen keine Schleifen in der Matrix vorkommen, bzw Kreise. Am besten wählst du eine sehr niedrige Kantenwahrscheinlichkeit (vllt 10%), dann kann man sich halbwegs sicher sein, dass zumindest auf der Hauptdiagonalen der Matrix kein true vorkommt. + Multi-Zitat Zitieren
#4 15. Juni 2010 AW: Topologisches Sortieren hmn okay, vielen Dank schonmal. Schaue heute nochmal darüber. + Multi-Zitat Zitieren