#include "pgr_minCostMaxFlow.hpp"

Collaboration diagram for pgrouting::graph::PgrCostFlowGraph:

[legend]

Public Member Functions
	PgrCostFlowGraph ()=delete

	PgrCostFlowGraph (const std::vector< pgr_costFlow_t > &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)

std::vector< pgr_flow_t >	GetFlowEdges () const

int64_t	GetMaxFlow () const

double	MinCostMaxFlow ()

Private Types
typedef Traits::edge_descriptor	E

typedef boost::graph_traits< CostFlowGraph >::edge_iterator	E_it

typedef Traits::vertex_descriptor	V

typedef boost::graph_traits< CostFlowGraph >::vertex_iterator	V_it

Private Member Functions
E	AddEdge (V v, V w, double wei, double cap)

template<typename T >
void	AddVertices (const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)

V	GetBoostVertex (int64_t id) const

int64_t	GetEdgeId (E e) const

int64_t	GetVertexId (V v) const

void	InsertEdges (const std::vector< pgr_costFlow_t > &edges)

void	SetSupersink (const std::set< int64_t > &sink_vertices)

void	SetSupersource (const std::set< int64_t > &source_vertices)

Private Attributes
Capacity	capacity

std::map< E, int64_t >	eToId

CostFlowGraph	graph

std::map< int64_t, V >	idToV

ResidualCapacity	residual_capacity

Reversed	rev

V	supersink

V	supersource

std::map< V, int64_t >	vToId

Weight	weight

Detailed Description

Definition at line 51 of file pgr_minCostMaxFlow.hpp.

Member Typedef Documentation

◆ E

typedef Traits::edge_descriptor pgrouting::graph::PgrCostFlowGraph::E

private

Definition at line 53 of file pgr_minCostMaxFlow.hpp.

◆ E_it

typedef boost::graph_traits<CostFlowGraph>::edge_iterator pgrouting::graph::PgrCostFlowGraph::E_it

private

Definition at line 55 of file pgr_minCostMaxFlow.hpp.

◆ V

typedef Traits::vertex_descriptor pgrouting::graph::PgrCostFlowGraph::V

private

Definition at line 52 of file pgr_minCostMaxFlow.hpp.

◆ V_it

typedef boost::graph_traits<CostFlowGraph>::vertex_iterator pgrouting::graph::PgrCostFlowGraph::V_it

private

Definition at line 54 of file pgr_minCostMaxFlow.hpp.

Constructor & Destructor Documentation

◆ PgrCostFlowGraph() [1/2]

pgrouting::graph::PgrCostFlowGraph::PgrCostFlowGraph ( )

delete

◆ PgrCostFlowGraph() [2/2]

pgrouting::graph::PgrCostFlowGraph::PgrCostFlowGraph	(	const std::vector< pgr_costFlow_t > &	edges,
		const std::set< int64_t > &	source_vertices,
		const std::set< int64_t > &	sink_vertices
	)

Definition at line 37 of file pgr_minCostMaxFlow.cpp.

                                              {
     AddVertices(edges, sourceVertices, sinkVertices);
  
     capacity = get(boost::edge_capacity, graph);
     weight = get(boost::edge_weight, graph);
     rev = get(boost::edge_reverse, graph);
     residual_capacity = get(boost::edge_residual_capacity, graph);
  
     InsertEdges(edges);
 }

References AddVertices(), capacity, graph, InsertEdges(), residual_capacity, rev, and weight.

Member Function Documentation

◆ AddEdge()

PgrCostFlowGraph::E pgrouting::graph::PgrCostFlowGraph::AddEdge	(	PgrCostFlowGraph::V	v,
		PgrCostFlowGraph::V	w,
		double	wei,
		double	cap
	)

private

Definition at line 51 of file pgr_minCostMaxFlow.cpp.

                                                      {
     bool b;
     PgrCostFlowGraph::E e;
     boost::tie(e, b) = boost::add_edge(vertex(v, graph),
                                        vertex(w, graph), graph);
     capacity[e] = cap;
     weight[e] = wei;
     return e;
 }

References capacity, graph, and weight.

