1

I'm implementing a simple DFS traversal for directed graph:

#include <iostream>
#include <vector>
#include <climits>
#include <utility>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <list>

using namespace std;

enum class color_type {
    BLACK,
    WHITE,
    GRAY
};

struct vertex {
    char label;
    color_type color;
    int start;
    int finish;
    vertex *parent;
    vector<vertex> adjacents;

    vertex(char label)
        :label(label), start(0), finish(0), color(color_type::WHITE) {
    }

    void add_neighbor(const vertex &v) {
        adjacents.push_back(v);
    }
};

class digraph {
private:
    vector<vertex> vertices;    
    int count;

public:
    digraph() 
        :count(0) {
        vertex a('a');
        vertex b('b');
        vertex c('c');
        add_edge(a, b);
        add_edge(b, c);
        add_edge(c, a);
        vertices.push_back(a);
        vertices.push_back(b);
        vertices.push_back(c);
        for (int i = 0; i < vertices.size(); ++i) {
            vertices[i].color = color_type::WHITE;
            vertices[i].parent = NULL;
        }
    }

    void add_edge(vertex &u, vertex &v) {
        u.add_neighbor(v);
    }

    void dfs() {
        dfs_visit(vertices[0]);
    }

    void dfs_visit(vertex &u) {
        count++;
        u.start = count;
        u.color = color_type::GRAY;
        cout << "??? visit = " << u.label << endl;
        cout << "# neighbors: " << u.adjacents.size() << '\n';
        for (int i = 0; i < u.adjacents.size(); ++i) {
            if (u.adjacents[i].color == color_type::WHITE) {
                cout << "visit neighbor of [" << u.label << "] is: " << u.adjacents[i].label << endl;
                u.adjacents[i].parent = &u;
                dfs_visit(u.adjacents[i]);
            } 
        }
        u.color = color_type::BLACK;
        count++;
        u.finish = count;
    }

public:
    friend ostream& operator <<(ostream& o, const digraph &dg) {
        for (int i = 0; i < dg.vertices.size(); ++i) {
            o << dg.vertices[i].label << ":\n";
            o << "\t start  = " << dg.vertices[i].start << endl;
            o << "\t finish = " << dg.vertices[i].finish << endl;
        }
        return o;
    }
};

int main() {
    digraph dg;
    dg.dfs();
    cout << dg << endl;
    return 0;
}

The problem is the call to dfs_visit() stop after visit the 2nd vertex. I pass a vertex u by reference as parameter of dfs_visit() function, but somehow the number of neighbor of vertex b suddenly becomes 0 which is very odd.
It seemed to me that the vertices stored in the vector vertices are not the same as the ones which are passed to dfs_visit, but I don't really see how this could be the case. I've been using Java for a while and now I'm really rusty with C++. So could anyone shed me some lights regarding this issue?

Edit enter image description here

