CriticalPath.java

//Dolocanje kriticne poti v grafu
 
public class CriticalPath {
 
  public double tExp(Vertex a, Vertex c,  DiGraph g) {
    if (a == c) return 0 ;
    else {
      Vertex b ;
      double max = 0, temp;
      Edge e = g.firstEdge(a) ;
      while (e != null) {
         b = g.endPoint(e) ;
         temp = ((Double)e.evalue).doubleValue() + tExp(b,c, g); // rekurzija
         if (temp > max)
             max = temp ;
         e = g.nextEdge(a, e) ;
      }
      return  max ;
    }
  }
 
  class ValueType {
    String name ;
    int inDegree;
    Vertex parent ; // kazalec na predhodnika
    double time ;
    public String toString() {
      return name ;
   }
 
  }
 
  private void prepareGraph(DiGraph g) {
    for (Vertex iv = g.firstVertex() ; iv != null ; iv = g.nextVertex(iv)) {
      ((ValueType)iv.value).inDegree = 0 ;
      ((ValueType)iv.value).time = 0.0 ;
      ((ValueType)iv.value).parent = null ;
    }
    for (Vertex iv = g.firstVertex() ; iv != null ; iv = g.nextVertex(iv))
      for (Edge ie = g.firstEdge(iv) ; ie != null ; ie = g.nextEdge(iv, ie))
        ((ValueType)g.endPoint(ie).value).inDegree ++ ;
  }
 
  public double tDynamic(Vertex a, Vertex c,  DiGraph g) {
    prepareGraph(g) ; // nastavi zacetne vrednosti casa in vhodne stopnje
    //  a - zacetno vozlisce, c - zakljucno vozlisce
    Vertex v, w ; //  trenutno vozlisce in njegov naslednik
    Edge e ; // povezava <v, w>
    List ls = new ListLinked(); // seznam vozlisc, katerih naslednikov
    Object pos ;                                 // se nismo pregledali
    ls.insert(a);
    while (! ls.empty()) {
       pos = ls.first() ; // izberemo lahko poljubno vozlisce
       v = (Vertex)ls.retrieve(pos) ;// vendar je najpreprosteje prvega
       ls.delete(pos);
       e = g.firstEdge(v);
       while (e != null) {
          w = g.endPoint(e);
          if (((ValueType)w.value).time < ((ValueType)v.value).time + ((Double)e.evalue).doubleValue())
                ((ValueType)w.value).time = ((ValueType)v.value).time + ((Double)e.evalue).doubleValue();
          ((ValueType)w.value).inDegree -- ; // ena pot do w ze pregledana
          // ce so pregledane vse poti do w, postane w kandidat za pregledovanje
          if ( ((ValueType)w.value).inDegree == 0)
             ls.insert(w);
          e = g.nextEdge(v, e) ;
        } // while e != null
      } // while ! ls.empty()
      // koncni cas je cas zakljucnega vozlisca
      return ((ValueType)c.value).time ;
    }
 
    public double tPath(Vertex a, Vertex c,  DiGraph g) {
      prepareGraph(g) ; // nastavi zacetne vrednosti casa in vhodne stopnje
      //  a - zacetno vozlisce, c - zakljucno vozlisce
      Vertex v, w ; //  trenutno vozlisce in njegov naslednik
      Edge e ; // povezava <v, w>
      List ls = new ListLinked(); // seznam vozlisc, katerih naslednikov
      Object pos ;                                 // se nismo pregledali
      ls.insert(a);
      while (! ls.empty()) {
         pos = ls.first() ; // izberemo lahko poljubno vozlisce
         v = (Vertex)ls.retrieve(pos) ;// vendar je najpreprosteje prvega
         ls.delete(pos);
         e = g.firstEdge(v);
         while (e != null) {
            w = g.endPoint(e);
            if (((ValueType)w.value).time < ((ValueType)v.value).time + ((Double)e.evalue).doubleValue()) {
              ( (ValueType) w.value).time = ( (ValueType) v.value).time +
                  ( (Double) e.evalue).doubleValue();
              ( (ValueType) w.value).parent = v; // *** dodano ***
            }
           ((ValueType)w.value).inDegree -- ; // ena pot do w ze pregledana
            // ce so pregledane vse poti do w, postane w kandidat za pregledovanje
            if ( ((ValueType)w.value).inDegree == 0)
               ls.insert(w);
            e = g.nextEdge(v, e) ;
          } // while e != null
        } // while ! ls.empty()
 
        // izpis kriticne poti
        w = c ;
        while (w != a) {
          v = ((ValueType)w.value).parent ;
          e = g.firstEdge(v) ;
          while (g.endPoint(e) != w)
            e = g.nextEdge(v, e) ;
          System.out.println("<" + v + ", " + w + ", " + e + ">") ;
          w  = v ;
        }
        // koncni cas je cas zakljucnega vozlisca
        return ((ValueType)c.value).time ;
    }
 
   public VertexAdj criticalVertex() {
     return new VertexAdj(new ValueType()) ;
   }
 
    public static void main(String[] args) {
      CriticalPath cp = new CriticalPath() ;
      DiGraph g = new DiGraphAdj() ;
      // primer: mrezni diagram s slike 54
      VertexAdj va[] = new VertexAdj[7] ;
      for (int i = 0 ; i < va.length ; i++) {
        va[i] = cp.criticalVertex();
        ((ValueType)va[i].value).name = new String(Integer.toString(i)) ;
        g.insertVertex(va[i]);
      }
      g.insertEdge(va[0],va[1]);
      g.firstEdge(va[0]).evalue = new Double(11) ;
      g.insertEdge(va[0],va[2]);
      g.firstEdge(va[0]).evalue = new Double(17) ;
      g.insertEdge(va[0],va[3]);
      g.firstEdge(va[0]).evalue = new Double(27) ;
      g.insertEdge(va[1],va[2]);
      g.firstEdge(va[1]).evalue = new Double(15) ;
      g.insertEdge(va[1],va[3]);
      g.firstEdge(va[1]).evalue = new Double(9) ;
      g.insertEdge(va[2],va[3]);
      g.firstEdge(va[2]).evalue = new Double(13) ;
      g.insertEdge(va[2],va[4]);
      g.firstEdge(va[2]).evalue = new Double(38) ;
      g.insertEdge(va[3],va[5]);
      g.firstEdge(va[3]).evalue = new Double(16) ;
      g.insertEdge(va[3],va[6]);
      g.firstEdge(va[3]).evalue = new Double(3) ;
      g.insertEdge(va[4],va[5]);
      g.firstEdge(va[4]).evalue = new Double(7) ;
      g.insertEdge(va[6],va[5]);
      g.firstEdge(va[6]).evalue = new Double(34) ;
 
      System.out.println("Critical path time (naive):" + cp.tExp(va[0], va[5], g));
      System.out.println("Critical path time (dynamic programming):" + cp.tDynamic(va[0], va[5], g));
      System.out.println("Critical path and time (dynamic programming):" + cp.tPath(va[0], va[5], g));
 
    }
 
}