PGROUTING  3.1
pgrouting::flow::PgrCardinalityGraph< G > Class Template Reference

#include "pgr_maximumcardinalitymatching.hpp"

Collaboration diagram for pgrouting::flow::PgrCardinalityGraph< G >:

Public Types

typedef boost::graph_traits< G >::edge_descriptor E
 
typedef boost::graph_traits< G >::edge_iterator E_it
 
typedef boost::graph_traits< G >::vertex_descriptor V
 
typedef boost::graph_traits< G >::vertex_iterator V_it
 

Public Member Functions

 PgrCardinalityGraph (pgr_basic_edge_t *data_edges, size_t total_tuples)
 
V get_boost_vertex (int64_t id)
 
int64_t get_edge_id (E e)
 
std::vector< pgr_basic_edge_tget_matched_vertices ()
 
int64_t get_vertex_id (V v)
 
void maximum_cardinality_matching (std::vector< V > &mate_map)
 

Public Attributes

boost_graph
 
std::map< E, int64_t > E_to_id
 
std::map< int64_t, Vid_to_V
 
std::map< V, int64_t > V_to_id
 

Detailed Description

template<class G>
class pgrouting::flow::PgrCardinalityGraph< G >

Definition at line 55 of file pgr_maximumcardinalitymatching.hpp.

Member Typedef Documentation

◆ E

template<class G>
typedef boost::graph_traits<G>::edge_descriptor pgrouting::flow::PgrCardinalityGraph< G >::E

Definition at line 60 of file pgr_maximumcardinalitymatching.hpp.

◆ E_it

template<class G>
typedef boost::graph_traits<G>::edge_iterator pgrouting::flow::PgrCardinalityGraph< G >::E_it

Definition at line 62 of file pgr_maximumcardinalitymatching.hpp.

◆ V

template<class G>
typedef boost::graph_traits<G>::vertex_descriptor pgrouting::flow::PgrCardinalityGraph< G >::V

Definition at line 59 of file pgr_maximumcardinalitymatching.hpp.

◆ V_it

template<class G>
typedef boost::graph_traits<G>::vertex_iterator pgrouting::flow::PgrCardinalityGraph< G >::V_it

Definition at line 61 of file pgr_maximumcardinalitymatching.hpp.

Constructor & Destructor Documentation

◆ PgrCardinalityGraph()

template<class G>
pgrouting::flow::PgrCardinalityGraph< G >::PgrCardinalityGraph ( pgr_basic_edge_t data_edges,
size_t  total_tuples 
)
inline

Definition at line 80 of file pgr_maximumcardinalitymatching.hpp.

References pgrouting::flow::PgrCardinalityGraph< G >::get_boost_vertex().

80  {
81  std::set<int64_t> vertices;
82  for (size_t i = 0; i < total_tuples; ++i) {
83  vertices.insert(data_edges[i].source);
84  vertices.insert(data_edges[i].target);
85  }
86  for (int64_t id : vertices) {
87  V v = add_vertex(boost_graph);
88  id_to_V.insert(std::pair<int64_t, V>(id, v));
89  V_to_id.insert(std::pair<V, int64_t>(v, id));
90  }
91  bool added;
92 
93  for (size_t i = 0; i < total_tuples; ++i) {
94  V v1 = get_boost_vertex(data_edges[i].source);
95  V v2 = get_boost_vertex(data_edges[i].target);
96  E e1;
97  E e2;
98  if (data_edges[i].going) {
99  boost::tie(e1, added) = boost::add_edge(v1, v2, boost_graph);
100  E_to_id.insert(std::pair<E, int64_t>(e1, data_edges[i].id));
101  }
102  if (data_edges[i].coming) {
103  boost::tie(e2, added) = boost::add_edge(v2, v1, boost_graph);
104  E_to_id.insert(std::pair<E, int64_t>(e2, data_edges[i].id));
105  }
106  }
107  }
boost::graph_traits< G >::vertex_descriptor V
boost::graph_traits< G >::edge_descriptor E

Member Function Documentation

◆ get_boost_vertex()

template<class G>
V pgrouting::flow::PgrCardinalityGraph< G >::get_boost_vertex ( int64_t  id)
inline

◆ get_edge_id()

