27 #ifndef SRC_METHODS_HED_IPP_ 28 #define SRC_METHODS_HED_IPP_ 33 template<
class UserNodeLabel,
class UserEdgeLabel>
34 HED<UserNodeLabel, UserEdgeLabel>::
37 template<
class UserNodeLabel,
class UserEdgeLabel>
38 HED<UserNodeLabel, UserEdgeLabel>::
39 HED(
const GEDData<UserNodeLabel, UserEdgeLabel> & ged_data) :
40 GEDMethod<UserNodeLabel, UserEdgeLabel>(ged_data),
41 lsape_model_{LSAPESolver::Model::ECBP},
45 template<
class UserNodeLabel,
class UserEdgeLabel>
50 populate_instance_(g, h, lsape_instance);
52 hed += lsape_instance.matrix().rowwise().minCoeff().sum();
53 hed += lsape_instance.matrix().colwise().minCoeff().sum();
57 template<
class UserNodeLabel,
class UserEdgeLabel>
61 if (option ==
"threads") {
63 num_threads_ = std::stoul(arg);
66 throw Error(std::string(
"Invalid argument \"") + arg +
"\" for option threads. Usage: options = \"[--threads <convertible to int greater 0>] [...]");
68 if (num_threads_ <= 0) {
69 throw Error(std::string(
"Invalid argument \"") + arg +
"\" for option threads. Usage: options = \"[--threads <convertible to int greater 0>] [...]");
73 else if (option ==
"lsape-model") {
77 else if (arg ==
"FLWC") {
80 else if (arg ==
"FLCC") {
83 else if (arg ==
"FBP") {
86 else if (arg ==
"SFBP") {
89 else if (arg ==
"FBP0") {
92 else if (arg !=
"ECBP") {
93 throw ged::Error(std::string(
"Invalid argument ") + arg +
" for option lsape-model. Usage: options = \"[--lsape-model ECBP|EBP|FLWC|FLCC|FBP|SFBP|FBP0] [...]\"");
100 template<
class UserNodeLabel,
class UserEdgeLabel>
104 return "[--lsape-model <arg>] [--threads <arg>]";
107 template<
class UserNodeLabel,
class UserEdgeLabel>
116 template<
class UserNodeLabel,
class UserEdgeLabel>
122 omp_set_num_threads(this->num_threads_ - 1);
123 #pragma omp parallel for if(this->num_threads_ > 1) 125 for (std::size_t row_in_master = 0; row_in_master < lsape_instance.
num_rows(); row_in_master++) {
126 for (std::size_t col_in_master = 0; col_in_master < lsape_instance.
num_cols(); col_in_master++) {
128 lsape_instance(row_in_master, col_in_master) = compute_substitution_cost_(g, h, row_in_master, col_in_master);
130 else if (row_in_master < g.
num_nodes()) {
131 lsape_instance(row_in_master, h.
num_nodes()) = compute_deletion_cost_(g, row_in_master);
133 else if (col_in_master < h.
num_nodes()) {
134 lsape_instance(g.
num_nodes(), col_in_master) = compute_insertion_cost_(h, col_in_master);
140 template<
class UserNodeLabel,
class UserEdgeLabel>
173 subproblem_solver.
set_model(this->lsape_model_);
174 subproblem_solver.
solve();
181 template<
class UserNodeLabel,
class UserEdgeLabel>
190 for (
auto ij = incident_edges_i.first; ij != incident_edges_i.second; ij++) {
198 template<
class UserNodeLabel,
class UserEdgeLabel>
207 for (
auto kl = incident_edges_k.first; kl != incident_edges_k.second; kl++) {
void set_model(const Model &model)
Makes the solver use a specific model for optimal solving.
Reduction to compact LSAP instance for quasimetric costs.
Reduction to compact LSAP instance for quasimetric costs.
std::size_t num_nodes() const
Returns the number of nodes.
Computes a lower bound for general edit costs.
This class solves LSAPE instances by calling the library lsape available at https://bougleux.users.greyc.fr/lsape/.
Reduction to compact LSAP instance without cost constraints.
virtual std::string ged_valid_options_string_() const final
Returns string of all valid options.
const GEDData< UserNodeLabel, UserEdgeLabel > & ged_data_
The data on which the method is run.
void set_lower_bound(double lower_bound)
Sets the lower bound for GED.
void solve(int num_solutions=1)
Solves the LSAPE problem instance.
std::size_t degree(NodeID node) const
Returns node degree.
A wrapper structure for the result of calls to ged::GEDMethod::run_as_util() and ged::GEDMethod::ged_...
Reduction to extended LSAP instance without cost constraints.
std::size_t num_cols() const
Returns the number of columns.
LabelID get_node_label(NodeID node) const
Returns the label of a given node.
Adaption of Hungarian Algorithm to LSAPE.
LabelID get_edge_label(EdgeID edge) const
Returns the label of a given edge.
std::pair< incident_edge_iterator, incident_edge_iterator > incident_edges(NodeID node) const
Provides access to all incident edges of a node.
double minimal_cost() const
Returns the cost of the computed solutions.
virtual void ged_run_(const GEDGraph &g, const GEDGraph &h, Result &result) final
Runs the method with options specified by set_options().
The normalized input graphs used by GEDLIB. All labels are integers.
constexpr LabelID dummy_label()
Returns a dummy label.
Reduction to compact LSAP instance for quasimetric costs.
Global namespace for GEDLIB.
virtual bool ged_parse_option_(const std::string &option, const std::string &arg) final
Parses one option.
virtual void ged_set_default_options_() final
Sets all options to default values.
std::size_t NodeID
Internally used vertex ID type.
Reduction to compact LSAP instance for quasimetric costs.
std::size_t num_rows() const
Returns the number of rows.