src.main/CjNLTopology.hh

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * mitie
 * Copyright (C) Jason Spencer 2009 <mitie@jasonspencer.org>
 * 
 * mitie is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * mitie is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef _CJNLTOPOLOGY_H_
#define _CJNLTOPOLOGY_H_ 1

#define INFWEIGHT 9999999 // 99999      // for APSP and others

#include <string>
#include <vector>
#include <stdexcept>    // TODO or exception?
#include <list>
#include <map>
#include <functional>
#include <utility>      // pair
#include "CjMatrix.hh"
#include "CjNLTopologyException.hh"
#include <boost/lexical_cast.hpp>
#include <boost/logic/tribool.hpp>

#include <boost/random/mersenne_twister.hpp>
#include <boost/random.hpp>

namespace jmitie {

namespace corelib {
}
using boost::logic::tribool;

// This is the maximum number of proxy bridge values ( see CjNLTopology::m_bridge_vals ) - when all values have been allocated then a compaction is forced. This cannot be smaller than 5
#define MAX_BRIDGE_VALS 1000

class CjNLTopology {
public:
        typedef int WT;
        typedef int LD;

        typedef std::pair< unsigned int, WT > adjwl_pair_t;

        typedef std::pair< unsigned int, LD > lpl_pair_t;

        typedef std::pair< unsigned int, unsigned int > rpl_pair_t;
        
        enum layercapab_t { NONE = 0, DIST = 1, GEO = (1 << 1), RPL = (1 << 2), RPN = (1 << 3), LPL = (1 << 4), LPN = (1 << 5) };

        struct link_t {
                link_t( unsigned int node_a_, unsigned int node_b_, WT wt_ab_, WT wt_ba_ ):node_a(node_a_),node_b(node_b_),wt_ab(wt_ab_),wt_ba(wt_ba_) {}
                unsigned int node_a;
                unsigned int node_b;
                WT wt_ab;
                WT wt_ba;
        };
        
private:
        void APSP_DFSearch() const;
        void APSP_DFSearch_localcache() const;
        void APSP_DFSrecursive(const int from, const int currNode, const int currDistance, int *distances ) const;
        void APSP_DFSrecursive_localcache(const int from, const int currNode, const unsigned int numHops, const int currDistance, int *distances, adjwl_pair_t ** adjL ) const;
        WT updateCell(const unsigned int row, const unsigned int col, WT & cell, const WT new_weight);
        void DFSrecursive(const unsigned int where, bool *visited, unsigned int &numVisited, const unsigned int skip_a = 0, const unsigned int skip_b = 0 ) const;
        CjNLTopology(const CjNLTopology &);     // prevent copying of CjNLTopology objects

protected:
        struct adjlist_cmp_lt : public std::binary_function<adjwl_pair_t, adjwl_pair_t, bool> { bool operator()( const adjwl_pair_t & lhs, const adjwl_pair_t & rhs ) { return lhs.first < rhs.first; /* return std::less(lhs,rhs); */ } };
        struct adjlist_cmp_eq : public std::binary_function<adjwl_pair_t, adjwl_pair_t, bool> { bool operator()( const adjwl_pair_t & lhs, const adjwl_pair_t & rhs ) { return ((lhs.first == rhs.first) && (lhs.second == rhs.second)); /* return std::less(lhs,rhs); */ } };
//      struct adjlist_cmp_eqnode : public std::binary_function<adjwl_pair_t, adjwl_pair_t, bool> { bool operator()( const adjwl_pair_t & lhs, const adjwl_pair_t & rhs ) { return lhs.first == rhs.first; /* return std::less(lhs,rhs); */ } };

        std::string m_name;
        unsigned int m_numNodes;
        const unsigned int m_maxNodes;
        unsigned int m_numLinks;
        CjMatrix <WT> * m_wt;   // the link weights
        const CjMatrix <LD> * m_traf;
        const CjMatrix<double> * m_geo;

        unsigned int * m_tiebreaker;

        enum apsp_t { APSP_MAT = 1, APSP_DFS, APSP_DFSLC, APSP_LAST  };
 // APSP_MAT_MT Floyd Warshall multi-threaded

        apsp_t m_apsp;

// secondary variables - the following variables are all somehow derived from m_wt

        mutable bool m_autoSync;

        mutable std::vector<adjwl_pair_t> * m_adj_wtlist;

        mutable bool m_valid_adj_wtlist;


        mutable CjMatrix <unsigned int> * m_rpl;        //      this isn't the most compact way of storing rpls - a list would be better - or better still together with weight in adjlist - but based on performance tests this is the most cahce friendly (weird, I know).

        mutable bool m_valid_rpl;


