// @file mst.h // @author Denis Felipe // @version 0.1 // // @brief // Minimum Spanning Tree problem. // // @example // #include // #include "mst.h" // // int main(int argc, char** argv) // { // algorithm::MST mst(5); // std::list> solution(std::move(mst.prim())); // // // Print graph and solution. // double solution_weight = 0.0; // std::cout << "Graph" << std::endl; // for (size_t i = 0; i < mst.size(); ++i) // { // for (size_t j = 0; j < mst.size(); ++j) // {std::cout << mst.graph(i, j) << " ";} // std::cout << std::endl; // } // std::cout << "Solution" << std::endl; // for (const auto& u : solution) // { // std::cout << u.first << " - " << u.second << " (" << mst.graph(u.first, u.second) << ")" << std::endl; // solution_weight += mst.graph(u.first, u.second); // } // std::cout << "Solution weight: " << solution_weight << std::endl; // // return 0; // } // function main // // @section LICENSE // Copyright (c) 2017, Denis Felipe // All rights reserved. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are met: // // 1. Redistributions of source code must retain the above copyright notice, this // list of conditions and the following disclaimer. // 2. Redistributions in binary form must reproduce the above copyright notice, // this list of conditions and the following disclaimer in the documentation // and/or other materials provided with the distribution. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR // ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // // The views and conclusions contained in the software and documentation are those // of the authors and should not be interpreted as representing official policies, // either expressed or implied, of the FreeBSD Project. // #define guard to prevent multiple inclusion. #ifndef MST_H #define MST_H #include #include #include #include "binary_heap.h" #include "random.h" namespace algorithm { // @class MST // @brief // Minimum Spanning Tree problem. class MST { public: // Default constructor MST() {;} // ctor // Copy constructor MST(const MST& rhs) : graph_(rhs.graph_) {;} // ctor // Move constructor MST(const MST&& rhs) : graph_(std::move(rhs.graph_)) {;} // ctor // Constructor // @param size_t $size // Number of vertices. MST(const size_t& size) : graph_(size) { rng::randomize(); // Select a random seed for the pseudo-random number generator. for (auto& u : graph_) // Initialize the graph. {u.resize(size);} for (size_t i = 0; i < size; ++i) { for (size_t j = i + 1; j < size; ++j) {insert_edge(i, j, rng::pick_a_number(10.0, 100.0));} } } // ctor // Constructor // @param size_t $graph // Weighted graph. MST(const std::vector>& graph) : graph_(graph) {;} // ctor // Constructor // @param size_t $graph // Weighted graph. MST(const std::vector>&& graph) : graph_(std::move(graph)) {;} // ctor // Destructor ~MST() {;} // dtor // Copy assignment operator const MST& operator=(const MST& rhs) { if (this != &rhs) // Avoid self-assignment. {graph_ = rhs.graph_;} return *this; // Allow cascaded assignment. } // Copy assignment // Move assignment operator const MST& operator=(const MST&& rhs) { if (this != &rhs) // Avoid self-assignment. {graph_ = std::move(rhs.graph_);} return *this; // Allow cascaded assignment. } // Move assignment // @brief // Find the minimum spanning tree of a graph. // @return list> // List of edges in the minimum spanning tree. std::list> prim() { std::list> solution; // List of edges in the minimum spanning tree. size_t in_vertex = rng::pick_a_number(0, size() - 1); // Start from a random vertex. size_t out_vertex; data_structure::BinaryHeap>> binary_heap; // Priority queue. for (size_t i = 0; i < in_vertex; ++i) {binary_heap.insert(std::make_pair(graph(in_vertex, i), std::make_pair(in_vertex, i)));} for (size_t i = in_vertex + 1; i < size(); ++i) {binary_heap.insert(std::make_pair(graph(in_vertex, i), std::make_pair(in_vertex, i)));} while (!binary_heap.empty()) // Insert the shortest edge connecting a visited vertex to an unvisited one. { in_vertex = binary_heap.find_min().second.first; out_vertex = binary_heap.find_min().second.second; solution.push_back(std::make_pair(in_vertex, out_vertex)); binary_heap.delete_min(); in_vertex = out_vertex; for (size_t i = 0; i < binary_heap.size(); ++i) { out_vertex = binary_heap.at(i).second.second; if (graph(in_vertex, out_vertex) < binary_heap.at(i).first) {binary_heap.increase_key(i, std::make_pair(graph(in_vertex, out_vertex), std::make_pair(in_vertex, out_vertex)));} } } return std::move(solution); } // function prim // @brief // Access number of vertices in graph. // @return size_t // Number of vertices. const size_t size() const {return graph_.size();} // function size // @brief // Add an edge in graph. // @param size_t $vertex_a // First vertex of edge. // @param size_t $vertex_b // Second vertex of edge. // @param double $weight // Weight of edge ($vertex_a, $vertex_b). void insert_edge(const size_t& vertex_a, const size_t& vertex_b, const double& weight) {graph_.at(vertex_a).at(vertex_b) = graph_.at(vertex_b).at(vertex_a) = weight;} // function insert_edge // @brief // Random access to edge of graph. // @param size_t $vertex_a // First vertex of edge. // @param size_t $vertex_b // Second vertex of edge. // @return double // Weight of edge ($vertex_a, $vertex_b). const double graph(const size_t& vertex_a, const size_t& vertex_b) const {return graph_.at(vertex_a).at(vertex_b);} // function graph private: // @brief // Graph container. std::vector> graph_; }; // class MST } // namespace algorithm #endif // MST_H