展示架 生物反应器 笔记本电脑 成人用品 翻译 鲜花 移民 翻译公司 租房 游戏 游戏下载 摸屏 壁纸 服务器 爱滋病 办公自动化 出国 短信 干燥设备 交友 聊天 门禁 内衣 升降机 视频 写真 仪器仪表 移动存储 音乐 自考 算命 惠普 诺基亚 体育彩票 网页制作 前列腺 索尼 宠物 大连 电力 福利彩票 个人主页 广告公司 国际贸易 会计 计算机等级考试 交通 宽带 免费空间 农业 企业文化 人才 人才网 设计 手机报价 图书 网络 网络游戏 物业管理 西门子 小灵通 幼儿教育 幼儿园 娱乐 注册会计师 财务 财务管理 出国留学 电脑培训 多媒体 翻译软件 飞机票 购物 管理 婚纱摄影 激光 计算机培训 空间 律师 律师事务所 贸易 美容美发 模型 纳米 商标 数据库 通讯 网络安全 项目管理 鞋 雅思 英语培训 园林 招标 纸 中医

皮革 床上用品 英语培训 优盘 油画 游戏机 有线电视 幼教 刻录 口吃 口罩 快餐 矿泉水 篮球鞋 浪潮 理财 粮食 猎头 猎头公司 旅游景点 玫瑰 美容院 棉花 民办大学 钱币 桥梁 情报 求职招聘 人才交流 软件公司 扫描 扫描仪 山水 商务网 商行 商业 上海房产 上海租房 上市 少儿英语 设计公司 民歌 玉器 服装辅料 元件 民谣 社保 社会保障 民族音乐 园艺 市场研究 灯箱 远程控制 明信片 社会调查 申请邮箱 牡丹 云南旅游 灯饰 保健食品 生日贺卡 生物工程 在线歌曲 霓虹灯 失眠 农药 造价 花店 农业网 实习 实验 暖通 招生简章 搬家 真空泵厂 世界杯 支原体 直销 试剂 室内装修 喷雾器 职业 盆景 书刊 屏幕 制药厂 卡片 数码照相机 奇石 卡特 痔疮 中草药 开发 棋牌 数字 开发区 考试中心 汽车销售 水环式真空泵 科普 科研 中国律师 展览会 税务师 招聘信息 招商引资 学校管理 思培 塑料包装 学英语 找工作 眼科 泰克 贴纸相 演唱会 植物 制药 药物流产 质量 质量管理 投资公司 智能 中国纺织网 液压 外语学院 一点通 医疗保健 网上商城 玩具出租 网上银行 医疗保险 中国旅行社 保洁 北京翻译 北京翻译公司 中国旅游 网上赚钱 稳压 抑郁症 背景音乐 音像 污水 主页空间 标牌 标志设计 自动化 印刷厂 无线网络 租赁 博士 应聘 无形资产评估 英汉翻译 步进电机 物资 仙人掌 彩信 先锋 纤维 饮食 现代 产品 香格里拉 邮件 成功 邮局 销售 邮票 协会 游记 传真 传真机 信息咨询 运动 姓名学 增高 打折 档案管理 点歌 电工 电力公司 电脑配件 电子信箱 电子邮件 调制解调器 高速公路 工程造价 工业设计 古董 骨科 管理制度 广告策划 规章制度 过滤 汉译英 汉英翻译 汉英互译 合同范本 合作 衡器 交流 交通安全 近视 经营 景点 开关电源 考勤 空压机近视 拉手 辣椒 礼品公司 礼仪 流产 取名 认证 润滑 三菱 设计在线 摄像 深呼吸 生日 石油 事务所 流星雨 互联网 对外贸易 外贸 花语 鼠标 美发 画廊 二胡 环球 美媚 数据 密码 换外汇 会计师事务所 密码破解 水果 水晶 免费MP3下载 绘画 法硕 惠普打印机 法语翻译 台球 机电机电 翻译英文 基金 民办高校 天文 铁道 计量 计数器 奶牛 听力 通信 技术 配件 投资 托福 皮肤 加密 粉碎 外贸公司 平安 家政 富士 家政服务 网吧 网校 维修 无线 无线电 武术 舞蹈 舞曲 系统 下载音乐 相册 项目 效果图 鞋业 心理咨询 信息管理 信箱 诚信 出租 处理 导游 电路 电气 电台 电梯 电子图书 电子邮箱 儿歌 二手 高校招生 工程 工具 公路 公司法 供求 供求信息 古筝 观赏鱼 国画 国际金融 国际旅行社 国家标准 海报 海运 航班 航空 航空公司 合金 合同法 行政管理 户外运动 护理 安防 熊猫 压缩 安全 化工网 案例 翻译社 黄金 婚庆 饭店 办公 阳光 养老保险 防盗 计算机考试 养殖 保温 防辐射 移动通信 房屋 房屋出租 保险公司 手机大全 手机之家 纺织网 交通管理 分析 标志 诺基亚手机 标准 风水 解密 经理人 服装学院 彩屏手机 妇科 九寨沟 餐饮 策划 就业 局域网 俱乐部