        mutable CjMatrix <LD> * m_lpl;  //      see m_rpl comments
        mutable bool m_valid_lpl;


        mutable unsigned int * m_rpn;   //      [m_maxNodes] array
        mutable bool m_valid_rpn;

        mutable LD * m_lpn;     //      [m_maxNodes] array
        mutable bool m_valid_lpn;

// keeping a record of the last removed and added links is a bit of a hack - it should probably be stored in the process arguments, however they could apply to different topologies
        link_t m_lastRemoved;
        bool m_lastRemoved_set;
        link_t m_lastAdded;
        bool m_lastAdded_set;


        mutable CjMatrix <tribool *> * m_isBridge;

        mutable bool m_valid_isBridge;

        mutable tribool m_bridge_vals [MAX_BRIDGE_VALS];

        mutable tribool * m_ptr_true;

        mutable tribool * m_ptr_false;

        mutable tribool * m_ptr_ind;

        mutable CjMatrix <WT> * m_distances;    // the distance between every node pair (numNodes,numNodes) in size
        mutable bool m_valid_distances;

        mutable unsigned int * m_node_degree;//  [m_maxNodes];
        mutable bool m_valid_node_degree;

        bool mk_adjL() const;

        bool mk_distances() const;
        bool mk_node_degrees() const;

        bool mk_lrpn_lrpl() const;

        void compact_bridge_vals() const;
        void invalidateBridges() const;
        void invalidateNonBridges() const;
        void init_bridge_vals() const;
                
public:

        CjNLTopology( const std::string name, unsigned int maxNodes, const CjMatrix<WT> & weightMatrix, const CjMatrix<LD> * trafficMatrix = 0, const CjMatrix<double> * geo = 0 );
        void init_tiebreaker( boost::mt19937 * m_rng = 0 );

        void initRPN() const;

        void initRPL() const;

        void initLPN() const;

        void initLPL() const;
        std::string getName() const { return m_name; }

        bool hasCapability( CjNLTopology::layercapab_t c ) const { return ( ( c & getCapability() ) == c ); }
        CjNLTopology::layercapab_t getCapability() const;

        unsigned int getRPL(unsigned int from, unsigned int to) const;

        CjNLTopology::LD getLPL(unsigned int from, unsigned int to) const;

        unsigned int getRPN(unsigned int node) const;

        CjNLTopology::LD getLPN(unsigned int node) const;


        const CjMatrix <LD> * getTrafficMatrix() const { return m_traf; }

        const CjMatrix <double> * getGeoMatrix() const { return m_geo; }

        double getGeoDistance(unsigned int a, unsigned int b) const { return m_geo->at(a,b); }

        bool getAutoSync() const { return m_autoSync; }
        bool setAutoSync(bool newval) const { bool oldval = m_autoSync; m_autoSync = newval; return oldval; }


        WT getWeight(const unsigned int node_a, const unsigned int node_b) const;

        WT setWeight(const unsigned int node_a, const unsigned int node_b, const WT new_weight);

        std::pair<CjNLTopology::WT, CjNLTopology::WT> setBiDirWeights(const unsigned int node_a, const unsigned int node_b, const WT ab, const WT ba );

        bool isFullyConnected(bool testDirectionally = false, unsigned int skip_a = 0, unsigned int skip_b = 0 ) const;

        bool isSymmetric() { return m_wt->isSymmetric(); }

        unsigned int getDegree(const unsigned int node) const;


        CjNLTopology::WT getDistance(unsigned int from, unsigned int to ) const;


        CjNLTopology::WT operator()(unsigned int node_a, unsigned int node_b );

        CjNLTopology::WT operator()(unsigned int node_a, unsigned int node_b, CjNLTopology::WT new_weight);

        const std::vector<adjwl_pair_t> * getNeighbours(const unsigned int node) const;

        unsigned int nextHop (const unsigned int where, const unsigned int destination ) const;

        bool isBridgeLink(const unsigned int from, const unsigned int to) const;

        tribool getBridgeState(const unsigned int from, const unsigned int to) const;

        unsigned int addDisconnectedNode();

        unsigned int newNodeNumber() const throw();

        unsigned int addNodeAndConnect(const unsigned int other, const WT to_other, const WT from_other );

        void bulkSetWeight( std::vector<link_t> & pairs, bool bidir = false );
        unsigned int getNumNodes() const {return m_numNodes;}
        unsigned int getNumLinks() const {return m_numLinks;}
        unsigned int getMaxNodes() const {return m_maxNodes;}
        unsigned int getNumSelfLoops() const;

