Cygwin 導入時の setup.ini と setup.bz2 に関する注意 (2013/8/28)

はじめに

最近、 Cygwin の setup.exe に32 bit 版と64 版のものが用意されたようで、
その影響で setup.ini と setup.bz2 の場所が変わり、エラーが生じているようです。

変更前: $mirror/setup.ini, $mirror/setup.bz2

変更後:
32 bit 版: $mirror/x86/setup.ini, $mirror/x86/setup.bz2
64 bit 版: $mirror/x86_64/setup.ini, $mirror/x86_64/setup.bz2

ただし、$mirror はミラーサイトの URL です。

いくつか解決法が分かったので、ここに情報元と併せて記します。
また、 apt-cyg という素晴らしいパッケージ管理システムを覚えたので、上記に付随するエラー対策とともに記します。
当方の環境は 32 bit なので、64 bit の方は適宜読み替えて頂けると幸いです。

新しい setup.exe

数か月前に Cygwin を再インストールして、久しぶりに setup.exe を起動したところ、
なぜかうまく動きませんでした。

そこで、再度公式ページから setup.exe を取得することにしました。
公式ページ: http://cygwin.com/install.html
すると、驚いたことに、32 bit 版の setup-x86.exe, 64 bit 版の setup-x86_64.exe という
新しい setup.exe がダウンロードできるようでした。
僕の環境では setup-x86.exe により、上手く再インストールできました。


apt-cyg との出会い

それから 3 日後、何気なくツイッターをしていたら、手さん (@myg_ さん) のツイートで、
「apt-cyg」というパッケージ管理システムが、最近インストール時にエラーを起こしているという情報を得ました。

まず、僕自身、apt-cyg は初耳で衝撃を受けました。おそらく、ネーミングから apt-get みたいなものだろうな
というのは分かるんですが、Cygwin にもこの種のツールがあることに衝撃を受けました。
迷わず、即座に、下記 URL を参考にインストールすることにしました。
Cygwinのapt-cyg, http://kkayataka.hatenablog.com/entry/2013/05/03/220854
apt-cyg の導入自体は大変すんなりいきました。apt-get に似た使用感、素晴らしいものがありました。
ただ、ここで、 setup.ini のエラーでうまく apt-cyg からインストールができませんでした。

