トップ > C++ > C++の練習として、グラフを表わすようなクラスとかを作ってみた

C++の練習として、グラフを表わすようなクラスとかを作ってみた

C++

土曜日にid:mickey24に叩かれる予定地のところ。墓場予定地。事前空爆も歓迎。

グラフにEdgeとArchを与えてあげると、グラフクラスのインスタンスを生成。始点と終点を入力するとそこまでの経路を木構造で表示する、みたいなプログラムです。最短路はどれか、とかはまだ作ってない。あと木の中に目的地に行きつかないものとかも混っているので、その辺を切ってあげないといけない。

対象として考えているグラフは下のような有向グラフ。


Quartz 2 [*]
igraphを使って実質2行でplotした。

install.packages("igraph")
library(igraph)
g <- graph( c(0,1, 1,2, 1,3, 2,0, 2,3, 2,4, 3,4, 3,5, 4,1, 4,5), directed=TRUE ) 
plot(g)

で、路を木構造を使って表示するとかそんなプログラムになってます。出力結果はこんな感じ。

/Users/yasuhisa/cpp% ./a.out
Added Edge and Arch to Graph...
Show the elements of Edge...
v0
v1
v2
v3
v4
v5
Show the elements of Arch...
v0 -> v1
v1 -> v2
v1 -> v3
v2 -> v0
v2 -> v3
v2 -> v4
v3 -> v4
v3 -> v5
v4 -> v1
v4 -> v5
Show the path...
Search the route from v0 to v4
v0
 v1
  v2
  v3
   v4
Search the route from v0 to v2
v0
 v1
  v2
Search the route from v0 to v3
v0
 v1
  v2
  v3
Search the route from v0 to v5
v0
 v1
  v2
  v3
   v4
   v5

悩んだところ

Cあんまり分かってない状態で、C++を勉強しているので色々つまづいた。なんか色々悩んだところを書いておきたい。

  • 経路を保持するのに木構造がいいかも、というのに気づくのに一日かかった。死にたい
  • 初期化するためのコンストラクタでつまづいた
    • Treeのparentを初期化するのにTreeで初期化して、という無限ループになっていた
    • こういうのの初期化はNULLでいいのかな
  • STLのiteratorの使い方は大分慣れてきた
  • 再帰構造になっているものに対してのdebugがあまりよく分かっておらず、無駄に時間を浪費した。なんかいい方法はないものか
    • gdb??
  • Rubyのようにattrに対するsetter、getterをわざわざ作らなくてもいい言語というのはいいなーと思うなどした
  • 木構造においてのポインタの重要性というのを理解した
    • 木構造から取り除く、みたいなときとかコピーはポインタがやりやすい
  • 再帰するような関数を作るとき、スタートのときだけ引数が違うようにしたい、っていうのはどういう風にするのがいいのかな
    • 関数内関数でやるのがいいのか、それともprivateな関数でやるのがいいのか
    • そもそも関数内関数をC++でできるのか
  • 「(*approached).find*1.getName())」みたいな感じのプログラミングになってしまって結構めんどくさく感じる
    • 「*」は仕方ない、という感じのものなのか、それとも設計が悪いのか
  • 再帰が深すぎるとsegmentation faultする、ということがあるのか
  • bus errorってなんなの?
  • backtraceのframeってどういうものなのか
  • リファレンスと(生の)ポインタの違い?

プログラム本体

header fileとかmainとかcppで分割したほうがいいのかなーと思いつつ、面倒なのでone fileでやってしまった。後々namespaceで問題が起きそうな気はしている。

#include <string>
#include <set>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

class Tree
{
public:
  Tree(string name) {
	this->name = name;
	this->parent = NULL;
  };
  virtual ~Tree(){
  };
  void addTree(Tree *t) {
	(*t).setParent(this);
	children.push_back(t);
  };
  void removeTree(Tree *t) {
	vector<Tree*>::iterator end_it = remove(children.begin(), children.end(), t);
	children.erase(end_it, (this->children).end());
	delete t;
  };
  virtual void print(ostream *os, int indent = 0) {
	string ret = "";
	for (int i=0;i < indent;i++) {
	  ret += " ";
	}
	cout << ret << name << endl;
	for (vector<Tree*>::iterator it = children.begin(); it != children.end(); ++it) {
	  (*it)->print(os, indent+1);
	}
  };
  void validTree(Tree *t){
	// 経路だけのを返すfunction
  }
  string getName(){
	return this->name;
  }
  Tree* getParent(){
  	return this->parent;
  }
private:
  string name;
  Tree *parent;
  vector<Tree*> children;

