Partition.hpp

/***********************************************************/
/***      ______  ____  ______                 _         ***/
/***     / ___\ \/ /\ \/ / ___|_ __ __ _ _ __ | |__      ***/
/***    | |    \  /  \  / |  _| '__/ _` | '_ \| '_ \     ***/
/***    | |___ /  \  /  \ |_| | | | (_| | |_) | | | |    ***/
/***     \____/_/\_\/_/\_\____|_|  \__,_| .__/|_| |_|    ***/
/***                                    |_|              ***/
/***********************************************************/
/***     Header-Only C++ Library for Graph               ***/
/***     Representation and Algorithms                   ***/
/***********************************************************/
/***     Author: ZigRazor                                ***/
/***     E-Mail: zigrazor@gmail.com                      ***/
/***********************************************************/
/***     Collaboration: -----------                      ***/
/***********************************************************/
/***     License: AGPL v3.0                              ***/
/***********************************************************/
 
#ifndef __CXXGRAPH_PARTITION_H__
#define __CXXGRAPH_PARTITION_H__
 
#pragma once
 
#include <list>
#include <unordered_set>
 
#include "Utility/Typedef.hpp"
#include "PartitioningStats.hpp"
 
namespace CXXGRAPH
{
    template <typename T>
    class Graph;
 
    template<typename T>
    using T_EdgeSet = std::unordered_set<const Edge<T> *>;
    namespace PARTITIONING
    {
        template <typename T>
        std::ostream &operator<<(std::ostream &o, const Partition<T> &partition);
 
        template <typename T>
        class Partition : public Graph<T>
        {
        public:
            Partition();
            Partition(unsigned int partitionId);
            Partition(const T_EdgeSet<T> &edgeSet);
            Partition(unsigned int partitionId, const T_EdgeSet<T> &edgeSet);
            ~Partition() = default;
            unsigned int getPartitionId() const;
            void setPartitionId(unsigned int partitionId);
 
        private:
            unsigned int partitionId = 0;
        };
 
        template <typename T>
        static PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        static unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap);
 
        template <typename T>
        Partition<T>::Partition() : Graph<T>()
        {
            partitionId = 0;
        }
 
        template <typename T>
        Partition<T>::Partition(unsigned int partitionId) : Graph<T>()
        {
            this->partitionId = partitionId;
        }
 
        template <typename T>
        Partition<T>::Partition(const T_EdgeSet<T> &edgeSet) : Graph<T>(edgeSet)
        {
            partitionId = 0;
        }
 
        template <typename T>
        Partition<T>::Partition(unsigned int partitionId, const T_EdgeSet<T> &edgeSet) : Graph<T>(edgeSet)
        {
            this->partitionId = partitionId;
        }
 
        template <typename T>
        unsigned int Partition<T>::getPartitionId() const
        {
            return partitionId;
        }
 
        template <typename T>
        void Partition<T>::setPartitionId(unsigned int partitionId)
        {
            this->partitionId = partitionId;
        }
 
