#include "pgr_chinesePostman.hpp"

Collaboration diagram for pgrouting::graph::PgrDirectedChPPGraph:

[legend]

Public Member Functions
	PgrDirectedChPPGraph (const pgr_edge_t *dataEdges, const size_t totalEdges)

	~PgrDirectedChPPGraph ()

double	DirectedChPP () const

std::vector< General_path_element_t >	GetPathEdges () const

Private Member Functions
void	BuildResultGraph ()

void	BuildResultPath ()

bool	EulerCircuitDFS (int64_t p)

void	setPathEdges (graph::PgrCostFlowGraph &flowGraph)

Private Attributes
std::vector< pgr_costFlow_t >	edges

std::map< std::pair< int64_t, int64_t >, size_t >	edgeToId

std::map< std::pair< int64_t, int64_t >, const pgr_edge_t * >	edgeToIdx
	(source, target) -> idx to originalEdges; Only the one with the lower cost is kept More...

Identifiers< size_t >	edgeVisited

double	m_cost

std::vector< pgr_edge_t >	originalEdges

std::stack< int64_t >	pathStack

std::vector< pgr_edge_t >	resultEdges

std::vector< std::pair< int64_t, std::vector< size_t > > >	resultGraph
	vector of vertex -> vector of edges More...

std::vector< General_path_element_t >	resultPath

std::set< int64_t >	sources

int64_t	startPoint

int64_t	superSource

int64_t	superTarget

std::set< int64_t >	targets

double	totalCost

int64_t	totalDeg

Identifiers< int64_t >	vertexVisited

Identifiers< int64_t >	vertices

std::map< int64_t, size_t >	VToVecid

Detailed Description

Definition at line 49 of file pgr_chinesePostman.hpp.

Constructor & Destructor Documentation

◆ PgrDirectedChPPGraph()

pgrouting::graph::PgrDirectedChPPGraph::PgrDirectedChPPGraph	(	const pgr_edge_t *	dataEdges,
		const size_t	totalEdges
	)

Definition at line 108 of file pgr_chinesePostman.hpp.

                                  :
     totalDeg(0), totalCost(0), vertices(),
     edgeToIdx(), originalEdges(),
     resultGraph(), VToVecid(), edgeVisited(),
     pathStack(), resultPath(),
     edges(), sources(), targets() {
     pgassert(totalEdges > 0);
     pgassert(pathStack.empty());
  
     pgassert(originalEdges.empty());
     startPoint = dataEdges[0].source;
     for (size_t i = 0; i < totalEdges; ++i) {
         if (dataEdges[i].cost > 0) {
             auto edge(dataEdges[i]);
             edge.reverse_cost = -1.0;
             totalCost += edge.cost;
             originalEdges.push_back(edge);
             vertices += dataEdges[i].source;
             vertices += dataEdges[i].target;
         }
         if (dataEdges[i].reverse_cost > 0) {
             auto edge(dataEdges[i]);
             std::swap(edge.source, edge.target);
             std::swap(edge.cost, edge.reverse_cost);
             edge.reverse_cost = -1.0;
             totalCost += edge.cost;
             originalEdges.push_back(edge);
             vertices += dataEdges[i].source;
             vertices += dataEdges[i].target;
             pgassert(dataEdges[i].source == edge.target);
             pgassert(dataEdges[i].target == edge.source);
         }
     }
  
     // calcu deg & build part of edges
     std::map<int64_t, int> deg;
     size_t i(0);
     for (const auto &e : originalEdges) {
         pgassert(e.cost > 0);
         /* has out going edge */
         deg[e.source]++;
         /* has out incoming edge */
         deg[e.target]--;
  
         auto current_edge(std::make_pair(e.source, e.target));
         if (edgeToIdx.find(current_edge) == edgeToIdx.end()) {
             edgeToIdx[current_edge] = &e;
         } else {
             if (edgeToIdx[current_edge]->cost > e.cost) {
                 edgeToIdx[current_edge] = &e;
             }
         }
  
         pgr_costFlow_t edge;
         edge.edge_id = e.id;
         edge.reverse_capacity = -1;
         edge.reverse_cost = -1.0;
         edge.source = e.source;
         edge.target = e.target;
         edge.capacity = (std::numeric_limits<int32_t>::max)();
         edge.cost = e.cost;
         edges.push_back(edge);
         ++i;
     }
  
     superSource = deg.rbegin()->first + 1;
     superTarget = deg.rbegin()->first + 2;
  
     sources.insert(superSource);
     targets.insert(superTarget);
  
     // build full edges
     std::map<int64_t, int>::iterator iter;
     totalDeg = 0;
     for (iter = deg.begin(); iter != deg.end(); ++iter) {
         int64_t p = iter->first;
         int d = iter->second;
         if (d == 0)
             continue;
         if (d > 0)
             totalDeg += d;
         pgr_costFlow_t edge;
         edge.reverse_capacity = -1;
         edge.reverse_cost = -1.0;
         edge.cost = 0.0;
         if (d > 0)
             edge.capacity = d;
         else
             edge.capacity = -d;
         edge.edge_id = 0;
         if (d > 0)
             edge.source = p, edge.target = superTarget;
         if (d < 0)
             edge.source = superSource, edge.target = p;
         edges.push_back(edge);
     }
  
     PgrCostFlowGraph flowGraph(edges, sources, targets);
     pgassert(pathStack.empty());
     try {
         pgrouting::graph::PgrCostFlowGraph digraph1(edges, sources, targets);
         auto minAddedCost = digraph1.MinCostMaxFlow();
         auto maxFlow = digraph1.GetMaxFlow();
         m_cost = (maxFlow == totalDeg)? minAddedCost + totalCost : -1.0;
     } catch (...) {
         m_cost = -1;
     }
     setPathEdges(flowGraph);
 }

