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);
  }
}