// @file design_of_networks.cc // @author Denis Felipe // @version 0.1 // // @brief // Design optimal networks, including computer, communication, transportation, water supply and electrical grids. // @warning // Contains C++11 features. // // @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 RANDOM_H #define RANDOM_H #include // Random devices and distributions namespace rng { // @brief // Access the random number engine used to generate pseudo-random numbers. // // @return default_random_engine // Random number engine. std::mt19937& global_urng() { static std::mt19937 u{}; return u; } // function global_urng // @brief // Use a true random number generator to re-initialize the internal state value of the random number engine. void randomize() { static std::random_device rd{}; global_urng().seed(rd()); } // function randomize // @brief // Set a seed to re-initialize the internal state value of the random number engine. // // @param unsigned int $seed // Seeding value. void randomize(const unsigned int& seed) {global_urng().seed(seed);} // function randomize // @brief // Generate a pseudo-random integer number in the range [$from, $thru] according to a uniform discrete distribution. // // @param int $from // Lower bound of range. // @param int $thru // Upper bound of range. const int pick_a_number(const int& from, const int& thru) { static std::uniform_int_distribution<> d{}; using parm_t = decltype(d)::param_type; return d(global_urng(), parm_t{from, thru}); } // function pick_a_number // @brief // Generate a pseudo-random real number in the range [$from, $upto) according to a uniform distribution. // // @param int $from // Lower bound of range. // @param int $upto // Upper bound of range. const double pick_a_number(const double& from, const double& upto) { static std::uniform_real_distribution<> d{}; using parm_t = decltype(d)::param_type; return d(global_urng(), parm_t{from, upto}); } // function pick_a_number } // namespace rng #endif // #define RANDOM_H // #define guard to prevent multiple inclusion. #ifndef BINARY_HEAP_H #define BINARY_HEAP_H #include #include namespace data_structure { // @class BinaryHeap // @brief // Binary Heap data structure. template class BinaryHeap { public: // Constructor BinaryHeap() {;} // ctor // Constructor // @param size_t $capacity // Initial capacity of the heap. BinaryHeap(const size_t& capacity) {binary_heap_.reserve(capacity);} // ctor // Destructor ~BinaryHeap() {;} // dtor // @brief // Check if heap is empty. // @return bool // True if heap has zero elements, false otherwise. const bool empty() const {return binary_heap_.empty();} // function empty // @brief // Access number of elements in heap. // @return size_t // Number of elements. const size_t size() const {return binary_heap_.size();} // function size // @brief // Access first element in heap. // @return T // First element. const T& find_min() const {return binary_heap_.front();} // function find_min // @brief // Add a new element in heap, effectively increasing the container size by one. // @param T $element // New element. void insert(const T& element) { binary_heap_.push_back(element); std::push_heap(binary_heap_.begin(), binary_heap_.end(), [](const T& a, const T& b){return a > b;}); } // function insert // @brief // Remove the minimum element of heap, effectively decreasing the container size by one. void delete_min() { std::pop_heap(binary_heap_.begin(), binary_heap_.end(), [](const T& a, const T& b){return a > b;}); binary_heap_.pop_back(); } // function delete_min // @brief // Random access to element in heap. // @param size_t $index // Index of element. // @return T // Element at index $index. const T& at(const size_t& index) {return binary_heap_.at(index);} // function at // @brief // Update an element in heap to a lower key. // @param size_t $index // Index of element. // @param T $element // New value with a lower key. void increase_key(const size_t& index, const T& element) { binary_heap_.at(index) = element; size_t current = index; size_t parent = current / 2; while (current > 0 && binary_heap_.at(current) < binary_heap_.at(parent)) { std::swap(binary_heap_.at(current), binary_heap_.at(parent)); current = parent; parent = current / 2; } } // function increase_key // @brief // Update an element in heap to a lower key. // @param size_t $index // Index of element. // @param T $element // New value with a lower key. void decrease_key(const size_t& index, const T& element) { binary_heap_.at(index) = element; size_t current; size_t left; size_t right; size_t lesser = index; do { current = lesser; left = current * 2; right = (current * 2) + 1; if (left < binary_heap_.size() && binary_heap_.at(left) < binary_heap_.at(lesser)) {lesser = left;} if (right < binary_heap_.size() && binary_heap_.at(right) < binary_heap_.at(lesser)) {lesser = right;} if (lesser != current) {std::swap(binary_heap_.at(current), binary_heap_.at(lesser));} } while (lesser != current); } // function decrease_key private: // @brief // Heap container. std::vector binary_heap_; }; // class BinaryHeap } // namespace data_structure #endif // BINARY_HEAP_H #ifndef MST_H #define MST_H #include #include #include 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 #include int main(int argc, char** argv) { algorithm::MST mst(5); // Generate a random set of nodes to be connected in a network. The weight $mst.graph($i, $j) represents the cost (money, distance, time, etc.) to connect node $i to node $j. std::list> solution(std::move(mst.prim())); // Find the optimal network by solving the minimum spanning tree problem. // 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

Design of optimal networks (computer, communication, transportation, water supply, electrical, etc.)