Referenced by InsertEdges(), SetSupersink(), and SetSupersource().

◆ AddVertices()

template<typename T >

void pgrouting::graph::PgrCostFlowGraph::AddVertices	(	const T &	edges,
		const std::set< int64_t > &	source_vertices,
		const std::set< int64_t > &	sink_vertices
	)

inlineprivate

Definition at line 111 of file pgr_minCostMaxFlow.hpp.

                                                    {
          std::set<int64_t> vertices(source_vertices);
          vertices.insert(sink_vertices.begin(), sink_vertices.end());
  
          for (const auto e : edges) {
              vertices.insert(e.source);
              vertices.insert(e.target);
          }
  
          for (const auto id : vertices) {
              V v = add_vertex(graph);
              idToV.insert(std::pair<int64_t, V>(id, v));
              vToId.insert(std::pair<V, int64_t>(v, id));
          }
  
          SetSupersource(source_vertices);
          SetSupersink(sink_vertices);
      }

References graph, idToV, SetSupersink(), SetSupersource(), and vToId.

Referenced by PgrCostFlowGraph().

◆ GetBoostVertex()

V pgrouting::graph::PgrCostFlowGraph::GetBoostVertex ( int64_t id ) const

inlineprivate

Definition at line 83 of file pgr_minCostMaxFlow.hpp.

                                         {
          return idToV.at(id);
      }

References idToV.

Referenced by InsertEdges(), SetSupersink(), and SetSupersource().

◆ GetEdgeId()

int64_t pgrouting::graph::PgrCostFlowGraph::GetEdgeId ( E e ) const

inlineprivate

Definition at line 91 of file pgr_minCostMaxFlow.hpp.

                                   {
          if (eToId.find(e) == eToId.end())
              return -1;
          return eToId.at(e);
      }

References eToId.

Referenced by GetFlowEdges().

◆ GetFlowEdges()

std::vector< pgr_flow_t > pgrouting::graph::PgrCostFlowGraph::GetFlowEdges ( ) const

Definition at line 141 of file pgr_minCostMaxFlow.cpp.

                                      {
     std::vector<pgr_flow_t> flowEdges;
     E_it e, eEnd;
     for (boost::tie(e, eEnd) = boost::edges(graph); e != eEnd; ++e) {
         if (((capacity[*e] - residual_capacity[*e]) > 0) &&
                 ((*e).m_source != supersource) &&
                 ((*e).m_target != supersink)) {
             pgr_flow_t edge;
             edge.edge = GetEdgeId(*e);
             edge.source = GetVertexId((*e).m_source);
             edge.target = GetVertexId((*e).m_target);
             edge.flow =
                 static_cast<int64_t>(capacity[*e] - residual_capacity[*e]);
             edge.residual_capacity =
                 static_cast<int64_t>(residual_capacity[*e]);
             edge.cost = weight[*e] * static_cast<double>(edge.flow);
             if (flowEdges.size() == 0)
                 edge.agg_cost = edge.cost;
             else
                 edge.agg_cost = (flowEdges.back()).agg_cost + edge.cost;
             flowEdges.push_back(edge);
         }
     }
     return flowEdges;
 }

References capacity, edge::cost, GetEdgeId(), GetVertexId(), graph, residual_capacity, edge::source, supersink, supersource, edge::target, and weight.

Referenced by do_pgr_minCostMaxFlow(), and pgrouting::graph::PgrDirectedChPPGraph::setPathEdges().

◆ GetMaxFlow()

int64_t pgrouting::graph::PgrCostFlowGraph::GetMaxFlow ( ) const

Definition at line 128 of file pgr_minCostMaxFlow.cpp.

                                    {
     int64_t maxFlow = 0;
     E_it e, eEnd;
     for (boost::tie(e, eEnd) = boost::edges(graph); e != eEnd; ++e) {
         if (((capacity[*e] - residual_capacity[*e]) > 0) &&
                 ((*e).m_source == supersource))
             maxFlow +=
                 static_cast<int64_t>(capacity[*e] - residual_capacity[*e]);
     }
     return maxFlow;
 }