template<class G>
int64_t pgrouting::flow::PgrCardinalityGraph< G >::get_edge_id ( E  e)
inline

◆ get_matched_vertices()

template<class G>
std::vector<pgr_basic_edge_t> pgrouting::flow::PgrCardinalityGraph< G >::get_matched_vertices ( )
inline

Definition at line 110 of file pgr_maximumcardinalitymatching.hpp.

References pgr_basic_edge_t::edge_id, pgrouting::flow::PgrCardinalityGraph< G >::get_edge_id(), pgrouting::flow::PgrCardinalityGraph< G >::get_vertex_id(), pgrouting::flow::PgrCardinalityGraph< G >::maximum_cardinality_matching(), pgr_basic_edge_t::source, and pgr_basic_edge_t::target.

Referenced by do_pgr_maximum_cardinality_matching().

110  {
111 
112  std::vector<V> mate_map(boost::num_vertices(boost_graph));
113  std::vector<pgr_basic_edge_t> matched_vertices;
115 
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) = boost::edge(*vi, mate_map[*vi], boost_graph);
133  if (((uint64_t)mate_map[*vi]
134  != boost::graph_traits<G>::null_vertex())
135  && exists && !already_matched[*vi]
136  && !already_matched[mate_map[*vi]]) {
137  already_matched[*vi] = true;
138  already_matched[mate_map[*vi]] = true;
139  pgr_basic_edge_t matched_couple;
140  matched_couple.source = get_vertex_id(*vi);
141  matched_couple.target = get_vertex_id(mate_map[*vi]);
142  matched_couple.edge_id = get_edge_id(e);
143  matched_vertices.push_back(matched_couple);
144  }
145  }
146  } else {
147  for (boost::tie(vi, vi_end) = boost::vertices(boost_graph);
148  vi != vi_end;
149  ++vi) {
150  boost::tie(e, exists) =
151  boost::edge(*vi, mate_map[*vi], boost_graph);
152  if (((uint64_t)mate_map[*vi]
153  != boost::graph_traits<G>::null_vertex())
154  && (*vi < (uint64_t)mate_map[*vi])) {
155  pgr_basic_edge_t matched_couple;
156  matched_couple.source = get_vertex_id(*vi);
157  matched_couple.target = get_vertex_id(mate_map[*vi]);
158  matched_couple.edge_id = get_edge_id(e);
159  matched_vertices.push_back(matched_couple);
160  }
161  }
162  }
163  return matched_vertices;
164  }
boost::graph_traits< G >::vertex_iterator V_it
void maximum_cardinality_matching(std::vector< V > &mate_map)
boost::graph_traits< G >::edge_descriptor E

◆ get_vertex_id()

template<class G>
int64_t pgrouting::flow::PgrCardinalityGraph< G >::get_vertex_id ( V  v)
inline

◆ maximum_cardinality_matching()

template<class G>
void pgrouting::flow::PgrCardinalityGraph< G >::maximum_cardinality_matching ( std::vector< V > &  mate_map)
inline

Definition at line 166 of file pgr_maximumcardinalitymatching.hpp.

Referenced by pgrouting::flow::PgrCardinalityGraph< G >::get_matched_vertices().

166  {
167  edmonds_maximum_cardinality_matching(boost_graph,
168  &mate_map[0]);
169  }

Member Data Documentation

◆ boost_graph

template<class G>
G pgrouting::flow::PgrCardinalityGraph< G >::boost_graph

Definition at line 57 of file pgr_maximumcardinalitymatching.hpp.

◆ E_to_id

template<class G>
std::map<E, int64_t> pgrouting::flow::PgrCardinalityGraph< G >::E_to_id

Definition at line 66 of file pgr_maximumcardinalitymatching.hpp.

◆ id_to_V

template<class G>
std::map<int64_t, V> pgrouting::flow::PgrCardinalityGraph< G >::id_to_V

Definition at line 64 of file pgr_maximumcardinalitymatching.hpp.

◆ V_to_id

template<class G>
std::map<V, int64_t> pgrouting::flow::PgrCardinalityGraph< G >::V_to_id

Definition at line 65 of file pgr_maximumcardinalitymatching.hpp.


The documentation for this class was generated from the following file: