pgrouting::graph::PgrFlowGraph Class Reference

#include "pgr_maxflow.hpp"

Collaboration diagram for pgrouting::graph::PgrFlowGraph:

Public Member Functions
	PgrFlowGraph (const std::vector< pgr_edge_t > &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices, bool directed)
	PgrFlowGraph (const std::vector< pgr_edge_t > &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices, int algorithm)
int64_t	boykov_kolmogorov ()
std::vector< General_path_element_t >	edge_disjoint_paths ()
int64_t	edmonds_karp ()
std::vector< General_path_element_t >	get_edge_disjoint_paths (size_t flow)
std::vector< pgr_flow_t >	get_flow_edges () const
int64_t	push_relabel ()

Private Types
typedef boost::graph_traits< FlowGraph >::edge_descriptor	E
typedef boost::graph_traits< FlowGraph >::edge_iterator	E_it
typedef boost::graph_traits< FlowGraph >::out_edge_iterator	Eout_it
typedef boost::graph_traits< FlowGraph >::vertex_descriptor	V
typedef boost::graph_traits< FlowGraph >::vertex_iterator	V_it

Private Member Functions
template<typename T >
void	add_vertices (const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)
void	flow_dfs (V vertex, size_t path_id, std::vector< std::vector< int64_t > > &paths)
V	get_boost_vertex (int64_t id) const
int64_t	get_edge_id (E e) const
int64_t	get_vertex_id (V v) const
void	insert_edges (const std::vector< pgr_edge_t > &edges)
void	insert_edges_edge_disjoint (const std::vector< pgr_edge_t > &edges, bool directed)
void	insert_edges_push_relabel (const std::vector< pgr_edge_t > &edges)
void	set_supersink (const std::set< int64_t > &sink_vertices)
void	set_supersource (const std::set< int64_t > &source_vertices)

Private Attributes
boost::property_map< FlowGraph, boost::edge_capacity_t >::type	capacity
std::map< E, int64_t >	E_to_id
FlowGraph	graph
std::map< int64_t, V >	id_to_V
boost::property_map< FlowGraph, boost::edge_residual_capacity_t >::type	residual_capacity
boost::property_map< FlowGraph, boost::edge_reverse_t >::type	rev
V	supersink
V	supersource
std::map< V, int64_t >	V_to_id

Detailed Description

Definition at line 55 of file pgr_maxflow.hpp.

Member Typedef Documentation

E

typedef boost::graph_traits<FlowGraph>::edge_descriptor pgrouting::graph::PgrFlowGraph::E

private

Definition at line 57 of file pgr_maxflow.hpp.

E_it

typedef boost::graph_traits<FlowGraph>::edge_iterator pgrouting::graph::PgrFlowGraph::E_it

private

Definition at line 59 of file pgr_maxflow.hpp.

Eout_it

typedef boost::graph_traits<FlowGraph>::out_edge_iterator pgrouting::graph::PgrFlowGraph::Eout_it

private

Definition at line 60 of file pgr_maxflow.hpp.

V

typedef boost::graph_traits<FlowGraph>::vertex_descriptor pgrouting::graph::PgrFlowGraph::V

private

Definition at line 56 of file pgr_maxflow.hpp.

V_it

typedef boost::graph_traits<FlowGraph>::vertex_iterator pgrouting::graph::PgrFlowGraph::V_it

private

Definition at line 58 of file pgr_maxflow.hpp.

Constructor & Destructor Documentation

PgrFlowGraph() [1/2]

pgrouting::graph::PgrFlowGraph::PgrFlowGraph	(	const std::vector< pgr_edge_t > &	edges,
		const std::set< int64_t > &	source_vertices,
		const std::set< int64_t > &	sink_vertices,
		int	algorithm
	)

Definition at line 38 of file pgr_maxflow.cpp.

                       {
    add_vertices(edges, source_vertices, sink_vertices);
 
    capacity = get(boost::edge_capacity, graph);
    rev = get(boost::edge_reverse, graph);
    residual_capacity = get(boost::edge_residual_capacity, graph);
 
    if (algorithm == 1) {
        insert_edges_push_relabel(edges);
    } else {
        insert_edges(edges);
    }
}

References add_vertices(), capacity, graph, insert_edges(), insert_edges_push_relabel(), residual_capacity, and rev.

PgrFlowGraph() [2/2]

pgrouting::graph::PgrFlowGraph::PgrFlowGraph	(	const std::vector< pgr_edge_t > &	edges,
		const std::set< int64_t > &	source_vertices,
		const std::set< int64_t > &	sink_vertices,
		bool	directed
	)

