A class representing the topology of a network layer. More...
#include <CjNLTopology.hh>
Classes | |
| struct | adjlist_cmp_eq |
| a functor to check for equality in adjwl_pair_t objects - comparison is based on node number of adjacency and respective weight More... | |
| struct | adjlist_cmp_lt |
| struct | link_t |
| A struct describing a simple link: two end-point nodes and the weight of the link in either direction. More... | |
Public Types | |
| enum | layercapab_t { NONE = 0, DIST = 1, GEO = (1 << 1), RPL = (1 << 2), RPN = (1 << 3), LPL = (1 << 4), LPN = (1 << 5) } |
A bit-mask for the capabilities of this CjNLTopology instance. More... | |
| typedef int | WT |
| the type stored in the weights matrix | |
| typedef int | LD |
| the unit of network load - used in the traffic matrix and various other places like LPN/LPL matrices | |
| typedef std::pair< unsigned int, WT > | adjwl_pair_t |
| Adjacency weight information type. | |
| typedef std::pair< unsigned int, LD > | lpl_pair_t |
| Adjacency link load information type. | |
| typedef std::pair< unsigned int, unsigned int > | rpl_pair_t |
| Adjacency link routes information type. | |
Public Member Functions | |
| CjNLTopology (const std::string name, unsigned int maxNodes, const CjMatrix< WT > &weightMatrix, const CjMatrix< LD > *trafficMatrix=0, const CjMatrix< double > *geo=0) | |
| Creates a new topology. | |
| void | init_tiebreaker (boost::mt19937 *m_rng=0) |
| Initialise the tiebreaker values for routing. An optional RNG can be supplied as an entropy source. | |
| void | initRPN () const |
| Initialise the RPN (Routes-Per-Node) functionality. | |
| void | initRPL () const |
| Initialise the RPL (Routes-Per-Link) functionality. | |
| void | initLPN () const |
| Initialise the LPN (Load-Per-Node) functionality. | |
| void | initLPL () const |
| Initialise the LPL (Load-Per-Link) functionality. | |
| std::string | getName () const |
| Returns the name of this layer (as specified in the constructor). | |
| bool | hasCapability (CjNLTopology::layercapab_t c) const |
| Checks whether all capabilities requested are available. | |
| CjNLTopology::layercapab_t | getCapability () const |
| Returns a bitmask of the available capabilities of this CjNLTopology. | |
| unsigned int | getRPL (unsigned int from, unsigned int to) const |
| Returns the number of routes (i.e. a full mesh of routes) traversing the link from node "from" to node "to". | |
| CjNLTopology::LD | getLPL (unsigned int from, unsigned int to) const |
| Returns the total traffic load (i.e. the sum of all demands in traffic matrix routed over this link) traversing the link from node "from" to node "to". | |
| unsigned int | getRPN (unsigned int node) const |
| Returns the total number of routes traversing, ingressing, or egressing node "node". | |
| CjNLTopology::LD | getLPN (unsigned int node) const |
| Returns the total traffic load (i.e. the sum of all demands in traffic matrix routed so they source, or terminate, or traverse this node) on node "node". | |
| const CjMatrix< LD > * | getTrafficMatrix () const |
| Returns the traffic matrix used in LPN, LPL calculations. | |
| const CjMatrix< double > * | getGeoMatrix () const |
| Returns the geographic distance matrix associated with this topology. | |
| double | getGeoDistance (unsigned int a, unsigned int b) const |
| Returns the normalised geographic distance between two nodes. | |
| bool | getAutoSync () const |
| DEPRECATED - returns the state of autosync - ie whether secondary variables are automatically updated (RPL, distances etc..). | |
| bool | setAutoSync (bool newval) const |
| DEPRECATED - enables/disables updates to secondary variables (RPL, distances etc..). | |
| WT | getWeight (const unsigned int node_a, const unsigned int node_b) const |
| Returns the weight of a single directional link in the topology. | |
| WT | setWeight (const unsigned int node_a, const unsigned int node_b, const WT new_weight) |
| Sets the weight of a single directional link in the topology. | |
| std::pair< CjNLTopology::WT, CjNLTopology::WT > | setBiDirWeights (const unsigned int node_a, const unsigned int node_b, const WT ab, const WT ba) |
| Sets the weights of both directions of a link in the topology. | |
| bool | isFullyConnected (bool testDirectionally=false, unsigned int skip_a=0, unsigned int skip_b=0) const |
| Checks whether the topology is partitioned or not. | |
| bool | isSymmetric () |
| Tests whether the topology matrix is symmetric. | |
| unsigned int | getDegree (const unsigned int node) const |
| Returns the outdegree of the specified node. | |
| CjNLTopology::WT | getDistance (unsigned int from, unsigned int to) const |
| Returns the minimum weight of a path between two nodes in the topology. | |
| CjNLTopology::WT | operator() (unsigned int node_a, unsigned int node_b) |
| Returns the weight of a single directional link in the topology. | |
| CjNLTopology::WT | operator() (unsigned int node_a, unsigned int node_b, CjNLTopology::WT new_weight) |
| Sets the weight of a single directional link in the topology. | |
| const std::vector< adjwl_pair_t > * | getNeighbours (const unsigned int node) const |
| Returns the outward links from a node. | |
| unsigned int | nextHop (const unsigned int where, const unsigned int destination) const |
| Returns the next hop along the least weight path through the topology. | |
| bool | isBridgeLink (const unsigned int from, const unsigned int to) const |
| Returns the bridge state of the specified link. | |
| tribool | getBridgeState (const unsigned int from, const unsigned int to) const |
| Returns the bridge state from the bridge state cache, but will not test for partitioning by removal of link. | |
| unsigned int | addDisconnectedNode () |
| Adds a single node to the network which is not connected to any existing node. | |
| unsigned int | newNodeNumber () const throw () |
| Returns the number of the node that would be returned with the next invocation of addDisconnectedNode(), but doesn't create or add the node. | |
| unsigned int | addNodeAndConnect (const unsigned int other, const WT to_other, const WT from_other) |
| Adds a single node to the network and connects it to a given existing node. | |
| void | bulkSetWeight (std::vector< link_t > &pairs, bool bidir=false) |
| Sets a group of link weights in one operation. | |
| unsigned int | getNumNodes () const |
| Returns the current number of nodes in the network. | |
| unsigned int | getNumLinks () const |
| Returns the current number of directional links in the network. | |
| unsigned int | getMaxNodes () const |
| Returns the maximum number of nodes the network can support. | |
| unsigned int | getNumSelfLoops () const |
| Returns the number of nodes that are connected to themselves. | |
| double | fractionConnectedNodePairs (bool incSelfLoops=false) const |
| Returns the fraction of node pairs that are linked compared to a full mesh. | |
| CjNLTopology::link_t | getLastRemovedLink () const |
| Returns the details of the last link that was removed from the network. | |
| CjNLTopology::link_t | getLastAddedLink () const |
| Returns the details of the last link that was added to the network. | |
| bool | forceAdjListUpdate () const |
| DEPRECATED. | |
| bool | forceDistancesUpdate () const |
| DEPRECATED. | |
| bool | checkAdjL_integrity () const |
| FOR TESTING USE ONLY - verifies the internal sparse adjacency matrix matches the weights matrix. | |
| bool | checkDegD_integrity () const |
| FOR TESTING USE ONLY - verifies that the internal list of node degrees matches the weights matrix. | |
Protected Types | |
| enum | apsp_t { APSP_MAT = 1, APSP_DFS, APSP_DFSLC, APSP_LAST } |
The routing algorithm options. More... | |
Protected Member Functions | |
| bool | mk_adjL () const |
| rebuilds m_adj_wtlist from m_wt if it is not invalid - returns true if an update had to be done, false otherwise | |
| bool | mk_distances () const |
| rebuilds m_distances from m_wt if it is not valid | |
| bool | mk_node_degrees () const |
| rebuilds m_node_degree from either m_adj_wtlist or m_wt | |
| bool | mk_lrpn_lrpl () const |
| rebuilds any of m_rpl, m_lpl, m_rpl m_lpl if necessary | |
| void | compact_bridge_vals () const |
| Rewrites values in m_isBridge and m_bridge_vals - see m_isBridge for details. | |
| void | invalidateBridges () const |
| All entries in m_isBridge which were [indirectly] true are set to [indirectly] indeterminate - see m_isBridge for details. | |
| void | invalidateNonBridges () const |
| All entries in m_isBridge which were [indirectly] false are set to [indirectly] indeterminate - see m_isBridge for details. | |
| void | init_bridge_vals () const |
| Initialise m_bridge_vals and m_isBridge. | |
Protected Attributes | |
| std::string | m_name |
| The name of this layer. | |
| unsigned int | m_numNodes |
| The number of nodes currently in this topology. | |
| const unsigned int | m_maxNodes |
| The maximum number of nodes that this topology can support. | |
| unsigned int | m_numLinks |
| The number of directional links in the topology - ie the number of non-zero weights in the weights matrix. | |
| CjMatrix< WT > * | m_wt |
| The weights matrix: m_wt(i,j) is the weight of the directional link from node i to node j. | |
| const CjMatrix< LD > * | m_traf |
| The traffic matrix as externally supplied - ownership is not assumed by CjNLTopology. | |
| const CjMatrix< double > * | m_geo |
| The normalised euclidean distance matrix as externally supplied - ownership is not assumed by CjNLTopology. | |
| unsigned int * | m_tiebreaker |
| An array of unique numbers which are shuffled on initialisation - they are used by nextHop() to make the final decision between equal-cost paths. | |
| apsp_t | m_apsp |
| which APSP algorithm is to be used (see apsp_t) | |
| bool | m_autoSync |
| if true then mk_*() and other functions will update any dependencies (adjacency list, weightsd matric etc..) that they require. set to false if making a large batch of updates to adjacency and don't want automatic updates after each update. TODO - this deserves to die - it breaks exception safety - leave it set to true and ignore. | |
| std::vector< adjwl_pair_t > * | m_adj_wtlist |
| The adjacency weights list. | |
| bool | m_valid_adj_wtlist |
| Validity flag for m_adj_wtlist. | |
| CjMatrix< unsigned int > * | m_rpl |
| The routes per link matrix. | |
| bool | m_valid_rpl |
| Validity flag for m_rpl. | |
| CjMatrix< LD > * | m_lpl |
| The load per link matrix. | |
| bool | m_valid_lpl |
| Validity flag for m_lpl. | |
| unsigned int * | m_rpn |
| The routes per node array. | |
| bool | m_valid_rpn |
| Validity flag for m_rpn. | |
| LD * | m_lpn |
| The load per node array. | |
| bool | m_valid_lpn |
| Validity flag for m_lpn. | |
| link_t | m_lastRemoved |
| The link that was last removed. | |
| bool | m_lastRemoved_set |
| m_lastRemoved validity flag | |
| link_t | m_lastAdded |
| The link that was last added. | |
| bool | m_lastAdded_set |
| m_lastAdded_set validity flag | |
| CjMatrix< tribool * > * | m_isBridge |
| A matrix which stores whether the link is a bridge. | |
| bool | m_valid_isBridge |
| m_isBridge validity flag | |
| tribool | m_bridge_vals [MAX_BRIDGE_VALS] |
| Array holding values for the indirect addressing in m_isBridge. | |
| tribool * | m_ptr_true |
| A pointer into m_bridge_vals which points to the current element in m_bridge_vals which is true. | |
| tribool * | m_ptr_false |
| A pointer into m_bridge_vals which points to the current element in m_bridge_vals which is false - see m_isBridge. | |
| tribool * | m_ptr_ind |
| A pointer into m_bridge_vals which points to the current element in m_bridge_vals which is indeterminate. | |
| CjMatrix< WT > * | m_distances |
| The minimal sum of weights between every node pair. | |
| bool | m_valid_distances |
| m_distances validity flag | |
| unsigned int * | m_node_degree |
| a cache of node degrees for every node | |
| bool | m_valid_node_degree |
| a validity flag for m_node_degree | |
A class representing the topology of a network layer.
This class stores a topology of nodes and directional links which describe a network layer.
A number of methods provide functionality which is closely related - including shortest path routing.
Other functionality, which in theory should be handled outside of this class, like geography and traffic load has been included to maximise performance. Traffic load calculations and geography are however optional.
Speed of execution is considered more important in the design of this class than memory footprint, therefore lazy calculation and local caching of data is extensively.
Topological distances, a sparse adjacency matrix, details about links, such as load and number of routes are cached and calculated only when necessary.
To prevent memory bloat some functionality is by default disabled and has to be enabled before use:
initRPN() should be called to allow the later look-up of Routes-Per-Node through getRPN()
initRPL() should be called to allow the later look-up of Routes-Per-Link through getRPL()
initLPN() should be called to allow the later look-up of Load-Per-Node through getLPN()
initLPL() should be called to allow the later look-up of Load-Per-Link through getLPL()
To test for which capabilities (including geography and traffix load) are present call hasCapability( CjNLTopology::layercapab_t c )
| typedef std::pair< unsigned int, WT > jmitie::CjNLTopology::adjwl_pair_t |
Adjacency weight information type.
The pair stores next hop node number and the weight of the link in that direction.
| typedef std::pair< unsigned int, LD > jmitie::CjNLTopology::lpl_pair_t |
Adjacency link load information type.
The pair stores next hop node number and the load of the link in that direction.
| typedef std::pair< unsigned int, unsigned int > jmitie::CjNLTopology::rpl_pair_t |
Adjacency link routes information type.
The pair stores next hop node number and the number of routes in that direction.
enum jmitie::CjNLTopology::apsp_t [protected] |
The routing algorithm options.
A bit-mask for the capabilities of this CjNLTopology instance.
| NONE |
Signifies that no capabilities are present. |
| DIST |
If set then this CjNLTopology is capable of returning information about topological distances. next hops and so on. |
| GEO |
If set then this CjNLTopology is capable of returning information about geography - specifically normalised inter-node distances through getGeoDistance() and getGeoMatrix(). |
| RPL |
If set then this CjNLTopology is capable of returning information about the number of routes traversing a given link. |
| RPN |
If set then this CjNLTopology is capable of returning information about the number of routes at a given node. |
| LPL |
If set then this CjNLTopology is capable of returning information about the traffic load on a link. |
| LPN |
If set then this CjNLTopology is capable of returning information about the traffic load on a node. |
| jmitie::CjNLTopology::CjNLTopology | ( | const std::string | name, | |
| unsigned int | maxNodes, | |||
| const CjMatrix< WT > & | weightMatrix, | |||
| const CjMatrix< LD > * | trafficMatrix = 0, |
|||
| const CjMatrix< double > * | geo = 0 | |||
| ) |
Creates a new topology.
This constructor is optionally provided with a traffix matrix (trafficMatrix) and euclidean geography (geo) - users of this object can test for their presence through hasCapability() and getCapability() The topology size after initialisation is the smaller of maxNodes and the height/width of weightMatrix
| name | An arbitrary name assigned to this CjNLTopology. | |
| maxNodes | The maximum number of nodes that this CjNLTopology can support. | |
| weightMatrix | The initial weights matrix. This must be square. | |
| trafficMatrix | The optional traffix matrix. This must be square. Ownership is not assumed. | |
| weightMatrix | The initial weights matrix. This must be square. Ownership is not assumed. | |
| geo | This matrix holds the geographic/euclidean distances between all node pairs. This must be square. Ownership is not assumed. |
| E_CjNLT_MemoryAllocFail | when memory cannot be allocated for internal data structures | |
| E_CjNLT_SizeError | in case the size parameters supplied are invalid (i.e. maxNodes is 0, or weightsMatrix is not square) |
| unsigned int jmitie::CjNLTopology::addDisconnectedNode | ( | ) |
Adds a single node to the network which is not connected to any existing node.
The number returned is the node number to use when connecting to the network with setWeight()
| E_CjNLT_SizeError | if the network is already maxNodes in size |
| unsigned int jmitie::CjNLTopology::addNodeAndConnect | ( | const unsigned int | other, | |
| const WT | to_other, | |||
| const WT | from_other | |||
| ) |
Adds a single node to the network and connects it to a given existing node.
The number returned is the node number of the node that was just added.
| E_CjNLT_SizeError | if the network is already maxNodes in size | |
| E_CjNLT_BoundsError | if an attempt is made to connect to a non-existing node |
| void jmitie::CjNLTopology::bulkSetWeight | ( | std::vector< link_t > & | pairs, | |
| bool | bidir = false | |||
| ) |
Sets a group of link weights in one operation.
All or none (on error) of the link weights will be set to the specified values. This method should be used with caution as it does not check for bridge removal i.e. network paritioning. This method is not re-entrant safe.
| pairs | a vector of link_t objects which specify the node of the link endpoints and the weight to set them | |
| bidir | if false then only linkt::wt_ab is read and applied to the network, otherwise linkt::wt_ab and linkt::wt_ba will be applied |
| E_CjMatrix_BoundsError | if any of the link_t::node_a or link_t::node_b values not less than numNodes |
| bool jmitie::CjNLTopology::checkAdjL_integrity | ( | ) | const |
FOR TESTING USE ONLY - verifies the internal sparse adjacency matrix matches the weights matrix.
returns true when they match
| bool jmitie::CjNLTopology::checkDegD_integrity | ( | ) | const |
FOR TESTING USE ONLY - verifies that the internal list of node degrees matches the weights matrix.
returns true when they match
| double jmitie::CjNLTopology::fractionConnectedNodePairs | ( | bool | incSelfLoops = false |
) | const [inline] |
Returns the fraction of node pairs that are linked compared to a full mesh.
| incSelfLoops | if true then links beginning and ending at the same node are also included |
| tribool jmitie::CjNLTopology::getBridgeState | ( | const unsigned int | from, | |
| const unsigned int | to | |||
| ) | const |
Returns the bridge state from the bridge state cache, but will not test for partitioning by removal of link.
Returns true if the links removal parition would the network, false if it wouldn't and boost::tribool::indeterminate if the answer is unknown. To update the bridge state cache use isBridgeLink()
| from | The start node of the link | |
| to | The end node of the link |
| E_CjMatrix_BoundsError | if argument node is equal to, or greater than, m_numNodes. |
| unsigned int jmitie::CjNLTopology::getDegree | ( | const unsigned int | node | ) | const [inline] |
Returns the outdegree of the specified node.
| node | The node for which to return the outdegree. You think!? |
| E_CjMatrix_BoundsError | if argument node is equal to, or greater than, m_numNodes. |
| CjNLTopology::WT jmitie::CjNLTopology::getDistance | ( | unsigned int | from, | |
| unsigned int | to | |||
| ) | const |
Returns the minimum weight of a path between two nodes in the topology.
APSP is performed and the sum of the link weights on the shortest path is returned
| from | the start node | |
| to | the destination node |
| E_CjMatrix_BoundsError | if argument nodes is equal to, or greater than, m_numNodes. | |
| E_CjNLT_RoutingError | when there is no path between the two nodes |
| double jmitie::CjNLTopology::getGeoDistance | ( | unsigned int | a, | |
| unsigned int | b | |||
| ) | const [inline] |
Returns the normalised geographic distance between two nodes.
Returns the normalised geographic distance between nodes a and b.
| const CjMatrix<double>* jmitie::CjNLTopology::getGeoMatrix | ( | ) | const [inline] |
Returns the geographic distance matrix associated with this topology.
This was specified in the constructor. Individual elements are available through getGeoDistance()
| CjNLTopology::LD jmitie::CjNLTopology::getLPL | ( | unsigned int | from, | |
| unsigned int | to | |||
| ) | const |
Returns the total traffic load (i.e. the sum of all demands in traffic matrix routed over this link) traversing the link from node "from" to node "to".
If initLPL() hasn't been first called then it will be called - and could throw anything that it could, otherwise, this won't throw. from and to are not bounds checked.
| CjNLTopology::LD jmitie::CjNLTopology::getLPN | ( | unsigned int | node | ) | const |
Returns the total traffic load (i.e. the sum of all demands in traffic matrix routed so they source, or terminate, or traverse this node) on node "node".
If initLPN() hasn't been first called then it will be called - and could throw anything that it could, otherwise, this won't throw. node is not bounds checked.
| const std::vector< CjNLTopology::adjwl_pair_t > * jmitie::CjNLTopology::getNeighbours | ( | const unsigned int | node | ) | const |
Returns the outward links from a node.
A vector of adjwl_pair_t objects is returned - this struct contains the outbound neighbour and the link weight. Beware: The pointer returned is only valid until any operation that may update the adjacency list is called. This method should only be used to scan neighbours for some property, or a copy of the returned pointed-to-vector should be made before making change to the topology.
| node | The node for which to return the neighbours. |
| E_CjMatrix_BoundsError | if argument node is equal to, or greater than, m_numNodes. |
| unsigned int jmitie::CjNLTopology::getRPL | ( | unsigned int | from, | |
| unsigned int | to | |||
| ) | const |
Returns the number of routes (i.e. a full mesh of routes) traversing the link from node "from" to node "to".
If initRPL() hasn't been first called then it will be called - and could throw anything that it could, otherwise, this won't throw. from and to are not bounds checked.
| unsigned int jmitie::CjNLTopology::getRPN | ( | unsigned int | node | ) | const |
Returns the total number of routes traversing, ingressing, or egressing node "node".
If initRPN() hasn't been first called then it will be called - and could throw anything that it could, otherwise, this won't throw. node is not bounds checked.
Returns the traffic matrix used in LPN, LPL calculations.
This was specified in the constructor
| CjNLTopology::WT jmitie::CjNLTopology::getWeight | ( | const unsigned int | node_a, | |
| const unsigned int | node_b | |||
| ) | const [inline] |
Returns the weight of a single directional link in the topology.
Returns the weight of a single directional link in the topology - use operator() for non-throwing (also non-bounds-checking version). A return value of 0 means the specified nodes are not connected.
| node_a | the start node of the directional link. | |
| node_b | the end node of the directional link. |
| E_CjMatrix_BoundsError | if either node_a or node_b are equal to, or greater than, m_numNodes. |
| bool jmitie::CjNLTopology::hasCapability | ( | CjNLTopology::layercapab_t | c | ) | const [inline] |
Checks whether all capabilities requested are available.
Checks whether all capabilities set in c are available.
c can either be any value of CjNLTopology::layercapab_t or an bitwise-ORed mask of values, e.g. hasCapability( GEO | RPL ) will return true if geography and routes-per-link are available.
| void jmitie::CjNLTopology::initLPL | ( | ) | const |
Initialise the LPL (Load-Per-Link) functionality.
| std::logic_error | If no traffic matrix was specified in the constructor. | |
| E_CjNLT_MemoryAllocFail | If LPL memory couldn't be allocated. |
| void jmitie::CjNLTopology::initLPN | ( | ) | const |
Initialise the LPN (Load-Per-Node) functionality.
| std::logic_error | If no traffic matrix was specified in the constructor. | |
| E_CjNLT_MemoryAllocFail | If LPN memory couldn't be allocated. |
| void jmitie::CjNLTopology::initRPL | ( | ) | const |
Initialise the RPL (Routes-Per-Link) functionality.
| E_CjNLT_MemoryAllocFail | If RPL memory couldn't be allocated. |
| void jmitie::CjNLTopology::initRPN | ( | ) | const |
Initialise the RPN (Routes-Per-Node) functionality.
| E_CjNLT_MemoryAllocFail | If RPN memory couldn't be allocated. |
| bool jmitie::CjNLTopology::isBridgeLink | ( | const unsigned int | from, | |
| const unsigned int | to | |||
| ) | const |
Returns the bridge state of the specified link.
Returns true if the links removal parition would the network, false otherwise. This is a potentially expensive operation since a single-source (TODO) walk is required across the network if the answer is not cached, but it is the only way to know for sure. In comparison getBridgeState() only returns the state stored in the cache (so answer could be tribool::indeterminate - without performing the test)
| from | The start node of the link | |
| to | The end node of the link |
| E_CjMatrix_BoundsError | if argument node is equal to, or greater than, m_numNodes. | |
| E_CjNLT_RoutingError | if one of the links reach a node that doesn't exist yet (according to numNodes) or if there is an internal error with routing and link weights |
| bool jmitie::CjNLTopology::isFullyConnected | ( | bool | testDirectionally = false, |
|
| unsigned int | skip_a = 0, |
|||
| unsigned int | skip_b = 0 | |||
| ) | const |
Checks whether the topology is partitioned or not.
Performs a walk of the topology to see if all nodes can be reached.
If testDirectionally is false then the walk will only be performed from one source node, otherwise it will be done from all m_numNodes nodes.
A link can be optionally specified which will be assumed not to exist during the walk - this is useful for checking whether it is a bridge link.
| testDirectionally | If true the testing will assume the links are directional. | |
| skip_a | the start node of a link to omit when performing the walk. | |
| skip_b | the end node of a link to omit when performing the walk. |
| E_CjMatrix_BoundsError | if either row or col are equal to, or greater than, m_numNodes. |
if(numVisited==m_numNodes) return true; else return false; // a node won't be visited more than once, so the number visited are the number seen.
| bool jmitie::CjNLTopology::isSymmetric | ( | ) | [inline] |
Tests whether the topology matrix is symmetric.
i.e. the wt(a,b) == wt(b,a) for all a and b such that 0 <= a < m_maxNodes, 0 <= b < m_maxNodes
| bool jmitie::CjNLTopology::mk_distances | ( | ) | const [protected] |
rebuilds m_distances from m_wt if it is not valid
If m_distances is not valid this will call APSP
| bool jmitie::CjNLTopology::mk_lrpn_lrpl | ( | ) | const [protected] |
rebuilds any of m_rpl, m_lpl, m_rpl m_lpl if necessary
return true is a rebuild was necessary, false otherwise
| unsigned int jmitie::CjNLTopology::newNodeNumber | ( | ) | const throw () |
Returns the number of the node that would be returned with the next invocation of addDisconnectedNode(), but doesn't create or add the node.
This operation exists to give a "peek" as to the new node number so a link dimensioner could be called in preparation for a call to addNodeAndConnect()
| unsigned int jmitie::CjNLTopology::nextHop | ( | const unsigned int | where, | |
| const unsigned int | destination | |||
| ) | const |
Returns the next hop along the least weight path through the topology.
In the case of there being more than one path which has equally low a costs the route is decided based on the tie-breaker values randomly generated for each node at initialisation (and reset by ()).
| where | The node from which to find the next hop. | |
| destination | The destination which is to be reached. |
| E_CjMatrix_BoundsError | if argument node is equal to, or greater than, m_numNodes. | |
| E_CjNLT_RoutingError | if where == destination |
| CjNLTopology::WT jmitie::CjNLTopology::operator() | ( | unsigned int | node_a, | |
| unsigned int | node_b | |||
| ) | [inline] |
Returns the weight of a single directional link in the topology.
Returns the weight of a single directional link in the topology, and doesn't perform bounds checking like getWeight().
| node_a | the start node of the directional link. | |
| node_b | the end node of the directional link. |
| CjNLTopology::WT jmitie::CjNLTopology::operator() | ( | unsigned int | node_a, | |
| unsigned int | node_b, | |||
| CjNLTopology::WT | new_weight | |||
| ) | [inline] |
Sets the weight of a single directional link in the topology.
Sets the weight of a single directional link in the topology and returns the previous link weight.
Use setWeight() for a bounds checking version.
A return value of 0 means the specified nodes were not connected before the update.
| node_a | the start node of the directional link. | |
| node_b | the end node of the directional link. | |
| new_weight | The weight to assign the directional link. |
| std::pair< CjNLTopology::WT, CjNLTopology::WT > jmitie::CjNLTopology::setBiDirWeights | ( | const unsigned int | node_a, | |
| const unsigned int | node_b, | |||
| const WT | ab, | |||
| const WT | ba | |||
| ) | [inline] |
Sets the weights of both directions of a link in the topology.
Sets the weight of both directions a link in the topology and returns the previous link weight.
The returned value is a pair<> - the first field is the old weight of the directional link from node_a to node_b, and the second field is the previous weight of directional link from node_b to node_a.
| node_a | the start node of the directional link. | |
| node_b | the end node of the directional link. | |
| ab | the link weight from node_a to node_b | |
| ba | the link weight from node_a to node_b |
| E_CjMatrix_BoundsError | if either node_a or node_b are equal to, or greater than, m_numNodes. |
| CjNLTopology::WT jmitie::CjNLTopology::setWeight | ( | const unsigned int | node_a, | |
| const unsigned int | node_b, | |||
| const WT | new_weight | |||
| ) | [inline] |
Sets the weight of a single directional link in the topology.
Sets the weight of a single directional link in the topology and returns the previous link weight.
use CjNLTopology::operator() for a non-throwing, non-bounds-checking version.
| node_a | the start node of the directional link. | |
| node_b | the end node of the directional link. | |
| new_weight | the link weight from node_a to node_b |
| E_CjMatrix_BoundsError | if either node_a or node_b are equal to, or greater than, m_numNodes. |
std::vector<adjwl_pair_t>* jmitie::CjNLTopology::m_adj_wtlist [mutable, protected] |
The adjacency weights list.
An array (m_maxNodes in size) of vectors, one for each node. Each vector stores a list of adjwl_pair_t objects describing the node that the node is connected to and the link weight.
tribool jmitie::CjNLTopology::m_bridge_vals[MAX_BRIDGE_VALS] [mutable, protected] |
Array holding values for the indirect addressing in m_isBridge.
[0] is always boost::logic::indeterminate, the remainder are either true or false or indeterminate depending on how they were created or invalidated. see m_isBridge for details
CjMatrix<tribool *>* jmitie::CjNLTopology::m_isBridge [mutable, protected] |
A matrix which stores whether the link is a bridge.
(*m_isBridge)(i,j) stores a pointer to the bridge state of the directional link connecting nodes i and j.
Calculating the bridge status of all links would require the APSP algorithm to run m_numLinks times so instead links are tested only when required, therefore m_isBridge stores whether a link is a bridge, i.e. one whose removal would partition the network, or whether it isn't, or whether it is as yet unknown.
The pointer stored points into m_bridge_vals which ultimately decides on the state. The boost::logic::tribool value pointed to can either true, false or indeterminate.
m_isBridge should be accessed via:
getBridgeState(i,j) to check whether link i,j is a bridge, is not a bridge, or whether it is unknown whether it is a bridge.
isBridgeLink(i,j) which will actually perform the test, update m_isBridge and return a definitive answer (either true or false, never indeterminate).
If a link is known to be a bridge then its state is no longer valid as soon as a new link is added.
Similarly if a link is known not to be a bridge then this state is invalidated as soon as a link is removed elsewhere in the network (since the removed link could have been the alternative path).
Instead of searching for all true, or all false values and re-testing them, which is very slow m_isBridge stores copies of the pointers stored at the time in m_ptr_true, m_ptr_false, or m_ptr_ind.
These pointers point into m_bridge_vals which actually store the value.
So, when a new link is added and we want to rewrite all true values (see invalidateBridges() ), instead of searching and rewriting m_isBridge, we overwrite the entry in m_bridge_vals pointed to by m_ptr_true with boost::logic::indeterminate value and create a new entry with boost::logic::true at the end of m_bridge_vals and update m_ptr_true to point to it.
The old pointer value of m_ptr_true which remains in m_isBridge now points to a value of boost::logic::indeterminate and we have updated all the values in a single step.
Similarly all false values can be all made indeterminate when a link is removed by calling invalidateNonBridges().
When m_ptr_true or m_ptr_false reaches the end of m_bridge_vals then compact_bridge_vals() is called to rewrite m_isBridge with new values - but this is done much much less often then would usually have to be done is m_isBridge stored values rather than pointers.
Methods invalidateBridges() and invalidateNonBridges() are called automatically by updateCell(), which should be the user's interface to these methods.
CjMatrix<LD>* jmitie::CjNLTopology::m_lpl [mutable, protected] |
The load per link matrix.
A matrix where (*m_lpl)(i,j) is the total load (sum of traffic demands) routed over the link between nodes i and j
LD* jmitie::CjNLTopology::m_lpn [mutable, protected] |
The load per node array.
An array m_maxNodes in length where m_lpn[i] is the sum of traffic load traversing, ingressing or egressing node i.
tribool* jmitie::CjNLTopology::m_ptr_false [mutable, protected] |
A pointer into m_bridge_vals which points to the current element in m_bridge_vals which is false - see m_isBridge.
see m_isBridge for details
tribool* jmitie::CjNLTopology::m_ptr_ind [mutable, protected] |
A pointer into m_bridge_vals which points to the current element in m_bridge_vals which is indeterminate.
see m_isBridge for details
tribool* jmitie::CjNLTopology::m_ptr_true [mutable, protected] |
A pointer into m_bridge_vals which points to the current element in m_bridge_vals which is true.
see m_isBridge for details
CjMatrix<unsigned int>* jmitie::CjNLTopology::m_rpl [mutable, protected] |
The routes per link matrix.
A matrix where (*m_rpl)(i,j) is the number of routes traversing the link between nodes i and j
unsigned int* jmitie::CjNLTopology::m_rpn [mutable, protected] |
The routes per node array.
An array m_maxNodes in length where m_rpn[i] is the number of routes traversing, ingressing or egressing node i.
bool jmitie::CjNLTopology::m_valid_adj_wtlist [mutable, protected] |
Validity flag for m_adj_wtlist.
If true then m_adj_wtlist is valid and accurately reflects a sparse representation of m_wt. If false then m_adj_wtlist will be re-generated from m_wt on the next call to mk_adjL()
bool jmitie::CjNLTopology::m_valid_isBridge [mutable, protected] |
m_isBridge validity flag
if false then m_isBridge will be initialised to all boost::logic::indeterminate values and incrementally recreated by calls to isBridgeLink()
bool jmitie::CjNLTopology::m_valid_rpl [mutable, protected] |
Validity flag for m_rpl.
If true then m_rpl is valid and accurately reflects a routes following the shortest paths between all node pairs. If false then m_rpl will be re-generated from m_distances on the next call to mk_adjL()
1.7.1
