HOME > ソフトウェアパッケージ > 数式処理/開発環境/ライブラリ > LEDA (レダ) > 製品概要
新規購入お見積
LEDA (レダ)
製品概要

LEDA 製品概要

LEDA は、独マックスプランク研究所で開発されたオブジェクト指向の C++ クラスライブラリです。『Library of Efficient Data types and Algorithms(効率的なデータ型とアルゴリズムのライブラリ)』の頭文字をとってその名が付けられました。LEDA は、「アルゴリズム+ LEDA = プログラム」の実現を目指したソフトウェア・ライブラリですが、単なるライブラリでなく、新たな高級言語とも見なすことができるものです。LEDA は、グラフ理論、ネットワーク問題、幾何学計算、組合せ最適化といった分野で利用される広範なアルゴリズムを提供します。

Professional Edition:

  • 対象者:
    一般企業の研究開発部門に従事される方、営利を目的とする機関に従事される方、一般企業の研究部門、一般ユーザーを含めたソフトウェアの自由な配布を希望される方、営利を目的とする組織や企業と共同で研究されている大学の研究部門、または政府機関。
  • 機能:
    グラフアルゴリズム
    圧縮および暗号アルゴリズム
    文字列配置
    幾何アルゴリズム
    曲線幾何
    新しいデータ型とアルゴリズムへのアクセス

Research Edition:

  • 対象者:
    教育目的で LEDA の使用を希望される大学の学部、研究目的で LEDA の使用を希望される大学の学部、他の研究部門に限定したソフトウェアの配布を希望される大学の学部
  • 機能:
    グラフアルゴリズム
    圧縮および暗号アルゴリズム
    文字列配置
    幾何アルゴリズム
    曲線幾何
    新しいデータ型とアルゴリズムへのアクセス

Free Edition:

  • 対象者:
    特に制限はありません。一般企業、非営利組織、大学、および個人ユーザーなど。
  • 機能:
    数値型、コンテナ型、アルゴリズムの開発、基礎データ型

LEDA 機能概要

技術的クオリティ

  • LEDA は、効率的で汎用性の高いデータ構造とアルゴリズムを提供します。アルゴリズムは、ユーザー定義又は問題に固有のデータによるパラメータ化が可能です。
  • LEDA は、データ型の時間と空間の効率を高める独自のメモリ管理機能を備えています (必要な場合はスイッチをオフに可能)。
  • LEDA は、任意精度の数値データ型はもちろん、データ構造のための効率的なイテレータを提供します。
  • 結果の正確さは常に保証されています。幾つかのアルゴリズムは、数学的法則を利用した短くて分かりやすいテストルーチンによってその結果を確認できます。
  • エラーハンドリングは、C++ の例外処理又は標準エラー出力を経て実行されます。
  • LEDA では、種々のアプローチを用いて、計算誤差を 0 または 最小にする配慮がなされています。
  • LEDA は、すべての一般的な C++ コンパイラや Windows、Linux および UNIX といったオペレーティングシステムに対応しています。

機能的なクオリティ

  • LEDA には、数値的に正確な幾何学アルゴリズム(convex hull、デローニー三角分割、線分の交点アルゴリズム、ポリゴンにおけるブール演算、ミンコフスキー和など多数)、コンテナ・データ型(list、array、map、dictionary、priority queue、stack、queue、set、dynamic tree 等)、および、基本データ型(検索やソートアルゴリズム等)が含まれます。
  • LEDA は、スタティックグラフのためのストレージおよびキャッシュ効率の高い実装はもちろん、イテレータ概念を実現する利用しやすいグラフデータ型を提供します。
  • LEDA は、広範にわたるグラフおよびネットワークアルゴリズムを提供します。アルゴリズムには、深さ優先探索 (depth-first search)、幅優先探索(breadth-first search)、最短経路(shortest paths)、最小全域木(minimal spanning trees)、マッチング(matching)、重み付きマッチング(weighted matching)、ネットワークフロー、平面性判定(planarity testing)、グラフレイアウトなどが含まれます。ネットワークアルゴリズムは、それらが使用する数値型 (int, double, integer, rational) でパラメータ化できます。int や double のような数値的に不正確な数値型の場合、このアルゴリズムは、丸めの誤差(rounding errors)と数値のオーバーフローを自動的に検出しますので、結果の正確さは常に保証されたものとなります。
  • 得られた結果は、結果の正確さが確認されても、チェックルーチンによって補正され、統合されます。
  • LEDA のクラスとアルゴリズムはすべて詳細にドキュメント化されています。

メリットと利点

  • 使い易さ:
    LEDA は、日常の開発工程でも利用できるように使いやすく作られています。LEDA は、直感的なクラスインターフェースを提供します。クラス名、関数名、アルゴリズム名は、統一的に規格化され文書化されています。
  • 再利用可能性:
    LEDA のコードは、再利用が可能です。開発に掛かる時間はきわめて少なく済み、プロトタイプを迅速に作成することができます。
  • 効率性:
    LEDA は、広範にわたる効率的なアルゴリズムを提供します。それらの多くは、「漸近的に最適(asymptotically optimal)」であることが証明されています。LEDA は、他のライブラリと比較しても優れた結果をもたらします。先進のアルゴリズム的方法論を採用し、標準アルゴリズムとデータ構造を効率的に実装すれば、新たな価値と技術革新が生み出されます。
  • 信頼性:
    実装されたアルゴリズムは信頼性があり、縮重したインプットや問題の事例にも利用できます。複数カーネルを提供することにより、有限精度の演算の際に生じる問題も防止されます。LEDA は、多数のユーザーによる使用はもとより、信頼できるオブジェクト指向の開発工程のあいだにも十分にテストされています。
  • 正確さのチェック:
    アルゴリズム的な結果はすべて正しく補正されます。加えて、LEDA は、ランタイムチェックを行います。
  • 拡張性:
    LEDA は、パラメータの多型 (parametric polymorphism) によって容易に拡張することができます。
  • 独立性:
    LEDA は、ほとんどの C++ コンパイラ を使用可能な Windows、UNIX、Linux といった様々なオペレーティングシステムで動作します。LEDA は、MFC や STL といったソフトウェアライブラリとは独立していますので、プロダクトの連続性や一貫性を保てるという点で優れています。
  • サポート:
    LEDA ユーザーフォーラムは、世界中の LEDA ユーザーにアルゴリズムや LEDA に関する問題や機能についての議論の場を提供します。このフォーラムでは、LEDA サポートチームからのサポート情報が得られることもあります。

サンプルアプリケーション:

  • サンプル・デモ
    二分木ソート、線分の交差 (Sweep 法 他)、一般ポリゴン (穴明きポリゴン) 、最短経路、最小全域ツリー 、最小カット、最小フロー、最大マッチング、5色問題など、LEDA CD には、アルゴリズムを理解するための豊富なサンプルデモとソースコードが備わっています。

  • myLEDA.ppt とサンプルアプリケーション
    パワーポイントによる解説と関連するサンプルアプリケーションを実行できます。