[Java] Topologisches Sortieren

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von osiris, 14. Juni 2010 .

Schlagworte:
  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');
     }
    
    }
     
  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.");
    
     
  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:
    Bild

    Hier der Code, mit dem ich den Graphen erzeugt habe:
    PHP:
    //TEST GRAPH
    = new  boolean [ 7 ][ 7 ];
    for (
    int i  0 a . length i ++){
      for (
    int j  0 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.
     
  4. 15. Juni 2010
    AW: Topologisches Sortieren

    hmn okay, vielen Dank schonmal.

    Schaue heute nochmal darüber.
     
  5. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.