        template <typename T>
        PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap)
        {
            PartitioningStats result;
            result.numberOfPartitions = partitionMap.size();
            result.numberOfNodes = getNumberOfNodes(partitionMap);
            result.numberOfEdges = getNumberOfEdges(partitionMap);
            result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
            result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
            result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
            result.minEdgesLoad = getMinEdgesLoad(partitionMap);
            result.maxNodesLoad = getMaxNodesLoad(partitionMap);
            result.minNodesLoad = getMinNodesLoad(partitionMap);
            result.edgesReplicationFactor = static_cast<double>(result.replicatedEdgesCount / result.numberOfEdges);
            result.nodesReplicationFactor = static_cast<double>(result.replicatedNodesCount / result.numberOfNodes);
            result.balanceEdgesFactor = static_cast<double>((result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad));
            result.balanceNodesFactor = static_cast<double>((result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad));
            return result;
        }
 
        template <typename T>
        unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap)
        {
            unsigned int maxLoad = 0;
            for (const auto& it : partitionMap)
            {
                if (it.second->getEdgeSet().size() > maxLoad)
                {
                    maxLoad = it.second->getEdgeSet().size();
                }
            }
            return maxLoad;
        }
 
        template <typename T>
        unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap)
        {
            unsigned int minLoad = std::numeric_limits<unsigned int>::max();
            for (const auto& it : partitionMap)
            {
                if (it.second->getEdgeSet().size() < minLoad)
                {
                    minLoad = it.second->getEdgeSet().size();
                }
            }
            return minLoad;
        }
 
        template <typename T>
        unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap)
        {
            unsigned int maxLoad = 0;
            for (const auto& it : partitionMap)
            {
                if (it.second->getNodeSet().size() > maxLoad)
                {
                    maxLoad = it.second->getNodeSet().size();
                }
            }
            return maxLoad;
        }
 
        template <typename T>
        unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap)
        {
            unsigned int minLoad = std::numeric_limits<unsigned int>::max();
            for (const auto& it : partitionMap)
            {
                if (it.second->getNodeSet().size() < minLoad)
                {
                    minLoad = it.second->getNodeSet().size();
                }
            }
            return minLoad;
        }
 
        template <typename T>
        unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap)
        {
            unsigned int numberOfEdges = 0;
            T_EdgeSet<T> edgeSet;
 
            for (const auto& it : partitionMap)
            {
                const T_EdgeSet<T> partitionEdgeSet = it.second->getEdgeSet();
                for (const auto& it2 : partitionEdgeSet)
                {
                    if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](const Edge<T> *edge)
                                     { return (*it2 == *edge); }) == edgeSet.end())
                    {
                        edgeSet.insert(it2);
                    }
                }
            }
 
            return edgeSet.size();
        }
 
        template <typename T>
        unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap)
        {
            unsigned int numberOfNodes = 0;
            std::deque<const Node<T> *> nodeSet;
 
            for (const auto& it : partitionMap)
            {
                const std::deque<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
                for (const auto& it2 : partitionNodeSet)
                {
                    if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](const Node<T> *node)
                                     { return (*it2 == *node); }) == nodeSet.end())
                    {
                        nodeSet.push_back(*it2);
                    }
                }
            }
 
            return nodeSet.size();
        }
 
        template <typename T>
        unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap)
        {
 
            unsigned int numberOfEdges = 0;
            for (const auto& it : partitionMap)
            {
                numberOfEdges += it.second->getEdgeSet().size();
            }
            return numberOfEdges;
        }
 
        template <typename T>
        unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap)
        {
            unsigned int numberOfNodes = 0;
            for (const auto& it : partitionMap)
            {
                numberOfNodes += it.second->getNodeSet().size();
            }
            return numberOfNodes;
        }
 
        template <typename T>
        std::ostream &operator<<(std::ostream &os, const Partition<T> &partition)
        {
            os << "Partition " << partition.getPartitionId() << ":\n";
            auto edgeList = partition.getEdgeSet();
            for (const auto& it : edgeList)
            {
                if(!(*it)->isDirected().has_value() && !(*it)->isWeighted().has_value()){
                    // Edge Case 
                    os << **it << "\n";
                }
                else if (((*it)->isDirected().has_value()&& (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
                {
                    os << dynamic_cast<const DirectedWeightedEdge<T> &>(*it) << "\n";
                }
                else if ((it->isDirected().has_value() && it->isDirected().value())  && !(it->isWeighted().has_value() && it->isWeighted().value()))
                {
                    os << dynamic_cast<const DirectedEdge<T> &>(*it) << "\n";
                }
                else if (!(it->isDirected().has_value() && it->isDirected().value()) && (it->isWeighted().has_value() && it->isWeighted().value()))
                {
                    os << dynamic_cast<const UndirectedWeightedEdge<T> &>(*it) << "\n";
                }
                else if (!(it->isDirected().has_value() && it->isDirected().value()) && !(it->isWeighted().has_value() && it->isWeighted().value()))
                {
                    os << dynamic_cast<const UndirectedEdge<T> &>(*it) << "\n";
                }
                else
                {
                    //Should never happens
                    os << "Wrong Edge Class" << "\n";
                }
            }
            return os;
        }
    }
 
}
 
#endif // __CXXGRAPH_PARTITION_H__