Definition at line 56 of file pgr_maxflow.cpp.

                       {
    add_vertices(edges, source_vertices, sink_vertices);
 
    capacity = get(boost::edge_capacity, graph);
    rev = get(boost::edge_reverse, graph);
    residual_capacity =
        get(boost::edge_residual_capacity, graph);
 
    insert_edges_edge_disjoint(edges, directed);
}

References add_vertices(), capacity, graph, insert_edges_edge_disjoint(), residual_capacity, and rev.

Member Function Documentation

add_vertices()

template<typename T >

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

inlineprivate

Definition at line 162 of file pgr_maxflow.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);
             id_to_V.insert(std::pair<int64_t, V>(id, v));
             V_to_id.insert(std::pair<V, int64_t>(v, id));
         }
 
         set_supersource(source_vertices);
         set_supersink(sink_vertices);
     }

References graph, id_to_V, set_supersink(), set_supersource(), and V_to_id.

Referenced by PgrFlowGraph().

boykov_kolmogorov()

int64_t pgrouting::graph::PgrFlowGraph::boykov_kolmogorov ( )

inline

Definition at line 90 of file pgr_maxflow.hpp.

                                 {
         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
         CHECK_FOR_INTERRUPTS();
         return boost::boykov_kolmogorov_max_flow(
                 graph,
                 supersource,
                 supersink);
     }

References graph, supersink, and supersource.

Referenced by do_pgr_max_flow().

edge_disjoint_paths()

std::vector<General_path_element_t> pgrouting::graph::PgrFlowGraph::edge_disjoint_paths ( )

inline

Definition at line 99 of file pgr_maxflow.hpp.

                                                             {
         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
         CHECK_FOR_INTERRUPTS();
         auto flow = boost::boykov_kolmogorov_max_flow(
                 graph,
                 supersource,
                 supersink);
         return get_edge_disjoint_paths(static_cast<size_t>(flow));
     }

References get_edge_disjoint_paths(), graph, supersink, and supersource.

edmonds_karp()

int64_t pgrouting::graph::PgrFlowGraph::edmonds_karp ( )

inline

Definition at line 81 of file pgr_maxflow.hpp.

                            {
         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
         CHECK_FOR_INTERRUPTS();
         return boost::edmonds_karp_max_flow(
                 graph,
                 supersource,
                 supersink);
     }

References graph, supersink, and supersource.

Referenced by do_pgr_max_flow().

flow_dfs()

void pgrouting::graph::PgrFlowGraph::flow_dfs ( V  vertex, size_t  path_id, std::vector< std::vector< int64_t > > &  paths  )

private

Definition at line 228 of file pgr_maxflow.cpp.

                                               {
    Eout_it ei, e_end;
    if (boost::edge(vertex, supersink, graph).second) {
        int64_t v_id = get_vertex_id(vertex);
        paths[path_id].push_back(v_id);
    } else {
        for (boost::tie(ei, e_end) =
                boost::out_edges(vertex, graph);
                ei != e_end; ++ei) {
            if (residual_capacity[*ei] < capacity[*ei]) {
                // exclude this edge from subsequent visits
                capacity[*ei] = -1;
                int64_t v_id = get_vertex_id(vertex);
                paths[path_id].push_back(v_id);
                flow_dfs((*ei).m_target,
                        path_id,
                        paths);
                break;
            }
        }
    }
}

References capacity, get_vertex_id(), graph, residual_capacity, and supersink.

Referenced by get_edge_disjoint_paths().

get_boost_vertex()

V pgrouting::graph::PgrFlowGraph::get_boost_vertex ( int64_t  id ) const

inlineprivate

Definition at line 128 of file pgr_maxflow.hpp.

                                          {
         return id_to_V.at(id);
     }

References id_to_V.

Referenced by get_edge_disjoint_paths(), insert_edges(), insert_edges_edge_disjoint(), insert_edges_push_relabel(), set_supersink(), and set_supersource().

get_edge_disjoint_paths()

std::vector< General_path_element_t > pgrouting::graph::PgrFlowGraph::get_edge_disjoint_paths

(

size_t

flow

)

