c++ - 幅優先探索（BFS）を使用した単純なグラフアルゴリズムのデバッグ

Question

単純な2次元配列で整数値のグラフの場所を検索、識別、およびマークするプログラムを構築しています。

最初の例を手作業でトレースしたところ、正確に機能しているように見えました。そうは言っても、私は自分が思っていることを実行しないコードを書いたか、手のトレースが不正確でした。

私のコードは近いと思います。デバッグの支援や一般的なスタイルなどについての考えを探しています。

最終的に、このアルゴリズムは、OCRの文字のピクセルのグラフを見つけるように変更されます。画像を処理するためのコードで物事を複雑にする前に、アルゴリズムの実装が正確であることを証明したいだけです。

入力配列は次のようになります。

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0

期待される結果は次のとおりです。

3 3 3 3 3 3
3 0 0 0 0 3
3 0 2 2 0 3
3 0 2 2 0 3
3 0 0 0 0 3
3 3 3 3 3 3

別の同様の可能性は次のとおりです。

0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

アウト：

0 3 3 3 3 3 3 0 0 0 0 0
0 3 0 0 0 0 3 0 0 0 0 0
0 3 0 2 2 0 3 0 0 0 0 0
0 3 0 2 2 0 3 0 0 0 0 0
0 3 0 0 0 0 3 0 0 0 0 0
0 3 3 3 3 3 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 3 3 3 3 3 3 3 3 3 0
0 0 3 0 0 0 0 0 0 0 3 0
0 0 3 0 2 2 2 2 2 0 3 0
0 0 3 0 0 0 0 0 0 0 3 0
0 0 3 3 3 3 3 3 3 3 3 0

基本的なルール：

1. 入力ファイルの配列サイズは、.cppファイルで定義されているGSと一致する必要があります（HはWがGSに等しい）。
2. グラフは、互いに隣接する1つ以上の「1」値として定義されます。
3. 検索は、単純なキューを使用した基本的なBFS手法を使用して実行されます。
4. グラフが見つかると、その値は「1」から「2」に更新されます。
5. グラフの最終値が決定されると、「3」の値の境界ボックスがグラフの周囲に描画されます。ボックスの最小のXは、グラフの最小のXから2を引いたものに等しく、ボックスの最小のYは、グラフの最小のYから2を引いたものに等しくなります。ボックスの最大のXは、グラフの最大のXに2を加えたものに等しく、ボックスの最大のYは、グラフの最大のYに2を加えたものに等しくなります。ボックスを描画できるように、すべてのグラフに境界線から少なくとも2行/列のバッファーがあると想定します。

この配列を処理する最新の試み：

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

この出力を生成します：

0 0 0 0 0 0 0 0
0 3 3 3 3 3 0 0
0 3 3 3 3 3 3 0
0 3 3 2 1 3 3 0
0 3 3 2 2 3 3 0
0 3 3 3 3 3 3 0
0 3 3 3 3 3 3 0
0 0 0 0 0 0 0 0

1桁のグラフはうまく機能しますが：

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

出力を生成します：

3 3 3 3 3
3 0 0 0 3
3 0 2 0 3
3 0 0 0 3
3 3 3 3 3

これが私のコードです：

#include <iostream>
#include <fstream>
#include <cstdlib>
#include "queue.h"

#define GS 8 /* GRID SIZE */

using namespace std;

void processCmdArgs (ifstream& input, int argc, char* argv[]);
void drawBoundingBox (int arr[][GS], int xLo, int yLo, int xHi, int yHi);
void checkNeighbors (int arr[][GS], bool vis[][GS], queue Q, point* p);
void print (int arr[][GS]);

int main( int argc, char* argv[] ) {

    int xLo = 0;
    int xHi = GS - 1;
    int yLo = 0;
    int yHi = GS - 1;
    ifstream input; /* filestream to read in file to parse */
    int arr[GS][GS]; /* declare array of vals to check for graph */
    bool visited[GS][GS]; /* array of bools to track progress */
    int count = 0; /* number of graphs found */
    processCmdArgs(input, argc, argv);

    /* populate array */
    for (int i = 0; i < GS; i++) {
        for (int j = 0; j < GS; j++) {
            input >> arr[i][j];
        }
    }
    input.close();

    /*init visited */
    for (int y = yLo; y < GS; y++) {
        for (int x = xLo; x < GS; x++) {
            visited[x][y] = false;
        }
    }

    /* print array */
    cout << "The array to find a graph is:\n";
    print(arr);

    /* find graph(s) in array */
    queue Q;
    for (int j = yLo; j < GS; j++) {
        for (int k = xLo; k < GS; k++) {
            if (arr[k][j] == 1) {
                count++;
                xLo = xHi = k;
                yLo = yHi = j;
                point *p = new point(k, j);
                Q.insert(p);
                delete p;
                visited[k][j] = true;
                while (!Q.isEmpty()) {
                    *p = Q.del(); /* does this really work? */
                    int x = p->getx();
                    int y = p->gety();
                    arr[x][y] = 2;
                    if (x < xLo) xLo = x;
                    if (y < yLo) yLo = y;
                    if (x > xHi) xHi = x;
                    if (y > yHi) yHi = y;
                    checkNeighbors(arr, visited, Q, p);
                }
                drawBoundingBox(arr, xLo, yLo, xHi, yHi);
            }
            else {
                visited[k][j] = true;
            }
        }
    }
    cout << "The updated array is:\n";
    print(arr);
    cout << "The number of graphs in arr is " << count << endl;

    return 0;
}
/*** END OF MAIN ***/