色々探していると、下記 URL を見つけました。
cygwinで「`setup.ini' というファイルはありません。 Error updating setup.ini, reverting」の対処法,
http://qiita.com/DQNEO/items/f49d5a534eee6c3352a8

上記の修正個所において、setup.bz2 と setup.ini を取ってくる際のディレクトリ名の
x86_64」を「x86」にすることで、僕の環境でも apt-cyg が上手く動作しました。
そして、先に書いた、新しい setup.exe に 32 bit 版と 64 bit 版が用意されたこととつながりました。

GitHub を使い始めました。

4 年前にアカウントを取得して放置していた GitHub を使い始めました。

練習用に、K&R の邦訳の p92 (Chap.4, §4.3) より、逆ポーランド電卓プログラムを、
オライリーC++: The Core Language を参考に、
C++ のクラスを用いて書き換えたコードを書いて GitHub に上げました。

https://github.com/salmonsnare/test/blob/master/reverse_poish.cc

ヒープソートの実装

はじめに

C++ を勉強したり、久々にコードを書いたりしている経緯で、
練習用に、[Cormen+Leiserson+Rivest+Stein 01] Introduction to Algorithms 2nd edition の Chap. 6 から、
ヒープソートを実装したので貼り付けました。



サブルーチンの切り分けは、
pp127〜142 に記載の擬似コードにできるだけ忠実にしました。
エレガントで新しいデバッグ技法をほとんど存じ上げない為、
「cout」がデバッグ用に頻出しております。



main 関数内に「/* */」のコメントが膨大にありますが、
これは関数それぞれのテスト用です。
こちらも、エレガントで新しいテスト技法をほとんど存じ上げない為、
こういうテストをしております。



課題

  • エレガントで新しいデバッグ技法とテスト技法を習得する。
  • しっかりしたコーディングスタイルを身に着ける。

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>

using namespace std;

#define INFTY 99999

/* prototype declarations */
int parent(int);
int left(int);
int right(int);

void hsort(int []);
void max_heapify(int [], int);
void build_max_heap(int []);
void swap(int [], int, int);

int heap_maximum(int []);
int heap_extract_max(int []);

void heap_increase_key(int [], int, int);
void max_heap_insert(int[], int);

void build_max_heap_p(int []);

int heap_size = 4;

/* a main function */
main()
{
  int v[5] = {2, 3, 5, 1, 4};
  int i;

  /* heap sort
  hsort(v);
  for (i = 0; i <= 4; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap and heap extract max
  build_max_heap(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";
  
  cout << "heap_extract_max = " << heap_extract_max(v) << "\n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap and increase key and insert key
  build_max_heap(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";
  
  heap_increase_key(v, 4, 8); 
  cout << "heap_increase_key 3 to 8 \n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";

  max_heap_insert(v, 3);
  cout << "insert 3 \n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap' */

  cout << "input \n";

  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";

  cout << "build_max_heap' \n";
  build_max_heap_p(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";

  return 0;
}

void hsort(int v[])
{
  int length_v = 4;
  int i, j;
  
  build_max_heap(v);
  cout << "build max heap has done.\n\n";

    for (i = 0; i <=4; i++)
    cout << v[i] << " ";

  cout << "\n";
  cout << "heap_maximum = " << heap_maximum(v) << "\n";

  cout << "a main routine of a heap sort starts.\n\n";
  
  for (i = length_v; i >= 2; i--) {
    cout << "length_v are down to 2. Now i = " << i << "\n";
    swap(v, 0, i);
    cout << "swap(v, 0, i): i = " << i << "\n";
 
    for (j = 0; j <= heap_size; j++){
    cout << v[j] << " ";
    }
    cout << "\n";

    heap_size--;
    max_heapify(v, 0);
  }
}

void max_heapify(int v[], int i)
{
  int l = left(i);
  int r = right(i);
  int largest;

  if ((l <= heap_size) && (v[l] > i)){
    largest = l;
    cout << "a largest is left:" << l << "\n";  
  }
  else {
    largest = i;
    cout << "a largest is i:" << i << "\n";  
  }
  if ((r <= heap_size) && (v[r] > v[largest])){
    largest = r;
    cout << "a largest is right:" << r << "\n";  
  }
  if (largest != i){
    cout << "Since a largest is not i, swap and max_heapify:" << i <<"\n";  
    swap(v, i, largest);

    for (i = 0; i <=4; i++)
    cout << v[i] << " ";

  cout << "\n";

  cout << "Now, max_heapify recursively calls max heapify.\n";

    max_heapify(v, largest);
  }
}

void build_max_heap(int v[])
{
  int length_v = 4;
  int i;

  for (i = int(floor(length_v / 2) - 1); i >= 0; i--){
    cout << "build max heap: i = " << i << " max heapify starts.\n";
    max_heapify(v, i);
    cout << "\n\n";
  }
}

void swap(int v[], int i, int j)
{
  int temp; 

  temp = v[i];
  v[i] = v[j];
  v[j] = temp;
  cout << i << " and " << j << " are swapped. \n";
}

int parent(int i)
{
  cout << "a parent is " << int(floor((i - 1) / 2)) << "\n"; 
  return int(floor((i - 1) / 2));
}

int left(int i)
{
  cout << "a left is " << 2 * i + 1 << "\n"; 
  return 2 * i + 1;
}

int right(int i)
{
  cout << "a right is " << 2 * i + 2 << "\n"; 
  return 2 * i + 2;
}

int heap_maximum(int v[])
{
  return v[0];
}

int heap_extract_max(int v[])
{
  int max;

  if (heap_size < 0) {
    cout << "heap underflow \n";
  }

  max = v[0];
  v[0] = v[heap_size];
  heap_size--;
  max_heapify(v, 0);
  return max;
}

void heap_increase_key(int v[], int i, int key)
{
  if (key < v[i]) {
    cout << "new key is smaller than current key\n";
  }
  v[i] = key;
  while ((i > 0) && v[parent(i)] < v[i]) {
    swap(v, i, parent(i));
    i = parent(i);
  }
}

void max_heap_insert(int v[], int key)
{
  heap_size++;
  v[heap_size] = -INFTY;
  heap_increase_key(v, heap_size, key);
}

void build_max_heap_p(int v[])
{
  int i;

  heap_size = 0;
  for (i = 1; i <= 4; i++){
    max_heap_insert(v, v[i]);
  }
}

組合せ最適化の定本

組合せ最適化の定本はいくつかあるようですが、
いろんな方にオススメを伺って購入したところ、
下記 3 冊がお気に入りです。

Theory of Linear and Integer Programming (Wiley Series in Discrete Mathematics & Optimization)

Theory of Linear and Integer Programming (Wiley Series in Discrete Mathematics & Optimization)

Combinatorial Optimization (Algorithms and Combinatorics)

Combinatorial Optimization (Algorithms and Combinatorics)

Submodular Functions and Optimization, Volume 58, Second Edition (Annals of Discrete Mathematics)

Submodular Functions and Optimization, Volume 58, Second Edition (Annals of Discrete Mathematics)

グラフ理論の資料について

下記の記事をご参照ください。

無向グラフ http://d.hatena.ne.jp/salmonsnare/20090313/1236942950
有向グラフ http://d.hatena.ne.jp/salmonsnare/20100830/1283154201

マトロイドの資料について

下記の記事をご参照ください。

http://d.hatena.ne.jp/salmonsnare/20090314/1237026194

Cygwin からC++ のグラフライブラリ LEMON をインストール

CMake を用いたインストールをした。
詳細は http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide を参照されたい。

インストールの際につまづいた点

ソースファイルのディレクトリ中で build (適当な名前でよい)
ディレクトリを作成しその中で、

cmake ..

と入力した。
cmake 自体はうまく通り、

make; make install;

の後、

g++ -O2 001.cc -lemon

コンパイルを試みる。
しかし、途中で ld がエラーを吐く。
対策として、build ディレクトリ内で

make check

を行い、再度コンパイルをすると通った。

簡単なコードの例

チュートリアル (http://lemon.cs.elte.hu/pub/tutorial/a00011.html) のコードを簡略化した以下のコードを作成しコンパイル

#include <iostream>
#include <lemon/list_graph.h>

using namespace lemon;
using namespace std;

int main()
{
  ListDigraph g;

  ListDigraph::Node u = g.addNode();
  ListDigraph::Node v = g.addNode();

  cout << countNodes(g) << " vertices " << endl;

  return 0;
}

ListDIgraph g; で空グラフ (頂点も辺も存在しないグラフ) g を生成。
ListDigraph::Node u = g.addNode(); でグラフ g に頂点 v を付加。
上位のコードの例だと、頂点2個のみからなるグラフを構成したことになる。

出力結果は以下。

2 vertices

Webページ

[@it][Hagiwara 05] 次世代開発基盤技術“Software Factories”詳解, http://www.atmarkit.co.jp/fdotnet/softfactory/index/
内容: ソフトウェア・サイエンスとソフトウェア工学の成果を生かす「ソフトウェア工業化」というコンセプトのもとで、様々なトピックを紹介


[international conference] http://requirements-engineering.org/
内容: 要求工学の国際学会のサイト


[introduction][Yamamoto] http://www.bcm.co.jp/site/youkyu/index.html
内容: 要求工学についての連載