Definition at line 254 of file pgr_maxflow.cpp.

                     {
    std::vector<General_path_element_t> path_elements;
 
    std::vector<std::vector<int64_t> > paths(flow, std::vector<int64_t>());
    size_t path_id = 0;
    Eout_it ei, e_end, ei2, e2_end;
    for (boost::tie(ei, e_end) =
            boost::out_edges(supersource, graph);
            ei != e_end; ++ei) {
        if (capacity[*ei] - residual_capacity[*ei] > 0) {
            for (boost::tie(ei2, e2_end) =
                    boost::out_edges((*ei).m_target, graph);
                    ei2 != e2_end; ++ei2) {
                if (capacity[*ei2] - residual_capacity[*ei2]
                        > 0) {
                    paths[path_id].push_back(get_vertex_id((*ei2).m_source));
                    flow_dfs((*ei2).m_target, path_id, paths);
                    path_id++;
                }
            }
        }
    }
    for (size_t i = 0; i < flow; i++) {
        size_t size = paths[i].size();
        E e;
        bool exists;
        size_t j;
        for (j = 0; j < size - 1; j++) {
            General_path_element_t edge;
            edge.seq = static_cast<int>(j + 1);
            edge.start_id = paths[i][0];
            edge.end_id = paths[i][size - 1];
            edge.node = paths[i][j];
            boost::tie(e, exists) = boost::edge(get_boost_vertex(paths[i][j]),
                    get_boost_vertex(paths[i][j + 1]),
                    graph);
            edge.edge = get_edge_id(e);
            path_elements.push_back(edge);
        }
        General_path_element_t edge;
        edge.seq = static_cast<int>(j + 1);
        edge.start_id = paths[i][0];
        edge.end_id = paths[i][size - 1];
        edge.node = paths[i][j];
        edge.edge = -1;
        path_elements.push_back(edge);
    }
    return path_elements;
}

References capacity, flow_dfs(), get_boost_vertex(), get_edge_id(), get_vertex_id(), graph, residual_capacity, and supersource.

Referenced by edge_disjoint_paths().

get_edge_id()

int64_t pgrouting::graph::PgrFlowGraph::get_edge_id ( E  e ) const

inlineprivate

Definition at line 136 of file pgr_maxflow.hpp.

                                    {
         return E_to_id.at(e);
     }

References E_to_id.

Referenced by get_edge_disjoint_paths(), and get_flow_edges().

get_flow_edges()

std::vector< pgr_flow_t > pgrouting::graph::PgrFlowGraph::get_flow_edges

(

)

const

Definition at line 204 of file pgr_maxflow.cpp.

                                   {
    std::vector<pgr_flow_t> flow_edges;
    E_it e, e_end;
    for (boost::tie(e, e_end) = boost::edges(graph); e != e_end;
            ++e) {
        // A supersource/supersink is used internally
        if (((capacity[*e] - residual_capacity[*e]) > 0) &&
                ((*e).m_source != supersource) &&
                ((*e).m_target != supersink)) {
            pgr_flow_t edge;
            edge.edge = get_edge_id(*e);
            edge.source = get_vertex_id((*e).m_source);
            edge.target = get_vertex_id((*e).m_target);
            edge.flow = capacity[*e] - residual_capacity[*e];
            edge.residual_capacity = residual_capacity[*e];
            flow_edges.push_back(edge);
        }
    }
    return flow_edges;
}

References capacity, get_edge_id(), get_vertex_id(), graph, residual_capacity, edge::source, supersink, supersource, and edge::target.

Referenced by do_pgr_max_flow().

get_vertex_id()

int64_t pgrouting::graph::PgrFlowGraph::get_vertex_id ( V  v ) const

inlineprivate

Definition at line 132 of file pgr_maxflow.hpp.

                                      {
         return V_to_id.at(v);
     }

References V_to_id.

Referenced by flow_dfs(), get_edge_disjoint_paths(), and get_flow_edges().

insert_edges()

void pgrouting::graph::PgrFlowGraph::insert_edges ( const std::vector< pgr_edge_t > &  edges )

private

Definition at line 109 of file pgr_maxflow.cpp.

                                            {
    bool added;
    for (const auto edge : edges) {
        V v1 = get_boost_vertex(edge.source);
        V v2 = get_boost_vertex(edge.target);
        E e, e_rev;
        boost::tie(e, added) = boost::add_edge(v1, v2, graph);
        boost::tie(e_rev, added) =
            boost::add_edge(v2, v1, graph);
        E_to_id.insert(std::pair<E, int64_t>(e, edge.id));
        E_to_id.insert(std::pair<E, int64_t>(e_rev, edge.id));
        capacity[e] = edge.cost > 0 ? (int64_t) edge.cost : 0;
        capacity[e_rev] = edge.reverse_cost > 0
            ? (int64_t) edge.reverse_cost : 0;
        rev[e] = e_rev;
        rev[e_rev] = e;
    }
}