/*** START OF FUNCTIONS ***/
void processCmdArgs(ifstream& input, int argc, char* argv[]) {
    /* Check command-line args first to avoid accessing nonexistent memory */
    if (argc != 2) {
        cerr << "Error: this program takes one command-line argument.\n";
        exit(1);
    }
    /* Try to open the file using the provided filename */
    input.open(argv[1]);
    /* Exit with error if it doesn't open */
    if (input.fail()) {
        cerr << "Error: could not open " << argv[1] << ".\n";
        exit(1);
    }
}

void drawBoundingBox (int arr[][GS], int xLo, int yLo, int xHi, int yHi) {
    // draw a box with (lowx-2,lowy-2) as NW and
    // (highx + 2, highy + 2) as SE boundary
    /* draw top and bottom of box */
    for (int x = xLo - 2; x <= xHi + 2; x++) {
        arr[x][yLo - 2] = 3;
        arr[x][yHi + 2] = 3;
    }
    /* draw sides of box */
    for (int y = yLo - 1; y <= yHi + 1; y++) {
        arr[xLo - 2][y] = 3;
        arr[xHi + 2][y] = 3;
    }
}

void checkNeighbors (int arr[][GS], bool vis[][GS], queue Q, point* p) {
    int pX = p->getx();
    int pY = p->gety();
    for (int y = pY - 1; y <= pY + 1; y++) {
        for (int x = pX - 1; x <= pX + 1; x++) {
            if (x == pX && y == pY) {/* easier than opposite boolean logic */ }
            else {
                if (vis[x][y] == false) vis[x][y] = true;
                if (arr[x][y] == 1) {
                    point *n = new point(x, y);
                    Q.insert(n);
                    delete n;
                }
            }
        }
    }
}

void print (int arr[][GS]) {
    /* print array */
    for (int i = 0; i < GS; i++) {
        for (int j = 0; j < GS; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}
/*** END OF FUNCTIONS ***/

/*** START of QUEUE CLASS ***/

const int MSIZE = 1000;

class point {
private:
    int x; int y;

public:
    point(int p, int q) {
        x = p; y = q;
    }

    int getx() {
        return x;
    }

    int gety() {
        return y;
    }
};

class queue {

private:
    point* Q[MSIZE];

    int front, rear, size;

public:
    queue() {
        // initialize an empty queue
        //front = 0; rear = 0; size = 0;
        front = rear = size = 0;
        for (int j = 0; j < MSIZE; ++j)
            Q[j] = 0;
    }

    void insert(point* x) {
        if (size != MSIZE) {
            front++; size++;
            if (front == MSIZE) front = 0;
            Q[front] = x;
        }
    }

    point del() {
        if (size != 0) {
            rear++; if (rear == MSIZE) rear = 0;
            point temp(Q[rear]->getx(), Q[rear]->gety());
            size--;
            return temp;
        }
    }
    void print() {
        for (int j = 1; j <= size; ++j) {
            int i = front - j + 1;
            cout << "x = " << Q[i]->getx() << " y = " << Q[i]->gety() << endl;
        }
        cout << "end of queue" << endl;
    }
    bool isEmpty() {
        return (size == 0);
    }
};

/*** END of QUEUE CLASS ***/

Answer 1

1. このコードはコンパイルされません。`queue.h`を省略しました。私たちはそれを推測することができますが、あなたは私たちにそれをさせてはいけません。
2. このソースファイルにはクラス宣言があります。それらはヘッダーファイルに属します（そうでなければ、ヘッダーファイルを持つことにあまり意味がありません）。
3. ソースファイルにクラス宣言を含める場合は、天国のために、クラス宣言を必要とするコードの前に配置します。
4. `queue :: del（）`には単純なコンパイル時のバグがあります。コンパイラがあまり良くないか、警告をオフにしたか、警告を無視しているか、簡単なものを修正するのに悩むことはできません。
5. STLコンテナの代わりに配列を使用している正当な理由はありますか？
6. ヒープ上でこれらすべてのポイントを宣言している正当な理由はありますか？
7. 結論に飛びつきたくはありませんが、メインループのロジックは本当に混乱していて複雑すぎているように見えます。
8. 最も重要なこと：バウンディングボックスを使わなくても、プログラムがバグなしで実行され、バグを見つけるのがはるかに簡単になるとはとても思えません。バウンディングボックスのコードを書く前に、それを試しましたか？新しい動作を入力するたびにテストする必要があり、機能しないコードを追加しないでください。（私はそれを「ベータのルール」と呼び始めるべきだと私は言います。）

それでは、バグを探しましょう...

1. メインループでは、`xLo`と`yLo`から繰り返しますが、ループ内でこれらの変数を変更します。
2. `[j] [k]`でインデックスを作成することもあれば、`[k][j]`でインデックスを作成することもあります。それをクリーンアップすると、いくつかの悪い動作が消えます。
3. グラフの すべてのポイントの周りに個別のバウンディングボックスを描画しています。
4. バウンディングボックスルーチンには、単純な1つずつのバグがあります。

そして今、それは1つのグラフに対して機能します。2つで試すつもりはありません。

編集：
私は私の言葉のいくつかを食べなければなりません：あなたはインデックスを付けません[j][k]、私はあなたの使用に混乱し、(k,j) <=> (x,y)他の場所で実際のバグと混同されました。そして今、私はあなたがで何をしているのかわかりますqueueが、真剣にあなたはSTLを調べる必要があります。

本当に深刻なバグは、の署名にありcheckNeighbors(...)ます。Q参照ではなく、値で渡します。これを修正すると、コードは複数のグラフで機能します。

編集：
うん、別のバグ：queue特別な理由なしに（上記の「6」を参照）、ポイントではなくポイントへのポインタを格納し、どういうわけかそれらを汚している。正確なバグを探すのではなく、queueポイントを処理するように変更し、複雑なグラフに対して正しい結果を得ました。