Pseudograph Implementation

Question

I needed a special graph structure for my code and thought I'd write a generic one for later reuse.
At first I wanted to use pointers instead of indices as map keys but I quickly forfeited that idea once I realized, that changing the vertex vector might invalidate them. I'm especially interested if there are problems with my design (I expect way below 100 vertices tops, in case that's relevant), code style suggestions and maybe some improvements on the print function, which admittedly looks a bit ugly, because I needed to write it for debugging purposes.

This graph is undirectional, allows multiple connections between two vertices and even connections from a vertex to itself.

#pragma once

#include <iostream>
#include <map>
#include <memory>
#include <vector>

namespace Util{
    /**
     * @class Pseudo_Graph 
     * An undirected graph that allows for multiple connections between the same vertices (including to itself)
     * Allows to specify additional information for each vertex and the costs to transverse between vertices
     * The graph is represented by an adjacency map
     *
     * Example:
     * Let there be vertices A, B, C and D where we use the vertex name as first template parameter <Info=char>
     * Let there be the following connections where the number behind denotes the cost to transverse <Cost=unsigned int>
     * A <-> A (1)
     * A <-> B (1)
     * A <-> D (8)
     * B <-> C (2)
     * B <-> C (4)
     * C <-> D (3)
     * This would be result in the following internal representation (numerical indices have been resolved for clarity)
     * Pseudo_Graph<char, unsigned int>
     * vertices = {'A', 'B', 'C', 'D'}
     * costs    = {1, 8, 2, 4, 3}
     * graph['A'] = {{'A', {1}}, {'B', {1}}, {'D', {8}}}
     * graph['B'] = {{'A', {1}}, {'C', {2, 4}}}
     * graph['C'] = {{'B', {2, 4}}, {'D', {3}}}
     * graph['D'] = {{'A', {8}}, {'C', {3}}}
     * @tparam Info the information associated with each vertex
     * @tparam Cost the cost to traverse from one vertex to another
     */
    template<class Info, class Cost>
    class Pseudo_Graph{
        protected:
            struct Vertex{
                Info info;
                bool visited;
            };
            std::vector<Vertex> vertices_;
            std::vector<Cost> costs_;

            std::map<std::size_t, std::map<std::size_t, std::vector<std::size_t>> > graph_;

            bool contains_loops(std::size_t last, std::size_t next){
                for( const auto& to_cost_pointer : graph_[next] ){
                    if( to_cost_pointer.first == last ){ // we just came from here
                        continue;
                    }
                    if( vertices_[to_cost_pointer.first].visited || to_cost_pointer.second.size() > 1 ){
                        return true;
                    }
                    vertices_[to_cost_pointer.first].visited = true;
                    if( contains_loops(next, to_cost_pointer.first) ){
                        return true;
                    }
                }
                return false;
            }

            void visit_neighbours(std::size_t next){
                for( const auto& to_cost_pointer : graph_[next] ){
                    if( vertices_[to_cost_pointer.first].visited ){
                        continue;
                    }
                    vertices_[to_cost_pointer.first].visited = true;
                    visit_neighbours(to_cost_pointer.first);
                }
            }

        public:
            void add_vertex(const Info& info){
                vertices_.push_back({info, false});
            }
            void add_vertices(const std::vector<Info>& info_vector){
                for( auto info : info_vector ){
                    vertices_.push_back({info, false});
                }
            }
            void add_link(const std::size_t from, const std::size_t to, const Cost& costs){
                if( from >= vertices_.size() ){
                    throw std::runtime_error("Can not add link: Source vertex does not exist in Graph.");
                }
                if( to >= vertices_.size() ){
                    throw std::runtime_error("Can not add link: Target vertex does not exist in Graph.");
                }
                graph_[from][to].push_back(costs);
                graph_[to][from].push_back(costs);
            }
            bool contains_loops(){
                unvisit_all();
                for( const auto& from_to_pair : graph_ ){
                    if( vertices_[from_to_pair.first].visited ){
                        continue;
                    }
                    vertices_[from_to_pair.first].visited = true;
                    for( const auto& to_cost_pair : from_to_pair.second ){
                        if( vertices_[to_cost_pair.first].visited ){
                            continue;
                        }
                        vertices_[to_cost_pair.first].visited = true;
                        if( to_cost_pair.second.size() > 1 || contains_loops(from_to_pair.first, to_cost_pair.first) ){
                            return true;
                        }
                    }
                }
                return false;
            }

            void unvisit_all(){
                for( auto& vertex : vertices_ ){
                    vertex.visited = false;
                }
            }

            bool is_connected(){
                unvisit_all();
                if( graph_.empty() ){
                    return false;
                }
                visit_neighbours((*graph_.begin()).first);
                for( const auto& vertex : vertices_ ){
                    if( !vertex.visited ){
                        return false;
                    }
                }
                return true;
            }

            void print() const{
                for( auto from_to_pair : graph_ ){
                    std::cout << "[" << from_to_pair.first << "] = [";
                    bool outer_is_first{true};
                    for( const auto& to_cost_pair : from_to_pair.second ){
                        if( !outer_is_first ){
                            std::cout << ", ";
                        }
                        outer_is_first = false;
                        std::cout << "[" << to_cost_pair.first << ", [";
                        bool inner_is_first{true};
                        for( const auto& cost : to_cost_pair.second ){
                            if( !inner_is_first ){
                                std::cout << ", ";
                            }
                            inner_is_first = false;
                            std::cout << cost;
                        }
                        std::cout << "]";
                    }
                    std::cout << "]\n";
                }
            }
    };
}

Answer 1

Some of the places where you use push_back would be better served using emplace_back. In add_vertex, using vertices_.emplace_back(info, false); would construct the Vertex directly in the vector and avoid creating a temporary object.

The first for loop in print should use const auto &from_to_pair (like you are with the other range based for loops) to avoid making a copy of all those map elements.

To reduce memory and help with cache usage, and since it is only used internally, consider making visited a separate (private) vector, rather than bundling it with Vertex. By adding that one bool to Vertex (along with Info) there will probably be 3 or 7 padding bytes added to the struct. If you put visited in a separate vector you can reclaim that memory, and not even have it allocated when you aren't using it. You could use std::vector<bool>, which packs all the bools into bits and has some restrictions, or std::vector<char>. Resize it before you use it, then clear it when you're done. This would then let you get rid of the unvisit_all method, unless you want to keep it around to resize that new vector properly. If this vector is declared mutable, then your is_connected and contains_loops could potentially be declared const, which would be the expectation given their names. Or this new vector could be a local variable in the functions that need it, and passed to the other functions that need it as a parameter, which would be a necessary step (but not the only step) to make the class friendlier for multithreaded use.

And one note on style: Your use of spaces is a bit atypical. It is more common to see a space between keyword and paren, and between close paren and the curly bracket, like if (condition) {. However, you are consistent in your usage which is good. Also, sometimes you have a blank line between functions and other times you don't. You could be more consistent in your use of spacing there.