References edge::cost, edges, edgeToIdx, pgrouting::graph::PgrCostFlowGraph::GetMaxFlow(), edge::id, m_cost, pgrouting::graph::PgrCostFlowGraph::MinCostMaxFlow(), originalEdges, pathStack, pgassert, edge::reverse_cost, setPathEdges(), pgr_edge_t::source, edge::source, sources, startPoint, superSource, superTarget, pgr_edge_t::target, edge::target, targets, totalCost, totalDeg, and vertices.

◆ ~PgrDirectedChPPGraph()

pgrouting::graph::PgrDirectedChPPGraph::~PgrDirectedChPPGraph ( )

Definition at line 105 of file pgr_chinesePostman.hpp.

                                             {
     edgeToIdx.clear();
 }

References edgeToIdx.

Member Function Documentation

◆ BuildResultGraph()

void pgrouting::graph::PgrDirectedChPPGraph::BuildResultGraph ( )

private

Definition at line 326 of file pgr_chinesePostman.hpp.

                                        {
     pgassert(resultGraph.empty());
     pgassert(VToVecid.empty());
     resultGraph.clear();
     VToVecid.clear();
     size_t e_id(0);
     for (const auto &edge_t : resultEdges) {
         if (VToVecid.find(edge_t.source) == VToVecid.end()) {
             VToVecid[edge_t.source] = resultGraph.size();
             resultGraph.resize(resultGraph.size() + 1);
         }
         size_t vid = VToVecid[edge_t.source];
         resultGraph[vid].second.push_back(e_id);
         resultGraph[vid].first = edge_t.source;
         ++e_id;
     }
 }

References pgassert, resultEdges, resultGraph, edge_t::source, and VToVecid.

Referenced by setPathEdges().

◆ BuildResultPath()

void pgrouting::graph::PgrDirectedChPPGraph::BuildResultPath ( )

private