  void setParent(Tree *t){
  	this->parent = t;
  }
};

class Leaf : public Tree
{
public:
  Leaf(string name) : Tree(name) {
	this->name = name;
  }
  virtual ~Leaf(){
  };
  void print(ostream *os, int indent = 0) {
	string ret = "";
	for(int i=0;i < indent;i++){
	  ret += " ";
	}
	*os << ret << this->name << endl;
  };
private:
  string name;
};

class Graph
{
public:
  Graph() {
  };
  virtual ~Graph() {
  };
  void addNode(string tail, string head) {
	(this->edges).insert(tail);
	(this->edges).insert(head);
	(this->delta[tail]).insert(head);
  };
  void print(ostream *os) {
	for(map<string, set<string> >::iterator hashit  = this->delta.begin(); hashit != this->delta.end(); ++hashit) {
	  for(set<string>::iterator vecit  = (*hashit).second.begin(); vecit != (*hashit).second.end(); ++vecit) {
		*os << (*hashit).first << " -> " << (*vecit) << endl;
	  }
	}
  };
  set<string> getNodeNames() {
	return this->edges;
  };
  Tree* getPaths(string a, string b) {
	Tree *t= new Tree(a);
	cout << "Search the route from " << a << " to " << b << endl;
  	return getPathsInternal(a, b, t, t);
  };
  set<string> getPathsApproached(Tree *t){
	set<string> approached;
	approached.insert((*t).getName());
	if ( (*t).getParent() == NULL) {
	} else {
	  getPathsApproachedInternal(&approached, (*t).getParent());
	}
	return approached;
  }

private:
  map<string, set<string> > delta;
  set<string> edges;

  set<string>* getPathsApproachedInternal(set<string> *approached, Tree *t){
	(*approached).insert((*t).getName());
	if ( (*t).getParent() == NULL) { // 木の頂点にきた
	  return approached;
	} else if ( (*approached).find((*(*t).getParent()).getName()) != (*approached).end() ) { // いままできたなかにあった
	  return approached;
	} else {
	  getPathsApproachedInternal(approached, (*t).getParent());
	}
	return approached;
  }
  
  Tree* getPathsInternal(string a, string b, Tree* t, Tree* previousAdded) {
	set<string> tails = this->delta[a];
	for (set<string>::iterator tail = tails.begin(); tail != tails.end(); ++tail) {
	  set<string> v = getPathsApproached(previousAdded); // 前回追加したものから辿って行ったもののvector

	  for (set<string>::iterator it = v.begin(); it != v.end(); ++it) { 
		if ( ((*it == *tail) && // 前回追加したもののなかの中に が approached にあったやつがいる
			  (*it != b)) // 目的地のところだけは例外
			 // (*it == (*previousAdded).getName()) 
			 ) { 
		  (*previousAdded).removeTree(new Tree(*tail)); // ならば削除
		  return t;
		} 
	  }
	  if ( tails.find( b ) != tails.end() ) {
		if ( *tail == b ) { // tail exactly coincides b
		  (*previousAdded).addTree(new Leaf(b));
		  return t;
		} else {
		  Tree *tmp = new Tree(*tail);
		  (*previousAdded).addTree(tmp);
		  getPathsInternal(*tail, b, t, tmp);
		}
	  } else {
		Tree *tmp = new Tree(*tail);
		(*previousAdded).addTree(tmp);
		getPathsInternal(*tail, b, t, tmp);
	  }
	}
	return t;
  };
};

int main(int argc, char *argv[])
{
  Graph g;
  set<string> heads;
  cout << "Added Edge and Arch to Graph..." << endl;

  g.addNode("v0", "v1");

  g.addNode("v1", "v3");
  g.addNode("v1", "v2");

  g.addNode("v2", "v0");
  g.addNode("v2", "v3");
  g.addNode("v2", "v4");

  g.addNode("v3", "v4");
  g.addNode("v3", "v5");

  g.addNode("v4", "v1");
  g.addNode("v4", "v5");

  cout << "Show the elements of Edge..." << endl;
  set<string> names = g.getNodeNames();
  for (set<string>::iterator it = names.begin(); it != names.end(); ++it) {
	cout << (*it) << endl;
  }
  cout << "Show the elements of Arch..." << endl;
  g.print(&cout);
  cout << "Show the path..." << endl;
  
  (*g.getPaths("v0","v4")).print(&cout);
  (*g.getPaths("v0","v2")).print(&cout);
  (*g.getPaths("v0","v3")).print(&cout);
  (*g.getPaths("v0","v5")).print(&cout);
  return 0;
}

*1:*(*t).getParent(