roxrook
  • 13,511
  • 40
  • 107
  • 156
  • How do you know it suddenly becomes 0? Can you construct a minimal test-case? (Because that's a lot of code you're asking us to wade through...) – Oliver Charlesworth Apr 09 '13 at 00:19
  • @Oli: You can just run my code. There were a graph of 3 vertices in my constructor. I'm using Visual Studio 2012. Thanks. – roxrook Apr 09 '13 at 00:20
  • You cannot expect people to copy-and-paste all of your code into a clean project, compile it, invent some sample input, and then start to debug it for you. Please try to narrow the problem down. – Oliver Charlesworth Apr 09 '13 at 00:22
  • @Oil: I added the screenshot. Sorry I didn't mean to ask for debugging my code, I just want to understand why it worked like that. – roxrook Apr 09 '13 at 00:22
  • Your `vertex` object has copies to other `vertex` objects. They are not referencing the `vertices` of your `digraph` class. – jxh Apr 09 '13 at 00:25
  • 3
    The best way for everyone to wrap their heads around this is for you to make a smaller bit of code that exhibits the thing you don't understand. The funny part about that is, by reducing the code in question to JUST the bits that don't make sense, you'll often find that you can answer the question yourself! – Michael Kohne Apr 09 '13 at 00:26
  • 1
    @Chan: Ok, if your question really is "how do references work?", then I guess try reading the answers to questions like this one: http://stackoverflow.com/questions/57483/what-are-the-differences-between-pointer-variable-and-reference-variable-in-c. If your question is actually "why doesn't my code work?", then you will need to narrow your code down before we can help you effectively... – Oliver Charlesworth Apr 09 '13 at 00:26
  • @Oil: Sorry for the confusion, I actually didn't know how to make the correct title for this problem. My initial guess was the call to `dfs_visit` which pass a vertex by reference. – roxrook Apr 09 '13 at 00:29
  • @user315052: Could you elaborate a bit? I thought I already passed a vertex by reference to a vertex stored in my vector? Does that call actually make a copy of that vertex? – roxrook Apr 09 '13 at 00:31
  • @Chan Consider the value-pushes being done into the adjacency lists of each node during your construction. You're pushing b into a's list (which now has a copy of b). then you push c into b's list (now has a copy of c). Does the b in a's list have a reference to c? Hmmm.... – WhozCraig Apr 09 '13 at 00:33
  • @MichaelKohne: I really didn't mean to be lazy, and the code snippet that I posted is actually very simple. I already narrowed it down to a test case with only 3 vertices with only a recursive call to `dfs_visit`. I don't really know what could I do to make it simpler! – roxrook Apr 09 '13 at 00:33
  • Your title is a quintessential question. (original title was: "Why doesn't my code work?") – Naftuli Kay Apr 09 '13 at 00:37
  • @WhozCraig: I purposely make both parameters of `add_edge` to be references, how could they push a copy of my vertice though? – roxrook Apr 09 '13 at 00:37
  • @Chan What do you think `push_back()` is *doing* ? Ex. You're sending a reference to your add_edge, which promptly sends it to push_back(), which makes a copy for the vector. – WhozCraig Apr 09 '13 at 00:39
  • @WhozCraig: Thanks a lot. I got affected by Java way for everything is a reference. I guess I have to use `vector`! – roxrook Apr 09 '13 at 00:43
  • @Chan My advice would be store your vertexes in a primary array (which you're doing) and store *pointers* to neighbors in each vertex, where the pointers are pointing to the instances in the primary container. I hope that made sense. Note: setup the pointers *after* adding to the primary container, and address *those* elements; not the locals. – WhozCraig Apr 09 '13 at 00:45
  • @WhozCraig: Or indices to the primary container instead of pointers, depending on personal preferences. – jxh Apr 09 '13 at 00:51
  • @user315052 exactly. however you can get to them by-reference, pointer, index. so long as its real vertices. – WhozCraig Apr 09 '13 at 00:54
  • @Chan If this is not an exercise, you might want to look in to Boost graph library. All of this already available. –  Apr 09 '13 at 00:55
  • @WhozCraig, user315052: Thanks a lot. – roxrook Apr 09 '13 at 01:33

1 Answers1

1

This is probably closer to what you're looking for, using pointers for neighbors. Hope this helps. Ultimately the difference is the by-pointer addressing of neighbors within the primary vertex container, as opposed to all those copies being made in your code.

Note: the add-construction just sets up a node to have the "next" node in the vertices collection as its neighbor, finishing with the last node getting the first for a neighbor. This seemed to be what you're code was trying to accomplish.

#include <iostream>
#include <vector>
#include <climits>
#include <utility>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <list>

using namespace std;

enum class color_type {
    BLACK,
    WHITE,
    GRAY
};

struct vertex {
    char label;
    color_type color;
    int start;
    int finish;
    vertex *parent;
    vector<vertex*> adjacents;

    vertex(char label)
    :label(label), start(0), finish(0), color(color_type::WHITE) {
    }

    void add_neighbor(vertex &v) {
        adjacents.push_back(std::addressof(v));
    }
};

class digraph {
private:
    vector<vertex> vertices;
    int count;

public:
    digraph()
    :count(0) {
        vertices.push_back(vertex('a'));
        vertices.push_back(vertex('b'));
        vertices.push_back(vertex('c'));
        for (size_t i=0; i<vertices.size(); ++i)
        {
            vertices[i].color = color_type::WHITE;
            vertices[i].parent = NULL;
            vertices[i].add_neighbor(vertices[(i+1)%vertices.size()]);
        }
    }

    void dfs() {
        dfs_visit(vertices[0]);
    }

    void dfs_visit(vertex &u) {
        count++;
        u.start = count;
        u.color = color_type::GRAY;
        cout << "??? visit = " << u.label << endl;
        cout << "# neighbors: " << u.adjacents.size() << '\n';
        for (int i = 0; i < u.adjacents.size(); ++i) {
            if (u.adjacents[i]->color == color_type::WHITE) {
                cout << "visit neighbor of [" << u.label << "] is: " << u.adjacents[i]->label << endl;
                u.adjacents[i]->parent = &u;
                dfs_visit(*(u.adjacents[i]));
            }
        }
        u.color = color_type::BLACK;
        count++;
        u.finish = count;
    }

public:
    friend ostream& operator <<(ostream& o, const digraph &dg) {
        for (int i = 0; i < dg.vertices.size(); ++i) {
            o << dg.vertices[i].label << ":\n";
            o << "\t start  = " << dg.vertices[i].start << endl;
            o << "\t finish = " << dg.vertices[i].finish << endl;
        }
        return o;
    }
};

int main() {
    digraph dg;
    dg.dfs();
    cout << dg << endl;
    return 0;
}

Output

??? visit = a
# neighbors: 1
visit neighbor of [a] is: b
??? visit = b
# neighbors: 1
visit neighbor of [b] is: c
??? visit = c
# neighbors: 1
a:
     start  = 1
     finish = 6
b:
     start  = 2
     finish = 5
c:
     start  = 3
     finish = 4
WhozCraig
  • 65,258
  • 11
  • 75
  • 141