55502f40dc8b7c769880b10874abc9d0

This is the BFS example used in the Introduction to Algorithm book by Cormen et al (page 533 of the second edition).
I would like a code review as I am trying to improve my C++ as well. Any thoughts you may have will be greatly appreciated. Thank you.

#include <iostream>
#include <limits>
#include <map>
#include <list>
#include <queue>

using namespace std;

const int INFINITY = INT_MAX;

enum Color { WHITE, GRAY, BLACK };

class Vertex
{
public:
    Vertex();
    Vertex(char id);
    ~Vertex();
    char Vertex::getId();
    void Vertex::setId(char arg);

    bool operator <(const Vertex& rhs) const
    {
        return id < rhs.id;
    }

private:
    char id;
};

Vertex::Vertex(): id('0')
{}

Vertex::Vertex(char id): id(id)
{}

Vertex::~Vertex()
{
}

char Vertex::getId()
{
    return id;
}

void Vertex::setId(char arg)
{
    id = arg;
}

int main()
{
    //created the vertices
    Vertex r('r');
    Vertex s('s');
    Vertex t('t');
    Vertex u('u');
    Vertex v('v');
    Vertex w('w');
    Vertex x('x');
    Vertex y('y');

    //use maps for keeping track of color, distance and parents
    map< Vertex , Color> color;
    color[r] = WHITE;
    color[s] = WHITE;
    color[t] = WHITE;
    color[u] = WHITE;
    color[v] = WHITE;
    color[w] = WHITE;
    color[x] = WHITE;
    color[y] = WHITE;

    map< Vertex , int> distance;
    distance[r] = INFINITY;
    distance[s] = INFINITY;
    distance[t] = INFINITY;
    distance[u] = INFINITY;
    distance[v] = INFINITY;
    distance[w] = INFINITY;
    distance[x] = INFINITY;
    distance[y] = INFINITY;

    map< Vertex , Vertex*> parent;
    parent[r] = NULL;
    parent[s] = NULL;
    parent[t] = NULL;
    parent[u] = NULL;
    parent[v] = NULL;
    parent[w] = NULL;
    parent[x] = NULL;
    parent[y] = NULL;

    //create the adj lists
    list<Vertex> adj_r;
    list<Vertex> adj_s;
    list<Vertex> adj_t;
    list<Vertex> adj_u;
    list<Vertex> adj_v;
    list<Vertex> adj_w;
    list<Vertex> adj_x;
    list<Vertex> adj_y;

    adj_r.push_back(s);
    adj_r.push_back(v);

    adj_s.push_back(r);
    adj_s.push_back(w);

    adj_t.push_back(w);
    adj_t.push_back(x);
    adj_t.push_back(u);

    adj_u.push_back(t);
    adj_u.push_back(x);
    adj_u.push_back(y);

    adj_v.push_back(r);

    adj_w.push_back(s);
    adj_w.push_back(t);
    adj_w.push_back(x);

    adj_x.push_back(w);
    adj_x.push_back(t);
    adj_x.push_back(y);
    adj_x.push_back(u);

    adj_y.push_back(x);
    adj_y.push_back(u);

    //map vertices to corresponding lists
    map< Vertex , list<Vertex> > adj;
    adj[r] = adj_r;
    adj[s] = adj_s;
    adj[t] = adj_t;
    adj[u] = adj_u;
    adj[v] = adj_v;
    adj[w] = adj_w;
    adj[x] = adj_x;
    adj[y] = adj_y;

    //other objects
    queue<Vertex> q;
    Vertex currentVertex;
    Vertex currentDecescendant;

    //start algorithm
    color[s] = GRAY;
    distance[s] = 0;
    parent[s] = NULL;

    q.push(s);

    //in while loop
    while( !q.empty() )
    {
        //dequeue
        currentVertex = q.front();
        q.pop();

        //for each currentDecescendant in adj[currentVertex]
        list<Vertex>::iterator it;
        for(it = adj[currentVertex].begin(); it != adj[currentVertex].end(); it++)
        {
            currentDecescendant.setId( it->getId() );

            if( color[currentDecescendant]==WHITE )
            {
                color[currentDecescendant] = GRAY;
                distance[currentDecescendant] = distance[currentVertex] + 1;
                parent[currentDecescendant] = &currentVertex;

                q.push(currentDecescendant);
            }
        }

        color[currentVertex] = BLACK;
    }

    cout << "distance[r]: " << distance[r] <<endl;
    cout << "distance[s]: " << distance[s] <<endl;
    cout << "distance[t]: " << distance[t] <<endl;
    cout << "distance[u]: " << distance[u] <<endl;
    cout << "distance[v]: " << distance[v] <<endl;
    cout << "distance[w]: " << distance[w] <<endl;
    cout << "distance[x]: " << distance[x] <<endl;
    cout << "distance[y]: " << distance[y] <<endl;

    return 0;
}

