home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / prog / graph.pro < prev    next >
Encoding:
Text File  |  1991-11-15  |  11.7 KB  |  413 lines
  1. {\bf Depth First Search}
  2.  
  3. \#include $<$LEDA/graph.h$>$\nl
  4. \#include $<$LEDA/stack.h$>$
  5. \medskip
  6. {\bf declare}(stack,node)
  7. \medskip
  8. \cleartabs
  9. \+list(node) DFS($graph\& G,\  node\  v,\  node\_array(bool)\& reached$)\cr
  10. \+$\{$\ \ &\cr 
  11. \+  &list(node)  $L$;\cr
  12. \+  &stack(node) $S$;\cr
  13. \+  &node $w$;\cr
  14. \smallskip
  15. \+  &\If ( ! $reached[v]$ )\cr
  16. \+  &\ \ \ &$\{$ &$reached[v]$ = true;\cr
  17. \+  &      &     &$L$.append($v$);\cr
  18. \+  &      &     &$S$.push($v$);\cr
  19. \+  &      &\ $\}$\cr
  20. \smallskip
  21. \+  &{\bf while} ( !$S$.empty() )\cr
  22. \+  &      &$\{$ &$v = S$.pop(); \cr
  23. \+  &      &     &{\bf forall\_adj\_nodes}($w,v$) \cr
  24. \+  &      &     &\ \ \ &{\bf if} ( !$reached[w]$ ) \cr
  25. \+  &      &     &      &$\{$ &$reached[w]$ = true;\cr
  26. \+  &      &     &      &     &$L$.append($w$);\cr
  27. \+  &      &     &      &     &$S$.push($w$);\cr
  28. \+  &      &     &      &\ $\}$\cr
  29. \+  &      &\ $\}$\cr
  30. \smallskip
  31. \+  &return $L$;\cr
  32. \+$\}$\cr
  33.  
  34. \vfill\eject
  35.  
  36. {\bf Breadth First Search}
  37.  
  38. \#include $<$LEDA/graph.h$>$\nl
  39. \#include $<$LEDA/queue.h$>$
  40. \medskip
  41. {\bf declare}(queue,node)
  42. \medskip
  43. \cleartabs
  44. \+void BFS($graph\&\ G,\ node\ v,\ node\_array(int)\&\ dist$)\cr
  45. \+$\{$\ \ &\cr
  46. \+  &queue(node) $Q$;\cr
  47. \+  &node $w$;\cr
  48. \smallskip
  49. \+  &{\bf forall\_nodes}($w,G$) $dist[w] = -1$;\cr
  50. \smallskip
  51. \+  &$dist[v] = 0$;\cr
  52. \+  &$Q$.append($v$);\cr
  53. \smallskip
  54. \+  &{\bf while} ( !$Q$.empty() )\cr
  55. \+  &\ \ &$\{$ &$v = Q$.pop();\cr
  56. \+  &    &     &{\bf forall\_adj\_nodes}($w,v$)\cr
  57. \+  &    &     &\ \ \ &{\bf if} ($dist[w] < 0$) \cr
  58. \+  &    &     &      &$\{$ &$Q$.append($w$); \cr
  59. \+  &    &     &      &     &$dist[w] = dist[v]+1$;\cr
  60. \+  &    &     &      &\ $\}$\cr
  61. \+  &    &\ $\}$\cr
  62. \smallskip
  63. \+$\}$\cr
  64.  
  65. {\bf Connected Components}
  66.  
  67. \#include $<$LEDA/graph.h$>$
  68. \medskip
  69. \cleartabs
  70. \+int COMPONENTS($ugraph\&\ G,\ node\_array(int)\&\ compnum$)\cr
  71. \+$\{$ \ & \cr
  72. \+  &node $v,w$;\cr
  73. \+  &list(node) $S$;\cr
  74. \+  &int $count = 0$;\cr
  75. \smallskip
  76. \+  &node\_array(bool) $reached(G,false)$;\cr
  77. \smallskip
  78. \+  &\Forallnodes($v,G$) \cr
  79. \+  &\ \ \ &\If ( !$reached[v]$ ) \cr
  80. \+  &      &\ \ &$\{$ &$S$ = DFS($G,v,reached$);\cr
  81. \+  &      &    &     &\Forall($w,S$) $compnum[w] = count$;\cr
  82. \+  &      &    &     &$count++$; \cr
  83. \+  &      &    &\ $\}$\cr
  84. \smallskip
  85. \+  &\Return $count$;\cr
  86. \+\ $\}$\cr
  87.  
  88. \vfill\eject
  89.  
  90.  
  91.  
  92. {\bf Depth First Search Numbering}
  93.  
  94. \#include $<$LEDA/graph.h$>$
  95. \medskip
  96. \cleartabs
  97. \+int $dfs\_count1,\ dfs\_count2$;\cr
  98. \medskip
  99. \+void d\_f\_s($node\ v,\ node\_array(bool)\&\ S$,
  100.                                         &$node\_array(int)\&\ dfsnum$, \cr
  101. \+                                      &$node\_array(int)\&\ compnum$,\cr
  102. \+                                      &$list(edge)\ T$ )\cr
  103. \cleartabs
  104. \+$\{$ \ &// recursive DFS\cr
  105. \smallskip
  106. \+  &node $w$;\cr
  107. \+  &edge $e$;\cr
  108. \smallskip
  109. \+  &$S[v] = true$;\cr
  110. \+  &$dfsnum[v] = ++dfs\_count1$;\cr
  111. \smallskip
  112. \+  &\Foralladjedges($e,v$) \cr
  113. \+  &\ \ \ &$\{$ &$w = G$.target(e);\cr
  114. \+  &      &    &\If ( !$S[w]$ ) \cr
  115. \+  &      &    &\ \ &$\{$ &$T$.append($e$);\cr
  116. \+  &      &    &    &    &d\_f\_s($w,S,dfsnum,compnum,T$);\cr
  117. \+  &      &    &    &\ $\}$\cr
  118. \+  &      &\ $\}$\cr
  119. \smallskip
  120. \+  &$compnum[v] = ++dfs\_count2$;\cr
  121. \+\ $\}$ \cr
  122. \bigskip
  123. \bigskip
  124. \cleartabs
  125. \+list(edge) DFS\_NUM($graph\&\ G,\ node\_array(int)\&\ dfsnum,\ node\_array(int)\&\ compnum$ )\cr
  126. \+$\{$ \ & \cr
  127. \+  &list(edge) $T$;\cr
  128. \+  &node\_array(bool) $reached(G,false)$;\cr
  129. \+  &node $v$;\cr
  130. \+  &$dfs\_count1 = dfs\_count2 = 0$;\cr
  131. \+  &\Forallnodes($v,G$) \cr
  132. \+  & \ \ \ \If ( !$reached[v]$ ) d\_f\_s($v,reached,dfsnum,compnum,T$);\cr
  133. \+  &\Return $T$;\cr
  134. \+\ $\}$\cr
  135.  
  136. \vfill\eject
  137.  
  138.  
  139.  
  140. {\bf Topological Sorting}
  141.  
  142. \#include $<$LEDA/graph.h$>$
  143. \medskip
  144. \cleartabs
  145. \+bool TOPSORT($graph\&\  G,\  node\_array(int)\& ord$)\cr
  146. \+$\{$\ \ &\cr 
  147. \+  &node\_array(int) INDEG($G$);\cr
  148. \+  &list(node) ZEROINDEG;\cr
  149. \smallskip
  150. \+  &int $count=0$;\cr
  151. \+  &node $v,w$;\cr
  152. \+  &edge $e$;\cr
  153. \smallskip
  154. \+  &{\bf forall\_nodes}($v,G$)\cr
  155. \+  &\ \ \ {\bf if} ((INDEG[$v$]=$G$.indeg($v$))==0) ZEROINDEG.append($v$); \cr
  156. \smallskip
  157. \+  &{\bf while} (!ZEROINDEG.empty())\cr
  158. \+  &\ \ &$\{$ &$v$ = ZEROINDEG.pop();\cr
  159. \+  &    &    &$ord[v] = ++count$;\cr
  160. \smallskip
  161. \+  &    &    &{\bf forall\_adj\_nodes}($w,v$) \cr
  162. \+  &    &    &\ \ \ {\bf if} ($--$INDEG[$w$]==0) ZEROINDEG.append($w$);\cr
  163. \+  &    &\ $\}$\cr
  164. \smallskip
  165. \+  &{\bf return} (count==G.number\_of\_nodes()); \cr
  166. \smallskip
  167. \+\ $\}$\cr
  168.  
  169. \bigskip
  170. //TOPSORT1 sorts node and edge lists according to the topological ordering:
  171. \bigskip
  172. \cleartabs
  173. \+$node\_array(int)$ $ord$;\cr
  174. \medskip
  175. \+$int$ cmp\_node\_ord($node\&\ v,\ node\&\ w$)\cr
  176. \+$\{$ {\bf return} $ord[v] - ord[w]$; $\}$\cr
  177. \medskip
  178. \+$int$ cmp\_edge\_ord($edge\&\ e1,\ edge\&\ e2$) \cr
  179. \+$\{$ {\bf return} cmp\_node\_ord(target($e1$),target($e2$)); $\}$\cr
  180. \bigskip
  181. \+$bool$ TOPSORT1($graph\&\ G$)\cr
  182. \+$\{$\ \ & \cr
  183. \+        &$ord$.init($G$);\cr
  184. \+        &{\bf if} (TOPSORT(G,ord))\cr
  185. \+        &$\{$ &$G$.sort\_nodes($cmp\_node\_ord$);\cr
  186. \+        &     &$G$.sort\_edges($cmp\_edge\_ord$);\cr
  187. \+        &     &{\bf return} true;\cr
  188. \+        &$\ \}$\cr
  189. \+        &{\bf return} false;\cr
  190. \+$\ \}$\cr
  191.  
  192. \vfill\eject
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199. {\bf Strongly Connected Components}
  200.  
  201. \#include $<$LEDA/array.h$>$
  202. \medskip
  203. {\bf declare}(array,node)
  204. \medskip
  205. \cleartabs
  206. \+int STRONG\_COMPONENTS($graph\&\ G,\ node\_array(int)\&\ compnum$)\cr
  207. \+$\{$ \ &\cr
  208. \+  &node $v,w$;\cr
  209. \+  &int $n = G$.number\_of\_nodes();\cr
  210. \+  &int $count = 0$;\cr
  211. \+  &int $i$;\cr
  212. \smallskip
  213. \+  &array(node) $V(1,n)$;\cr
  214. \+  &list(node) $S$;\cr
  215. \+  &node\_array(int)  $dfs\_num(G), compl\_num(G)$;\cr
  216. \+  &node\_array(bool) $reached(G,false)$;\cr
  217. \smallskip
  218. \+  &DFS\_NUM($G,dfs\_num,compl\_num$);\cr
  219. \smallskip
  220. \+  &\Forallnodes($v,G$) $V[compl\_num[v]] = v$;\cr
  221. \smallskip
  222. \+  &$G$.rev();\cr
  223. \smallskip
  224. \+  &\For($i=n;\ i>0;\ i--$)\cr
  225. \+  &\ \ \ &\If ( !$reached[V[i]]$ ) \cr
  226. \+  &      &\ \ &$\{$ &$S$ = DFS($G,V[i],reached$);\cr
  227. \+  &      &    &     &\Forall($w,S$) $compnum[w] = count$;\cr
  228. \+  &      &    &     &$count++$;\cr
  229. \+  &      &    &\ $\}$\cr
  230. \smallskip
  231. \+  &\Return $count$;\cr
  232. \smallskip
  233. \+\ $\}$\cr
  234.  
  235. \vfill\eject
  236.  
  237.  
  238.  
  239.  
  240.  
  241. {\bf Dijkstra's Algorithm}
  242.  
  243.  
  244. \#include $<$LEDA/graph.h$>$\nl 
  245. \medskip
  246. \cleartabs
  247. \+void DIJKSTRA(& graph\& $G$, node $s$, edge\_array(int)\& $cost$, \cr
  248. \+              & node\_array(int)\& $dist$, node\_array(edge)\& $pred$ ) \cr
  249. \+\cleartabs 
  250.   $\{$ & node\_pq(int) $PQ(G)$;\cr
  251. \smallskip
  252. \+     &int $c$;\cr
  253. \+     &node $u,v$;\cr
  254. \+     &edge $e$;\cr
  255. \smallskip
  256. \+     &{\bf forall\_nodes}($v,G$)\cr
  257. \+     &\ \ \ &$\{$ & $ pred[v] = 0$;\cr
  258. \+     &      &     & $dist[v] = infinity$;\cr
  259. \+     &      &     & $PQ$.insert($v,dist[v])$;\cr
  260. \+     &      &\ $\}$\cr
  261. \smallskip
  262. \+     &$dist[s] = 0$;\cr
  263. \+     &$PQ$.decrease\_inf($s,0)$;\cr
  264. \smallskip
  265. \+     &{\bf while} ( ! $PQ$.empty())\cr
  266. \+     &\ \ \ &$\{$ &$u = PQ$.delete\_min()\cr
  267. \smallskip
  268. \+     &      &     &{\bf forall\_adj\_edges}($e,u$)\cr
  269. \+     &      &     &\ \ \ &$\{$ &$v = G.target(e) $;       \cr
  270. \+     &      &     &      &     &$c = dist[u] + cost[e] $;\cr
  271. \+     &      &     &      &     &{\bf if} ( $c < dist[v] $)\cr
  272. \+     &      &     &      &     &\ \ &$\{$ &$dist[v] = c$;\cr
  273. \+     &      &     &      &     &    &     &$pred[v] = e$;\cr
  274. \+     &      &     &      &     &    &     &$PQ$.decrease\_inf($v,c$);\cr
  275. \+     &      &     &      &     &    &\ $\}$\cr
  276. \+     &      &     &      &\ $\}$ /$*$ forall\_adj\_edges $*$/\cr
  277. \smallskip
  278. \+     &      &\ $\}$ /$*$ while $*$/\cr
  279. \smallskip
  280. \+$\}$\cr
  281.  
  282. \vfill\eject
  283.  
  284. {\bf Bellman/Ford Algorithm}
  285.  
  286. \#include $<$LEDA/graph.h$>$\nl
  287. \#include $<$LEDA/queue.h$>$
  288. \smallskip
  289. {\bf declare}(queue,node)
  290. \smallskip
  291. \cleartabs
  292. \+bool BELLMAN\_FORD(&$graph\&\ G,\ node\ s,\ edge\_array(int)\&\ cost$,\cr
  293. \+                   &$node\_array(int)\&\ dist,\ node\_array(edge)\&\ pred$)\cr
  294. \+\cleartabs
  295.   $\{$ \ 
  296.     &node\_array(bool) $in\_Q(G,false)$;\cr
  297. \+  &node\_array(int)  $count(G,0)$;\cr
  298. \smallskip
  299. \+  &int $n = G$.number\_of\_nodes();\cr
  300. \+  &queue(node) $Q(n)$;\cr
  301. \smallskip
  302. \+  &node $u,v$;\cr
  303. \+  &edge $e$;\cr
  304. \+  &int  $c$;\cr
  305. \smallskip
  306. \+  &\Forallnodes($v,G$) \ &$\{$ &$pred[v] = 0$;\cr
  307. \+  &                      &     &$dist[v] =  infinity$; \cr
  308. \+  &                      &\ $\}$\cr
  309. \+  &\cleartabs
  310.      $dist[s] = 0$;\cr
  311. \+  &$Q$.append($s$);\cr
  312. \+  &$in\_Q[s] = true$;\cr
  313. \smallskip
  314. \+  &while (!$Q$.empty())\cr
  315. \+  &\ \ \ &$\{$ &$u = Q$.pop();\cr
  316. \+  &      &     &$in\_Q[u] = false$;\cr
  317. \smallskip
  318. \+  &      &     &\If ($++count[u] > n$)  {\bf return} false;\quad //negative cycle\cr
  319. \smallskip
  320. \+  &      &     &\Foralladjedges($e,u$) \cr
  321. \+  &      &     &\ \ \ &$\{$ &$v$ = $G$.target($e$);\cr
  322. \+  &      &     &      &$c = dist[u] + cost[e]$;\cr
  323. \smallskip
  324. \+  &      &     &      &\If ($c < dist[v]$) \cr
  325. \+  &      &     &      &\ \ &$\{$ &$dist[v] = c$; \cr
  326. \+  &      &     &      &    &     &$pred[v] = e$;\cr
  327. \+  &      &     &      &    &     &\If (!$in\_Q[v]$)  \cr
  328. \+  &      &     &      &    &     &\ \ &$\{$ &$Q$.append($v$);\cr
  329. \+  &      &     &      &    &     &    &     &$in\_Q[v]=true$;\cr
  330. \+  &      &     &      &    &     &    &\ $\}$\cr
  331. \+  &      &     &      &    &\ $\}$\cr
  332. \+  &      &     &      &\ $\}$ /$*$ forall\_adj\_edges $*$/\cr
  333. \+  &      &\ $\}$ /$*$ while $*$/\cr
  334. \+  &{\bf return} true;\cr
  335. \+\ $\}$\cr
  336. \vfill\eject
  337.  
  338. {\bf All Pairs Shortest Paths}
  339.  
  340. \#include $<$LEDA/graph.h$>$
  341. \medskip
  342. \cleartabs
  343. \+void all\_pairs\_shortest\_paths(graph\& $G$, &edge\_array(real)\& $cost$,\cr
  344. \+                                              &node\_matrix(real)\& $DIST$)\cr
  345. \cleartabs 
  346. \+$\{$\ &\cr
  347. \+      &// computes for every node pair $(v,w)$ $DIST(v,w)$ = cost of the least cost\cr
  348. \+      &// path from $v$ to $w$, the single source shortest paths algorithms BELLMAN\_FORD\cr
  349. \+      &// and DIJKSTRA are used as subroutines\cr
  350. \smallskip
  351. \+      &edge $e$;\cr
  352. \+      &node $v$;\cr
  353. \+      &real $C = 0$;\cr
  354. \smallskip
  355. \+      &{\bf forall\_edges}($e,G$) $C += fabs(cost[e]$);\cr
  356. \+      &node $s = G$.new\_node(); \hskip 3truecm         & // add $s$ to $G$\cr
  357. \+      &{\bf forall\_nodes}($v,G$) $G$.new\_edge($s,v$); & // add edges ($s,v$) to $G$\cr
  358. \smallskip
  359. \+      &node\_array(real) $dist1(G)$;\cr
  360. \+      &node\_array(edge) $pred(G)$;\cr
  361. \+      &edge\_array(real) $cost1(G)$;\cr
  362. \+      &{\bf forall\_edges}($e,G$) 
  363.                  $cost1[e] = (G$.source$(e)==s)$ ? $C : cost[e]$;\cr
  364. \smallskip
  365. \+      &BELLMAN\_FORD($G,s,cost1,dist1,pred$);\cr
  366. \smallskip
  367. \+      &$G$.del\_node($s$);                              & // delete $s$ from $G$\cr
  368. \+      &edge\_array(real) $cost2(G)$;\cr
  369. \+      &{\bf forall\_edges}($e,G$) $cost2[e] = dist1[G.source(e)] + cost[e] - dist1[G.target(e)]$;\cr
  370. \smallskip
  371. \+      &{\bf forall\_nodes}($v,G$)  DIJKSTRA($G,v,cost2,DIST[v],pred$);\cr
  372. \smallskip
  373. \+      &{\bf forall\_nodes}($v,G$)\cr
  374. \+      &\quad {\bf forall\_nodes}($w,G$) $DIST(v,w) = DIST(v,w) - dist1[v] + dist1[w]$;\cr
  375. \+ $\}$\cr
  376.  
  377. \vfill\eject
  378.  
  379.  
  380. {\bf Minimum Spanning Tree}
  381.  
  382.  
  383. \#include $<$LEDA/graph.h$>$
  384. \medskip
  385. \+edge\_array(real)$*$ $C$;\cr
  386. \smallskip
  387. \+int cmp\_edges($edge\&\ e1,\ edge\&\ e2$)\cr
  388. \+$\{$ {\bf return} $(*C)[e1] - (*C)[e2]$; $\}$\cr
  389. \medskip
  390. \cleartabs
  391. \+void MIN\_SPANNING\_TREE(graph\& $G$, edge\_array(real)\& $cost$, list(edge)\& $EL$)\cr
  392. \+$\{$\ \ &\cr 
  393. \+       &node $v,w$;\cr
  394. \+       &edge $e$;\cr
  395. \+       &node\_partition $Q(G)$;\cr
  396. \smallskip
  397. \+       &list(edge) $OEL$ = $G$.all\_edges();\cr
  398. \+       &$C = \&cost$;\cr
  399. \+       &$OEL$.sort($cmp\_edges$);\cr
  400. \smallskip
  401. \+       &$EL$.clear();\cr
  402. \+       &{\bf forall}($e,OEL$)\cr
  403. \+       &\ \ \ &$\{$ &$v = G.source(e)$;\cr
  404. \+       &      &     &$w = G.target(e)$;\cr
  405. \+       &      &     &{\bf if} ($!(Q$.same\_block($v,w$))\cr
  406. \+       &      &     &\ \ &$\{$ & $Q$.union\_blocks($v,w$);\cr
  407. \+       &      &     &    &     & $EL$.append($e$);\cr
  408. \+       &      &     &    &\ $\}$\cr
  409. \+       &      &\ $\}$\cr
  410. \+\ $\}$\cr
  411.  
  412. \vfill\eject
  413.