References capacity, edge::cost, E_to_id, get_boost_vertex(), graph, edge::id, rev, edge::reverse_cost, edge::source, and edge::target.

Referenced by PgrFlowGraph().

insert_edges_edge_disjoint()

void pgrouting::graph::PgrFlowGraph::insert_edges_edge_disjoint ( const std::vector< pgr_edge_t > &  edges, bool  directed  )

private

Definition at line 132 of file pgr_maxflow.cpp.

                       {
    bool added;
    for (const auto edge : edges) {
        V v1 = get_boost_vertex(edge.source);
        V v2 = get_boost_vertex(edge.target);
        E e, e_rev;
        boost::tie(e, added) =
            boost::add_edge(v1, v2, graph);
        boost::tie(e_rev, added) =
            boost::add_edge(v2, v1, graph);
        E_to_id.insert(std::pair<E, int64_t>(e, edge.id));
        E_to_id.insert(std::pair<E, int64_t>(e_rev,
                    edge.id));
        if (directed) {
            capacity[e] = edge.cost >= 0 ? 1 : 0;
            capacity[e_rev] = edge.reverse_cost >= 0 ? 1 : 0;
        } else {
            if (edge.cost >= 0 || edge.reverse_cost >= 0) {
                capacity[e] = 1;
                capacity[e_rev] = 1;
            }
        }
        rev[e] = e_rev;
        rev[e_rev] = e;
    }
}

References capacity, edge::cost, E_to_id, get_boost_vertex(), graph, edge::id, rev, edge::reverse_cost, edge::source, and edge::target.

Referenced by PgrFlowGraph().

insert_edges_push_relabel()

void pgrouting::graph::PgrFlowGraph::insert_edges_push_relabel ( const std::vector< pgr_edge_t > &  edges )

private

Definition at line 74 of file pgr_maxflow.cpp.

                                            {
    bool added;
    for (const auto edge : edges) {
        V v1 = get_boost_vertex(edge.source);
        V v2 = get_boost_vertex(edge.target);
        E e1, e1_rev, e2, e2_rev;
        if (edge.cost > 0) {
            boost::tie(e1, added) = boost::add_edge(v1, v2, graph);
            boost::tie(e1_rev, added) =
                boost::add_edge(v2, v1, graph);
            E_to_id.insert(std::pair<E, int64_t>(e1, edge.id));
            E_to_id.insert(std::pair<E, int64_t>(e1_rev, edge.id));
            capacity[e1] = (int64_t) edge.cost;
            capacity[e1_rev] = 0;
            rev[e1] = e1_rev;
            rev[e1_rev] = e1;
        }
        if (edge.reverse_cost > 0) {
            boost::tie(e2, added) = boost::add_edge(v2, v1, graph);
            boost::tie(e2_rev, added) =
                boost::add_edge(v1, v2, graph);
            E_to_id.insert(std::pair<E, int64_t>(e2, edge.id));
            E_to_id.insert(std::pair<E, int64_t>(e2_rev, edge.id));
            capacity[e2] = (int64_t) edge.reverse_cost;
            capacity[e2_rev] = 0;
            rev[e2] = e2_rev;
            rev[e2_rev] = e2;
        }
    }
}

References capacity, edge::cost, E_to_id, get_boost_vertex(), graph, edge::id, rev, edge::reverse_cost, edge::source, and edge::target.

Referenced by PgrFlowGraph().

push_relabel()

int64_t pgrouting::graph::PgrFlowGraph::push_relabel ( )

inline

Definition at line 72 of file pgr_maxflow.hpp.

                            {
         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
         CHECK_FOR_INTERRUPTS();
         return boost::push_relabel_max_flow(
                 graph,
                 supersource,
                 supersink);
     }

References graph, supersink, and supersource.

Referenced by do_pgr_max_flow().

set_supersink()

void pgrouting::graph::PgrFlowGraph::set_supersink ( const std::set< int64_t > &  sink_vertices )

private

Definition at line 181 of file pgr_maxflow.cpp.

                                              {
    bool added;
    supersink = add_vertex(graph);
    for (int64_t sink_id : sink_vertices) {
        V sink = get_boost_vertex(sink_id);
        E e, e_rev;
        boost::tie(e, added) = boost::add_edge(sink, supersink, graph);
        boost::tie(e_rev, added) =
            boost::add_edge(supersink, sink, graph);
        /*
         * NOTE: int64_t crashes the server
         */
        /* From sinks to supersink has maximum capacity*/
        capacity[e] = (std::numeric_limits<int32_t>::max)();
        /* From supersink to sinks has 0 capacity*/
        capacity[e_rev] = 0;
        rev[e] = e_rev;
        rev[e_rev] = e;
    }
}

