Labelling
-
class Label
Single node label. With resource, cost and other attributes.
Main functionality includes:
Checking resource feasibility
Checking dominance
Public Functions
-
inline Label()
Dummy constructor.
-
Label(const double &weight_in, const bidirectional::Vertex &vertex_in, const std::vector<double> &resource_consumption_in, const std::vector<int> &partial_path_in, bidirectional::Params *params)
Constructor.
-
Label(const double &weight_in, const bidirectional::Vertex &vertex_in, const std::vector<double> &resource_consumption_in, const std::vector<int> &partial_path_in, bidirectional::Params *params, const double &phi_in)
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
-
inline ~Label()
default destructor
-
Label extend(const bidirectional::AdjVertex &adjacent_vertex, const bidirectional::Directions &direction, const std::vector<double> &max_res = {}, const std::vector<double> &min_res = {})
Generate new label extensions from the current label and return only if resource feasible. The input label is a pointer as it may be modified in the case that the edge / adjacent_vertex is found to be resource infeasible, in which case, the head/tail node becomes unreachable and the attribute is updated.
- Parameters
label, labelling::Label, current – [out] label to extend (and maybe update
unreachable_nodes
)adjacent_vertex, AdjVertex, edge – [in]
direction – [in] Directions
elementary – [in] bool
max_res, vector – [in] of double with upper bound(s) for resource consumption
min_res, vector – [in] of double with lower bound(s) for resource consumption
- Returns
Label object with extended label. Note this may be empty if the extension is resource infeasible
-
bool checkDominance(const Label &other, const bidirectional::Directions &direction) const
Check if this dominates other. Assumes the labels are comparable i.e. same nodes
- Parameters
other – [in] Label
direction – [in] Directions
elementary – [in] bool, optional
- Returns
bool
-
bool fullDominance(const Label &other, const bidirectional::Directions &direction) const
Checks whether
this
dominatesother
for the input direction. In the case when neither dominates , i.e. they are non-dominated, the direction is flipped labels are compared again.- Parameters
other – [in] Label
direction – [in] Directions
elementary – [in] bool
- Returns
bool
-
bool checkFeasibility(const std::vector<double> &max_res, const std::vector<double> &min_res, const bool &soft = false) const
Check resource feasibility of current label i.e.
min_res[i] <= resource_consumption[i] <= max_res[i]
fori
in0,...,resource_consumption.size()
. If “soft” check, then the lower bound is only checked if either: resource indexi
is the index of the critical resource ormin_res[i]<= 0
(See issue #90). If not “soft”, then all lower bounds are checked as expected.- Parameters
max_res, vector – [in] of double with upper bound(s) for resource consumption. Checks values are <= bound
min_res, vector – [in] of double with lower bound(s) for resource consumption. Checks values are >= bound
soft, bool – [in] with whether the minimum resources should be checked “softly”. Default is false.
-
bool checkThreshold(const double &threshold) const
Check if weight is under the input threshold.
-
bool checkStPath(const int &source_id, const int &sink_id) const
Check whether the current partial path is Source - Sink
- Parameters
source_id, int – [in] with user_id of the source node.
sink_id, int – [in] with user_id of the sink node.
-
bool checkPathExtension(const int &user_id) const
Returns true is the partial path extension is OK.
-
bool checkSameFeasibleExtensionTwoCycleSimple(const Label &other) const
Simple check if both lables have the same feasible extension with regard to 2-cycle elimination. this and other have same feasible extension if predecessor is the same.
- Parameters
other, Label – [in] with other label to compare
- Returns
true if this and other have same feasible extension
-
bool checkSameFeasibleExtensionElementary(const Label &other) const
Simple check if both lables have the same feasible extension under elementary conditions. this and other have the same feasible extension if unreachable_nodes of this is subset of unreachable_nodes of other
- Parameters
other, Label – [in] with other label to compare
- Returns
true if this and other have same feasible extension
-
bool checkSameFeasibleExtension(const Label &other) const
Check if both lables have the same feasible extension, i.e., if they both can extend to the same nodes. Important for correct dominance check. Labels with different feasible extension cannot dominate each other.
- Parameters
other, Label – [in] with other label to compare
- Returns
true if this and other have same feasible extension
-
inline void setPhi(const double &phi_in)
set phi attribute for merged labels from Righini and Salani (2006)
-
inline int getPredecessorId() const
gets the id of the predecessor node TODO can be replaced as member of label
Public Members
-
std::set<int> unreachable_nodes = {}
Set of unreachable nodes. This is only used in the elementary case.
-
bool labelling::runDominanceEff(std::vector<Label> *efficient_labels_ptr, const Label &label, const bidirectional::Directions &direction, const bool &elementary)
Misc functionality
Check whether the input label dominates any efficient label (previously undominated labels) at the same node. If any label is dominated by the input label, they are removed.
- Parameters
efficient_labels, pointer – [out] to a vector of Label with the efficient labels at the same node as
label
. If a label is dominated bylabel
, it is removed from this vector.label, Label – [in] to compare
direction, Directions – [in] with direction of search
elementary, bool – [in] with whether non-elementary paths are allowed
- Returns
bool, true if
label
is dominated, false otherwise
-
Label labelling::mergeLabels(const Label &fwd_label, const Label &bwd_label, const bidirectional::AdjVertex &adj_vertex, const bidirectional::Vertex &sink, const std::vector<double> &max_res, const std::vector<double> &min_res)
Merge labels produced by a backward and forward label. If an s-t compatible path can be obtained the appropriately extended and merged label is returned.
- Returns
merged label with updated attributes and new phi value.
-
Label labelling::processBwdLabel(const labelling::Label &label, const std::vector<double> &max_res, const std::vector<double> &cumulative_resource, const bool &invert_min_res)
Reverse backward path and inverts resource consumption and returns resulting forward-compatible label.
- Parameters
label, labelling::Label, current – [out] label to extend (and maybe update
unreachable_nodes
)max_res, vector – [in] of double with upper bound(s) for resource consumption. To use to invert monotone resource
invert_min_res, bool – [in]
- Returns
inverted label