Ggthjy

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 << "rn{";

    out << "rnt EDGES_IN = {";

    for (auto edge : rhs.edges_in_)

    {

        out << " (" << edge.first->value_ << ", " << edge.second << ")";

    }

    out << " },";

    out << "rnt EDGES_OUT = {";

    for (auto edge : rhs.edges_out_)

    {

        out << " (" << edge.first->value_ << ", " << edge.second << ")";

    }

    out << " }";

    out << "rn};";

    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;

}

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_));