pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
maximum_cardinality_matching_driver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: maximum_cardinality_matching_driver.cpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 Function's developer:
9 Copyright (c) 2016 Andrea Nardelli
10 Mail: nrd.nardelli@gmail.com
11 
12 ------
13 
14 This program is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18 
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23 
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 
28 ********************************************************************PGR-GNU*/
29 
30 #if defined(__MINGW32__) || defined(_MSC_VER)
31 #include <winsock2.h>
32 #include <windows.h>
33 #endif
34 
35 
36 #include <sstream>
37 #include <vector>
38 
41 #include "../../common/src/pgr_alloc.hpp"
42 
43 // #define DEBUG
44 extern "C" {
45 #include "./../../common/src/pgr_types.h"
46 }
47 
48 void
50  pgr_basic_edge_t *data_edges,
51  bool directed,
52  size_t total_tuples,
53  pgr_basic_edge_t **return_tuples,
54  size_t *return_count,
55  char **err_msg) {
56  std::ostringstream log;
57 
58  try {
59  std::vector<pgr_basic_edge_t> matched_vertices;
60 
61  if (directed) {
63  G.create_max_cardinality_graph(data_edges, total_tuples);
64  std::vector<int64_t> mate_map(boost::num_vertices(G.boost_graph));
65  G.maximum_cardinality_matching(mate_map);
66  G.get_matched_vertices(matched_vertices, mate_map);
67  } else {
69  G.create_max_cardinality_graph(data_edges, total_tuples);
70  std::vector<int64_t> mate_map(boost::num_vertices(G.boost_graph));
71  G.maximum_cardinality_matching(mate_map);
72  G.get_matched_vertices(matched_vertices, mate_map);
73  }
74 
75  (*return_tuples) = pgr_alloc(matched_vertices.size(), (*return_tuples));
76  for (size_t i = 0; i < matched_vertices.size(); ++i) {
77  (*return_tuples)[i] = matched_vertices[i];
78  }
79  *return_count = matched_vertices.size();
80 
81 #ifndef DEBUG
82  *err_msg = strdup("OK");
83 #else
84  *err_msg = strdup(log.str().c_str());
85 #endif
86 
87  return;
88  } catch (...) {
89  log << "Caught unknown exception!\n";
90  *err_msg = strdup(log.str().c_str());
91  return;
92  }
93 }
94 
95 
96 
97 
98 
void get_matched_vertices(std::vector< pgr_basic_edge_t > &matched_vertices, const std::vector< int64_t > &mate_map)
void create_max_cardinality_graph(pgr_basic_edge_t *data_edges, size_t total_tuples)
void do_pgr_maximum_cardinality_matching(pgr_basic_edge_t *data_edges, bool directed, size_t total_tuples, pgr_basic_edge_t **return_tuples, size_t *return_count, char **err_msg)
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:52
char * err_msg
Definition: BDATester.cpp:50
void maximum_cardinality_matching(std::vector< int64_t > &mate_map)