References capacity, graph, residual_capacity, and supersource.

Referenced by pgrouting::graph::PgrDirectedChPPGraph::PgrDirectedChPPGraph(), and pgrouting::graph::PgrDirectedChPPGraph::setPathEdges().

◆ GetVertexId()

int64_t pgrouting::graph::PgrCostFlowGraph::GetVertexId ( V v ) const

inlineprivate

Definition at line 87 of file pgr_minCostMaxFlow.hpp.

                                     {
          return vToId.at(v);
      }

References vToId.

Referenced by GetFlowEdges().

◆ InsertEdges()

void pgrouting::graph::PgrCostFlowGraph::InsertEdges ( const std::vector< pgr_costFlow_t > & edges )

private

Definition at line 63 of file pgr_minCostMaxFlow.cpp.

                                                 {
     for (const auto edge : edges) {
         PgrCostFlowGraph::E e1, e1Rev, e2, e2Rev;
         V v1 = GetBoostVertex(edge.source);
         V v2 = GetBoostVertex(edge.target);
  
         if (edge.capacity > 0) {
             e1 = AddEdge(v1, v2, edge.cost,
                                   static_cast<double>(edge.capacity));
             e1Rev = AddEdge(v2, v1, -edge.cost, 0);
  
             eToId.insert(std::pair<PgrCostFlowGraph::E,
                                      int64_t>(e1, edge.edge_id));
             eToId.insert(std::pair<PgrCostFlowGraph::E,
                                      int64_t>(e1Rev, edge.edge_id));
  
             rev[e1] = e1Rev;
             rev[e1Rev] = e1;
         }
  
         if (edge.reverse_capacity > 0) {
             e2 = AddEdge(v2, v1, edge.reverse_cost,
                                   static_cast<double>(edge.reverse_capacity));
             e2Rev = AddEdge(v1, v2, -edge.reverse_cost, 0);
  
             eToId.insert(std::pair<PgrCostFlowGraph::E,
                                      int64_t>(e2, edge.edge_id));
             eToId.insert(std::pair<PgrCostFlowGraph::E,
                                      int64_t>(e2Rev, edge.edge_id));
  
             rev[e2] = e2Rev;
             rev[e2Rev] = e2;
         }
     }
 }

References AddEdge(), edge::cost, eToId, GetBoostVertex(), rev, edge::reverse_cost, edge::source, and edge::target.

Referenced by PgrCostFlowGraph().

◆ MinCostMaxFlow()

double pgrouting::graph::PgrCostFlowGraph::MinCostMaxFlow ( )

inline

Definition at line 63 of file pgr_minCostMaxFlow.hpp.

                              {
          boost::successive_shortest_path_nonnegative_weights(
              graph,
              supersource,
              supersink);
          return boost::find_flow_cost(graph);
      }

References graph, supersink, and supersource.

Referenced by do_pgr_minCostMaxFlow(), pgrouting::graph::PgrDirectedChPPGraph::PgrDirectedChPPGraph(), and pgrouting::graph::PgrDirectedChPPGraph::setPathEdges().

◆ SetSupersink()

void pgrouting::graph::PgrCostFlowGraph::SetSupersink ( const std::set< int64_t > & sink_vertices )

private

Definition at line 114 of file pgr_minCostMaxFlow.cpp.

                                              {
     supersink = add_vertex(graph);
     for (int64_t sink_id : sinkVertices) {
         PgrCostFlowGraph::V sink = GetBoostVertex(sink_id);
         PgrCostFlowGraph::E e, eRev;
         e = AddEdge(sink, supersink, 0, (std::numeric_limits<int32_t>::max)());
         eRev = AddEdge(supersink, sink, 0, 0);
         rev[e] = eRev;
         rev[eRev] = e;
     }
 }

References AddEdge(), GetBoostVertex(), graph, rev, and supersink.

Referenced by AddVertices().

◆ SetSupersource()

void pgrouting::graph::PgrCostFlowGraph::SetSupersource ( const std::set< int64_t > & source_vertices )

private

