Poslať Pia Mar 14, 2008 11:11 pm

Topologické triedenie backtrackom

Výhoda: Netreba nič dokazovať :)
Nevýhoda: O(N!)

  Kód:
package cvicenia;

import sk.upjs.paz.*;

public class L04_Mar13_TopologicalSort {

   public static void main(String[] args) {
      Graph g = new Graph();
      g.setDirected(true);
      g.loadFromFile("/media/USB DISK/skola/graf.txt");
      for (Vertex v : g.getVertices()) {
         v.setValue("order", -1);
      }
      
      if (backtrack(g, 0)) {
         String[] sorted = new String[g.getVertices().size()];
         for (Vertex v : g.getVertices()) {
            sorted[v.getIntValue("order")] = v.getLabel();
         }
         for (String s : sorted) {
            System.out.print(s + ", ");
         }
         System.out.println();
      } else {
         System.out.println("Neda sa topologicky utriedit.");
      }
   }

   
   /**
    * Postupne oznaci vsetky neoznacene vrcholy aktualnym poradim. Ak su uz
    * vsetky vrcholy oznacene, zavola {@link #check}.
    *
    * @param g graf, ktoreho vrcholy maju byt oznacovane
    * @param order poradie, ktorym maju byt vrcholy oznacene
    * @return true, ak niektore oznacenie vedie k platnemu topologickemu utriedeniu
    */
   private static boolean backtrack(Graph g, int order) {
      if (order >= g.getVertices().size()) {
         return check(g);
      } else {
         for (Vertex v : g.getVertices()) {
            if (v.getIntValue("order") == -1) {
               v.setValue("order", order);
               if (backtrack(g, order + 1)) {
                  return true;
               }
               v.setValue("order", -1);
            }
         }
         return false;
      }
   }
   
   
   /**
    * Overi podmienku z definicie topologickeho triedenia.
    *
    * "A topological sort of a dag G = (V, E) is a linear ordering of all its
    * vertices such that if G contains an edge (u, v), then u appears before v
    * in the ordering."
    * - Introduction to Algorithms, Second Edition, The MIT Press 2001
    *
    * @param g graf s oznacenymi poradiami kazdeho vrcholu
    * @return true, ak oznacene poradia tvoria platne topologicke utriedenie
    */
   private static boolean check(Graph g) {
      for (Edge e : g.getEdges()) {
         if (e.getSource().getIntValue("order") > e.getTarget().getIntValue("order")) {
            return false;
         }
      }
      return true;
   }

}
E-mail/Jabber: jan[zavináč]jergus.eu