皮革 床上用品 英语培训 优盘 油画 游戏机 有线电视 幼教 刻录 口吃 口罩 快餐 矿泉水 篮球鞋 浪潮 理财 粮食 猎头 猎头公司 旅游景点 玫瑰 美容院 棉花 民办大学 钱币 桥梁 情报 求职招聘 人才交流 软件公司 扫描 扫描仪 山水 商务网 商行 商业 上海房产 上海租房 上市 少儿英语 设计公司 民歌 玉器 服装辅料 元件 民谣 社保 社会保障 民族音乐 园艺 市场研究 灯箱 远程控制 明信片 社会调查 申请邮箱 牡丹 云南旅游 灯饰 保健食品 生日贺卡 生物工程 在线歌曲 霓虹灯 失眠 农药 造价 花店 农业网 实习 实验 暖通 招生简章 搬家 真空泵厂 世界杯 支原体 直销 试剂 室内装修 喷雾器 职业 盆景 书刊 屏幕 制药厂 卡片 数码照相机 奇石 卡特 痔疮 中草药 开发 棋牌 数字 开发区 考试中心 汽车销售 水环式真空泵 科普 科研 中国律师 展览会 税务师 招聘信息 招商引资 学校管理 思培 塑料包装 学英语 找工作 眼科 泰克 贴纸相 演唱会 植物 制药 药物流产 质量 质量管理 投资公司 智能 中国纺织网 液压 外语学院 一点通 医疗保健 网上商城 玩具出租 网上银行 医疗保险 中国旅行社 保洁 北京翻译 北京翻译公司 中国旅游 网上赚钱 稳压 抑郁症 背景音乐 音像 污水 主页空间 标牌 标志设计 自动化 印刷厂 无线网络 租赁 博士 应聘 无形资产评估 英汉翻译 步进电机 物资 仙人掌 彩信 先锋 纤维 饮食 现代 产品 香格里拉 邮件 成功 邮局 销售 邮票 协会 游记 传真 传真机 信息咨询 运动 姓名学 增高 打折 档案管理 点歌 电工 电力公司 电脑配件 电子信箱 电子邮件 调制解调器 高速公路 工程造价 工业设计 古董 骨科 管理制度 广告策划 规章制度 过滤 汉译英 汉英翻译 汉英互译 合同范本 合作 衡器 交流 交通安全 近视 经营 景点 开关电源 考勤 空压机近视 拉手 辣椒 礼品公司 礼仪 流产 取名 认证 润滑 三菱 设计在线 摄像 深呼吸 生日 石油 事务所 流星雨 互联网 对外贸易 外贸 花语 鼠标 美发 画廊 二胡 环球 美媚 数据 密码 换外汇 会计师事务所 密码破解 水果 水晶 免费MP3下载 绘画 法硕 惠普打印机 法语翻译 台球 机电机电 翻译英文 基金 民办高校 天文 铁道 计量 计数器 奶牛 听力 通信 技术 配件 投资 托福 皮肤 加密 粉碎 外贸公司 平安 家政 富士 家政服务 网吧 网校 维修 无线 无线电 武术 舞蹈 舞曲 系统 下载音乐 相册 项目 效果图 鞋业 心理咨询 信息管理 信箱 诚信 出租 处理 导游 电路 电气 电台 电梯 电子图书 电子邮箱 儿歌 二手 高校招生 工程 工具 公路 公司法 供求 供求信息 古筝 观赏鱼 国画 国际金融 国际旅行社 国家标准 海报 海运 航班 航空 航空公司 合金 合同法 行政管理 户外运动 护理 安防 熊猫 压缩 安全 化工网 案例 翻译社 黄金 婚庆 饭店 办公 阳光 养老保险 防盗 计算机考试 养殖 保温 防辐射 移动通信 房屋 房屋出租 保险公司 手机大全 手机之家 纺织网 交通管理 分析 标志 诺基亚手机 标准 风水 解密 经理人 服装学院 彩屏手机 妇科 九寨沟 餐饮 策划 就业 局域网 俱乐部

