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

天津货运 天津物流 不锈钢 打印机 钢结构 计算机 加盟 建筑材料 旅行社 企业管理 人力资源 网页设计 市场营销 室内设计 手机 饲料 涂料 卫星电视 物流 远程教育 展览 包装机械 包装设计 玻璃钢 瓷砖 地板 电池 电动工具 电话 电缆 电器 电线电缆 电源 雕塑 耳机 二手电脑 二手房 发电机 防盗门 纺织 机票 复印机 钢铁 工程机械 广告设计 继电器 家电 建筑设计 交换机 洁具 开关 乐器 木地板 皮革 啤酒 润滑油 摄像机 摄像头 数码摄像机 塑料机械 体育用品 网络电话 望远镜 文具 五金工具 显示器 相机 香水 蓄电池 仪表 中央空调 珠宝 平面设计 传感器 摩托车 玻璃 电机 工艺品 化工 化妆品 机械 空调 时装 食品 塑料 陶瓷 玩具 五金 印刷 轴承 钢材 汽车配件 橡胶 变压器 订房 订票 水处理 显示屏 礼品 旅游 汽车 服装 电影 数码相机 稳压器 招聘 触摸屏 机柜 酒店预定 模具 在线电影 笔记本 虚拟主机 管理咨询 域名注册 成人电影 肾病 免费电影 肿瘤 显微镜 婚介 股票 交换机 糖尿病 企业邮箱 乙肝 对讲机 化妆品 股骨头坏死 电子商务 网站推广 美女 UPS 液晶 尿毒症 条码打印机 电脑 家具 投影幕 服饰 网站空间 轮胎 网上购物 化学试剂 媒体 手套 二手笔记本 发动机 免费下载电影 水泥 塑料制品 机床 免费音乐下载 随身听 防水材料 纺织机械 耐火材料 肺结核 肺炎 风机 家居装饰 脱发 钢板 汽车美容 网络电话 监理 减速机 钢板网 钢管 网络设备 洗衣机 显卡 刀具 电视机 锅炉 二手车 滑板 眼镜 办公用品 防盗门 仪器 保温材料 继电器 变频器 办公家具 货运 高尔夫 叉车 插件 超声 泳装 箱包 小提琴 冲压 除湿机 油漆 小尾寒羊 元器件 磁性材料 刺绣 运动鞋 型材 打火机 打折机票 灯泡 电子产品 电子技术 垫仓板 吊钩 吊网 合成纤维吊装带 烘干机 胶带 结核 咖啡 空压机 冷却塔 热水器 日用品 乳品机械 石材 食品机械 收音机 手表 化工原料 多电脑切换器 茶叶 医疗设备 微型打印机 饮水机 污水处理 印刷机 冰箱 财务软件 彩钢板 音响 仓储 木制品 遥控器 摄影器材 数码产品 床上用品 面料 拉链 机箱 包装材料 涂装 水表 管理培训 门窗 破碎机 自动门 自吸泵 硬盘 绿色食品 燃气设备 容器 软管 木业

天津货运 天津物流 不锈钢 打印机 钢结构 计算机 加盟 建筑材料 旅行社 企业管理 人力资源 网页设计 市场营销 室内设计 手机 饲料 涂料 卫星电视 物流 远程教育 展览 包装机械 包装设计 玻璃钢 瓷砖 地板 电池 电动工具 电话 电缆 电器 电线电缆 电源 雕塑 耳机 二手电脑 二手房 发电机 防盗门 纺织 机票 复印机 钢铁 工程机械 广告设计 继电器 家电 建筑设计 交换机 洁具 开关 乐器 木地板 皮革 啤酒 润滑油 摄像机 摄像头 数码摄像机 塑料机械 体育用品 网络电话 望远镜 文具 五金工具 显示器 相机 香水 蓄电池 仪表 中央空调 珠宝 平面设计 传感器 摩托车 玻璃 电机 工艺品 化工 化妆品 机械 空调 时装 食品 塑料 陶瓷 玩具 五金 印刷 轴承 钢材 汽车配件 橡胶 变压器 订房 订票 水处理 显示屏 礼品 旅游 汽车 服装 电影 数码相机 稳压器 招聘 触摸屏 机柜 酒店预定 模具 在线电影 笔记本 虚拟主机 管理咨询 域名注册 成人电影 肾病 免费电影 肿瘤 显微镜 婚介 股票 交换机 糖尿病 企业邮箱 乙肝 对讲机 化妆品 股骨头坏死 电子商务 网站推广 美女 UPS 液晶 尿毒症 条码打印机 电脑 家具 投影幕 服饰 网站空间 轮胎 网上购物 化学试剂 媒体 手套 二手笔记本 发动机 免费下载电影 水泥 塑料制品 机床 免费音乐下载 随身听 防水材料 纺织机械 耐火材料 肺结核 肺炎 风机 家居装饰 脱发 钢板 汽车美容 网络电话 监理 减速机 钢板网 钢管 网络设备 洗衣机 显卡 刀具 电视机 锅炉 二手车 滑板 眼镜 办公用品 防盗门 仪器 保温材料 继电器 变频器 办公家具 货运 高尔夫 叉车 插件 超声 泳装 箱包 小提琴 冲压 除湿机 油漆 小尾寒羊 元器件 磁性材料 刺绣 运动鞋 型材 打火机 打折机票 灯泡 电子产品 电子技术 垫仓板 吊钩 吊网 合成纤维吊装带 烘干机 胶带 结核 咖啡 空压机 冷却塔 热水器 日用品 乳品机械 石材 食品机械 收音机 手表 化工原料 多电脑切换器 茶叶 医疗设备 微型打印机 饮水机 污水处理 印刷机 冰箱 财务软件 彩钢板 音响 仓储 木制品 遥控器 摄影器材 数码产品 床上用品 面料 拉链 机箱 包装材料 涂装 水表 管理培训 门窗 破碎机 自动门 自吸泵 硬盘 绿色食品 燃气设备 容器 软管 木业

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