References capacity, get_boost_vertex(), graph, rev, and supersink.

Referenced by add_vertices().

set_supersource()

void pgrouting::graph::PgrFlowGraph::set_supersource ( const std::set< int64_t > &  source_vertices )

private

Definition at line 161 of file pgr_maxflow.cpp.

                                                {
    bool added;
    supersource = add_vertex(graph);
    for (int64_t source_id : source_vertices) {
        V source = get_boost_vertex(source_id);
        E e, e_rev;
        boost::tie(e, added) =
            boost::add_edge(supersource, source, graph);
        boost::tie(e_rev, added) =
            boost::add_edge(source, supersource, graph);
 
        capacity[e] = (std::numeric_limits<int32_t>::max)();
        /* From sources to supersource has 0 capacity*/
        capacity[e_rev] = 0;
        rev[e] = e_rev;
        rev[e_rev] = e;
    }
}

References capacity, get_boost_vertex(), graph, rev, and supersource.

Referenced by add_vertices().

Member Data Documentation

capacity

boost::property_map<FlowGraph, boost::edge_capacity_t>::type pgrouting::graph::PgrFlowGraph::capacity

private

Definition at line 64 of file pgr_maxflow.hpp.

Referenced by flow_dfs(), get_edge_disjoint_paths(), get_flow_edges(), insert_edges(), insert_edges_edge_disjoint(), insert_edges_push_relabel(), PgrFlowGraph(), set_supersink(), and set_supersource().

E_to_id

std::map<E, int64_t> pgrouting::graph::PgrFlowGraph::E_to_id

private

Definition at line 188 of file pgr_maxflow.hpp.

Referenced by get_edge_id(), insert_edges(), insert_edges_edge_disjoint(), and insert_edges_push_relabel().

graph

FlowGraph pgrouting::graph::PgrFlowGraph::graph

private

Definition at line 185 of file pgr_maxflow.hpp.

Referenced by add_vertices(), boykov_kolmogorov(), edge_disjoint_paths(), edmonds_karp(), flow_dfs(), get_edge_disjoint_paths(), get_flow_edges(), insert_edges(), insert_edges_edge_disjoint(), insert_edges_push_relabel(), PgrFlowGraph(), push_relabel(), set_supersink(), and set_supersource().

id_to_V

std::map<int64_t, V> pgrouting::graph::PgrFlowGraph::id_to_V

private

Definition at line 186 of file pgr_maxflow.hpp.

Referenced by add_vertices(), and get_boost_vertex().

residual_capacity

boost::property_map<FlowGraph, boost::edge_residual_capacity_t>::type pgrouting::graph::PgrFlowGraph::residual_capacity

private

Definition at line 68 of file pgr_maxflow.hpp.

Referenced by flow_dfs(), get_edge_disjoint_paths(), get_flow_edges(), and PgrFlowGraph().

rev

boost::property_map<FlowGraph, boost::edge_reverse_t>::type pgrouting::graph::PgrFlowGraph::rev

private

Definition at line 66 of file pgr_maxflow.hpp.

Referenced by insert_edges(), insert_edges_edge_disjoint(), insert_edges_push_relabel(), PgrFlowGraph(), set_supersink(), and set_supersource().

supersink

V pgrouting::graph::PgrFlowGraph::supersink

private

Definition at line 196 of file pgr_maxflow.hpp.

Referenced by boykov_kolmogorov(), edge_disjoint_paths(), edmonds_karp(), flow_dfs(), get_flow_edges(), push_relabel(), and set_supersink().

supersource

V pgrouting::graph::PgrFlowGraph::supersource

private

Definition at line 195 of file pgr_maxflow.hpp.

Referenced by boykov_kolmogorov(), edge_disjoint_paths(), edmonds_karp(), get_edge_disjoint_paths(), get_flow_edges(), push_relabel(), and set_supersource().

V_to_id

std::map<V, int64_t> pgrouting::graph::PgrFlowGraph::V_to_id

private

Definition at line 187 of file pgr_maxflow.hpp.

Referenced by add_vertices(), and get_vertex_id().

---

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

• pgr_maxflow.hpp
• pgr_maxflow.cpp