        double fractionConnectedNodePairs(bool incSelfLoops=false) const;
        CjNLTopology::link_t getLastRemovedLink() const;
        CjNLTopology::link_t getLastAddedLink() const;
        bool forceAdjListUpdate() const;
        bool forceDistancesUpdate() const;

        bool checkAdjL_integrity() const;

        bool checkDegD_integrity() const;
        ~CjNLTopology();

};

inline CjNLTopology::layercapab_t operator| (CjNLTopology::layercapab_t a, CjNLTopology::layercapab_t b) { return CjNLTopology::layercapab_t(static_cast<int>(a) | static_cast<int>(b)); }
inline CjNLTopology::layercapab_t operator& (CjNLTopology::layercapab_t a, CjNLTopology::layercapab_t b) { return CjNLTopology::layercapab_t(static_cast<int>(a) & static_cast<int>(b)); }
inline CjNLTopology::layercapab_t & operator|= (CjNLTopology::layercapab_t & a, CjNLTopology::layercapab_t b) { return a = a | b; }
inline CjNLTopology::layercapab_t & operator&= (CjNLTopology::layercapab_t & a, CjNLTopology::layercapab_t b) { return a = a & b; }


inline double CjNLTopology::fractionConnectedNodePairs(bool incSelfLoops) const {
        return (double)m_numLinks/(double)(m_numNodes*(m_numNodes - (incSelfLoops?0:1)));
}

inline unsigned int CjNLTopology::getDegree(const unsigned int node) const {
        if(node>=m_numNodes) throw E_CjNLT_BoundsError("CjNLTopology::getDegree(const unsigned int node): Requested node " + boost::lexical_cast<std::string>(node) + " is more than the number of nodes, " + boost::lexical_cast<std::string>(m_numNodes) + ".");
        mk_node_degrees();
        return m_node_degree[node];
}

inline CjNLTopology::WT CjNLTopology::getWeight(const unsigned int row, const unsigned int col) const { return m_wt->at(row,col); }
inline CjNLTopology::WT CjNLTopology::setWeight(const unsigned int row, const unsigned int col, const WT new_weight) {  // throws E_CjMatrix_BoundsError
        CjNLTopology::WT & cell = m_wt->at(row,col);    // could throw
        return updateCell(row, col, cell, new_weight);
}

inline std::pair<CjNLTopology::WT, CjNLTopology::WT> CjNLTopology::setBiDirWeights(const unsigned int node_a, const unsigned int node_b, const WT ab, const WT ba ) {
        CjNLTopology::WT & a_to_b = m_wt->at( node_a, node_b ); // could throw
        CjNLTopology::WT & b_to_a = m_wt->at( node_b, node_a ); // could throw
        CjNLTopology::WT old_ab = updateCell( node_a, node_b, a_to_b, ab);
        CjNLTopology::WT old_ba = updateCell( node_b, node_a, b_to_a, ba);
        return std::make_pair(old_ab, old_ba);
}

inline CjNLTopology::WT CjNLTopology::operator()(const unsigned int row, const unsigned int col, const WT new_weight) {
        CjNLTopology::WT & cell = m_wt->operator()(row,col);    // won't throw if out of bounds
        return updateCell(row, col, cell, new_weight);
}

inline CjNLTopology::WT CjNLTopology::operator()(const unsigned int row, const unsigned int col) {
        return m_wt->operator()(row,col); // won't throw if out of bounds
}

// link_t::wt_ba will always be 0 as the removal is of a singular link
inline CjNLTopology::link_t CjNLTopology::getLastRemovedLink() const {
        if (m_lastRemoved_set) return m_lastRemoved;
        else throw std::runtime_error("There is no previous removed link");
        }

// link_t::wt_ba will always be 0 as the addition is of a singular link
inline CjNLTopology::link_t CjNLTopology::getLastAddedLink() const {
        if (m_lastAdded_set) return m_lastAdded;
        else throw std::runtime_error("There is no previous added link");
        }

class RandomSource : public std::unary_function <ptrdiff_t, ptrdiff_t> {
protected:
        boost::uniform_01<> w;
        boost::variate_generator<boost::mt19937&, boost::uniform_01<> > ball;
public:
        RandomSource( boost::mt19937& rng ):w(),ball(rng,w) {}
        ptrdiff_t operator()(ptrdiff_t i) { return ((ptrdiff_t)(ball()*(double)i))%i; }
};

struct Scoped_autosync_disable {
        bool m_status;
        CjNLTopology & m_top;
        Scoped_autosync_disable (CjNLTopology & top):m_status(top.setAutoSync(false)),m_top(top) {}
        ~Scoped_autosync_disable() { m_top.setAutoSync(m_status); }
};

} // namespace jmitie

#endif // _CJNLTOPOLOGY_H_