LEDA:,,,, Kurt Mehlhorn LEDA LEDA 1 [2] LEDA Library for Efficient Data types and Algorithms LEDA LEDA C++ 1
LEDA LEDA Dijkstra( ) LEDA 2 : LEDA LEDA VORONOI() 1, LEDA voronoi demo.c LEDA 2
1: LEDA LEDA 1997 Mehlhorn Mehlhorn LEDA Nina Amenta [1] Nina S VD(S) V S L = S [ V L L L L S LEDA Mehlhorn
#include <LEDA/graph.h> #include <LEDA/map.h> #include <LEDA/float kernel.h> #include <LEDA/geo alg.h> #include <LEDA/window.h> void CRUST(const list<point>& S, GRAPH<point, int>& G) f list<point> L=S; GRAPH<circle, point> VD; VORONOI(L, VD); // add Voronoi vertices and mark them map<point, bool> voronoi vertex(false); node v; forall nodes(v, VD) f if (VD.outdeg(v) < 2)continue; point p = VD[v].center(); voronoi vertex[p] = true; L.append(p); g DELAUNAY TRIANG(L, G); forall nodes(v, G) if (voronoi vertex[g[v]]) G.del node(v); g int main() f list<point> S; window W; W.display(); point p; while(w>>p) //input points in the window S.append(p); GRAPH<point, int> G; CRUST(S, G); node v; edge e; W.clear(); forall nodes(v, G)W.draw node(g[v]); forall edges(e, G) W.draw segment(g[source(e)], G[target(e)]); W.screenshot("crust.ps"); 4
g //output the screen image to a ps file. leda wait(2.0); //wait 2 seconds return 0; 2 2: CRUST 4 LEDA 5
17 1 2 9 11 16 18 19 4 14 15 5 8 6 7 1 : 17 1 2 9 11 16 18 19 4 14 15 5 8 6 7 1 4: 1 n n n i j (i; j) (j; i) 1 0 5 6
4 7 5 11 9 0 1 6 8 1 2 5: Hopcroft Tarjan 1974 LEDA gw plan demo 6 LEDA ps, 6 7 Layout Simple Layout circular layout?? Kuratowski K ; LEDA Kuratowski 7
7 15 9 14 4 11 5 1 8 6 1 0 2 6: 5 5 LEDA LEDA, C++ LEDA http://www.mpi-sb.mpg.de/leda/download/ Unix Sparc-Solaris, Mips-Irix, i86-linux Windows Visual C++, Borland C++ /usr/local/lib /usr/local/include (make) 6 LEDA LEDA LEDA LEDA 8
5 4 6 2 7 1 8 0 4 9 15 6 7 14 11 1 2 1 7: Kuratowski 50 1500 LEDA 7 LEDA LEDA MCI(USA), Comptel(Finnland), France Telecom, ATR(Japan), Siemens(Germany), Sun Microsystems(USA), Daimler Benz(Germany), Ford(USA), Silicon Graphics(USA), DEC(USA), Minolta(USA) 8 LEDA Dijkstra LEDA Dijkstra G =(V;E), s 2 V, 9
cost: E! N, begin dist(s) =0; dist(v) =1; for v 6= s; ; end while do u dist ; od u for u e =(u; v) do dist(v)= min(dist(v), dist(u)+ cost(e)); od Dijkstra dist LEDA LEDA void DIJKSTRA(const graph &G, node s, const edge array<double>& cost, node array<double>& dist) f node pq <double> PQ(G); node v; edge e; forall nodes(v, G) f if (v == s)dist[v] = 0; else dist[v] = MAXDOUBLE; PQ.insert(v, dist[v]); g while(!pq.empty()) f node u = PQ.del min(); forall out edges(e, u) f v = target(e); double c = dist[u] + cost[e];
g g g if(c < dist[v]) f PQ.decrease p(v, c); dist[v] = c; g 9 LEDA LEDA list<int> L; CGAL LEDA LEDA short, int, long, float, double integer, bigfloat rational bigfloat bigfloat::set precision(2λm); LEDA real real x = (sqrt(17) 2) Λ (sqrt(17)+ 2); real 17 2 2 =1 LEDA real LEDA Book[] LEDA Manual[4] 11 LEDA 1. 2. : 11
. : 4. : 5. : 6. : 7. : 7.1 : Dijkstra Bellman-Ford. 7.2 :. 8. : preflow-push Goldberg-Tarjan. 9. : capacity-scaling.. :. 11. :. : 1. : 14. : Kuratowski. 15. : 16. : 17. : 1. 2. (. 4. 5. 6. 7. 8. 9.
. : 11. (CRUST). 1. 14. 15. 1 LEDA LEDA http://www-or.amp.i.kyoto-u.ac.jp /algo-eng/db/index.html [1] N. Amenta, M. Bern, and D. Eppstein: "The crust and the fi-skeleton: Combinatorial curve reconstruction," Graphics Models and Image Processing, pp.5-15 (1998). [2] (1979). [] K. Mehlhorn and S. Näher: "LEDA: A platform for combinatorial and geometric computing," Cmbridge Univ. Press (1999). [4] K. Mehlhorn et al.: "The LEDA User Manual Version 4.0," Max Planck Institute für Informatik, Germenay (1999). 1