4
\$\begingroup\$

What can be done better? My future plans is to implement algorithms such as: DFS, BFS, Prims, Dijkstra, Kruskal, ...


Faults I know of:

  • Not implementing rule of five

Vertex.h:

#pragma once

#include <iostream>
#include <unordered_map>

template<typename T>
class Vertex
{
public:
    Vertex(const T& value);
    ~Vertex();

    const T& value() const;

    void add_edge_in(Vertex<T>* dest, int weight);
    void add_edge_out(Vertex<T>* dest, int weight);
    void remove_edge_in(Vertex<T>* dest);
    void remove_edge_out(Vertex<T>* dest);
private:
    template<typename T> friend std::ostream& operator<<(std::ostream& out, const Vertex<T>& rhs);

    const T value_;
    std::unordered_map<Vertex<T>*, int> edges_in_;
    std::unordered_map<Vertex<T>*, int> edges_out_;
};

template<typename T>
Vertex<T>::Vertex(const T& value)
    : value_(value)
{
}

/*
    Removes all edges associated with this vertex
*/
template<typename T>
Vertex<T>::~Vertex<T>()
{
    for (auto edge : edges_in_)
    {
        Vertex<T>* dest = edge.first;
        dest->remove_edge_in(this);
    }
    for (auto edge : edges_out_)
    {
        Vertex<T>* dest = edge.first;
        dest->remove_edge_out(this);
    }
}

template<typename T>
const T& Vertex<T>::value() const
{
    return value_;
}

template<typename T>
void Vertex<T>::add_edge_in(Vertex<T>* dest, int weight)
{
    edges_in_.insert({ dest, weight });
}

template<typename T>
void Vertex<T>::add_edge_out(Vertex<T>* dest, int weight)
{
    edges_out_.insert({ dest, weight });
}

template<typename T>
void Vertex<T>::remove_edge_in(Vertex<T>* dest)
{
    edges_in_.erase(dest);
}

template<typename T>
void Vertex<T>::remove_edge_out(Vertex<T>* dest)
{
    edges_out_.erase(dest);
}

template<typename T>
std::ostream& operator<<(std::ostream& out, const Vertex<T>& rhs)
{
    out << "[" << rhs.value_ << "]:";
    out << "\r\n{";
    out << "\r\n\t EDGES_IN = {";
    for (auto edge : rhs.edges_in_)
    {
        out << " (" << edge.first->value_ << ", " << edge.second << ")";
    }
    out << " },";
    out << "\r\n\t EDGES_OUT = {";
    for (auto edge : rhs.edges_out_)
    {
        out << " (" << edge.first->value_ << ", " << edge.second << ")";
    }
    out << " }";
    out << "\r\n};";
    return out;
}


Graph.h:

#pragma once

#include "Vertex.h"
#include <iostream>
#include <vector>

template<typename T>
class Graph
{
public:
    Graph(const bool directed);
    ~Graph();

    void print() const;
    bool is_directed() const;

    void add_vertex(const T&);
    void remove_vertex(const T&);
    void add_edge(const T&, const T&, int weight);
    void remove_edge(const T&, const T&);
private:
    Vertex<T>* get_vertex(const T&);

    std::vector<Vertex<T>*> graph_;
    const bool directed_;
};

template<typename T>
Graph<T>::Graph(const bool directed)
    : directed_(directed)
{
}

template<typename T>
Graph<T>::~Graph()
{
    for (Vertex<T>* v : graph_)
    {
        delete v;
    }
}

template<typename T>
void Graph<T>::print() const
{
    for (Vertex<T>* v : graph_)
    {
        std::cout << *v << std::endl;
    }
}

template<typename T>
bool Graph<T>::is_directed() const
{
    return directed_;
}

template<typename T>
void Graph<T>::add_vertex(const T& value)
{
    graph_.push_back(new Vertex<T>(value));
    return;
}

template<typename T>
void Graph<T>::remove_vertex(const T& value)
{
    for (auto it = graph_.begin(); it != graph_.end(); ++it)
    {
        if ((*it)->value() == value)
        {
            delete *it;
            graph_.erase(it);
            return;
        }
    }
}

