开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
graph.prog
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：11k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

graph.prog：源码内容
  1. {bf Depth First Search}
  3. #include <LEDA/graph.h>\
  4. #include <LEDA/stack.h>
  6. list<node> DFS($graph&$ $G$, $node$ $v$, $node_array<bool>&$ $reached$)
  8. ${$ 
  10. hspace*{.5cm}list<node>  $L$;\
  11. hspace*{.5cm}stack<node> $S$;\
  12. hspace*{.5cm}node $w$;
  14. smallskip
  15. hspace*{.5cm}If ( !$reached[v]$ )\
  16. hspace*{.70cm}${$  $reached[v]$ = true;\
  17. hspace*{1cm}$S$.push($v$);\
  18. hspace*{.70cm} $}$
  20. smallskip
  21. hspace*{.5cm}{bf while} ( !$S$.empty() )\
  22. hspace*{1.5cm}${$ $v = S$.pop();\ 
  23. hspace*{1.85cm}$L$.append($v$);\
  24. hspace*{1.85cm}{bf forall_adj_nodes}($w,v$)\ 
  25. hspace*{2.25cm}{bf if} ( !$reached[w]$ )\ 
  26. hspace*{2.5cm}${$ $reached[w]$ = true;\
  27. hspace*{2.75cm}$S$.push($w$);\
  28. hspace*{2.5cm}$}$
  30. smallskip
  31. hspace*{1.5cm}$}$
  33. smallskip
  34. hspace{.5cm}return $L$;
  36. smallskip
  37. $}$
  39. bigskip
  40. bigskip
  42. {bf Breadth First Search}
  44. bigskip
  45. #include <LEDA/graph.h>\ 
  46. #include <LEDA/queue.h>
  48. void BFS($graph& G, node v, node_array<int>& dist$)
  50. ${$
  52. hspace*{.5cm}queue<node> $Q$;\
  53. hspace*{.5cm}node $w$;
  55. smallskip
  56. hspace*{.5cm}{bf forall_nodes}($w,G$) $dist[w] = -1$;
  58. smallskip
  59. hspace*{.5cm}$dist[v] = 0$;\
  60. hspace*{.5cm}$Q$.append($v$);
  62. smallskip
  63. hspace*{.5cm}{bf while} ( !$Q$.empty() )\
  64. hspace*{1.5cm}${$ $v = Q$.pop();\
  65. hspace*{1.75cm}{bf forall_adj_nodes}($w,v$)\
  66. hspace*{2.25cm}{bf if} ($dist[w] < 0$)\ 
  67. hspace*{2.5cm}${$ $Q$.append($w$);\ 
  68. hspace*{2.75cm}$dist[w] = dist[v]+1$;\
  69. hspace*{2.5cm}$}$\
  70. hspace*{1.5cm}$}$
  72. smallskip
  73. $}$
  75. bigskip
  76. bigskip
  77. bigskip
  78. {bf Connected Components}
  80. bigskip
  81. #include <LEDA/graph.h>
  83. int COMPONENTS($ugraph&$ $G$, $node_array<int>&$ $compnum$)
  85. ${$
  87. hspace*{.5cm}node $v,w$;\
  88. hspace*{.5cm}list<node> $S$;\
  89. hspace*{.5cm}int $count = 0$;
  91. smallskip
  92. hspace*{.5cm}node_array(bool) $reached(G,false)$;
  94. smallskip
  95. hspace*{.5cm}Forallnodes($v,G$)
  97. hspace*{1cm}If ( !$reached[v]$ )\ 
  98. hspace*{1.25cm}${$ $S$ = DFS($G,v,reached$);\
  99. hspace*{1.5cm}Forall($w,S$) $compnum[w] = count$;\
  100. hspace*{1.5cm}$count++$;\ 
  101. hspace*{1.25cm}$}$
  103. smallskip
  104. hspace*{.5cm}Return $count$;\
  105. $}$
  108. newpage
  109. {bf Depth First Search Numbering}
  111. bigskip
  112. #include <LEDA/graph.h>
  114. int $dfs_count1, dfs_count2$;
  116. void 
  117. parbox[t]{14cm}{d_f_s($node$ $v$,$node_array<bool>&$ $S$,
  118.                                         $node_array<int>&$ $dfsnum$, 
  119.                                         $node_array<int>&$ $compnum$,
  120.                                         $list<edge>$ $T$ )}
  122. ${$ // recursive DFS
  124. smallskip
  125. hspace*{.5cm}node $w$;\
  126. hspace*{.5cm}edge $e$;
  128. smallskip
  129. hspace*{.5cm}$S[v] = true$;\
  130. hspace*{.5cm}$dfsnum[v] = ++dfs_count1$;
  132. smallskip
  133. hspace*{.5cm}Foralladjedges($e,v$)\ 
  134. hspace*{1cm}${$ $w = G$.target(e);\
  135. hspace*{1.25cm}If ( !$S[w]$ ) \
  136. hspace*{1.5cm}${$ $T$.append($e$);\
  137. hspace*{1.75cm}d_f_s($w,S,dfsnum,compnum,T$);\
  138. hspace*{1.5cm}$}$\
  139. hspace*{1cm}$}$
  141. smallskip
  142. hspace*{.5cm}$compnum[v] = ++dfs_count2$;\
  143. $}$ 
  145. bigskip
  146. bigskip
  147. list<edge> DFS_NUM($graph& G, node_array<int>& dfsnum, node_array<int>& compnum$ )
  149. ${$ \
  150. hspace*{.5cm}list<edge> $T$;\
  151. hspace*{.5cm}node_array<bool> $reached(G,false)$;\
  152. hspace*{.5cm}node $v$;\
  153. hspace*{.5cm}$dfs_count1 = dfs_count2 = 0$;\
  154. hspace*{.5cm}Forallnodes($v,G$) \
  155. hspace*{1cm}If ( !$reached[v]$ ) d_f_s($v,reached,dfsnum,compnum,T$);\
  156. hspace*{.5cm}Return $T$;\
  157. $}$\
  159. newpage
  162. {bf Topological Sorting}
  164. #include <LEDA/graph.h>
  166. bool TOPSORT($graph& G, node_array<int>& ord$)
  168. ${$\ 
  169. hspace*{.5cm}node_array<int> INDEG($G$);\
  170. hspace*{.5cm}list<node> ZEROINDEG;
  172. smallskip
  173. hspace*{.5cm}int $count=0$;\
  174. hspace*{.5cm}node $v,w$;\
  175. hspace*{.5cm}edge $e$;
  177. smallskip
  178. hspace*{.5cm}{bf forall_nodes}($v,G$)\
  179. hspace*{1cm}{bf if} ((INDEG[$v$]=$G$.indeg($v$))==0) ZEROINDEG.append($v$); 
  181. smallskip
  182. hspace*{.5cm}{bf while} (!ZEROINDEG.empty())\
  183. hspace*{1cm}${$ $v$ = ZEROINDEG.pop();\
  184. hspace*{1.25cm}$ord[v] = ++count$;
  186. smallskip
  187. hspace*{1.25cm}{bf forall_adj_nodes}($w,v$) \
  188. hspace*{1.75cm}{bf if} ($--$INDEG[$w$]==0) ZEROINDEG.append($w$);\
  189. hspace*{1cm} $}$
  191. smallskip
  192. hspace*{.5cm}{bf return} (count==G.number_of_nodes()); 
  194. smallskip
  195. $}$\
  197. bigskip
  198. //TOPSORT1 sorts node and edge lists according to the topological ordering:
  200. bigskip
  201. $bool$ TOPSORT1($graph& G$)
  203. smallskip
  204. {${$\ 
  205. hspace*{.5cm}node_array<int> node_ord($G$);\
  206. hspace*{.5cm}edge_array<int> edge_ord($G$);
  208. smallskip
  209. hspace*{.5cm}{bf if} (TOPSORT(G,node_ord))\
  210. hspace*{.75cm}${$ edge $e$;\
  211. hspace*{1cm}{bf forall_edges}($e,G$) edge_ord[$e$]=node_ord[$target(e)$];\
  212. hspace*{1cm}$G$.sort_nodes(node_ord);\
  213. hspace*{1cm}$G$.sort_edges(edge_ord);\
  214. hspace*{1cm}{bf return} true;\
  215. hspace*{.75cm}$}$\
  216. hspace*{.5cm}{bf return} false;\
  217. $}$\
  223. newpage
  225. {bf Strongly Connected Components}
  227. #include <LEDA/graph.h>\
  228. #include <LEDA/array.h>
  230. medskip
  231. int STRONG_COMPONENTS($graph& G, node_array<int>& compnum$)\
  232. ${$\
  233. hspace*{.5cm}node $v,w$;\
  234. hspace*{.5cm}int $n = G$.number_of_nodes();\
  235. hspace*{.5cm}int $count = 0$;\
  236. hspace*{.5cm}int $i$;
  238. smallskip
  239. hspace*{.5cm}array<node> $V(1,n)$;\
  240. hspace*{.5cm}list<node> $S$;\
  241. hspace*{.5cm}node_array<int>  $dfs_num(G), compl_num(G)$;\
  242. hspace*{.5cm}node_array<bool> $reached(G,false)$;
  244. smallskip
  245. hspace*{.5cm}DFS_NUM($G,dfs_num,compl_num$);
  247. smallskip
  248. hspace*{.5cm}Forallnodes($v,G$) $V[compl_num[v]] = v$;
  250. smallskip
  251. hspace*{.5cm}$G$.rev();
  253. smallskip
  254. hspace*{.5cm}For($i=n; i>0; i--$)\
  255. hspace*{1cm}If ( !$reached[V[i]]$ ) \
  256. hspace*{1.25cm}${$ $S$ = DFS($G,V[i],reached$);\
  257. hspace*{1.5cm}Forall($w,S$) $compnum[w] = count$;\
  258. hspace*{1.5cm}$count++$;\
  259. hspace*{1.25cm}$}$
  261. smallskip
  262. hspace*{.5cm}Return $count$;
  264. smallskip
  265. $}$\
  269. newpage
  272. {bf Dijkstra's Algorithm}
  275. #include <LEDA/graph.h>\ 
  276. #include <LEDA/node_pq.h>
  278. medskip
  279. void DIJKSTRA( graph& $G$, node $s$, edge_array<int>& $cost$, \
  280. hspace*{1cm}node_array<int>& $dist$, node_array<edge>& $pred$ )
  282. ${$\ 
  283. hspace*{.5cm}node_pq<int> $PQ(G)$;
  285. smallskip
  286. hspace*{.5cm}int $c$;\
  287. hspace*{.5cm}node $u,v$;\
  288. hspace*{.5cm}edge $e$;
  290. smallskip
  291. hspace*{.5cm}{bf forall_nodes}($v,G$)\
  292. hspace*{1cm}${$ $ pred[v] = 0$;\
  293. hspace*{1.25cm}$dist[v] = infinity$;\
  294. hspace*{1.25cm}$PQ$.insert($v,dist[v])$;\
  295. hspace*{1cm}$}$
  297. smallskip
  298. hspace*{.5cm}$dist[s] = 0$;\
  299. hspace*{.5cm}$PQ$.decrease_inf($s,0)$;
  301. smallskip
  302. hspace*{.5cm}{bf while} ( ! $PQ$.empty())\
  303. hspace*{1cm}${$ $u = PQ$.del_min();
  305. smallskip
  306. hspace*{1.25cm}{bf forall_adj_edges}($e,u$)\
  307. hspace*{1.75cm}${$ $v = G.target(e) $;\ 
  308. hspace*{2cm}$c = dist[u] + cost[e] $;\
  309. hspace*{2cm}{bf if} ( $c < dist[v] $)\
  310. hspace*{2.25cm}${$ $dist[v] = c$;\
  311. hspace*{2.5cm}$pred[v] = e$;\
  312. hspace*{2.5cm}$PQ$.decrease_inf($v,c$);\
  313. hspace*{2.25cm}$}$\
  314. hspace*{1.75cm}$}$ /$*$ forall_adj_edges $*$
  316. smallskip
  317. hspace*{1cm}$}$ /$*$ while $*$/
  319. smallskip
  320. $}$\
  322. newpage
  323. {bf Bellman/Ford Algorithm}
  325. #include <LEDA/graph.h>\
  326. #include <LEDA/queue.h>
  328. medskip
  329. bool BELLMAN_FORD($graph& G, node s, edge_array<int>& cost$,\
  330. hspace*{1cm}$node_array<int>& dist, node_array<edge>& pred$)
  332. ${$\ 
  333. hspace*{.5cm}node_array<bool> $in_Q(G,false)$;\
  334. hspace*{.5cm}node_array<int>  $count(G,0)$;
  336. smallskip
  337. hspace*{.5cm}int $n = G$.number_of_nodes();\
  338. hspace*{.5cm}queue<node> $Q(n)$;
  340. smallskip
  341. hspace*{.5cm}node $u,v$;\
  342. hspace*{.5cm}edge $e$;\
  343. hspace*{.5cm}int  $c$;
  345. smallskip
  346. hspace*{.5cm}Forallnodes($v,G$)\
  347. hspace*{1cm}${$ $pred[v] = 0$;\
  348. hspace*{1.25cm}$dist[v] =  infinity$; \
  349. hspace*{1cm}$}$\
  350. hspace*{.5cm}$dist[s] = 0$;\
  351. hspace*{.5cm}$Q$.append($s$);\
  352. hspace*{.5cm}$in_Q[s] = true$;
  354. smallskip
  355. hspace*{.5cm}{bf while} (!$Q$.empty())\
  356. hspace*{1cm}${$ $u = Q$.pop();\
  357. hspace*{1.25cm}$in_Q[u] = false$;
  359. smallskip
  360. hspace*{1.25cm}If ($++count[u] > n$)  {bf return} false;quad //negative cycle
  362. smallskip
  363. hspace*{1.25cm}Foralladjedges($e,u$) \
  364. hspace*{1.75cm}${$ $v$ = $G$.target($e$);\
  365. hspace*{2cm}$c = dist[u] + cost[e]$;
  367. smallskip
  368. hspace*{2cm}If ($c < dist[v]$) \
  369. hspace*{2.25cm}${$ $dist[v] = c$; \
  370. hspace*{2.5cm}$pred[v] = e$;\
  371. hspace*{2.5cm}If (!$in_Q[v]$)  \
  372. hspace*{2.75cm}${$ $Q$.append($v$);\
  373. hspace*{3cm}$in_Q[v]=true$;\
  374. hspace*{2.75cm}$}$\
  375. hspace*{2.25cm}$}$\
  376. hspace*{1.75cm}$}$ /$*$ forall_adj_edges $*$/\
  377. hspace*{1cm}$}$ /$*$ while $*$/\
  378. hspace*{.5cm}{bf return} true;\
  379. $}$\
  381. newpage
  382. {bf All Pairs Shortest Paths}
  384. #include <LEDA/graph.h>
  386. void all_pairs_shortest_paths(graph& $G$, edge_array<double>& $cost$,\
  387. hspace*{1cm}node_matrix<double>& $DIST$)\
  388. ${$\
  389. hspace*{.5cm}// computes for every node pair $(v,w)$ $DIST(v,w)$ = cost of the least cost\
  390. hspace*{.5cm}// path from $v$ to $w$, the single source shortest paths algorithms BELLMAN_FORD\
  391. hspace*{.5cm}// and DIJKSTRA are used as subroutines
  393. smallskip
  394. hspace*{.5cm}edge $e$;\
  395. hspace*{.5cm}node $v$;\
  396. hspace*{.5cm}double $C = 0$;
  398. smallskip
  399. hspace*{.5cm}{bf forall_edges}($e,G$) $C += fabs(cost[e]$);\
  400. hspace*{.5cm}node $s = G$.new_node(); hspace{3cm} // add $s$ to $G$\
  401. hspace*{.5cm}{bf forall_nodes}($v,G$) $G$.new_edge($s,v$); hspace{.75cm} // add edges ($s,v$) to $G$
  403. smallskip
  404. hspace*{.5cm}node_array<double> $dist1(G)$;\
  405. hspace*{.5cm}node_array<edge>   $pred(G)$;\
  406. hspace*{.5cm}edge_array<double> $cost1(G)$;\
  407. hspace*{.5cm}{bf forall_edges}($e,G$) 
  408. $cost1[e] = (G$.source$(e)==s)$ ? $C : cost[e]$;
  410. smallskip
  411. hspace*{.5cm}BELLMAN_FORD($G,s,cost1,dist1,pred$);
  413. smallskip
  414. hspace*{.5cm}$G$.del_node($s$); hspace{4.75cm}// delete $s$ from $G$\
  415. hspace*{.5cm}edge_array(double) $cost2(G)$;\
  416. hspace*{.5cm}{bf forall_edges}($e,G$) $cost2[e] = dist1[G.source(e)] + cost[e] - dist1[G.target(e)]$;
  418. smallskip
  419. hspace*{.5cm}{bf forall_nodes}($v,G$)  DIJKSTRA($G,v,cost2,DIST[v],pred$);
  421. smallskip
  422. hspace*{.5cm}{bf forall_nodes}($v,G$)\
  423. hspace*{1cm}bf forall_nodes}($w,G$) $DIST(v,w) = DIST(v,w) - dist1[v] + dist1[w]$;\
  424. $}$
  426. newpage
  428. {bf Minimum Spanning Tree}
  431. #include <LEDA/graph.h>\
  432. #include <LEDA/node_partition.h>
  434. medskip
  435. void MIN_SPANNING_TREE(graph& $G$, edge_array<double>& $cost$, list<edge>& $EL$)\
  436. ${$\
  437. hspace*{.5cm}node $v,w$;\
  438. hspace*{.5cm}edge $e$;\
  439. hspace*{.5cm}node_partition $Q(G)$;
  441. smallskip
  442. hspace*{.5cm}$G$.sort_edges($cost$);
  444. smallskip
  445. hspace*{.5cm}$EL$.clear();\
  446. hspace*{.5cm}{bf forall}_edges($e,G$)\
  447. hspace*{.75cm}${$ $v = G.source(e)$;\
  448. hspace*{1cm}$w = G.target(e)$;\
  449. hspace*{1cm}{bf if} ($!(Q$.same_block($v,w$))\
  450. hspace*{1.25cm}${$  $Q$.union_blocks($v,w$);\
  451. hspace*{1.5cm}$EL$.append($e$);\
  452. hspace*{1.25cm}$}$\
  453. hspace*{.75cm}$}$\
  454. $}$\
  456. newpage