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

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

数值算法/人工智能

开发平台：

MultiPlatform

graph_alg.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  graph_alg.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_GRAPHALG_H
  14. #define LEDA_GRAPHALG_H
  16. #include <LEDA/graph.h>
  17. #include <LEDA/node_matrix.h>
  20. /*{Manpage {graph_alg} {} {Graph Algorithms}}*/
  22. /*{Mtext
  23. bigskip
  24. This section gives a summary of the graph algorithms contained in LEDA.
  25. All algorithms are generic, i.e., they accept instances of any user defined
  26. parameterized graph type $GRAPH${tt <}$vtype,etype${tt >} as arguments.
  27. The header file {tt <}LEDA/graph_alg.h{tt >} has to be included.
  28. }*/
  31. //-----------------------------------------------------------------------------
  32. // basic graph algorithms:
  33. //-----------------------------------------------------------------------------
  35. /*{Mtext
  36. bigskip
  37. subsection{Basic Algorithms}
  39. label{Basic Algorithms}
  40. }*/
  43. bool        TOPSORT(const graph& G, node_array<int>& ord);
  44. /*{Mtext
  45. $bullet$ {bf Topological Sorting}
  47. medskip
  48. $bool$ TOPSORT($graph& G, node_array<int>& ord$)
  50. medskip
  51. TOPSORT takes as argument a directed graph $G(V,E)$. It sorts $G$ topologically 
  52. (if $G$ is acyclic) by computing for every node $v in V$ an integer $ord[v]$ 
  53. such that $1le ord[v]le |V|$ and $ord[v] < ord[w]$ for all edges 
  54. $(v,w) in E$. TOPSORT returns true if $G$ is acyclic and false otherwise.
  56. The algorithm (cite{Ka62}) has running time $O(|V|+|E|)$.
  57. }*/
  60. bool        TOPSORT1(graph& G);
  62. /*{Mtext
  63. medskip
  65. $bullet$ {bf Depth First Search}
  66. }*/
  68. list<node>  DFS(const graph& G, node s, node_array<bool>& reached) ;
  69. /*{Mtext
  70. $list<node>$  DFS($graph& G, node s, 
  71. node_array<bool>& reached$)
  73. medskip
  74. DFS takes as argument a directed graph $G(V,E)$, a node $s$ of $G$ and a 
  75. node_array $reached$ of boolean values. It performs a depth first search 
  76. starting at $s$ visiting all reachable nodes $v$ with $reached[v]$ = false. 
  77. For every visited node $v$ $reached[v]$ is changed to true. DFS returns the 
  78. list of all reached nodes.
  80. The algorithm (cite{T72}) has running time $O(|V|+|E|)$.
  81. }*/
  83. list<edge>  DFS_NUM(const graph& G, node_array<int>& dfsnum,
  84.                                     node_array<int>& compnum);
  85. /*{Mtext
  86. bigskip
  87. $list<edge>$  
  88. parbox[t]{12.5cm}{DFS_NUM($graph& G, node_array<int>&  
  89. dfsnum, node_array<int>&$ $compnum$)}
  91. medskip
  92. DFS_NUM takes as argument a directed graph $G(V,E)$. It performs a 
  93. depth first search of $G$ numbering the nodes of $G$ in two different ways. 
  94. $dfsnum$ is a numbering with respect to the calling time and $compnum$ a 
  95. numbering with respect to the completion time of the recursive calls. DFS_NUM 
  96. returns a depth first search forest of $G$ (list of tree edges).
  98. The algorithm (cite{T72}) has running time $O(|V|+|E|)$.
  99.  }*/
  102. list<node>  BFS(const graph& G, node s, node_array<int>& dist);
  103. /*{Mtext
  104. bigskip
  105. $bullet$ {bf Breadth First Search}
  107. medskip
  108. $list<node>$
  109. BFS($graph& G, node s, node_array<int>& dist$)
  111. medskip
  112. BFS takes as argument a directed graph $G(V,E)$ and a node $s$ of $G$. It 
  113. performs a breadth first search starting at $s$ computing for every visited 
  114. node $v$ the distance $dist[v]$ from $s$ to $v$. BFS returns the list of all 
  115. reached nodes.
  117. The algorithm (cite{M84}) has running time $O(|V|+|E|)$.
  118. }*/
  120. /*{Mtext
  121. bigskip
  122. $bullet$ {bf Connected Components}
  123. }*/
  125. int         COMPONENTS(const graph& G, node_array<int>& compnum);
  126. /*{Mtext
  127. $int$   COMPONENTS($graph& G, node_array<int>& compnum$)
  129. medskip
  130. COMPONENTS takes a graph $G(V,E)$ as argument and computes the connected
  131. components of the underlying undirected graph, i.e., for every node $vin V$ 
  132. an integer $compnum[v]$ from $[0dots c-1]$ where $c$ is the number of 
  133. connected components of $G$ and $v$ belongs to the $i$-th connected 
  134. component iff $compnum[v] = i$.  COMPONENTS returns $c$.
  136. The algorithm (cite{M84}) has running time $O(|V|+|E|)$.
  137. }*/
  140. int         COMPONENTS1(const graph& G, node_array<int>& compnum);
  142. int         STRONG_COMPONENTS(const graph& G, node_array<int>& compnum);
  143. /*{Mtext
  144. bigskip
  145. $bullet$ {bf Strong Connected Components}
  147. medskip
  148. $int$   STRONG_COMPONENTS($graph& G, node_array<int>& compnum
  149. $)
  151. medskip
  152. STRONG_COMPONENTS takes a directed graph $G(V,E)$ as argument and computes for 
  153. every node $vin V$ an integer $compnum[v]$ from $[0dots c-1]$ where
  154. $c$ is the number of strongly connected components of $G$ and
  155. $v$ belongs to the $i$-th strongly connected component iff $compnum[v] = i$.
  156. STRONG_COMPONENTS returns $c$.
  158. The algorithm (cite{M84}) has running time $O(|V|+|E|)$.
  159. }*/
  162. int         STRONG_COMPONENTS1(const graph& G, node_array<int>& compnum);
  164. int         BICONNECTED_COMPONENTS(const graph& G, edge_array<int>& compnum);
  166. /*{Mtext
  167. bigskip
  168. $bullet$ {bf Transitive Closure}
  169. }*/
  171. graph       TRANSITIVE_CLOSURE(const graph& G);
  172. /*{Mtext
  173. $graph$ TRANSITIVE_CLOSURE($graph& G$)
  175. medskip
  176. TRANSITIVE_CLOSURE takes a directed graph $G(V,E)$ as argument and computes 
  177. the transitive closure of $G(V,E)$. It returns a directed graph $G'(V',E')$ 
  178. with $V' = V$ and $(v,w) in E'  Leftrightarrow$ there is a path form
  179. $v$ to $w$ in $G$.
  181. The algorithm (cite{GK79}) has running time $O(|V|cdot |E|)$.
  182. }*/
  187. /*{Mtext
  188. subsection{Network Algorithms}
  190. label{Network Algorithms}
  192. Most of the following network algorithms are overloaded. They work
  193. for both integer and real valued edge costs.
  194. }*/
  196. //-----------------------------------------------------------------------------
  197. // shortest paths:
  198. //-----------------------------------------------------------------------------
  199. /*{Mtext
  200. bigskip
  201. $bullet$ {bf Single Source Shortest Paths }
  202. }*/
  205. void DIJKSTRA(const graph& G, node s, const edge_array<int>& cost, 
  206.                                             node_array<int>& dist, 
  207.                                             node_array<edge>& pred);
  208. /*{Mtext
  209. $void$ 
  210. parbox[t]{14cm}{DIJKSTRA($graph& G, node s$, $edge_array<int>$ $cost$,
  211.                  $node_array<int>$ $dist$,
  212.  $node_array<edge>$ $pred$)}
  214. smallskip
  215. $void$ 
  216. parbox[t]{14.5cm}{DIJKSTRA($graph& G, node s$, $edge_array<double>$ $cost$,
  217.                   $node_array<double>$ $dist$,
  218.                   $node_array<edge>$  $pred$)}
  220. medskip
  221. DIJKSTRA takes as arguments a directed graph $G(V,E)$, a source node $s$ and an 
  222. edge_array $cost$ giving for each edge in $G$ a non-negative cost. It 
  223. computes for each node $v$ in $G$ the distance $dist[v]$ from $s$ (cost of the 
  224. least cost path from $s$ to $v$) and the predecessor edge $pred[v]$ in the 
  225. shortest path tree.
  227. The algorithm (cite{Di59}, cite{FT87}) has running time $O(|E|+|V|log |V|)$.
  228. }*/
  231. bool BELLMAN_FORD(const graph& G, node s, const edge_array<int>& cost,
  232.                                                 node_array<int>& dist,
  233.                                                 node_array<edge>& pred);
  234. /*{Mtext
  235. bigskip
  236. $bool$ 
  237. parbox[t]{13.5cm}{BELLMAN_FORD($graph& G, node s$, 
  238.                  $edge_array<int>$ $cost$,
  239.  $node_array<int>$ $dist$,
  240.  $node_array<int>$ $pred$)}
  243. smallskip
  244. $bool$ 
  245. parbox[t]{12cm}{BELLMAN_FORD($graph& G, node s$, 
  246.                 $edge_array<double>$ $cost$,
  247. $node_array<double>$ $dist$,
  248. $node_array<edge>$ $pred$)}
  250. medskip
  251. BELLMAN_FORD takes as arguments a graph $G(V,E)$, a source node $s$ and an 
  252. edge_array $cost$ giving for each edge in $G$ a real (integer) cost. It 
  253. computes for each node $v$ in $G$ the distance $dist[v]$ from $s$ (cost of 
  254. the least cost path from $s$ to $v$) and the predecessor edge $pred[v]$ in 
  255. the shortest path tree. BELLMAN_FORD returns false if there is a negative
  256. cycle in $G$ and true otherwise
  258. The algorithm (cite{Be58}) has running time $O(|V|cdot |E|)$.
  259. }*/
  262. bool ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array<int>&  cost,
  263.                                               node_matrix<int>& dist);
  264. /*{Mtext
  265. bigskip
  266. $bullet$ {bf All Pairs Shortest Paths }
  268. medskip
  269. $bool$ 
  270. parbox[t]{12cm}{ALL_PAIRS_SHORTEST_PATHS($graph& G$,
  271.                  $edge_array<int>&$ $cost$,
  272.  $node_matrix<int>&$ $dist$)}
  274. smallskip
  275. $bool$ 
  276. parbox[t]{12cm}{ALL_PAIRS_SHORTEST_PATHS($graph& G$,
  277.                  $edge_array<double>&$ $cost$,
  278.  $node_matrix<double>&$ $dist$)}
  280. medskip
  281. ALL_PAIRS_SHORTEST_PATHS takes as arguments a graph $G(V,E)$ and an 
  282. edge_array $cost$ giving for each edge in $G$ a real (integer) valued cost. 
  283. It computes for each node pair $(v,w)$ of $G$ the distance $dist(v,w)$ from 
  284. $v$ to $w$ (cost of the least cost path from $v$ to $w$).
  285. ALL_PAIRS_SHORTEST_PATHS returns false if there is a negative cycle in $G$
  286. and true otherwise.
  288. The algorithm (cite{Be58}, cite{Fl62}) has running time $O(|V|cdot |E| + |V|^2
  289.  log|V|)$.
  290. }*/
  296. //-----------------------------------------------------------------------------
  297. // maximum flow:
  298. //-----------------------------------------------------------------------------
  300. /*{Mtext
  301. bigskip
  302. $bullet$ {bf Maximum Flow }
  303. }*/
  307. int  MAX_FLOW(graph& G, node s, node t, const edge_array<int>& cap,
  308.                                               edge_array<int>& flow);
  309. /*{Mtext
  310. $int$ 
  311. parbox[t]{11cm}{MAX_FLOW($graph& G, node s, node t$, 
  312.                  $edge_array<int>& cap$,
  313.  $edge_array<int>& flow$)}
  315. smallskip
  316. $int$ 
  317. parbox[t]{11.5cm}{MAX_FLOW($graph& G, node s, node t$, 
  318.                  $edge_array<double>& cap$,
  319.  $edge_array<double>& flow$)}
  321. medskip
  322. MAX_FLOW takes as arguments a directed graph $G(V,E)$, a source node $s$, a 
  323. sink node $t$ and an edge_array $cap$ giving for each edge in $G$ a capacity. 
  324. It computes for every edge $e$ in $G$ a flow $flow[e]$ such that the total 
  325. flow from $s$ to $t$ is maximal and $flow[e] le cap[e]$ for all edges $e$. 
  326. MAX_FLOW returns the total flow from $s$ to $t$.
  328. The algorithm (cite{GT88}) has running time $O(|V|^3)$.
  329. }*/
  332. //-----------------------------------------------------------------------------
  333. // min cost flow:
  334. //-----------------------------------------------------------------------------
  336. int MIN_COST_MAX_FLOW(graph& G, node s, node t, const edge_array<int>& cap,
  337.                                                 const edge_array<int>& cost,
  338.                                                 edge_array<int>& flow);
  339. /*{Mtext
  340. $int$ 
  341. parbox[t]{11cm}{MIN_COST_MAX_FLOW($graph& G, node s, node t$, 
  342.                  $edge_array<int>& cap$,
  343.                  $edge_array<int>& cost$,
  344.  $edge_array<int>& flow$)}
  346. medskip
  347. MIN_COST_MAX_FLOW takes as arguments a directed graph $G(V,E)$, a source 
  348. node $s$, a sink node $t$, an edge_array $cap$ giving for each edge in $G$ a 
  349. capacity, and an edge_array $cost$ specifying for each edge an integer cost. 
  350. It computes for every edge $e$ in $G$ a flow $flow[e]$ such that the total 
  351. flow from $s$ to $t$ is maximal, the total cost of the flow is minimal,
  352. and $flow[e] le cap[e]$ for all edges $e$. 
  353. MIN_CONST_MAX_FLOW returns the total flow from $s$ to $t$.
  354. }*/
  356. //-----------------------------------------------------------------------------
  357. // minimum cut :
  358. //-----------------------------------------------------------------------------
  360. // Stoer and Wagner's algorithm
  362. /*{Mtext
  363. bigskip
  364. $bullet$ {bf Minimum Cut}
  365. }*/
  367. list<node> MIN_CUT(const graph& G, edge_array<int>& weight);
  369. /*{Mtext
  370. $list<node>$ MIN_CUT($graph& G$, $edge_array<int>& weight$)
  372. medskip
  373. MIN_CUT($G$, $weight$) takes as arguments a graph $G$ and an 
  374. edge_array
  375. giving for each edge an integer weight. The algorithm
  376. (cite{SW94}) computes
  377. the cut of minimum weight and returns it as a list of nodes. It
  378. has running time
  379. $O(|V|cdot |E| + |V|^2 log |V|)$.
  380. }*/ 
  382. //-----------------------------------------------------------------------------
  383. // matchings:
  384. //-----------------------------------------------------------------------------
  386. // Edmond's algorithm
  388. /*{Mtext
  389. bigskip
  390. $bullet$ {bf Maximum Cardinality Matching}
  391. }*/
  394. list<edge> MAX_CARD_MATCHING(graph& G, int heur = 1);    
  395. /*{Mtext
  396. $list<edge>$ MAX_CARD_MATCHING($graph& G$) 
  398. medskip
  399. MAX_CARD_MATCHING($G$) computes a maximum cardinality matching of $G$, i.e., 
  400. a maximal set of edges $M$ such that no two edges in $M$ share an end point.
  401. It returns $M$ as a list of edges.
  403. The algorithm (cite{E65}, cite{T83}) has running time $O(|V|cdot |E|cdotalpha(|E|))$.
  404. }*/
  408. // Hopcroft/Karp
  410. /*{Mtext
  411. bigskip
  412. $bullet$ {bf Maximum Cardinality Bipartite Matching}
  413. }*/
  416. list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G, const list<node>& A, const list<node>& B);
  417. /*{Mtext
  418. $list{tt <}edge>$ MAX_CARD_BIPARTITE_MATCHING($graph& G$, 
  419.                $list<node>& A$,
  420.        $list<node>& B$)
  422. medskip
  423. MAX_CARD_BIPARTITE_MATCHING takes as arguments a directed graph $G(V,E)$ and
  424. two lists $A$ and $B$ of nodes. All edges in $G$ must be directed from nodes
  425. in $A$ to nodes in $B$. It returns a maximum cardinality matching of $G$.
  427. The algorithm (cite{HK75}) has running time $O(|E|sqrt{|V|})$.
  428. }*/
  431. list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G);
  433. list<edge> MAX_CARD_BIPARTITE_MATCHING1(graph& G, const list<node>& A, const list<node>& B);
  435. list<edge> MAX_CARD_BIPARTITE_MATCHING1(graph& G);
  437. /*{Mtext
  438. bigskip
  439. $bullet$ {bf Maximum Weighted Matching}
  440. }*/
  442. list <edge> MAX_WEIGHT_MATCHING (const ugraph&,
  443.                                  const edge_array<int>&);
  445. /*{Mtext
  446. $list<edge>$ 
  447. parbox[t]{12.5cm}{MAX_WEIGHT_MATCHING($ugraph& G$,
  448.    $edge_array<int>& weight$)}
  450. smallskip
  451. $list<edge>$ 
  452. parbox[t]{12.5cm}{MAX_WEIGHT_MATCHING($ugraph& G$,
  453.  $edge_array<double>& weight$)}
  455. medskip
  456. MAX_WEIGHT_MATCHING takes as arguments an undirected graph $G$ 
  457. and an edge_array giving for each edge an 
  458. integer (real) weight. 
  459. It computes a maximum weighted matching of $G$, i.e., a set of edges $M$
  460. such that the sum of weights of all edges in $M$ is maximal and no two edges 
  461. in $M$ share an end point. MAX_WEIGHT_MATCHING returns $M$ as a 
  462. list of edges.
  464. The algorithm (cite{E65}, cite{G74}, cite{L76}) has running 
  465. time $O(|V|^3)$.
  466. }*/
  468. /*{Mtext
  469. bigskip
  470. $bullet$ {bf Maximum Weight Bipartite Matching}
  471. }*/
  474. list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list<node>&A, 
  475.                                                    const list<node>&B,
  476.                                                    const edge_array<int>&);
  478. /*{Mtext
  479. $list<edge>$ 
  480. parbox[t]{12.5cm}{MAX_WEIGHT_BIPARTITE_MATCHING($graph& G$,
  481.                    $list<node>& A$,
  482.    $list<node>& B$,
  483.    $edge_array<int>& weight$)}
  485. smallskip
  486. $list<edge>$ 
  487. parbox[t]{12.5cm}{MAX_WEIGHT_BIPARTITE_MATCHING($graph& G$,
  488.                  $list<node>& A$,
  489.  $list<node>& B$,
  490.  $edge_array<double>& weight$)}
  492. medskip
  493. MAX_WEIGHT_BIPARTITE_MATCHING takes as arguments a directed graph $G$, 
  494. two lists $A$ and $B$ of nodes and an edge_array giving for each edge an 
  495. integer (real) weight. All edges in $G$ must be directed from nodes in $A$ 
  496. to nodes in $B$. 
  497. It computes a maximum weight bipartite matching of $G$, i.e., a set of edges $M$
  498. such that the sum of weights of all edges in $M$ is maximal and no two edges 
  499. in $M$ share an end point. MAX_WEIGHT_BIPARTITE_MATCHING returns $M$ as a 
  500. list of edges.
  502. The algorithm (cite{FT87}) has running time $O(|V|cdot |E|)$.
  503. }*/
  508. //-----------------------------------------------------------------------------
  509. // spanning trees:
  510. //-----------------------------------------------------------------------------
  512. /*{Mtext
  513. bigskip
  514. $bullet$ {bf Spanning Tree}
  515. }*/
  517. list<edge> SPANNING_TREE(const graph& G);
  518. /*{Mtext
  519. $list<edge>$ SPANNING_TREE($graph& G$)
  521. medskip
  522. SPANNING_TREE takes as argument a graph $G(V,E)$. It computes a spanning
  523. tree $T$ of of the underlying undirected graph, SPANNING_TREE returns the 
  524. list of edges of $T$.
  526. The algorithm (cite{M84}) has running time $O(|V|+|E|)$.
  527. }*/
  530. /*{Mtext
  531. bigskip
  532. $bullet$ {bf Minimum Spanning Tree}
  533. }*/
  535. list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<int>& cost);
  536. /*{Mtext
  537. medskip
  538. $list<edge>$ MIN_SPANNING_TREE($graph& G, edge_array<int>& cost$)
  539. }*/
  541. list<edge> MIN_SPANNING_TREE1(const graph& G, const edge_array<int>& cost);
  542. /*{Mtext
  543. smallskip
  544. $list<edge>$ MIN_SPANNING_TREE1($graph& G, edge_array<double>& cost$)
  546. medskip
  547. MIN_SPANNING_TREE takes as argument an undirected graph $G(V,E)$ and an 
  548. edge_array $cost$ giving for each edge an integer cost. 
  549. It computes a minimum spanning 
  550. tree $T$ of $G$, i.e., a spanning tree such that the sum of all edge costs
  551. is minimal. MIN_SPANNING_TREE returns the list of edges of $T$.
  553. The algorithm (cite{Kr56}) has running time $O(|E|log|V|)$.
  554. }*/
  559. //-----------------------------------------------------------------------------
  560. // planar graphs
  561. //-----------------------------------------------------------------------------
  563. /*{Mtext
  564. subsection{Algorithms for Planar Graphs}
  566. label{Algorithms for Planar Graphs}
  567. }*/
  570. /*{Mtext
  571. bigskip
  572. $bullet$ {bf Planarity Test}
  573. }*/
  575. bool PLANAR(graph&, bool embed=false);
  577. /*{Mtext
  578. $bool$ PLANAR($graph& G, bool embed=false$)
  580. medskip
  581. PLANAR takes as input a directed graph $G(V,E)$ and performs a planarity test
  582. for $G$. If the second argument $embed$ has value $true$ and $G$ is a planar 
  583. graph it is transformed into a planar map (a combinatorial embedding such that
  584. the edges in all adjacency lists are in clockwise ordering). PLANAR returns 
  585. true if $G$ is planar and false otherwise.
  587. The algorithm (cite{HT74}) has running time $O(|V|+|E|)$.
  588. }*/
  591. bool PLANAR(graph&, list<edge>&, bool embed=false);
  593. /*{Mtext
  594. $bool$ PLANAR($graph& G, list<edge>& el$)
  596. medskip
  597. PLANAR takes as input a directed graph $G(V,E)$ and performs a planarity test
  598. for $G$. PLANAR returns true if $G$ is planar and false otherwise.
  599. If $G$ is not planar a Kuratowsky-Subgraph is computed and returned in $el$.  
  600. }*/
  602. list<edge> make_biconnected_graph(graph&G);
  604. /*{Mtext
  605. bigskip
  606. $bullet$ {bf Triangulation}
  607. }*/
  609. list<edge> TRIANGULATE_PLANAR_MAP(graph&);
  610. /*{Mtext
  611. $list{tt <}edge{tt >}$ TRIANGULATE_PLANAR_MAP($graph& G$)
  613. medskip
  614. TRIANGULATE_PLANAR_MAP takes a directed graph $G$ representing a planar map.
  615. It triangulates the faces of $G$ by inserting additional edges. The list of
  616. inserted edges is returned. precond $G$ must be connected.
  618. The algorithm (cite{HU89}) has running time $O(|V|+|E|)$.
  619. }*/
  622. /*{Mtext
  623. bigskip
  624. $bullet$ {bf Straight Line Embedding}
  625. }*/
  627. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array<int>& xcoord,
  628.                                      node_array<int>& ycoord);
  629. /*{Mtext
  630. $int$ 
  631. parbox[t]{12.5cm}{STRAIGHT_LINE_EMBEDDING($graph& G$, 
  632.                  $node_array<int>& xcoord$,
  633.  $node_array<int>& ycoord$)}
  635. medskip
  636. STRAIGHT_LINE_EMBEDDING takes as argument a directed graph $G$ representing
  637. a planar map. It computes a straight line embedding of $G$ by assigning 
  638. non-negative integer coordinates ($xcoord$ and $ycoord$) in the range 
  639. $0..2(n-1)$ to the nodes. STRAIGHT_LINE_EMBEDDING returns the maximal 
  640. coordinate.
  642. The algorithm (cite{Fa48}) has running time $O(|V|^2)$.
  643. }*/
  645. int STRAIGHT_LINE_EMBEDDING2(graph& G, node_array<int>& xcoord,
  646.                                        node_array<int>& ycoord);
  649. //-----------------------------------------------------------------------------
  650. // floating point (double) versions 
  651. //-----------------------------------------------------------------------------
  654. void DIJKSTRA(const graph& G, node s, const edge_array<double>& cost, 
  655.                                             node_array<double>& dist, 
  656.                                             node_array<edge>& pred);
  658. bool BELLMAN_FORD(const graph& G, node s, const edge_array<double>& cost,
  659.                                                 node_array<double>& dist,
  660.                                                 node_array<edge>& pred);
  663. bool ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array<double>&  cost,
  664.                                               node_matrix<double>& dist);
  667. double MAX_FLOW(graph& G, node s, node t, const edge_array<double>& cap,
  668.                                                 edge_array<double>& flow);
  670. list <edge> MAX_WEIGHT_MATCHING (const ugraph&,
  671.                                    const edge_array<double>&);
  672.    
  674. list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list<node>&, 
  675.                                                    const list<node>&,
  676.                                                    const edge_array<double>&);
  680. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array<double>& xcoord,
  681.                                      node_array<double>& ycoord);
  683. int STRAIGHT_LINE_EMBEDDING2(graph& G,node_array<double>& xcoord,
  684.                                       node_array<double>& ycoord);
  687. list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<double>& cost);
  689. list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<double>& cost);
  692. #endif