template<typename T>
void Graph<T>::add_edge(const T& src_value, const T& dest_value, int weight)
{
    Vertex<T>* src = get_vertex(src_value);
    Vertex<T>* dest = get_vertex(dest_value);

    src->add_edge_out(dest, weight);
    dest->add_edge_in(src, weight);

    if (!directed_)
    {
        src->add_edge_in(dest, weight);
        dest->add_edge_out(src, weight);
    }
}

template<typename T>
void Graph<T>::remove_edge(const T& src_value, const T& dest_value)
{
    Vertex<T>* src = get_vertex(src_value);
    Vertex<T>* dest = get_vertex(dest_value);

    src->remove_edge_out(dest);
    dest->remove_edge_in(src);

    if (!directed_)
    {
        src->remove_edge_in(dest);
        dest->remove_edge_out(src);
    }
}

template<typename T>
Vertex<T>* Graph<T>::get_vertex(const T& value)
{
    for (Vertex<T>* v : graph_)
    {
        if (v->value() == value)
        {
            return v;
        }
    }
    return nullptr;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The rule of five would become the rule of zero if it weren't for your decision to use dynamically-allocated T objects in your vertices. I can understand an implementation of a graph where it holds pointers to resources it does not own, but that's not what's happening here. Using new and delete in your case offers no advantages and only makes things more complicated. If you store plain-old Vertex<T>'s in your std::vector, then your rule of five functions can all be defaulted. \$\endgroup\$ – Mike Borkland Apr 8 at 1:07
  • \$\begingroup\$ Too many pointers being passed around. \$\endgroup\$ – Martin York Apr 8 at 15:25
3
\$\begingroup\$

Design

The problem is that there can only be one vertext with a particular value. Well actually you can add the same value multiple times BUT any operation will be applied to the first vertex with that value, so its like there is only one visible value in the vertex list.

Either you should allow multiple values (in which case use the value is not a valid way to find a vertex). Or you should prevent the same value being added to the vertex list more than once.

You have issues with memory management. Caused by using new/delete and not considering the rule of 5.

You play with pointers all over the place with no attempt to check that they are nullptr.

Code Review

Yes you need to store them as pointers (non owning).

std::unordered_map<Vertex<T>*, int> edges_in_;
std::unordered_map<Vertex<T>*, int> edges_out_;

But that does not mean the interface needs to be pointers.

void add_edge_in(Vertex<T>* dest, int weight);
void add_edge_out(Vertex<T>* dest, int weight);
void remove_edge_in(Vertex<T>* dest);
void remove_edge_out(Vertex<T>* dest);

Here I would pass in references. That way you know that a dest can never be null.


I don't see why you are storing pointer here:

std::vector<Vertex<T>*> graph_;

Here the graph has ownership (and Vertex<T> is not polymorphic). So by using pointers you are adding the whole issue of memory management to your class without needing to.

By making this std::vector<Vertex<T>> you get around the whole problem of memory management. By making this std::vector<std::unique_ptr<Vertex<T>>> you make the graph non copyable (an alternative solution). I would go with the first.


Because you store owned RAW pointers you need to implement the rule of 3/5. Or you need to fix it like I suggest above.

 {
     Graph<int>    x;
     x. add_vertex(1);
     Graph<int>    y(x);
 }
 // This currently is broken and will result in a double delete.

Sure. I don't mind a void Graph<T>::print() const. But I also expect to see friend std::ostream& operator<<(std::ostream&, Graph<T> const&) for printing.

Also why does print() only print to std::cout you should allow it to print to any stream!

class Graph
{
    void print(std::ostream& str = std::cout) const;
    friend std::ostream& operator<<(std::ostream& s, Graph const& d) {
        d.print(s);
        return s;
    }
};

Vertex<T>* Graph<T>::get_vertex(const T& value)
{
    // STUFF
    return nullptr;
}

No caller of get_vertex() ever checks for nullptr being returned. This is going to blow up so easily.


for (auto it = graph_.begin(); it != graph_.end(); ++it)
{
    if ((*it)->value() == value)
    {
        delete *it;
        graph_.erase(it);
        return;
    }
}

There is a pattern for this: Erase Remove Idiom.

auto end = std::remove_if(std::begin(graph_), std::end(graph_), [&value](Vertex* it){return it->value == value;});
for(auto loop = end; loop != std::end(graph_); ++loop) {
    delete *loop;
}
graph_.erase(end, std::end(graph_));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.