#include "pgr_maximumcardinalitymatching.hpp"

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

[legend]

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_t >	get_matched_vertices ()

int64_t	get_vertex_id (V v)

void	maximum_cardinality_matching (std::vector< V > &mate_map)

Public Attributes
G	boost_graph

std::map< E, int64_t >	E_to_id

std::map< int64_t, V >	id_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.

                                                                          {
       std::set<int64_t> vertices;
       for (size_t i = 0; i < total_tuples; ++i) {
           vertices.insert(data_edges[i].source);
           vertices.insert(data_edges[i].target);
       }
       for (int64_t id : vertices) {
           V v = add_vertex(boost_graph);
           id_to_V.insert(std::pair<int64_t, V>(id, v));
           V_to_id.insert(std::pair<V, int64_t>(v, id));
       }
       bool added;
  
       for (size_t i = 0; i < total_tuples; ++i) {
           V v1 = get_boost_vertex(data_edges[i].source);
           V v2 = get_boost_vertex(data_edges[i].target);
           E e1;
           E e2;
           if (data_edges[i].going) {
               boost::tie(e1, added) = boost::add_edge(v1, v2, boost_graph);
               E_to_id.insert(std::pair<E, int64_t>(e1, data_edges[i].id));
           }
           if (data_edges[i].coming) {
               boost::tie(e2, added) = boost::add_edge(v2, v1, boost_graph);
               E_to_id.insert(std::pair<E, int64_t>(e2, data_edges[i].id));
           }
       }
   }

References pgrouting::flow::PgrCardinalityGraph< G >::boost_graph, pgrouting::flow::PgrCardinalityGraph< G >::E_to_id, pgrouting::flow::PgrCardinalityGraph< G >::get_boost_vertex(), pgrouting::flow::PgrCardinalityGraph< G >::id_to_V, and pgrouting::flow::PgrCardinalityGraph< G >::V_to_id.

Member Function Documentation

◆ get_boost_vertex()

template<class G >

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

inline

Definition at line 68 of file pgr_maximumcardinalitymatching.hpp.

                                  {
       return id_to_V[id];
   }

References pgrouting::flow::PgrCardinalityGraph< G >::id_to_V.

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

◆ get_edge_id()

template<class G >

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

inline

Definition at line 76 of file pgr_maximumcardinalitymatching.hpp.

                            {
       return E_to_id[e];
   }

References pgrouting::flow::PgrCardinalityGraph< G >::E_to_id.

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

◆ 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.

                          {
       std::vector<V> mate_map(boost::num_vertices(boost_graph));
       std::vector<pgr_basic_edge_t> matched_vertices;
       maximum_cardinality_matching(mate_map);
  
       V_it vi, vi_end;
       E e;
       bool exists;
       if (boost::is_directed(boost_graph)) {
           std::vector<bool> already_matched(num_vertices(boost_graph), false);
           for (boost::tie(vi, vi_end) = boost::vertices(boost_graph);
                vi != vi_end;
                ++vi) {
               /*
                * For each vertex I check:
                * 1) It is matched with a non-null vertex
                * 2) An edge exists from this vertex to his mate
                * 3) The vertices have not been matched already
                * (this last point prevents having double output with reversed
                * source and target)
                */
               boost::tie(e, exists) = boost::edge(*vi, mate_map[*vi], boost_graph);
               if (((uint64_t)mate_map[*vi]
                           != boost::graph_traits<G>::null_vertex())
                   && exists && !already_matched[*vi]
                   && !already_matched[mate_map[*vi]]) {
                   already_matched[*vi] = true;
                   already_matched[mate_map[*vi]] = true;
                   pgr_basic_edge_t matched_couple;
                   matched_couple.source = get_vertex_id(*vi);
                   matched_couple.target = get_vertex_id(mate_map[*vi]);
                   matched_couple.edge_id = get_edge_id(e);
                   matched_vertices.push_back(matched_couple);
               }
           }
       } else {
           for (boost::tie(vi, vi_end) = boost::vertices(boost_graph);
                vi != vi_end;
                ++vi) {
               boost::tie(e, exists) =
                   boost::edge(*vi, mate_map[*vi], boost_graph);
               if (((uint64_t)mate_map[*vi]
                           != boost::graph_traits<G>::null_vertex())
                   && (*vi < (uint64_t)mate_map[*vi])) {
                   pgr_basic_edge_t matched_couple;
                   matched_couple.source = get_vertex_id(*vi);
                   matched_couple.target = get_vertex_id(mate_map[*vi]);
                   matched_couple.edge_id = get_edge_id(e);
                   matched_vertices.push_back(matched_couple);
               }
           }
       }
       return matched_vertices;
   }

References pgrouting::flow::PgrCardinalityGraph< G >::boost_graph, 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.

◆ get_vertex_id()

template<class G >

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

inline

Definition at line 72 of file pgr_maximumcardinalitymatching.hpp.

                              {
       return V_to_id[v];
   }

References pgrouting::flow::PgrCardinalityGraph< G >::V_to_id.

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

◆ maximum_cardinality_matching()

template<class G >

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

inline

Definition at line 165 of file pgr_maximumcardinalitymatching.hpp.

                                                             {
       edmonds_maximum_cardinality_matching(boost_graph,
                                            &mate_map[0]);
   }

References pgrouting::flow::PgrCardinalityGraph< G >::boost_graph.

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