GEDLIB  1.0
hed.ipp
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2018 by David B. Blumenthal *
4  * *
5  * This file is part of GEDLIB. *
6  * *
7  * GEDLIB is free software: you can redistribute it and/or modify it *
8  * under the terms of the GNU Lesser General Public License as published *
9  * by the Free Software Foundation, either version 3 of the License, or *
10  * (at your option) any later version. *
11  * *
12  * GEDLIB is distributed in the hope that it will be useful, *
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
15  * GNU Lesser General Public License for more details. *
16  * *
17  * You should have received a copy of the GNU Lesser General Public *
18  * License along with GEDLIB. If not, see <http://www.gnu.org/licenses/>. *
19  * *
20  ***************************************************************************/
21 
27 #ifndef SRC_METHODS_HED_IPP_
28 #define SRC_METHODS_HED_IPP_
29 
30 namespace ged {
31 
32 // === Definitions of destructor and constructor. ===
33 template<class UserNodeLabel, class UserEdgeLabel>
34 HED<UserNodeLabel, UserEdgeLabel>::
35 ~HED() {}
36 
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},
42 num_threads_{1} {}
43 
44 // === Definitions of member functions inherited from GEDMethod. ===
45 template<class UserNodeLabel, class UserEdgeLabel>
46 void
48 ged_run_(const GEDGraph & g, const GEDGraph & h, Result & result) {
49  DMatrix lsape_instance(g.num_nodes() + 1, h.num_nodes() + 1);
50  populate_instance_(g, h, lsape_instance);
51  double hed{0};
52  hed += lsape_instance.matrix().rowwise().minCoeff().sum();
53  hed += lsape_instance.matrix().colwise().minCoeff().sum();
54  result.set_lower_bound(hed);
55 }
56 
57 template<class UserNodeLabel, class UserEdgeLabel>
58 bool
60 ged_parse_option_(const std::string & option, const std::string & arg) {
61  if (option == "threads") {
62  try {
63  num_threads_ = std::stoul(arg);
64  }
65  catch (...) {
66  throw Error(std::string("Invalid argument \"") + arg + "\" for option threads. Usage: options = \"[--threads <convertible to int greater 0>] [...]");
67  }
68  if (num_threads_ <= 0) {
69  throw Error(std::string("Invalid argument \"") + arg + "\" for option threads. Usage: options = \"[--threads <convertible to int greater 0>] [...]");
70  }
71  return true;
72  }
73  else if (option == "lsape-model") {
74  if (arg == "EBP") {
75  lsape_model_ = LSAPESolver::EBP;
76  }
77  else if (arg == "FLWC") {
78  lsape_model_ = LSAPESolver::FLWC;
79  }
80  else if (arg == "FLCC") {
81  lsape_model_ = LSAPESolver::FLCC;
82  }
83  else if (arg == "FBP") {
84  lsape_model_ = LSAPESolver::FBP;
85  }
86  else if (arg == "SFBP") {
87  lsape_model_ = LSAPESolver::SFBP;
88  }
89  else if (arg == "FBP0") {
90  lsape_model_ = LSAPESolver::FBP0;
91  }
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] [...]\"");
94  }
95  return true;
96  }
97  return false;
98 }
99 
100 template<class UserNodeLabel, class UserEdgeLabel>
101 std::string
104  return "[--lsape-model <arg>] [--threads <arg>]";
105 }
106 
107 template<class UserNodeLabel, class UserEdgeLabel>
108 void
111  lsape_model_ = LSAPESolver::ECBP;
112  num_threads_ = 1;
113 }
114 
115 // === Definitions of private helper member functions. ===
116 template<class UserNodeLabel, class UserEdgeLabel>
117 void
119 populate_instance_(const GEDGraph & g, const GEDGraph & h, DMatrix & lsape_instance) const {
120 
121 #ifdef _OPENMP
122  omp_set_num_threads(this->num_threads_ - 1);
123 #pragma omp parallel for if(this->num_threads_ > 1)
124 #endif
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++) {
127  if ((row_in_master < g.num_nodes()) and (col_in_master < h.num_nodes())) {
128  lsape_instance(row_in_master, col_in_master) = compute_substitution_cost_(g, h, row_in_master, col_in_master);
129  }
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);
132  }
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);
135  }
136  }
137  }
138 }
139 
140 template<class UserNodeLabel, class UserEdgeLabel>
141 double
144  // Collect node substitution costs.
145  double cost{this->ged_data_.node_cost(g.get_node_label(i), h.get_node_label(k))};
146 
147  // Initialize subproblem.
148  DMatrix subproblem(g.degree(i) + 1, h.degree(k) + 1);
149 
150  // Collect edge deletion costs.
151  std::size_t j{0};
152  for (auto ij = g.incident_edges(i).first; ij != g.incident_edges(i).second; ij++, j++) {
153  subproblem(j, h.degree(k)) = this->ged_data_.edge_cost(g.get_edge_label(*ij), ged::dummy_label()) / 2.0;
154  }
155 
156  // Collect edge insertion costs.
157  std::size_t l{0};
158  for (auto kl = h.incident_edges(k).first; kl != h.incident_edges(k).second; kl++, l++) {
159  subproblem(g.degree(i), l) = this->ged_data_.edge_cost(ged::dummy_label(), h.get_edge_label(*kl)) / 2.0;
160  }
161  j = 0;
162 
163  // Collect edge relabelling costs.
164  for (auto ij = g.incident_edges(i).first; ij != g.incident_edges(i).second; ij++, j++) {
165  l = 0;
166  for (auto kl = h.incident_edges(k).first; kl != h.incident_edges(k).second; kl++, l++) {
167  subproblem(j, l) = this->ged_data_.edge_cost(g.get_edge_label(*ij), h.get_edge_label(*kl)) / 2.0;
168  }
169  }
170 
171  // Solve subproblem.
172  LSAPESolver subproblem_solver(&subproblem);
173  subproblem_solver.set_model(this->lsape_model_);
174  subproblem_solver.solve();
175 
176  // Update and return overall substitution cost.
177  cost += subproblem_solver.minimal_cost();
178  return cost / 2;
179 }
180 
181 template<class UserNodeLabel, class UserEdgeLabel>
182 double
185  // Collect node deletion cost.
186  double cost{this->ged_data_.node_cost(g.get_node_label(i), ged::dummy_label())};
187 
188  // Collect edge deletion costs.
189  auto incident_edges_i = g.incident_edges(i);
190  for (auto ij = incident_edges_i.first; ij != incident_edges_i.second; ij++) {
191  cost += this->ged_data_.edge_cost(g.get_edge_label(*ij), ged::dummy_label()) / 2.0;
192  }
193 
194  // Return overall deletion cost.
195  return cost;
196 }
197 
198 template<class UserNodeLabel, class UserEdgeLabel>
199 double
202  // Collect node insertion cost.
203  double cost{this->ged_data_.node_cost(ged::dummy_label(), h.get_node_label(k))};
204 
205  // Collect edge insertion costs.
206  auto incident_edges_k = h.incident_edges(k);
207  for (auto kl = incident_edges_k.first; kl != incident_edges_k.second; kl++) {
208  cost += this->ged_data_.edge_cost(ged::dummy_label(), h.get_edge_label(*kl)) / 2.0;
209  }
210 
211  // Return overall insertion cost.
212  return cost;
213 }
214 
215 }
216 
217 
218 
219 #endif /* SRC_METHODS_HED_IPP_ */
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.
Definition: ged_graph.ipp:211
Computes a lower bound for general edit costs.
Definition: hed.hpp:46
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.
Definition: hed.ipp:103
const GEDData< UserNodeLabel, UserEdgeLabel > & ged_data_
The data on which the method is run.
Definition: ged_method.hpp:124
void set_lower_bound(double lower_bound)
Sets the lower bound for GED.
Definition: result.ipp:39
void solve(int num_solutions=1)
Solves the LSAPE problem instance.
std::size_t degree(NodeID node) const
Returns node degree.
Definition: ged_graph.ipp:162
A wrapper structure for the result of calls to ged::GEDMethod::run_as_util() and ged::GEDMethod::ged_...
Definition: result.hpp:38
Reduction to extended LSAP instance without cost constraints.
std::size_t num_cols() const
Returns the number of columns.
Definition: matrix.ipp:110
LabelID get_node_label(NodeID node) const
Returns the label of a given node.
Definition: ged_graph.ipp:126
Runtime error class.
Definition: error.hpp:37
Adaption of Hungarian Algorithm to LSAPE.
LabelID get_edge_label(EdgeID edge) const
Returns the label of a given edge.
Definition: ged_graph.ipp:135
std::pair< incident_edge_iterator, incident_edge_iterator > incident_edges(NodeID node) const
Provides access to all incident edges of a node.
Definition: ged_graph.ipp:150
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().
Definition: hed.ipp:48
The normalized input graphs used by GEDLIB. All labels are integers.
Definition: ged_graph.hpp:104
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.
Definition: hed.ipp:60
virtual void ged_set_default_options_() final
Sets all options to default values.
Definition: hed.ipp:110
std::size_t NodeID
Internally used vertex ID type.
Definition: ged_graph.hpp:108
Reduction to compact LSAP instance for quasimetric costs.
std::size_t num_rows() const
Returns the number of rows.
Definition: matrix.ipp:85