The generic algorithms BreadthFirstSearchExample, DijkstraShortestPathsExample, PrimMinimumSpanningTreeExample, BellmanFordShortestPathsExample, and JohnsonAllPairsShortestPathsExample, make use of GraphConceptsExample and GraphClassesExample and GraphTestExample.

The generic algorithms Breadth First Search, Dijkstra Shortest Paths, Prim's Minimum Spanning Tree, Bellman Ford Shortest Paths, and Johnson All Pairs Shortest Paths, make use of Graph Concepts and Graph Classes and Graph Tests.

(For tests in GraphTestExample.)

(See test code)

%META:TOPICMOVED{by="IsaacGouy" date="1076170967" from="Doc.GenericProgrammingIntermediateExample" to="Doc.GraphParametricTypeExample"}%

for (i : 40003..40006) {

for (i : 3..6) {

// Maybe a Vertex has no predecessors? 40003

// Maybe a Vertex has no predecessors? 3

initialize 40003 initialize 40004 initialize 40005 initialize 40006 discover 40003 discover 40003 examine edge(40003 -> 40006) tree edge(40003 -> 40006) examine edge(40003 -> 40005) tree edge(40003 -> 40005) finish 40003 discover 40006 examine edge(40006 -> 40004) tree edge(40006 -> 40004) finish 40006 discover 40005 finish 40005 discover 40004 examine edge(40004 -> 40005) nontree edge(40004 -> 40005) black target edge(40004 -> 40005) examine edge(40004 -> 40003) nontree edge(40004 -> 40003) black target edge(40004 -> 40003) finish 40004

initialize 3 initialize 4 initialize 5 initialize 6 discover 3 discover 3 examine edge(3 -> 6) tree edge(3 -> 6) examine edge(3 -> 5) tree edge(3 -> 5) finish 3 discover 6 examine edge(6 -> 4) tree edge(6 -> 4) finish 6 discover 5 finish 5 discover 4 examine edge(4 -> 5) nontree edge(4 -> 5) black target edge(4 -> 5) examine edge(4 -> 3) nontree edge(4 -> 3) black target edge(4 -> 3) finish 4

Dist(40003)=0.0, Pred(40003)=40003 Dist(40004)=7.0, Pred(40004)=40006 Dist(40005)=8.0, Pred(40005)=40003 Dist(40006)=5.0, Pred(40006)=40003

Dist(3)=0.0, Pred(3)=3 Dist(4)=7.0, Pred(4)=6 Dist(5)=8.0, Pred(5)=3 Dist(6)=5.0, Pred(6)=3

Pred(40003) = 40003 Pred(40004) = 40006 Pred(40005) = 40004 Pred(40006) = 40003

Pred(3) = 3 Pred(4) = 6 Pred(5) = 4 Pred(6) = 3

Dist(40003)=0.0, Pred(40003)= Dist(40004)=3.0, Pred(40004)=40006 Dist(40005)=2.0, Pred(40005)=40004 Dist(40006)=5.0, Pred(40006)=40003

Dist(3)=0.0, Pred(3)= Dist(4)=3.0, Pred(4)=6 Dist(5)=2.0, Pred(5)=4 Dist(6)=5.0, Pred(6)=3

40003: 0.0 3.0 2.0 5.0 40004: 3.0 0.0 -1.0 8.0 40005: Infinity Infinity 0.0 Infinity 40006: 1.0 -2.0 -3.0 0.0

3: 0.0 3.0 2.0 5.0 4: 3.0 0.0 -1.0 8.0 5: Infinity Infinity 0.0 Infinity 6: 1.0 -2.0 -3.0 0.0

The generic algorithms BreadthFirstSearchExample, DijkstraShortestPathsExample, PrimMinimumSpanningTreeExample, BellmanFordShortestPathsExample, and JohnsonAllPairsShortestPathsExample, make use of GraphConceptsExamples and GraphClassesExamples.

The generic algorithms BreadthFirstSearchExample, DijkstraShortestPathsExample, PrimMinimumSpanningTreeExample, BellmanFordShortestPathsExample, and JohnsonAllPairsShortestPathsExample, make use of GraphConceptsExample and GraphClassesExample and GraphTestExample.

%META:TOPICINFO{author="IsaacGouy" date="1073512440" format="1.0" version="1.1"}% %META:TOPICPARENT{name="CodeExamples"}% "A Comparative Study of Language Support for Generic Programming" used a sample of the Boost Graph Library to compare the generic programming techniques available in C++, ML, Haskell, Eiffel, Java Generics, Generic C# (Source code). These Nice implementations use parameterised interfaces to represent most concepts (a few are represented by functions).

The generic algorithms BreadthFirstSearchExample, DijkstraShortestPathsExample, PrimMinimumSpanningTreeExample, BellmanFordShortestPathsExample, and JohnsonAllPairsShortestPathsExample, make use of GraphConceptsExamples and GraphClassesExamples.

Bellman Ford Shortest Paths

package graph;

<Vertex, Edge, Distance, T | Edge <: GraphEdge<Vertex> > 
boolean bellmanFordShortestPaths(
   EdgeListGraph<Vertex,Edge> graph,
   int size,
   ReadablePropertyMap<Edge,Distance> weightMap,
   ReadWritePropertyMap<Vertex,Vertex> predecessor,
   ReadWritePropertyMap<Vertex,Distance> distance,
   (Distance, Distance)->Distance combine,
   (Distance, Distance)->boolean compare
   ){
   
   for (int i = 0; i < size; ++i) {
      boolean anyRelaxed = false; // Optimization from BGL
      for ( Edge edge : graph.edges )
         if( relax(edge, weightMap, distance, predecessor, combine, compare) )
            anyRelaxed = true; 
                       
      if (!anyRelaxed) break;
   }

   for ( Edge edge : graph.edges() )
      if (compare( 
         combine(weightMap[edge], distance[edge.source]), 
         distance[edge.target])
         )
            return false;

   return true;
}


void bellmanFordTest(){ 
   AdjacencyList <int, AdjacencyListEdge<int>> g = simpleGraph(); 
   HashPropertyMap<int, double> distanceMap = simpleDistanceMap();  
   HashPropertyMap<AdjacencyListEdge<int>, double> weightMap = negativeWeights();    
   
   HashPropertyMap<int, int> predMap = new HashPropertyMap();  
    
   bellmanFordShortestPaths(
      g, 
      4,
      weightMap,
      predMap,
      distanceMap,
      (double a, double b) => { return a + b; },
      (double a, double b) => { return a < b; }
      );

   for (i : 40003..40006) {
      print("Dist(" i ")="   distanceMap.get(i));                     
      print(", Pred(" i ")=");
      
      // Maybe a Vertex has no predecessors? 40003
      try { print( predMap.get(i) ); 
      } catch (NoSuchElementException ex){}    
        
      println("");
   }
}

Test Results

Breadth First Search Test
=========================
initialize 40003
initialize 40004
initialize 40005
initialize 40006
discover 40003
discover 40003
examine edge(40003 -> 40006)
tree edge(40003 -> 40006)
examine edge(40003 -> 40005)
tree edge(40003 -> 40005)
finish 40003
discover 40006
examine edge(40006 -> 40004)
tree edge(40006 -> 40004)
finish 40006
discover 40005
finish 40005
discover 40004
examine edge(40004 -> 40005)
nontree edge(40004 -> 40005)
black target edge(40004 -> 40005)
examine edge(40004 -> 40003)
nontree edge(40004 -> 40003)
black target edge(40004 -> 40003)
finish 40004

Dijkstra Shortest Paths Test
============================
Dist(40003)=0.0, Pred(40003)=40003
Dist(40004)=7.0, Pred(40004)=40006
Dist(40005)=8.0, Pred(40005)=40003
Dist(40006)=5.0, Pred(40006)=40003

Prim Minimum Spanning Tree Test
===============================
Pred(40003) = 40003
Pred(40004) = 40006
Pred(40005) = 40004
Pred(40006) = 40003

Bellman-Ford Shortest Paths Test
================================
Dist(40003)=0.0, Pred(40003)=
Dist(40004)=3.0, Pred(40004)=40006
Dist(40005)=2.0, Pred(40005)=40004
Dist(40006)=5.0, Pred(40006)=40003

Johnson All-Pairs Shortest Paths Test
=====================================
40003: 0.0 3.0 2.0 5.0
40004: 3.0 0.0 -1.0 8.0
40005: Infinity Infinity 0.0 Infinity
40006: 1.0 -2.0 -3.0 0.0

-- IsaacGouy - 07 Jan 2004