Nice TWiki > Doc > CodeExamples > GraphParametricTypeExample > GraphClassesExample TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Doc . { Changes | Index | Search | Go }
// compilation unit ColorValue.nice
package graph;

public enum ColorValue {white, gray, black}

// compilation unit HashPropertyMap.nice
package graph;

public class HashPropertyMap<K, V> implements ReadWritePropertyMap<K, V> {
   private HashMap<K, V> data = new HashMap();

   get(key){
      let res = data[key];
      if (res == null){           
        throw new NoSuchElementException();        
      }
      return res;
   }

   set(key, value) = data.put(key, value);
}

public class NullPropertyMap<K, V> extends  HashPropertyMap<K, V> {
   set(key, value) {}
}

// compilation unit Queues.nice
package graph;

public class Queue<T> implements Buffer<T> {
  private LinkedList<T> data = new LinkedList();

  push(value) = data.add(value);

  pop() = data.removeFirst();

  empty() = data.isEmpty();
}


public class MutableQueue<V> implements MutableBuffer<V> {
  private ArrayList<V> vertices_ = new ArrayList();
  private (V,V)->boolean compare;

  push(value) = vertices_.add(value);

   pop() {
      var best = vertices_[0];
      int best_idx = 0;
      for (int i = 1; i < vertices_.size(); ++i){
         let f = compare;
         if ( f(vertices_[i], best) ) {
            best = vertices_[i];
            best_idx = i;
         }
      }
      vertices_.removeAt(best_idx);
      return best;
   }

  empty() = vertices_.isEmpty();

  update(value) {}
}

// compilation unit Relax.nice
package graph;

<Edge,Vertex,Distance, T | Edge <: GraphEdge<Vertex> > 
boolean relax(
   Edge edge,
   ReadablePropertyMap<Edge,Distance> weightMap,
   ReadWritePropertyMap<Vertex,Distance> distance,
   ReadWritePropertyMap<Vertex,Vertex> predecessor,
   (Distance,Distance)->Distance combine,
   (Distance,Distance)->boolean compare
   ){

   let dnew = combine( distance[edge.source], weightMap[edge] );

   if ( compare(dnew, distance[edge.target]) ){
      distance[edge.target] = dnew;
      predecessor[edge.target] = edge.source;   
      return true;
   }
   return false;
}

// compilation unit AdjacencyList.nice
package graph;

public class AdjacencyListEdge<Vertex> 
   implements GraphEdge<Vertex> {
   
   private Vertex source_;
   private Vertex target_;
  
   source() = source_;
  
   target() = target_;
  
   toString() = "edge(" + source_ + " -> " + target_ + ")";
  
   hashCode() = 
       notNull(source_).hashCode() + notNull(target_).hashCode();
  
   equals(AdjacencyListEdge o) = 
       source_.equals(o.source) && target_.equals(o.target);
}


<Vertex> new AdjacencyListEdge(Vertex source, Vertex target) = 
   this(source_: source, target_: target);


public class AdjacencyList<Vertex, Edge | 
   Vertex <: int, int <: Vertex, 
   Edge <: AdjacencyListEdge<int>, AdjacencyListEdge<int> <: Edge > 
   implements VertexListAndIncidenceAndEdgeListGraph<Vertex, Edge> {
   
  private ArrayList<int> vertices_ = new ArrayList();

  vertices() = vertices_.iterator();

  nVertices() = vertices_.size();

     private Map<int, ArrayList<AdjacencyListEdge<int> > > 
  edges_ = new HashMap();
  
     private ArrayList<AdjacencyListEdge<int> > 
  allEdges_ = new ArrayList();

  outEdges(v) = notNull(edges_[v]).iterator();

  outDegree(v) = notNull(edges_[v]).size();

  public void addVertex(Vertex v) {
    vertices_.add(v);
    edges_[v] = new ArrayList();
  }

  public void addEdge(Vertex u, Vertex v) {
    AdjacencyListEdge<Vertex> edge = new AdjacencyListEdge(u,v);
    notNull(edges_[u]).add(edge);
    allEdges_.add(edge);
  }

  edges() =  allEdges_.iterator();
}

// compilation unit PrintingVisitor.nice
package graph;

public interface Visitor<Graph,Vertex,Edge,Dummy | Edge <: GraphEdge<Vertex>> {
   void initializeVertex(Vertex u, Graph g);
   void discoverVertex(Vertex u, Graph g);
   void examineEdge(Edge e, Graph g);
   void treeEdge(Edge e, Graph g);
   void nonTreeEdge(Edge e, Graph g);
   void grayTarget(Edge e, Graph g);
   void blackTarget(Edge e, Graph g);
   void finishVertex(Vertex u, Graph g);
}

public class PrintingVisitor<Graph,Vertex,Edge,Dummy>
      implements Visitor<Graph,Vertex,Edge,Dummy> {

  initializeVertex(u, g) {
    println("initialize " u);
  }

  discoverVertex(u, g) {
    println("discover " u);
  }

  finishVertex(u, g) {
    println("finish " u);
  }

  examineEdge(e, g) {
    println("examine " e);
  }

  treeEdge(e, g) {
    println("tree " e);
  }

  nonTreeEdge(e, g) {
    println("nontree " e);
  }

  grayTarget(e, g) {
    println("gray target " e);
  }

  blackTarget(e, g) {
    println("black target " e);
  }
}
-- IsaacGouy - 07 Jan 2004

Topic GraphClassesExample . { Edit | Attach | Ref-By | Printable | Diffs | r1.7 | > | r1.6 | > | r1.5 | More }
Revision r1.7 - 28 Apr 2005 - 11:50 GMT - TWikiGuest
Parents: WebHome > CodeExamples > GraphParametricTypeExample
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.

Doc.GraphClassesExample moved from Doc.GraphClassesExamples on 08 Jan 2004 - 09:16 by IsaacGouy - put it back