LEDA

LEDA は、効率的なデータ構造とアルゴリズムのためのオブジェクト指向C++ クラスライブラリである。LEDA は、グラフ理論、ネットワーク問題、幾何学計算、組合せ最適化などの分野における広範なアルゴリズムを提供する。 以前は株式会社ヒューリンクスで販売されていた。

以下のエディションが用意されている。 Professional Edition 対象者 営利目的の組織や企業、それらと共同で研究を行う大学の研究部門や政府機関

Research Edition 対象者 教育・研究目的の大学

Free Edition 対象者 制限なし

特徴 豊富なデータ型と制御構造が提供されている。 幾何学アルゴリズム convex hull デローニー三角分割 線分の交点アルゴリズム ポリゴンにおけるブール演算 ミンコフスキー和 様々なコンテナ・データ型 list、array、map、dictionary、priority queue、stack、queue、set、dynamic tree 等 多くのネットワークアルゴリズムをクラスとして提供。 最短経路 深さ優先探索 幅優先探索 最小全域木 マッチング 重み付きマッチング ネットワークフロー 平面性判定 グラフレイアウト 高機能 GUI が種々のウィンドウ（グラフィック・ウィンドウ、グラフ・ウィンドウ、幾何ウィンドウ） で利用可能。 計算誤差対策のための数値型 桁数制限なしの整数型 （Integer） 有理数型 （Rational） 実数 （Real）

歴史 LEDA は、独マックスプランク研究所で開発された。『Library of Efficient Data types and Algorithms（効率的なデータ型とアルゴリズムのライブラリ）』の頭文字をとってその名が付けられた。

バージョン説明2.0.12.12.1.12.22.2.12.2.23.4ウィンドウライブラリの名前を変更3.4.13.53.5.1ループ内で要素を削除する場合の挙動の変更3.5.2全ての読み取り専用アクセスの戻り値の型をconst T&に変更3.63.6.13.73.7.13.84.1Borland C++ 5.4をサポート4.2KAI C++ 3.4、Borland C++ 5.5をサポート4.2.1Sun C++ 6.0、g++2.96をサポート4.3SunPro C++ 5.2、g++3.0、Metrowerks C++、aCCをサポート4.44.4.1ダイナミック・リンク・ライブラリのみがサポートされ、スタティック・ライブラリはサポートされなくなった。4.55.0g++3.4.xをサポート5.0.15.1g++4.0.x、Visual Studio 2005(x86)をサポート5.1.1Visual Studio 2005(x64)をサポート5.2g++4.1をサポート6.0g++4.2をサポート6.1.NET 2008をサポート6.2g++4.3.xをサポート6.2.16.2.26.3g++4.5.x、.NET 2010をサポート6.4geometry メソッド追加 graph メソッド追加

応用事例 LEDA は、テレコミュニケーション、GIS (地理情報システム) 、VLSI 設計、スケジューリング、交通計画、計算生物学、およびコンピュータを利用する様々な分野で利用されている。

セレラゲノミックス社： ヒトゲノム解読 2000年9月、セレラゲノミックス社の Dr.Knut Reinert 氏が LEDA 開発元のマックスプランク研究所を訪問し、ヒトゲノム解読問題を解決するために、LEDA を使用していることを明らかにした。 ゲノムの断片の並び替えやDNAの基礎構造の可視化、DNAの部分配列の対話的な修正のためにLEDA を使用している。

独 Mobile Connect 社：無線およびモバイル通信システムのシミュレーション RadioTracerは、無線およびモバイル通信システムの電磁特性を推定するシミュレーションプログラムである。 RadioTracerは、データの維持と格納、無線パスの格納、図の可視化のためにLEDA を使用している。

独 Softwareburo Bubel（現CAIGOS GmbH）社：地理情報システム PolyGISは、地理情報システム（GIS）である。 PolyGISは、地理情報の地域中の交差や結合の部分の誤差無し計算のためにLEDAを使用している。

独 Encom社：プロジェクト･プランニング、プロジェクトコントロール関連の開発、製品 Encom社は、各種データ構造や、タイムスケジュール、ネットワーク計画、資源配分の表現、計算、最適化のために、LEDAを使用している。

参考文献