Labelling

class labelling::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.

inline void setPhi(const double &phi_in)

set phi attribute for merged labels from Righini and Salani (2006)

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