タグ

グラフ理論とC++に関するDrunkarのブックマーク (1)

  • グラフライブラリ

    グラフを扱うためのオープンなクラスライブラリにはBGL(Boost Graph Library)を筆頭に優れたものがたくさんありますが,ライブラリは 導入が容易:簡単な機能は簡単に記述できること. カスタマイズが容易:ソースコードの一覧性が高いこと. ソコソコの機能でソレナリのパフォーマンス という点を目標に作成しています.特徴は以下の通りです. ノードとエッジの追加(定数時間) ノードとエッジへのインデクスを用いたランダムアクセス(定数時間) 任意のノードとエッジの削除(定数時間) ノードに隣接するノード群とその接続を媒介するエッジ群へのランダムアクセス(定数時間) ノードに隣接する特定のノード,あるいはエッジの検索(線形時間) エッジの両端に接続するノードの検索(定数時間) 有向グラフとして動作(無向グラフとしての利用も可能) 自己ループエッジ(両端が同一ノードのエッジ)と多重エッジ

  • 1