Refactorings

No refactoring yet !

F9a9ba6663645458aa8630157ed5e71e

Ants

July 18, 2009, July 18, 2009 06:45, permalink

1 rating. Login to rate!

A simple first pass refactoring...

#include "stdafx.h"

using namespace std;

class Vertex
{
public:
    typedef list<const Vertex *> Edges;

    Vertex(char id)
        : id(id)
    {
    }

    char Vertex::getId() const
    {
        return id;
    }

    void AddEdgeTo(const Vertex * endPoint)
    {
        m_edges.push_back(endPoint);
    }

    const Edges& getEdges() const
    {
        return m_edges;
    }

private:
    char id;
    list<const Vertex *> m_edges;
};

class Graph
{
private:
    typedef set<Vertex *>::iterator VertexIterator;

public:
    typedef set<Vertex *> Vertices;

    Graph()
    {
    }

    ~Graph()
    {
        Clear();
    }

    Vertex * AddVertex(char id)
    {
        Vertex * vertex = new Vertex(id);
        m_vertices.insert(vertex);
        return vertex;
    }

    Vertex * GetVertex(char id)
    {
        VertexIterator iter;
        for (iter = m_vertices.begin(); iter != m_vertices.end(); iter++)
        {
            if (id == (*iter)->getId())
                return *iter;
        }
        return NULL;
    }

    void AddBiEdge(Vertex * vertex1, Vertex * vertex2)
    {
        vertex1->AddEdgeTo(vertex2);
        vertex2->AddEdgeTo(vertex1);
    }

    void Clear()
    {
        VertexIterator iter;
        for (iter = m_vertices.begin(); iter != m_vertices.end(); iter++)
            delete *iter;
    }

    const Vertices& getVertices() const
    {
        return m_vertices;
    }

private:
    Vertices m_vertices;
};

class BFS
{
public:
    enum StatusType { NotSeen, Seen, Visited };

    class Attribute
    {
    public:
        StatusType		Status;
        unsigned int	Distance;
        const Vertex *	Parent;

        Attribute()
            : Status(NotSeen)
            , Distance(UINT_MAX)
            , Parent(NULL)
        {
        }

        Attribute(StatusType status, unsigned int distance, const Vertex * parent)
            : Status(status)
            , Distance(distance)
            , Parent(parent)
        {
        }
    };

    map<const Vertex *, Attribute> Attributes;

    static BFS * Compute(const Vertex * startVertex)
    {
        if (!startVertex)
            return NULL;

        BFS * search = new BFS();
        search->Walk(startVertex);
        return search;
    }

private:
    BFS()
    {
    }

    void Walk(const Vertex * startVertex)
    {
        queue<const Vertex *> q;

        Attributes[startVertex] = Attribute(Seen, 0, NULL);

        q.push(startVertex);
        while (!q.empty())
        {
            const Vertex * current = q.front();
            q.pop();

            Attributes[current].Status = Visited;

            const Attribute seen = Attribute(Seen, Attributes[current].Distance + 1, current);

            for (Vertex::Edges::const_iterator iter = current->getEdges().begin();
                 iter != current->getEdges().end();
                 iter++)
            {
                if (NotSeen == Attributes[*iter].Status)
                {
                    Attributes[*iter] = seen;
                    q.push(*iter);
                }
            }
        }
    }
};

Graph* BuildGraph()
{
    Graph * graph = new Graph();

    Vertex * r = graph->AddVertex('r');
    Vertex * s = graph->AddVertex('s');
    Vertex * t = graph->AddVertex('t');
    Vertex * u = graph->AddVertex('u');
    Vertex * v = graph->AddVertex('v');
    Vertex * w = graph->AddVertex('w');
    Vertex * x = graph->AddVertex('x');
    Vertex * y = graph->AddVertex('y');

    graph->AddBiEdge(r, s);
    graph->AddBiEdge(r, v);
    graph->AddBiEdge(s, w);
    graph->AddBiEdge(t, w);
    graph->AddBiEdge(t, x);
    graph->AddBiEdge(t, u);
    graph->AddBiEdge(u, x);
    graph->AddBiEdge(u, y);
    graph->AddBiEdge(w, x);
    graph->AddBiEdge(x, y);

    return graph;
}

void DumpResults(const Graph * graph, BFS * bfs)
{
    for(Graph::Vertices::const_iterator iter = graph->getVertices().begin();
        iter != graph->getVertices().end();
        iter++)
    {
        const Vertex * vertex = *iter;
        unsigned int distance = bfs->Attributes[vertex].Distance;
        cout << "distance[" << vertex->getId() << "]: " << distance << endl;
    }
}

int main()
{
    Graph * graph = BuildGraph();
    BFS * bfs = BFS::Compute(graph->GetVertex('s'));
    DumpResults(graph, bfs);
    delete graph;
    return 0;
}

Your refactoring





Format Copy from initial code

or Cancel