現在の Graph のデータ構造は、辺と頂点との関係をメモリへのオーバーヘッド軽減の観点から隣接リストを改変した方式で管理しているが、これによって Vertex 及び Edge に隣接/接続情報が分散し、辺と頂点セットで削除する場合にはおよそ O(V^2+VE) の計算量を要してしまう。すなわち、辺や頂点の削除には以下のような処理が伴う:
- Graph.vertices 内の全要素を走査し、Vertex.adj_vertices 及び Vertex.connected_edges 内に含まれる削除対象への参照を削除する
- Graph.vertices 及び Graph.edges 内から削除対象のインスタンスを削除する
- Graph.vertices 内の Vertex.index を更新する
しかし、これらは Vertex.adj_vertices や Vertex.connected_edges を集合で管理することで O(V+E) にまで改善できるかもしれない。更に Graph.vertices, Graph.edges も集合で扱うことができれば O(1) での操作が可能になるかもしれないが、辺の追加や隣接行列への変換が Graph.vertices の順序構造に依存している以上実装は難しい（と思われる）。
現在の Graph のデータ構造は、辺と頂点との関係をメモリへのオーバーヘッド軽減の観点から隣接リストを改変した方式で管理しているが、これによって Vertex 及び Edge に隣接/接続情報が分散し、辺と頂点セットで削除する場合にはおよそ O(V^2+VE) の計算量を要してしまう。すなわち、辺や頂点の削除には以下のような処理が伴う:
しかし、これらは Vertex.adj_vertices や Vertex.connected_edges を集合で管理することで O(V+E) にまで改善できるかもしれない。更に Graph.vertices, Graph.edges も集合で扱うことができれば O(1) での操作が可能になるかもしれないが、辺の追加や隣接行列への変換が Graph.vertices の順序構造に依存している以上実装は難しい（と思われる）。