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

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 dominates other 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] for i in 0,...,resource_consumption.size(). If “soft” check, then the lower bound is only checked if either: resource index i is the index of the critical resource or min_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 by label, 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