Skip to main content
Code Review

Return to Answer

use the name ofthe class rather the old from copy and paste
Source Link
miscco
miscco
  • 4.4k
  • 12
  • 17
class GraphIterator
{   
    public:
        typedef std::input_iterator_tag     iterator_category;
        typedef int                         value_type;
        typedef std::size_t                 difference_type;
        typedef int*                        pointer;
        typedef int&                        reference;

        GraphIterator(int value) :current(value){}

        // Pre Increment
        CSVIterator&GraphIterator & operator++()               {++current;return *this;}
        // Post increment
        CSVIteratorGraphIterator operator++(int)             {return GraphIterator(current++);}

        // De-Reference
        value_type operator*() const            {return current;}

        bool operator==(CSVIteratorGraphIterator const& rhs) {return current == rhs.current}
        bool operator!=(CSVIteratorGraphIterator const& rhs) {return !((*this) == rhs);}
    private:
        int current;
};
GraphIterator begin() const {return GraphIterator(0);}
GraphIterator end()   const {return GraphIterator(vertices.size());}

class GraphIterator
{   
    public:
        typedef std::input_iterator_tag     iterator_category;
        typedef int                         value_type;
        typedef std::size_t                 difference_type;
        typedef int*                        pointer;
        typedef int&                        reference;

        GraphIterator(int value) :current(value){}

        // Pre Increment
        CSVIterator& operator++()               {++current;return *this;}
        // Post increment
        CSVIterator operator++(int)             {return GraphIterator(current++);}

        // De-Reference
        value_type operator*() const            {return current;}

        bool operator==(CSVIterator const& rhs) {return current == rhs.current}
        bool operator!=(CSVIterator const& rhs) {return !((*this) == rhs);}
    private:
        int current;
};
GraphIterator begin() const {return GraphIterator(0);}
GraphIterator end()   const {return GraphIterator(vertices.size());}

class GraphIterator
{   
    public:
        typedef std::input_iterator_tag     iterator_category;
        typedef int                         value_type;
        typedef std::size_t                 difference_type;
        typedef int*                        pointer;
        typedef int&                        reference;

        GraphIterator(int value) :current(value){}

        // Pre Increment
        GraphIterator & operator++()               {++current;return *this;}
        // Post increment
        GraphIterator operator++(int)             {return GraphIterator(current++);}

        // De-Reference
        value_type operator*() const            {return current;}

        bool operator==(GraphIterator const& rhs) {return current == rhs.current}
        bool operator!=(GraphIterator const& rhs) {return !((*this) == rhs);}
    private:
        int current;
};
GraphIterator begin() const {return GraphIterator(0);}
GraphIterator end()   const {return GraphIterator(vertices.size());}
added 1274 characters in body
Source Link
Loki Astari
Loki Astari
  • 97.7k
  • 5
  • 126
  • 341

A Graph Iterator

Here is an iterator to iterator across the Verticies in your graph (should be declared as a public member of Graph):

class GraphIterator
{   
    public:
        typedef std::input_iterator_tag     iterator_category;
        typedef int                         value_type;
        typedef std::size_t                 difference_type;
        typedef int*                        pointer;
        typedef int&                        reference;

        GraphIterator(int value) :current(value){}

        // Pre Increment
        CSVIterator& operator++()               {++current;return *this;}
        // Post increment
        CSVIterator operator++(int)             {return GraphIterator(current++);}

        // De-Reference
        value_type operator*() const            {return current;}

        bool operator==(CSVIterator const& rhs) {return current == rhs.current}
        bool operator!=(CSVIterator const& rhs) {return !((*this) == rhs);}
    private:
        int current;
};
GraphIterator begin() const {return GraphIterator(0);}
GraphIterator end()   const {return GraphIterator(vertices.size());}

A Graph Iterator

Here is an iterator to iterator across the Verticies in your graph (should be declared as a public member of Graph):

class GraphIterator
{   
    public:
        typedef std::input_iterator_tag     iterator_category;
        typedef int                         value_type;
        typedef std::size_t                 difference_type;
        typedef int*                        pointer;
        typedef int&                        reference;

        GraphIterator(int value) :current(value){}

        // Pre Increment
        CSVIterator& operator++()               {++current;return *this;}
        // Post increment
        CSVIterator operator++(int)             {return GraphIterator(current++);}

        // De-Reference
        value_type operator*() const            {return current;}

        bool operator==(CSVIterator const& rhs) {return current == rhs.current}
        bool operator!=(CSVIterator const& rhs) {return !((*this) == rhs);}
    private:
        int current;
};
GraphIterator begin() const {return GraphIterator(0);}
GraphIterator end()   const {return GraphIterator(vertices.size());}
Source Link
Loki Astari
Loki Astari
  • 97.7k
  • 5
  • 126
  • 341