Definition at line 268 of file pgr_chinesePostman.hpp.

                                       {
     if (pathStack.empty()) return;
     pgassert(resultPath.empty());
  
     int64_t preNode = pathStack.top();
     pathStack.pop();
  
     General_path_element_t newElement;
     while (!pathStack.empty()) {
         int64_t nowNode = pathStack.top();
         pathStack.pop();
  
         auto edge_t = *edgeToIdx[std::make_pair(preNode, nowNode)];
         newElement.node = edge_t.source;
         newElement.edge = edge_t.id;
         newElement.cost = edge_t.cost;
         if (resultPath.empty()) {
             /* adding the first row because is a cycle */
             newElement.seq = 1;
             newElement.agg_cost = 0.0;
         } else {
             newElement.seq = resultPath.back().seq + 1;
             newElement.agg_cost = resultPath.back().agg_cost + resultPath.back().cost;
         }
         resultPath.push_back(newElement);
         preNode = nowNode;
     }
     newElement.node = preNode;
     newElement.edge = -1;
     newElement.cost = 0;
     if (resultPath.empty()) {
         newElement.seq = 1;
         newElement.agg_cost = 0.0;
     } else {
         newElement.seq = resultPath.back().seq + 1;
         newElement.agg_cost =
             resultPath.back().agg_cost + resultPath.back().cost;
     }
     resultPath.push_back(newElement);
 }

References General_path_element_t::agg_cost, edge_t::cost, General_path_element_t::cost, General_path_element_t::edge, edgeToIdx, edge_t::id, General_path_element_t::node, pathStack, pgassert, resultPath, General_path_element_t::seq, and edge_t::source.

Referenced by setPathEdges().

◆ DirectedChPP()

double pgrouting::graph::PgrDirectedChPPGraph::DirectedChPP ( ) const

inline

Definition at line 55 of file pgr_chinesePostman.hpp.

                                  {
          return m_cost;
      }

References m_cost.

Referenced by do_pgr_directedChPP().

◆ EulerCircuitDFS()

bool pgrouting::graph::PgrDirectedChPPGraph::EulerCircuitDFS ( int64_t p )

private

Definition at line 313 of file pgr_chinesePostman.hpp.

                                                     {
     for (const auto e : resultGraph[VToVecid[vertex]].second) {
         if (!edgeVisited.has(e)) {
             edgeVisited += e;
             EulerCircuitDFS(resultEdges[e].target);
         }
     }
     pathStack.push(vertex);
     vertexVisited += vertex;
     return true;
 }

References edgeVisited, Identifiers< T >::has(), pathStack, resultEdges, resultGraph, vertexVisited, and VToVecid.

Referenced by setPathEdges().

◆ GetPathEdges()

std::vector<General_path_element_t> pgrouting::graph::PgrDirectedChPPGraph::GetPathEdges ( ) const

inline

Definition at line 59 of file pgr_chinesePostman.hpp.

                                                             {
          return resultPath;
      }

References resultPath.

Referenced by do_pgr_directedChPP().

◆ setPathEdges()

void pgrouting::graph::PgrDirectedChPPGraph::setPathEdges ( graph::PgrCostFlowGraph & flowGraph )

private

Definition at line 222 of file pgr_chinesePostman.hpp.

                                                                    {
     pgassert(pathStack.empty());
     resultPath.clear();
     if (m_cost == -1) return;
     // catch new edges
     try {
         flowGraph.MinCostMaxFlow();
         flowGraph.GetMaxFlow();
         std::vector<pgr_flow_t> addedEdges = flowGraph.GetFlowEdges();
         resultEdges = originalEdges;
         for (auto &flow_t : addedEdges) {
             if (flow_t.source != superSource && flow_t.source != superTarget
                     && flow_t.target != superSource && flow_t.target != superTarget) {
                 auto current_edge(std::make_pair(flow_t.source, flow_t.target));
                 pgr_edge_t newEdge = *edgeToIdx[current_edge];
                 /* adding edges that need to be traversed twice */
                 while (flow_t.flow--) resultEdges.push_back(newEdge);
             }
         }
     } catch (...) {
         resultPath.clear();
         return;
     }
  
     pgassert(pathStack.empty());
     BuildResultGraph();
  
     pgassert(pathStack.empty());
     pgassert(edgeVisited.empty());
  
  
     EulerCircuitDFS(startPoint);
  
     if (!(vertices - vertexVisited).empty()) {
         resultPath.clear();
         return;
     }
     pgassert(!pathStack.empty());
  
     BuildResultPath();
  
  
     return;
 }