Topologisches Sortieren nach Präferenzen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Topologisches Sortieren nach Präferenzen

    Quellcode

    1. import java.util.*;
    2. import fhw.ADSTool;
    4. /**
    5. * A1: Topologisches Sortieren
    6. * @author Torben Brodt & Marco May
    7. *
    8. */
    9. public class A1 {
    11. enum Status {start, stop};
    13. /**
    14. * Mainmethode
    15. * @param args-Kommandozeilenparameter
    16. */
    17. public static void main(String[] args) {
    18. Graph g = new Graph();
    19. String[] zahlen = ADSTool.readStringArray(args.length == 0 ? "u12a1simple.dat" : args[0]);
    21. for (int i = 0; i < zahlen.length - 1; i += 2) {
    22. if (!g.containsNode(zahlen[i]))
    23. g.addNode(zahlen[i]);
    25. if (!g.containsNode(zahlen[i + 1]))
    26. g.addNode(zahlen[i + 1]);
    28. if (!g.containsEdge(zahlen[i], zahlen[i + 1]))
    29. g.addEdge(zahlen[i], zahlen[i + 1]);
    30. }
    32. //g.show();
    33. List<String> llist = new LinkedList<String>();
    35. if (acyclic(g, llist)){ //Graph ist nicht zyklisch und f�llt Liste
    36. if (check(zahlen, llist)) { //wenn Liste identisch mit Vorgabe
    37. for (ListIterator it = llist.listIterator(); it.hasNext();)
    38. System.out.print(it.next()+" < ");
    39. }
    40. }
    41. else //Graph ist zyklisch
    42. System.out.println("Zyklus");
    43. }
    45. /**
    46. * Test den Graphen auf einen Zyklus (aus der Vorlesung)
    47. * @param g -Der Graph
    48. * @param llist-Liste
    49. */
    50. static boolean acyclic(Graph g, List<String> llist) {
    51. Map<String, Status> visited = new TreeMap<String, Status>();
    52. for (Iterator<String> it = g.nodeIterator(); it.hasNext();) {
    53. String n = it.next();
    54. if (!visited.containsKey(n))
    55. if (!acyclicRek(g, n, visited, llist))
    56. return false;
    57. }
    58. return true;
    59. }
    61. /**
    62. * Prueft ob unsere Liste richtig ist
    63. * @param objects - Zu pruefende Objekte
    64. * @param llist -Liste, die wir erstellt haben
    65. * @return true, gdw. Check erfolgreich war
    66. */
    67. static boolean check(String[] objects, List<String> llist) {
    68. for(int i=0; i<objects.length-1; i+=2) {
    69. String left = objects[i];
    70. String right = objects[i+1];
    71. boolean oK = false;
    72. boolean leftNumberFound = false; //Bevor man die Liste durchgeht
    74. //9 & 2 sollen gefunden werden
    76. for (ListIterator<String> it = llist.listIterator(); it.hasNext();){
    77. String suche = it.next();
    78. if(suche.equals(left)) {
    79. //Suche erst nach der linken Zahl
    80. //9 gefunden. Suche rechts davon nach 2
    81. leftNumberFound = true; //Linke Zahl gefunden
    82. }
    84. if(leftNumberFound == true && suche.equals(right)) {
    85. // Wenn die linke Zahl schon gefunden wurde,
    86. // dann suche nach der rechten Zahl
    87. // 2 rechts davon gefunden - alles i.O.
    88. oK = true; // In diesem Durchlauf ist also alles OK
    89. break;
    90. }
    91. }
    92. if(oK == false)
    93. return false;
    94. }
    95. return true;
    96. }
    97. /**
    98. * Rekursive Hilfsfunktion fuer acyclic()
    99. * @param g - zu pruefender Graph
    100. * @param node -aktueller Knoten
    101. * @param visited -Besuchte Objekte
    102. * @param llist -Liste der Zahlen
    103. * @return true, gdw. Rek. erfolgreich
    104. */
    105. @SuppressWarnings("unchecked")
    106. static boolean acyclicRek(Graph g, String node, Map<String, Status> visited, List<String> llist) {
    107. visited.put(node, Status.start); // Start Knoten expandieren
    108. for (Iterator<String> it = g.edgeIterator(node); it.hasNext();) {
    109. String expanded = it.next();
    110. if (visited.containsKey(expanded)) {
    111. if (visited.get(expanded).equals(Status.start)) // Back-Edge,
    112. // Zyklus
    113. return false; // else Cross-Edge, ok
    114. } else { // !visited.containsKey(expanded)
    115. visited.put(expanded, Status.start);
    116. if (!acyclicRek(g, expanded, visited, llist)) // rekursiv Zyklus
    117. // erkannt
    118. return false;
    119. }
    120. }
    121. visited.put(node, Status.stop); // Stop Knoten expandieren
    122. llist.add(0,node);
    123. return true;
    124. }
    125. }
    Alles anzeigen
    Dateien

    • GraphException.java

      (297 Byte, 296 mal heruntergeladen, zuletzt: )

    • Graph.java

      (6,81 kB, 415 mal heruntergeladen, zuletzt: )