search

zer0-star / Nim-ACL

ACL (AtCoder Library) implementation in Nim
Creative Commons Zero v1.0 Universal
22 stars 3 forks source link

グラフの多様化 #38

Open chaemon opened 3 years ago

chaemon commented 3 years ago

グラフのデータ構造について以下のようなものを考えており、dijkstra等のグラフ処理はできるだけすべての場合に対応させたいです。（すべてのアルゴリズムに対応させるのが結構大変。。。）

  1. 整数のノード, 配列による隣接ノード(達成)
  2. 整数に限らないノード, 配列による隣接ノード, 整数のid関数を指定(達成)
    • id関数によってノードの一次元配列での管理が可能
    • idの逆関数が必要かも。。。
  3. 整数に限らないノード, 関数による隣接ノード, 整数のid関数を指定(達成)
    • 隣接点は到達したときにはじめて呼ばれるため、最初から配列を用意する必要がない。各種のアルゴリズムで到達しない点の分だけ高速化が期待される。
  4. 整数に限らないノード, イテレータによる隣接ノード, 整数のid関数を指定(達成)
    • 関数指定と似ているがイテレータの方が指定がしやすい。
    • イテレータはclosureでないとだめそう。closureのイテレータのリセットはdeepCopyでやった（これが最善か？）。しかし遅いかも？
  5. 整数に限らないノード, 関数・イテレータによる隣接ノード, idなし(未達)
    • ノードの構造が複雑でidを振ることが難しい場合に使うことを想定
    • ノードはTableで管理する。その際の性能低下は許す