Nice TWiki > Doc > CodeExamples > GraphParametricTypeExample > GraphClassesExample (r1.5) 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.5 - 25 Jan 2005 - 06:20 GMT - LiYan
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