##Interface

Your interface locks you into certain design decisions.

std::vector<int> GetAllVertexIDs() const;

Why return a verctor of all the node ID(s)? A more classic approach would be to return an iterator that allows you to iterate over all the nodes.

I am not sure what a depth or a breadth first search of a graph mean?

std::pair<std::vector<int>, std::vector<int>> BreadthFirstSearch(int start_id) const;
std::vector<int> DepthFirstSearch(int start_id, bool recursive = false) const;

Also why are they returning different things? I would expect any type of search to return the same thing. Otherwise how can I write generic code that searches for stuff and be expected to swap one search function for another?

Pass vertex data by reference (or R-Value reference) to prevent excessive copying.

int AddVertex(T value);

// I would have written three versions of this.
int addVertex(T const& value);         // Copy value into Graph
int addVertex(T&& value);              // Move value into Graph
template<typename... Args>
int emplaceVertex(Args... args);       // Construct in place in Graph

Accessing the data of a vertex via a reference. You do fine, but most containers allow you to mutate the date via the reference. So usually you see two versions of this method:

const T & GetVertexData(int vertex_id) const;

// Unless the graph data should be immutable I would have added:
T const& getVertexData(int vertex_id) const;
T&       getVertexData(int vertex_id);

A bit more white space in the class declaration to make it more readable would have been nice.

template <typename T>
class Graph
{
    public:
        using InsertPair = std::pair<int, int>;

        Graph(bool directed = false) : directed(directed) {}

        int      VertexCount() const;
        int      AddVertex(T const& value);
        T const& GetVertexData(int vertex_id) const;

        void       AddEdge(int start_id, int end_id, int cost = 0);
        InsertPair AddEdgeAndVertices(T const& start_value, T const& end_value, int cost = 0);

        
        std::vector<int> GetAllVertexIDs() const;

        // BFS returns vector pair <vertex_id, parent of this vertex>
        std::pair<std::vector<int>, std::vector<int>> BreadthFirstSearch(int start_id) const;
        std::vector<int> DepthFirstSearch(int start_id, bool recursive = false) const;


        template <typename U>
        friend std::ostream & operator<<(std::ostream & out, Graph<U> & g);

##Naming conventions

There is no standard.
But a common convention is:

  1. User defined types have an initial upper case letter.
  2. Objects (variables/methods/functions) have an initial lower case letter.

##File Names

You have split the declaration and definition of your template class into two files (which is fine). But the definition is in a *.cpp file.

A more common convention is to use *.tpp file for the definition. When your code gets installed on other people systems you will then not be installing *.cpp files (which would look strange).

##Code Review

As mention above pass objects by const reference when possible to avoid copying.

template <typename T>
int Graph<T>::AddVertex(T value)  // Copy to here that is not needed.
{
    int id = VertexCount(); // id is the index into vertices array
    vertices.push_back(Vertex(id, value));
    return id;
}

Avoid comments that should be obvious from reading the code.

int id = VertexCount(); // id is the index into vertices array

There is already a function that does this:

    return std::pair<int, int> (start_id, end_id);

    // Easier to write:
    return std::make_pair(start_id, end_id);

Avoid this kind of assert.

template <typename T>
void Graph<T>::AddEdge(int start_id, int end_id, int cost)
{
    assert(start_id >= 0 && start_id < VertexCount());
    assert(end_id >= 0 && end_id < VertexCount());

When you compile this code for production then these assert's disappear (ie they become noops). So they provide no real protection.

The assert should be used to validate that internal state of your object is consistent. Then your test code should try and throw all sorts of data through the public API to make sure the object can not be put in an inconsistent state.

Here you are validating user input. This is not the kind of data that should be evaluated by assert. You can not test all code that uses your code in a testing environment so these assert's provide no real protection. So either do real tests that throw or do no tests and define the contract and assume the user stays within the contract.

Example:

 std::vector::at(std::size_t index); // Throws if index is out of range.
 std::vector::operator[](std::size_t index); // Does nothing.
                                             // It assumes user has already
                                             // validated the input
                                             // and obeys the contract.

This is doing a lot of work. That may just be discarded by the caller after looking at a few nodes. Also it may become invalid very quickly if the graph is mutated and need to be regenerated.

template <typename T>
std::vector<int> Graph<T>::GetAllVertexIDs() const
{
    std::vector<int> vertex_ids(VertexCount());
    for (size_t i = 0; i < vertex_ids.size(); ++i)
        vertex_ids[i] = i;
    return vertex_ids;
}

I would return an iterator (they are cheap to construct). If the graph is mutated then creating another is not an issue. Also you make it return the id or a reference to the object (whichever suits your use case best).

Visitor pattern

I would look into the visitor pattern for doing graph traversal.