PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_maximumcardinalitymatching.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 Copyright (c) 2016 Andrea Nardelli
7 Mail: nrd.nardelli@gmail.com
8 
9 ------
10 
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15 
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20 
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 
25 ********************************************************************PGR-GNU*/
26 
27 #ifndef SRC_MAX_FLOW_SRC_PGR_MAXIMUMCARDINALITYMATCHING_HPP_
28 #define SRC_MAX_FLOW_SRC_PGR_MAXIMUMCARDINALITYMATCHING_HPP_
29 #pragma once
30 
31 #include "./../../common/src/pgr_types.h"
32 #ifdef unlink
33 #undef unlink
34 #endif
35 
36 #include <boost/config.hpp>
37 #include <boost/graph/adjacency_list.hpp>
38 #include <boost/graph/max_cardinality_matching.hpp>
39 
40 
41 #include <map>
42 #include <vector>
43 #include <utility>
44 #include <set>
45 
46 
47 
48 
49 namespace pgrouting {
50 
51 typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS>
53 typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS>
55 
56 namespace flow {
57 
58 template<class G>
60  public:
62 
63  typedef typename boost::graph_traits<G>::vertex_descriptor V;
64  typedef typename boost::graph_traits<G>::edge_descriptor E;
65  typedef typename boost::graph_traits<G>::vertex_iterator V_it;
66  typedef typename boost::graph_traits<G>::edge_iterator E_it;
67 
68  std::map<int64_t, V> id_to_V;
69  std::map<V, int64_t> V_to_id;
70  std::map<E, int64_t> E_to_id;
71 
72  V get_boost_vertex(int64_t id) {
73  return id_to_V[id];
74  }
75 
76  int64_t get_vertex_id(V v) {
77  return V_to_id[v];
78  }
79 
80  int64_t get_edge_id(E e) {
81  return E_to_id[e];
82  }
83 
85  size_t total_tuples) {
86  std::set<int64_t> vertices;
87  for (size_t i = 0; i < total_tuples; ++i) {
88  vertices.insert(data_edges[i].source);
89  vertices.insert(data_edges[i].target);
90  }
91  for (int64_t id : vertices) {
92  V v = add_vertex(boost_graph);
93  id_to_V.insert(std::pair<int64_t, V>(id, v));
94  V_to_id.insert(std::pair<V, int64_t>(v, id));
95  }
96  bool added;
97 
98  for (size_t i = 0; i < total_tuples; ++i) {
99  V v1 = get_boost_vertex(data_edges[i].source);
100  V v2 = get_boost_vertex(data_edges[i].target);
101  E e1;
102  E e2;
103  if (data_edges[i].going) {
104  boost::tie(e1, added) = boost::add_edge(v1, v2, boost_graph);
105  E_to_id.insert(std::pair<E, int64_t>(e1, data_edges[i].id));
106  }
107  if (data_edges[i].coming) {
108  boost::tie(e2, added) = boost::add_edge(v2, v1, boost_graph);
109  E_to_id.insert(std::pair<E, int64_t>(e2, data_edges[i].id));
110  }
111  }
112  }
113 
114  void get_matched_vertices(std::vector<pgr_basic_edge_t> &matched_vertices,
115  const std::vector<int64_t> &mate_map) {
116  V_it vi, vi_end;
117  E e;
118  bool exists;
119  if (boost::is_directed(boost_graph)) {
120  std::vector<bool> already_matched(num_vertices(boost_graph), false);
121  for (boost::tie(vi, vi_end) = boost::vertices(boost_graph);
122  vi != vi_end;
123  ++vi) {
124  /*
125  * For each vertex I check:
126  * 1) It is matched with a non-null vertex
127  * 2) An edge exists from this vertex to his mate
128  * 3) The vertices have not been matched already
129  * (this last point prevents having double output with reversed
130  * source and target)
131  */
132  boost::tie(e, exists) =
133  boost::edge(*vi, mate_map[*vi], boost_graph);
134  if (((uint64_t)mate_map[*vi]
135  != boost::graph_traits<G>::null_vertex())
136  && exists && !already_matched[*vi]
137  && !already_matched[mate_map[*vi]]) {
138  already_matched[*vi] = true;
139  already_matched[mate_map[*vi]] = true;
140  pgr_basic_edge_t matched_couple;
141  matched_couple.source = get_vertex_id(*vi);
142  matched_couple.target = get_vertex_id(mate_map[*vi]);
143  matched_couple.edge_id = get_edge_id(e);
144  matched_vertices.push_back(matched_couple);
145  }
146  }
147  } else {
148  for (boost::tie(vi, vi_end) = boost::vertices(boost_graph);
149  vi != vi_end;
150  ++vi) {
151  boost::tie(e, exists) =
152  boost::edge(*vi, mate_map[*vi], boost_graph);
153  if (((uint64_t)mate_map[*vi]
154  != boost::graph_traits<G>::null_vertex())
155  && (*vi < (uint64_t)mate_map[*vi])) {
156  pgr_basic_edge_t matched_couple;
157  matched_couple.source = get_vertex_id(*vi);
158  matched_couple.target = get_vertex_id(mate_map[*vi]);
159  matched_couple.edge_id = get_edge_id(e);
160  matched_vertices.push_back(matched_couple);
161  }
162  }
163  }
164  }
165 
166  void maximum_cardinality_matching(std::vector<int64_t> &mate_map) {
167  edmonds_maximum_cardinality_matching(boost_graph,
168  &mate_map[0]);
169  }
170 };
171 
172 } // namespace flow
173 } // namespace pgrouting
174 
175 #endif // SRC_MAX_FLOW_SRC_PGR_MAXIMUMCARDINALITYMATCHING_HPP_
int64_t edge_id
Definition: pgr_types.h:138
boost::graph_traits< G >::vertex_iterator V_it
void get_matched_vertices(std::vector< pgr_basic_edge_t > &matched_vertices, const std::vector< int64_t > &mate_map)
boost::adjacency_list< boost::listS, boost::vecS, boost::directedS > BasicDirectedGraph
boost::graph_traits< G >::vertex_descriptor V
void maximum_cardinality_matching(std::vector< int64_t > &mate_map)
boost::adjacency_list< boost::listS, boost::vecS, boost::undirectedS > BasicUndirectedGraph
void create_max_cardinality_graph(pgr_basic_edge_t *data_edges, size_t total_tuples)
int64_t source
Definition: pgr_types.h:134
int64_t target
Definition: pgr_types.h:135
boost::graph_traits< G >::edge_descriptor E
boost::graph_traits< G >::edge_iterator E_it