展示架 生物反应器 笔记本电脑 成人用品 翻译 鲜花 移民 翻译公司 租房 游戏 游戏下载 摸屏 壁纸 服务器 爱滋病 办公自动化 出国 短信 干燥设备 交友 聊天 门禁 内衣 升降机 视频 写真 仪器仪表 移动存储 音乐 自考 算命 惠普 诺基亚 体育彩票 网页制作 前列腺 索尼 宠物 大连 电力 福利彩票 个人主页 广告公司 国际贸易 会计 计算机等级考试 交通 宽带 免费空间 农业 企业文化 人才 人才网 设计 手机报价 图书 网络 网络游戏 物业管理 西门子 小灵通 幼儿教育 幼儿园 娱乐 注册会计师 财务 财务管理 出国留学 电脑培训 多媒体 翻译软件 飞机票 购物 管理 婚纱摄影 激光 计算机培训 空间 律师 律师事务所 贸易 美容美发 模型 纳米 商标 数据库 通讯 网络安全 项目管理 鞋 雅思 英语培训 园林 招标 纸 中医

%META:TOPICPARENT{name="GenericProgrammingIntermediateExample"}%

%META:TOPICPARENT{name="GraphParametricTypeExample"}%

%META:TOPICINFO{author="IsaacGouy" date="1073513979" format="1.0" version="1.1"}% %META:TOPICPARENT{name="GenericProgrammingIntermediateExample"}%

// compilation unit Dijkstra.nice
package graph;

<Vertex, Edge, GraphT, Distance, T | 
Edge <: GraphEdge<Vertex>, 
GraphT <: VertexListAndIncidenceGraph<Vertex, Edge> 
>
void dijkstraShortestPaths(
   GraphT g,
   Vertex s,
   ReadWritePropertyMap<Vertex,Vertex> predecessor,
   ReadWritePropertyMap<Vertex,Distance> distance,
   ReadablePropertyMap<Edge,Distance> weight,
   (Distance,Distance)->boolean compare,
   (Distance,Distance)->Distance combine,
   Distance inf,
   Distance zero
   ){
   
   for (Vertex u : g.vertices()) {
      distance[u] = inf;
      predecessor[u] = u;
   }
   distance[s] = zero;
   
   MutableBuffer<Vertex> Q = new MutableQueue( compare: 
      (Vertex a, Vertex b) => 
         { return compare(distance[a], distance[b]); }
      );
      
   DijkstraVisitor<GraphT, Vertex, Edge, Distance> vis = 
      new DijkstraVisitor(
         m_Q: Q, 
         m_weight: weight, 
         m_predecessor: predecessor, 
         m_distance: distance, 
         m_combine: combine, 
         m_compare: compare, 
         m_zero: zero
      );

   ReadWritePropertyMap<Vertex, ColorValue> color = new HashPropertyMap();

   // Initialize color map
   for (Vertex v : g.vertices())
      color[v] = white;

   graphSearch(g, s, vis, color, Q);
}


public class DijkstraVisitor
<Graph, Vertex, Edge, Distance | Edge <: GraphEdge<Vertex> > 
implements Visitor<Graph, Vertex, Edge, Distance>
{
   private ReadablePropertyMap<Edge,Distance> m_weight;
   private (Distance, Distance)->boolean m_compare;
   private (Distance, Distance)->Distance m_combine;
   private Distance m_zero;
   private ReadWritePropertyMap<Vertex,Distance> m_distance;
   private ReadWritePropertyMap<Vertex,Vertex> m_predecessor;
   private MutableBuffer<Vertex> m_Q;

   initializeVertex(u, g) {}

   discoverVertex(u, g) {}

   examineEdge(e, g) {      
      try { 
         let f = m_compare;
         if ( f(m_weight[e], m_zero) )
            throw new NegativeEdge();                
      }
      catch (NoSuchElementException ex) {  }             
   }

   treeEdge(e, g) {
      relax(e, m_weight, m_distance, m_predecessor, m_combine, m_compare);
   }

   nonTreeEdge(e, g) {}

   grayTarget(e, g) {
      let relaxed = relax(e, m_weight, m_distance, m_predecessor, m_combine, m_compare);
      if (relaxed)
         m_Q.update(e.target);
   }

   blackTarget(e, g) {} 

   finishVertex( u, g) {}
}

public class NegativeEdge extends Exception {}

-- IsaacGouy - 07 Jan 2004