伪图实现

Question

我的代码需要一个特殊的图形结构，我认为我应该编写一个通用的图形结构，以供以后重用。起初，我想使用指针而不是索引作为映射键，但当我意识到更改顶点向量可能会使它们失效时，我很快就放弃了这个想法。我特别感兴趣的是，如果我的设计有问题(我预计在100个顶点以下，如果这是相关的话)，代码风格的建议，也许是对打印函数的一些改进，这看起来有点难看，因为我需要为调试目的编写它。

这个图是无方向的，允许两个顶点之间的多个连接，甚至一个顶点到它自己的连接。

#pragma once

#include 
#include 
#include 
#include 

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 
     * Let there be the following connections where the number behind denotes the cost to transverse 
     * 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
     * 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 Pseudo_Graph{
        protected:
            struct Vertex{
                Info info;
                bool visited;
            };
            std::vector vertices_;
            std::vector costs_;

            std::map> > 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_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

使用push_back的一些地方使用emplace_back会更好。在add_vertex中，使用vertices_.emplace_back(info, false);将直接在向量中构造顶点，并避免创建临时对象。

print中的第一个D5循环应该使用const auto &from_to_pair (就像其他基于for循环的范围一样)，以避免复制所有这些映射元素。

为了减少内存和帮助缓存的使用，并且由于它只在内部使用，请考虑将visited作为一个单独的(私有)向量，而不是将它与Vertex捆绑在一起。通过将一个bool添加到Vertex (以及Info)，可能会有3个或7个填充字节添加到结构中。如果您将visited放在一个单独的向量中，您可以回收该内存，甚至在不使用它时也不会分配它。您可以使用std::vector，它将所有的bools打包成位，并有一些限制，或者std::vector。在你使用它之前，调整它的大小，然后当你完成的时候清除它。这将让您摆脱unvisit_all方法，除非您希望保持它来适当地调整新向量的大小。如果这个向量被声明为mutable，那么您的is_connected和contains_loops可能被声明为const，这将是给定它们名称的期望。或者，这个新向量可以是需要它的函数中的局部变量，然后作为参数传递给其他需要它的函数，这将是一个必要的步骤(但不是唯一的一步)，以使类更友好地用于多线程使用。

还有一个关于风格的注意:你对空间的使用有点不典型。更常见的情况是，在关键字和paren之间，在close paren和卷曲括号之间有一个空格，比如if (condition) {。然而，你的用法是一致的，这是好的。此外，有时函数之间有空行，而有时则没有。在使用空格时，您可能会更加一致。