Definition at line 100 of file pgr_minCostMaxFlow.cpp.

                                                {
     supersource = add_vertex(graph);
     for (int64_t source_id : sourceVertices) {
         PgrCostFlowGraph::V source = GetBoostVertex(source_id);
         PgrCostFlowGraph::E e, eRev;
         e = AddEdge(supersource, source,
                      0, (std::numeric_limits<int32_t>::max)());
         eRev = AddEdge(source, supersource, 0, 0);
         rev[e] = eRev;
         rev[eRev] = e;
     }
 }

References AddEdge(), GetBoostVertex(), graph, rev, and supersource.

Referenced by AddVertices().

Member Data Documentation

◆ capacity

Capacity pgrouting::graph::PgrCostFlowGraph::capacity

private

Definition at line 57 of file pgr_minCostMaxFlow.hpp.

Referenced by AddEdge(), GetFlowEdges(), GetMaxFlow(), and PgrCostFlowGraph().

◆ eToId

std::map<E, int64_t> pgrouting::graph::PgrCostFlowGraph::eToId

private

Definition at line 137 of file pgr_minCostMaxFlow.hpp.

Referenced by GetEdgeId(), and InsertEdges().

◆ graph

CostFlowGraph pgrouting::graph::PgrCostFlowGraph::graph

private

Definition at line 134 of file pgr_minCostMaxFlow.hpp.

Referenced by AddEdge(), AddVertices(), GetFlowEdges(), GetMaxFlow(), MinCostMaxFlow(), PgrCostFlowGraph(), SetSupersink(), and SetSupersource().

◆ idToV

std::map<int64_t, V> pgrouting::graph::PgrCostFlowGraph::idToV

private

Definition at line 135 of file pgr_minCostMaxFlow.hpp.

Referenced by AddVertices(), and GetBoostVertex().

◆ residual_capacity

ResidualCapacity pgrouting::graph::PgrCostFlowGraph::residual_capacity

private

Definition at line 58 of file pgr_minCostMaxFlow.hpp.

Referenced by GetFlowEdges(), GetMaxFlow(), and PgrCostFlowGraph().

◆ rev

Reversed pgrouting::graph::PgrCostFlowGraph::rev

private

Definition at line 59 of file pgr_minCostMaxFlow.hpp.

Referenced by InsertEdges(), PgrCostFlowGraph(), SetSupersink(), and SetSupersource().

◆ supersink

V pgrouting::graph::PgrCostFlowGraph::supersink

private

Definition at line 145 of file pgr_minCostMaxFlow.hpp.

Referenced by GetFlowEdges(), MinCostMaxFlow(), and SetSupersink().

◆ supersource

V pgrouting::graph::PgrCostFlowGraph::supersource

private

Definition at line 144 of file pgr_minCostMaxFlow.hpp.

Referenced by GetFlowEdges(), GetMaxFlow(), MinCostMaxFlow(), and SetSupersource().

◆ vToId

std::map<V, int64_t> pgrouting::graph::PgrCostFlowGraph::vToId

private

Definition at line 136 of file pgr_minCostMaxFlow.hpp.

Referenced by AddVertices(), and GetVertexId().

◆ weight

Weight pgrouting::graph::PgrCostFlowGraph::weight

private

Definition at line 60 of file pgr_minCostMaxFlow.hpp.

Referenced by AddEdge(), GetFlowEdges(), and PgrCostFlowGraph().

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

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ E

◆ E_it

◆ V

◆ V_it

Constructor & Destructor Documentation

◆ PgrCostFlowGraph() [1/2]

◆ PgrCostFlowGraph() [2/2]

Member Function Documentation

◆ AddEdge()

◆ AddVertices()

◆ GetBoostVertex()

◆ GetEdgeId()

◆ GetFlowEdges()

◆ GetMaxFlow()

◆ GetVertexId()

◆ InsertEdges()

◆ MinCostMaxFlow()

◆ SetSupersink()

◆ SetSupersource()

Member Data Documentation

◆ capacity

◆ eToId

◆ graph

◆ idToV

◆ residual_capacity

◆ rev

◆ supersink

◆ supersource

◆ vToId

◆ weight