minimum spanning treeを作る

久しぶりの技術ブログ

今回minimum spanning treeを作る目的
・対象ノードの関係をみる
・グラフをスパースにして視覚的に見やすくする！

・minimum spanning treeとは
グラフにリンクと距離が与えられたとき，重みの総和が最小になるように辺を選んで作った全域木

参考文献
[http://d.hatena.ne.jp/mickey24/20090605/1244132474:@mickey24さんのブログ]
ここを見れば完璧に理解できます

流れ
・入力

7 7 1
2 2:7.0 4:5.0 1 1
4 1:7.0 3:8.0 4:9.0 5:7.0 1 1
2 2:8.0 5:5.0 1 1
4 1:5.0 2:9.0 5:15.0 6:6.0 1 1
4 2:7.0 3:8.0 4:15.0 6:8.0 1 1
3 4:6.0 5:8.0 7:11.0 1 1
2 5:9.0 6:11.0 1 1

ノード数を1行目
2行目以降はリンク先ノードIDとその距離になってます

・処理
クラスカル法で求める

・出力

7 7 1
2 4:1 2:1 1 1
2 1:1 5:1 1 1
1 5:1 1 1
2 1:1 6:1 1 1
3 3:1 2:1 7:1 1 1
1 4:1 1 1
1 5:1 1 1

ノード数を1行目
2行目以降はリンク先ノードID(後につく：１は仕様)

プログラム
相変わらず汚いプログラムですね

#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;
int Dm;
std::vector< int > VecA;//node cluster
std::vector< vector<int> > MatA;//spanning tree
std::vector< vector<int> > MatB;//各クラスタに属するノードID

class Init{
public:
  int from,to;
  double distance;
  std::vector<Init> FT;
  bool operator<(const Init &comp) const
  {
    if(this->distance < comp.distance) {
      return true;
    }else{
      return false;
    }
  }
  void readlbl(char *fn1);
  void printValue(char *fn1);
  void calValue();
};

void Init::readlbl(char *fn1)
{
  ifstream fin;
  int i,j,sum,Dn,k,l,m,Dc;
  char c;
  double d;
  Init tmp;
  fin.open(fn1);
  if(!fin){
    cerr << "ERROR: Failed to open file" << endl;
    exit(1);
  }
  fin >> Dm >> Dn >> Dc;
  for(i=0;i<Dm;i++){
    fin >> sum;
    tmp.from = i;
    for(j=0;j<sum;j++){
      fin >> k >> c >> d;
      tmp.to = k-1;
      tmp.distance = d;
      FT.push_back(tmp);
    }
    fin >> l >> l;
  }
  fin.close();
  std::stable_sort(FT.begin(),FT.end());
}

void initValue(){
  int i,j,k;
  MatA.resize(Dm);
  MatB.resize(Dm);
  VecA.resize(Dm);
  for(i=0;i<Dm;i++){
    MatB[i].resize(1);
    MatB[i][j] = i; 
    VecA[i] = i;
  }
}

void Init::calValue(){
  int i,j,before,after;
  Init cls;
  for(i=0;i<FT.size();i++){
    if(VecA[FT[i].to]!=VecA[FT[i].from]){
      MatA[FT[i].to].push_back(FT[i].from+1);
      MatA[FT[i].from].push_back(FT[i].to+1);
      if(VecA[FT[i].to] < VecA[FT[i].from]){
	before = VecA[FT[i].from];
	after = VecA[FT[i].to];
      }else{
	before = VecA[FT[i].to];
        after = VecA[FT[i].from];
      }
      for(j=MatB[before].size()-1;j>=0;j--){
	VecA[MatB[before][j]] = after;
	MatB[after].push_back(MatB[before][j]);
	MatB[before].pop_back();
      }
      if(MatB[after].size() == Dm) break;
    }else{
      continue;
    }
  }
}


void Init::printValue(char* fn1)
{
  ofstream fout;
  int i,j,Dn;
  fout.open(fn1);
  fout << Dm << " " << Dm << " " << 1 << endl;
  for(i = 0; i < Dm; i++){
    fout << MatA[i].size() << " ";
    for(j=0;j<MatA[i].size();j++){
      fout << MatA[i][j] << ":1 ";
    }
    fout << "1 1" << endl;
  }
  fout.close();
}


int main(int argc, char **argv){
  int i;
  Init cls;
  cls.readlbl(argv[1]);
  cout << "read ok\n";
  initValue();
  cout << "init ok\n";
  cls.calValue();
  cout << "cal ok\n";
  cls.printValue(argv[2]);
  cout << "print OK\n";
}

データの詳細は明かせませんがこんなグラフが書けました．