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 版が用意されたこととつながりました。

勉強ノートの置き場

勉強ノートとして、はてなダイアリーを主に使ってたんですが、
今後はこちらに PDF にしたものをアップロードします。

salmonsnare のノート, https://sites.google.com/site/salmonsnare/

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)

Combinatorial Optimization (Algorithms and Combinatorics)

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
内容: 要求工学についての連載