BPGraphクラス

簡単なところから。


STLは遅いので、クラスを作って使いやすく、速くする。
基本的には、2部グラフの2つの点集合の点をそれぞれ0,1,2,…として、辺でつながっていたら、その辺の両端を行番号と列番号とする要素を1とする行列で表現する。


2部グラフは、


bipartite graph


と呼ぶので、こう名前をつけた。
2つの点集合の大きさが、NとM。
2がついているのは点集合の大きさMのほう。
neighborは隣の点でj番目のもの。
deletevertexは関連する辺も消える。

  class BPGraph {
      int     a[N][M];
      int     degree[N];
      bool    existvertex[N];
      int     degree2[M];
      bool    existvertex2[M];
  public:
      BPGraph();
      BPGraph(CODE c);
      int size(int i) const;
      int size2(int i) const;
      bool isexist(int i) const;
      bool isexist2(int i) const;
      int getelement(int i, int j) const;
      int neighbor(int i, int k) const;
      int neighbor2(int i, int k) const;
      void addvertex(int i);
      void addvertex2(int i);
      void deletevertex(int i);
      void deletevertex2(int i);
      void addedge(int i, int j);
      void deleteedge(int i, int j);
  };


こういうクラスを作ったら、マッチングの判定が63倍速くなった。