FM / graph

/usr/include/boost/graph

Name	Size	Mode	Actions
detail/	-	0755	rm
distributed/	-	0755	rm
parallel/	-	0755	rm
planar_detail/	-	0755	rm
property_maps/	-	0755	rm
accounting.hpp	876	0644	edit dl rm
adjacency_iterator.hpp	2899	0644	edit dl rm
adjacency_list.hpp	13692	0644	edit dl rm
adjacency_list_io.hpp	11849	0644	edit dl rm
adjacency_matrix.hpp	45743	0644	edit dl rm
adj_list_serialize.hpp	4523	0644	edit dl rm
astar_search.hpp	26736	0644	edit dl rm
bandwidth.hpp	2992	0644	edit dl rm
bc_clustering.hpp	5937	0644	edit dl rm
bellman_ford_shortest_paths.hpp	8229	0644	edit dl rm
betweenness_centrality.hpp	26290	0644	edit dl rm
biconnected_components.hpp	16701	0644	edit dl rm
bipartite.hpp	13492	0644	edit dl rm
boyer_myrvold_planar_test.hpp	9849	0644	edit dl rm
boykov_kolmogorov_max_flow.hpp	47342	0644	edit dl rm
breadth_first_search.hpp	14751	0644	edit dl rm
bron_kerbosch_all_cliques.hpp	11736	0644	edit dl rm
buffer_concepts.hpp	2429	0644	edit dl rm
chrobak_payne_drawing.hpp	8641	0644	edit dl rm
circle_layout.hpp	1924	0644	edit dl rm
closeness_centrality.hpp	6057	0644	edit dl rm
clustering_coefficient.hpp	5726	0644	edit dl rm
compressed_sparse_row_graph.hpp	69887	0644	edit dl rm
connected_components.hpp	4134	0644	edit dl rm
copy.hpp	21225	0644	edit dl rm
core_numbers.hpp	13663	0644	edit dl rm
create_condensation_graph.hpp	3159	0644	edit dl rm
cuthill_mckee_ordering.hpp	5992	0644	edit dl rm
cycle_canceling.hpp	6645	0644	edit dl rm
dag_shortest_paths.hpp	6064	0644	edit dl rm
degree_centrality.hpp	4236	0644	edit dl rm
depth_first_search.hpp	15430	0644	edit dl rm
dijkstra_shortest_paths.hpp	23687	0644	edit dl rm
dijkstra_shortest_paths_no_color_map.hpp	9620	0644	edit dl rm
dimacs.hpp	10448	0644	edit dl rm
directed_graph.hpp	24214	0644	edit dl rm
dll_import_export.hpp	892	0644	edit dl rm
dominator_tree.hpp	17553	0644	edit dl rm
eccentricity.hpp	4611	0644	edit dl rm
edge_coloring.hpp	6809	0644	edit dl rm
edge_connectivity.hpp	6796	0644	edit dl rm
edge_list.hpp	9948	0644	edit dl rm
edmonds_karp_max_flow.hpp	10177	0644	edit dl rm
edmunds_karp_max_flow.hpp	982	0644	edit dl rm
erdos_renyi_generator.hpp	7257	0644	edit dl rm
exception.hpp	1466	0644	edit dl rm
exterior_property.hpp	4289	0644	edit dl rm
filtered_graph.hpp	20098	0644	edit dl rm
find_flow_cost.hpp	1859	0644	edit dl rm
floyd_warshall_shortest.hpp	8510	0644	edit dl rm
fruchterman_reingold.hpp	17325	0644	edit dl rm
geodesic_distance.hpp	8015	0644	edit dl rm
graphml.hpp	13460	0644	edit dl rm
graphviz.hpp	33503	0644	edit dl rm
graph_archetypes.hpp	11008	0644	edit dl rm
graph_as_tree.hpp	4532	0644	edit dl rm
graph_concepts.hpp	19785	0644	edit dl rm
graph_mutability_traits.hpp	4995	0644	edit dl rm
graph_selectors.hpp	1274	0644	edit dl rm
graph_stats.hpp	4394	0644	edit dl rm
graph_traits.hpp	13065	0644	edit dl rm
graph_utility.hpp	16182	0644	edit dl rm
grid_graph.hpp	33830	0644	edit dl rm
gursoy_atun_layout.hpp	13248	0644	edit dl rm
hawick_circuits.hpp	14593	0644	edit dl rm
howard_cycle_ratio.hpp	23107	0644	edit dl rm
incremental_components.hpp	8224	0644	edit dl rm
isomorphism.hpp	26308	0644	edit dl rm
is_kuratowski_subgraph.hpp	10260	0644	edit dl rm
is_straight_line_drawing.hpp	7230	0644	edit dl rm
iteration_macros.hpp	11659	0644	edit dl rm
iteration_macros_undef.hpp	673	0644	edit dl rm
johnson_all_pairs_shortest.hpp	7646	0644	edit dl rm
kamada_kawai_spring_layout.hpp	28048	0644	edit dl rm
king_ordering.hpp	12101	0644	edit dl rm
kruskal_min_spanning_tree.hpp	5743	0644	edit dl rm
labeled_graph.hpp	30914	0644	edit dl rm
leda_graph.hpp	28789	0644	edit dl rm
lookup_edge.hpp	1894	0644	edit dl rm
loop_erased_random_walk.hpp	4436	0644	edit dl rm
make_biconnected_planar.hpp	3513	0644	edit dl rm
make_connected.hpp	2645	0644	edit dl rm
make_maximal_planar.hpp	7578	0644	edit dl rm
matrix_as_graph.hpp	7227	0644	edit dl rm
maximum_adjacency_search.hpp	15125	0644	edit dl rm
maximum_weighted_matching.hpp	49722	0644	edit dl rm
max_cardinality_matching.hpp	31000	0644	edit dl rm
mcgregor_common_subgraphs.hpp	43470	0644	edit dl rm
mesh_graph_generator.hpp	5616	0644	edit dl rm
metis.hpp	10982	0644	edit dl rm
metric_tsp_approx.hpp	10809	0644	edit dl rm
minimum_degree_ordering.hpp	27087	0644	edit dl rm
named_function_params.hpp	39639	0644	edit dl rm
named_graph.hpp	20614	0644	edit dl rm
neighbor_bfs.hpp	11763	0644	edit dl rm
numeric_values.hpp	1814	0644	edit dl rm
one_bit_color_map.hpp	3277	0644	edit dl rm
overloading.hpp	1584	0644	edit dl rm
page_rank.hpp	6164	0644	edit dl rm
planar_canonical_ordering.hpp	7203	0644	edit dl rm
planar_face_traversal.hpp	6020	0644	edit dl rm
plod_generator.hpp	7708	0644	edit dl rm
point_traits.hpp	782	0644	edit dl rm
prim_minimum_spanning_tree.hpp	2960	0644	edit dl rm
profile.hpp	1327	0644	edit dl rm
properties.hpp	12417	0644	edit dl rm
property_iter_range.hpp	4345	0644	edit dl rm
push_relabel_max_flow.hpp	34737	0644	edit dl rm
random.hpp	9672	0644	edit dl rm
random_layout.hpp	988	0644	edit dl rm
random_spanning_tree.hpp	5775	0644	edit dl rm
read_dimacs.hpp	12080	0644	edit dl rm
relax.hpp	4400	0644	edit dl rm
reverse_graph.hpp	22402	0644	edit dl rm
rmat_graph_generator.hpp	19291	0644	edit dl rm
r_c_shortest_paths.hpp	30673	0644	edit dl rm
sequential_vertex_coloring.hpp	4562	0644	edit dl rm
simple_point.hpp	628	0644	edit dl rm
sloan_ordering.hpp	15540	0644	edit dl rm
smallest_last_ordering.hpp	5458	0644	edit dl rm
small_world_generator.hpp	3670	0644	edit dl rm
ssca_graph_generator.hpp	6564	0644	edit dl rm
stanford_graph.hpp	20126	0644	edit dl rm
stoer_wagner_min_cut.hpp	12415	0644	edit dl rm
strong_components.hpp	13009	0644	edit dl rm
st_connected.hpp	2852	0644	edit dl rm
subgraph.hpp	39996	0644	edit dl rm
successive_shortest_path_nonnegative_weights.hpp	10413	0644	edit dl rm
tiernan_all_cycles.hpp	12547	0644	edit dl rm
topological_sort.hpp	2611	0644	edit dl rm
topology.hpp	20389	0644	edit dl rm
transitive_closure.hpp	14260	0644	edit dl rm
transitive_reduction.hpp	5326	0644	edit dl rm
transpose_graph.hpp	1198	0644	edit dl rm
tree_traits.hpp	1338	0644	edit dl rm
two_bit_color_map.hpp	3510	0644	edit dl rm
two_graphs_common_spanning_trees.hpp	34996	0644	edit dl rm
undirected_dfs.hpp	10672	0644	edit dl rm
undirected_graph.hpp	25276	0644	edit dl rm
use_mpi.hpp	437	0644	edit dl rm
vector_as_graph.hpp	10474	0644	edit dl rm
vertex_and_edge_range.hpp	5528	0644	edit dl rm
vf2_sub_graph_iso.hpp	48585	0644	edit dl rm
visitors.hpp	11318	0644	edit dl rm
wavefront.hpp	3932	0644	edit dl rm
write_dimacs.hpp	2889	0644	edit dl rm

Edit: /usr/include/boost/graph/r_c_shortest_paths.hpp (30673B)

// r_c_shortest_paths.hpp header file

// Copyright Michael Drexl 2005, 2006.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
#define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP

#include <map>
#include <queue>
#include <vector>
#include <list>

#include <boost/make_shared.hpp>
#include <boost/enable_shared_from_this.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/property_map/property_map.hpp>

namespace boost
{

// r_c_shortest_paths_label struct
template < class Graph, class Resource_Container >
struct r_c_shortest_paths_label
: public boost::enable_shared_from_this<
      r_c_shortest_paths_label< Graph, Resource_Container > >
{
    r_c_shortest_paths_label(const unsigned long n,
        const Resource_Container& rc = Resource_Container(),
        const boost::shared_ptr<
            r_c_shortest_paths_label< Graph, Resource_Container > >
            pl
        = boost::shared_ptr<
            r_c_shortest_paths_label< Graph, Resource_Container > >(),
        const typename graph_traits< Graph >::edge_descriptor& ed
        = graph_traits< Graph >::edge_descriptor(),
        const typename graph_traits< Graph >::vertex_descriptor& vd
        = graph_traits< Graph >::vertex_descriptor())
    : num(n)
    , cumulated_resource_consumption(rc)
    , p_pred_label(pl)
    , pred_edge(ed)
    , resident_vertex(vd)
    , b_is_dominated(false)
    , b_is_processed(false)
    {
    }

r_c_shortest_paths_label& operator=(const r_c_shortest_paths_label& other)
    {
        if (this == &other)
            return *this;
        this->~r_c_shortest_paths_label();
        new (this) r_c_shortest_paths_label(other);
        return *this;
    }
    const unsigned long num;
    Resource_Container cumulated_resource_consumption;
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >
        p_pred_label;
    const typename graph_traits< Graph >::edge_descriptor pred_edge;
    const typename graph_traits< Graph >::vertex_descriptor resident_vertex;
    bool b_is_dominated;
    bool b_is_processed;
}; // r_c_shortest_paths_label

template < class Graph, class Resource_Container >
inline bool operator==(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l1.cumulated_resource_consumption
        == l2.cumulated_resource_consumption;
}

template < class Graph, class Resource_Container >
inline bool operator!=(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return !(l1 == l2);
}

template < class Graph, class Resource_Container >
inline bool operator<(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l1.cumulated_resource_consumption
        < l2.cumulated_resource_consumption;
}

template < class Graph, class Resource_Container >
inline bool operator>(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l2.cumulated_resource_consumption
        < l1.cumulated_resource_consumption;
}

template < class Graph, class Resource_Container >
inline bool operator<=(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l1 < l2 || l1 == l2;
}

template < class Graph, class Resource_Container >
inline bool operator>=(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l2 < l1 || l1 == l2;
}

template < typename Graph, typename Resource_Container >
inline bool operator<(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t < *u;
}

template < typename Graph, typename Resource_Container >
inline bool operator<=(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t <= *u;
}

template < typename Graph, typename Resource_Container >
inline bool operator>(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t > *u;
}

template < typename Graph, typename Resource_Container >
inline bool operator>=(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t >= *u;
}

namespace detail
{

// r_c_shortest_paths_dispatch function (body/implementation)
    template < class Graph, class VertexIndexMap, class EdgeIndexMap,
        class Resource_Container, class Resource_Extension_Function,
        class Dominance_Function, class Label_Allocator, class Visitor >
    void r_c_shortest_paths_dispatch(const Graph& g,
        const VertexIndexMap& vertex_index_map,
        const EdgeIndexMap& /*edge_index_map*/,
        typename graph_traits< Graph >::vertex_descriptor s,
        typename graph_traits< Graph >::vertex_descriptor t,
        // each inner vector corresponds to a pareto-optimal path
        std::vector<
            std::vector< typename graph_traits< Graph >::edge_descriptor > >&
            pareto_optimal_solutions,
        std::vector< Resource_Container >& pareto_optimal_resource_containers,
        bool b_all_pareto_optimal_solutions,
        // to initialize the first label/resource container
        // and to carry the type information
        const Resource_Container& rc, Resource_Extension_Function& ref,
        Dominance_Function& dominance,
        // to specify the memory management strategy for the labels
        Label_Allocator /*la*/, Visitor vis)
    {
        pareto_optimal_resource_containers.clear();
        pareto_optimal_solutions.clear();

size_t i_label_num = 0;
#if defined(BOOST_NO_CXX11_ALLOCATOR)
        typedef typename Label_Allocator::template rebind<
            r_c_shortest_paths_label< Graph, Resource_Container > >::other
            LAlloc;
#else
        typedef typename std::allocator_traits< Label_Allocator >::
            template rebind_alloc<
                r_c_shortest_paths_label< Graph, Resource_Container > >
                LAlloc;
        typedef std::allocator_traits< LAlloc > LTraits;
#endif
        LAlloc l_alloc;
        typedef boost::shared_ptr<
            r_c_shortest_paths_label< Graph, Resource_Container > >
            Splabel;
        std::priority_queue< Splabel, std::vector< Splabel >,
            std::greater< Splabel > >
            unprocessed_labels;

bool b_feasible = true;
        Splabel splabel_first_label = boost::allocate_shared<
            r_c_shortest_paths_label< Graph, Resource_Container > >(l_alloc,
            i_label_num++, rc,
            boost::shared_ptr<
                r_c_shortest_paths_label< Graph, Resource_Container > >(),
            typename graph_traits< Graph >::edge_descriptor(), s);

unprocessed_labels.push(splabel_first_label);
        std::vector< std::list< Splabel > > vec_vertex_labels_data(
            num_vertices(g));
        iterator_property_map<
            typename std::vector< std::list< Splabel > >::iterator,
            VertexIndexMap >
            vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map);
        vec_vertex_labels[s].push_back(splabel_first_label);
        typedef std::vector< typename std::list< Splabel >::iterator >
            vec_last_valid_positions_for_dominance_data_type;
        vec_last_valid_positions_for_dominance_data_type
            vec_last_valid_positions_for_dominance_data(num_vertices(g));
        iterator_property_map<
            typename vec_last_valid_positions_for_dominance_data_type::iterator,
            VertexIndexMap >
            vec_last_valid_positions_for_dominance(
                vec_last_valid_positions_for_dominance_data.begin(),
                vertex_index_map);
        BGL_FORALL_VERTICES_T(v, g, Graph)
        {
            put(vec_last_valid_positions_for_dominance, v,
                vec_vertex_labels[v].begin());
        }
        std::vector< size_t > vec_last_valid_index_for_dominance_data(
            num_vertices(g), 0);
        iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap >
            vec_last_valid_index_for_dominance(
                vec_last_valid_index_for_dominance_data.begin(),
                vertex_index_map);
        std::vector< bool > b_vec_vertex_already_checked_for_dominance_data(
            num_vertices(g), false);
        iterator_property_map< std::vector< bool >::iterator, VertexIndexMap >
            b_vec_vertex_already_checked_for_dominance(
                b_vec_vertex_already_checked_for_dominance_data.begin(),
                vertex_index_map);

while (!unprocessed_labels.empty()
            && vis.on_enter_loop(unprocessed_labels, g))
        {
            Splabel cur_label = unprocessed_labels.top();
            unprocessed_labels.pop();
            vis.on_label_popped(*cur_label, g);
            // an Splabel object in unprocessed_labels and the respective
            // Splabel object in the respective list<Splabel> of
            // vec_vertex_labels share their embedded r_c_shortest_paths_label
            // object to avoid memory leaks, dominated r_c_shortest_paths_label
            // objects are marked and deleted when popped from
            // unprocessed_labels, as they can no longer be deleted at the end
            // of the function; only the Splabel object in unprocessed_labels
            // still references the r_c_shortest_paths_label object this is also
            // for efficiency, because the else branch is executed only if there
            // is a chance that extending the label leads to new undominated
            // labels, which in turn is possible only if the label to be
            // extended is undominated
            if (!cur_label->b_is_dominated)
            {
                typename boost::graph_traits< Graph >::vertex_descriptor
                    i_cur_resident_vertex
                    = cur_label->resident_vertex;
                std::list< Splabel >& list_labels_cur_vertex
                    = get(vec_vertex_labels, i_cur_resident_vertex);
                if (list_labels_cur_vertex.size() >= 2
                    && vec_last_valid_index_for_dominance[i_cur_resident_vertex]
                        < list_labels_cur_vertex.size())
                {
                    typename std::list< Splabel >::iterator outer_iter
                        = list_labels_cur_vertex.begin();
                    bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
                        = false;
                    while (outer_iter != list_labels_cur_vertex.end())
                    {
                        Splabel cur_outer_splabel = *outer_iter;
                        typename std::list< Splabel >::iterator inner_iter
                            = outer_iter;
                        if (!b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
                            && outer_iter
                                == get(vec_last_valid_positions_for_dominance,
                                    i_cur_resident_vertex))
                            b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
                                = true;
                        if (!get(b_vec_vertex_already_checked_for_dominance,
                                i_cur_resident_vertex)
                            || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance)
                        {
                            ++inner_iter;
                        }
                        else
                        {
                            inner_iter
                                = get(vec_last_valid_positions_for_dominance,
                                    i_cur_resident_vertex);
                            ++inner_iter;
                        }
                        bool b_outer_iter_erased = false;
                        while (inner_iter != list_labels_cur_vertex.end())
                        {
                            Splabel cur_inner_splabel = *inner_iter;
                            if (dominance(cur_outer_splabel
                                              ->cumulated_resource_consumption,
                                    cur_inner_splabel
                                        ->cumulated_resource_consumption))
                            {
                                typename std::list< Splabel >::iterator buf
                                    = inner_iter;
                                ++inner_iter;
                                list_labels_cur_vertex.erase(buf);
                                if (cur_inner_splabel->b_is_processed)
                                {
                                    cur_inner_splabel.reset();
                                }
                                else
                                    cur_inner_splabel->b_is_dominated = true;
                                continue;
                            }
                            else
                                ++inner_iter;
                            if (dominance(cur_inner_splabel
                                              ->cumulated_resource_consumption,
                                    cur_outer_splabel
                                        ->cumulated_resource_consumption))
                            {
                                typename std::list< Splabel >::iterator buf
                                    = outer_iter;
                                ++outer_iter;
                                list_labels_cur_vertex.erase(buf);
                                b_outer_iter_erased = true;
                                if (cur_outer_splabel->b_is_processed)
                                {
                                    cur_outer_splabel.reset();
                                }
                                else
                                    cur_outer_splabel->b_is_dominated = true;
                                break;
                            }
                        }
                        if (!b_outer_iter_erased)
                            ++outer_iter;
                    }
                    if (list_labels_cur_vertex.size() > 1)
                        put(vec_last_valid_positions_for_dominance,
                            i_cur_resident_vertex,
                            (--(list_labels_cur_vertex.end())));
                    else
                        put(vec_last_valid_positions_for_dominance,
                            i_cur_resident_vertex,
                            list_labels_cur_vertex.begin());
                    put(b_vec_vertex_already_checked_for_dominance,
                        i_cur_resident_vertex, true);
                    put(vec_last_valid_index_for_dominance,
                        i_cur_resident_vertex,
                        list_labels_cur_vertex.size() - 1);
                }
            }
            if (!b_all_pareto_optimal_solutions
                && cur_label->resident_vertex == t)
            {
                // the devil don't sleep
                if (cur_label->b_is_dominated)
                {
                    cur_label.reset();
                }
                while (unprocessed_labels.size())
                {
                    Splabel l = unprocessed_labels.top();
                    unprocessed_labels.pop();
                    // delete only dominated labels, because nondominated labels
                    // are deleted at the end of the function
                    if (l->b_is_dominated)
                    {
                        l.reset();
                    }
                }
                break;
            }
            if (!cur_label->b_is_dominated)
            {
                cur_label->b_is_processed = true;
                vis.on_label_not_dominated(*cur_label, g);
                typename graph_traits< Graph >::vertex_descriptor cur_vertex
                    = cur_label->resident_vertex;
                typename graph_traits< Graph >::out_edge_iterator oei, oei_end;
                for (boost::tie(oei, oei_end) = out_edges(cur_vertex, g);
                     oei != oei_end; ++oei)
                {
                    b_feasible = true;
                    Splabel new_label = boost::allocate_shared<
                        r_c_shortest_paths_label< Graph, Resource_Container > >(
                        l_alloc, i_label_num++,
                        cur_label->cumulated_resource_consumption, cur_label,
                        *oei, target(*oei, g));
                    b_feasible = ref(g,
                        new_label->cumulated_resource_consumption,
                        new_label->p_pred_label->cumulated_resource_consumption,
                        new_label->pred_edge);

if (!b_feasible)
                    {
                        vis.on_label_not_feasible(*new_label, g);
                        new_label.reset();
                    }
                    else
                    {
                        vis.on_label_feasible(*new_label, g);
                        vec_vertex_labels[new_label->resident_vertex].push_back(
                            new_label);
                        unprocessed_labels.push(new_label);
                    }
                }
            }
            else
            {
                vis.on_label_dominated(*cur_label, g);
                cur_label.reset();
            }
        }
        std::list< Splabel > dsplabels = get(vec_vertex_labels, t);
        typename std::list< Splabel >::const_iterator csi = dsplabels.begin();
        typename std::list< Splabel >::const_iterator csi_end = dsplabels.end();
        // if d could be reached from o
        if (!dsplabels.empty())
        {
            for (; csi != csi_end; ++csi)
            {
                std::vector< typename graph_traits< Graph >::edge_descriptor >
                    cur_pareto_optimal_path;
                boost::shared_ptr<
                    r_c_shortest_paths_label< Graph, Resource_Container > >
                    p_cur_label = *csi;
                pareto_optimal_resource_containers.push_back(
                    p_cur_label->cumulated_resource_consumption);
                while (p_cur_label->num != 0)
                {
                    cur_pareto_optimal_path.push_back(p_cur_label->pred_edge);
                    p_cur_label = p_cur_label->p_pred_label;

// assertion b_is_valid beyond this point is not correct if
                    // the domination function requires resource levels to be
                    // strictly greater than existing values
                    //
                    // Example
                    // Customers
                    // id   min_arrival   max_departure
                    //  2             0             974
                    //  3             0             972
                    //  4             0             964
                    //  5           678             801
                    //
                    // Path A: 2-3-4-5 (times: 0-16-49-84-678)
                    // Path B: 3-2-4-5 (times: 0-18-51-62-678)
                    // The partial path 3-2-4 dominates the other partial path
                    // 2-3-4, though the path 3-2-4-5 does not strictly dominate
                    // the path 2-3-4-5
                }
                pareto_optimal_solutions.push_back(cur_pareto_optimal_path);
                if (!b_all_pareto_optimal_solutions)
                    break;
            }
        }

BGL_FORALL_VERTICES_T(i, g, Graph)
        {
            std::list< Splabel >& list_labels_cur_vertex = vec_vertex_labels[i];
            typename std::list< Splabel >::iterator si
                = list_labels_cur_vertex.begin();
            const typename std::list< Splabel >::iterator si_end
                = list_labels_cur_vertex.end();
            for (; si != si_end; ++si)
            {
                (*si).reset();
            }
        }
    } // r_c_shortest_paths_dispatch

} // detail

// default_r_c_shortest_paths_visitor struct
struct default_r_c_shortest_paths_visitor
{
    template < class Label, class Graph >
    void on_label_popped(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_feasible(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_not_feasible(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_dominated(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_not_dominated(const Label&, const Graph&)
    {
    }
    template < class Queue, class Graph >
    bool on_enter_loop(const Queue& queue, const Graph& graph)
    {
        return true;
    }
}; // default_r_c_shortest_paths_visitor

// default_r_c_shortest_paths_allocator
typedef std::allocator< int > default_r_c_shortest_paths_allocator;
// default_r_c_shortest_paths_allocator

// r_c_shortest_paths functions (handle/interface)
// first overload:
// - return all pareto-optimal solutions
// - specify Label_Allocator and Visitor arguments
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function, class Label_Allocator, class Visitor >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >&
        pareto_optimal_solutions,
    std::vector< Resource_Container >& pareto_optimal_resource_containers,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance,
    // to specify the memory management strategy for the labels
    Label_Allocator la, Visitor vis)
{
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
        ref, dominance, la, vis);
}

// second overload:
// - return only one pareto-optimal solution
// - specify Label_Allocator and Visitor arguments
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function, class Label_Allocator, class Visitor >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    std::vector< typename graph_traits< Graph >::edge_descriptor >&
        pareto_optimal_solution,
    Resource_Container& pareto_optimal_resource_container,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance,
    // to specify the memory management strategy for the labels
    Label_Allocator la, Visitor vis)
{
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >
        pareto_optimal_solutions;
    std::vector< Resource_Container > pareto_optimal_resource_containers;
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
        ref, dominance, la, vis);
    if (!pareto_optimal_solutions.empty())
    {
        pareto_optimal_solution = pareto_optimal_solutions[0];
        pareto_optimal_resource_container
            = pareto_optimal_resource_containers[0];
    }
}

// third overload:
// - return all pareto-optimal solutions
// - use default Label_Allocator and Visitor
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >&
        pareto_optimal_solutions,
    std::vector< Resource_Container >& pareto_optimal_resource_containers,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance)
{
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
        ref, dominance, default_r_c_shortest_paths_allocator(),
        default_r_c_shortest_paths_visitor());
}

// fourth overload:
// - return only one pareto-optimal solution
// - use default Label_Allocator and Visitor
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    std::vector< typename graph_traits< Graph >::edge_descriptor >&
        pareto_optimal_solution,
    Resource_Container& pareto_optimal_resource_container,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance)
{
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >
        pareto_optimal_solutions;
    std::vector< Resource_Container > pareto_optimal_resource_containers;
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
        ref, dominance, default_r_c_shortest_paths_allocator(),
        default_r_c_shortest_paths_visitor());
    if (!pareto_optimal_solutions.empty())
    {
        pareto_optimal_solution = pareto_optimal_solutions[0];
        pareto_optimal_resource_container
            = pareto_optimal_resource_containers[0];
    }
}
// r_c_shortest_paths

// check_r_c_path function
template < class Graph, class Resource_Container,
    class Resource_Extension_Function >
void check_r_c_path(const Graph& g,
    const std::vector< typename graph_traits< Graph >::edge_descriptor >&
        ed_vec_path,
    const Resource_Container& initial_resource_levels,
    // if true, computed accumulated final resource levels must
    // be equal to desired_final_resource_levels
    // if false, computed accumulated final resource levels must
    // be less than or equal to desired_final_resource_levels
    bool b_result_must_be_equal_to_desired_final_resource_levels,
    const Resource_Container& desired_final_resource_levels,
    Resource_Container& actual_final_resource_levels,
    const Resource_Extension_Function& ref, bool& b_is_a_path_at_all,
    bool& b_feasible, bool& b_correctly_extended,
    typename graph_traits< Graph >::edge_descriptor& ed_last_extended_arc)
{
    size_t i_size_ed_vec_path = ed_vec_path.size();
    std::vector< typename graph_traits< Graph >::edge_descriptor > buf_path;
    if (i_size_ed_vec_path == 0)
        b_feasible = true;
    else
    {
        if (i_size_ed_vec_path == 1
            || target(ed_vec_path[0], g) == source(ed_vec_path[1], g))
            buf_path = ed_vec_path;
        else
            for (size_t i = i_size_ed_vec_path; i > 0; --i)
                buf_path.push_back(ed_vec_path[i - 1]);
        for (size_t i = 0; i < i_size_ed_vec_path - 1; ++i)
        {
            if (target(buf_path[i], g) != source(buf_path[i + 1], g))
            {
                b_is_a_path_at_all = false;
                b_feasible = false;
                b_correctly_extended = false;
                return;
            }
        }
    }
    b_is_a_path_at_all = true;
    b_feasible = true;
    b_correctly_extended = false;
    Resource_Container current_resource_levels = initial_resource_levels;
    actual_final_resource_levels = current_resource_levels;
    for (size_t i = 0; i < i_size_ed_vec_path; ++i)
    {
        ed_last_extended_arc = buf_path[i];
        b_feasible = ref(g, actual_final_resource_levels,
            current_resource_levels, buf_path[i]);
        current_resource_levels = actual_final_resource_levels;
        if (!b_feasible)
            return;
    }
    if (b_result_must_be_equal_to_desired_final_resource_levels)
        b_correctly_extended
            = actual_final_resource_levels == desired_final_resource_levels
            ? true
            : false;
    else
    {
        if (actual_final_resource_levels < desired_final_resource_levels
            || actual_final_resource_levels == desired_final_resource_levels)
            b_correctly_extended = true;
    }
} // check_path

} // namespace

#endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP

// r_c_shortest_paths.hpp header file // Copyright Michael Drexl 2005, 2006. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://boost.org/LICENSE_1_0.txt) #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP #define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP #include #include #include #include #include #include #include #include #include namespace boost { // r_c_shortest_paths_label struct template < class Graph, class Resource_Container > struct r_c_shortest_paths_label : public boost::enable_shared_from_this< r_c_shortest_paths_label< Graph, Resource_Container > > { r_c_shortest_paths_label(const unsigned long n, const Resource_Container& rc = Resource_Container(), const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > > pl = boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >(), const typename graph_traits< Graph >::edge_descriptor& ed = graph_traits< Graph >::edge_descriptor(), const typename graph_traits< Graph >::vertex_descriptor& vd = graph_traits< Graph >::vertex_descriptor()) : num(n) , cumulated_resource_consumption(rc) , p_pred_label(pl) , pred_edge(ed) , resident_vertex(vd) , b_is_dominated(false) , b_is_processed(false) { } r_c_shortest_paths_label& operator=(const r_c_shortest_paths_label& other) { if (this == &other) return *this; this->~r_c_shortest_paths_label(); new (this) r_c_shortest_paths_label(other); return *this; } const unsigned long num; Resource_Container cumulated_resource_consumption; const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > > p_pred_label; const typename graph_traits< Graph >::edge_descriptor pred_edge; const typename graph_traits< Graph >::vertex_descriptor resident_vertex; bool b_is_dominated; bool b_is_processed; }; // r_c_shortest_paths_label template < class Graph, class Resource_Container > inline bool operator==( const r_c_shortest_paths_label< Graph, Resource_Container >& l1, const r_c_shortest_paths_label< Graph, Resource_Container >& l2) { return l1.cumulated_resource_consumption == l2.cumulated_resource_consumption; } template < class Graph, class Resource_Container > inline bool operator!=( const r_c_shortest_paths_label< Graph, Resource_Container >& l1, const r_c_shortest_paths_label< Graph, Resource_Container >& l2) { return !(l1 == l2); } template < class Graph, class Resource_Container > inline bool operator<( const r_c_shortest_paths_label< Graph, Resource_Container >& l1, const r_c_shortest_paths_label< Graph, Resource_Container >& l2) { return l1.cumulated_resource_consumption < l2.cumulated_resource_consumption; } template < class Graph, class Resource_Container > inline bool operator>( const r_c_shortest_paths_label< Graph, Resource_Container >& l1, const r_c_shortest_paths_label< Graph, Resource_Container >& l2) { return l2.cumulated_resource_consumption < l1.cumulated_resource_consumption; } template < class Graph, class Resource_Container > inline bool operator<=( const r_c_shortest_paths_label< Graph, Resource_Container >& l1, const r_c_shortest_paths_label< Graph, Resource_Container >& l2) { return l1 < l2 || l1 == l2; } template < class Graph, class Resource_Container > inline bool operator>=( const r_c_shortest_paths_label< Graph, Resource_Container >& l1, const r_c_shortest_paths_label< Graph, Resource_Container >& l2) { return l2 < l1 || l1 == l2; } template < typename Graph, typename Resource_Container > inline bool operator<( const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& t, const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& u) { return *t < *u; } template < typename Graph, typename Resource_Container > inline bool operator<=( const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& t, const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& u) { return *t <= *u; } template < typename Graph, typename Resource_Container > inline bool operator>( const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& t, const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& u) { return *t > *u; } template < typename Graph, typename Resource_Container > inline bool operator>=( const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& t, const boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >& u) { return *t >= *u; } namespace detail { // r_c_shortest_paths_dispatch function (body/implementation) template < class Graph, class VertexIndexMap, class EdgeIndexMap, class Resource_Container, class Resource_Extension_Function, class Dominance_Function, class Label_Allocator, class Visitor > void r_c_shortest_paths_dispatch(const Graph& g, const VertexIndexMap& vertex_index_map, const EdgeIndexMap& /*edge_index_map*/, typename graph_traits< Graph >::vertex_descriptor s, typename graph_traits< Graph >::vertex_descriptor t, // each inner vector corresponds to a pareto-optimal path std::vector< std::vector< typename graph_traits< Graph >::edge_descriptor > >& pareto_optimal_solutions, std::vector< Resource_Container >& pareto_optimal_resource_containers, bool b_all_pareto_optimal_solutions, // to initialize the first label/resource container // and to carry the type information const Resource_Container& rc, Resource_Extension_Function& ref, Dominance_Function& dominance, // to specify the memory management strategy for the labels Label_Allocator /*la*/, Visitor vis) { pareto_optimal_resource_containers.clear(); pareto_optimal_solutions.clear(); size_t i_label_num = 0; #if defined(BOOST_NO_CXX11_ALLOCATOR) typedef typename Label_Allocator::template rebind< r_c_shortest_paths_label< Graph, Resource_Container > >::other LAlloc; #else typedef typename std::allocator_traits< Label_Allocator >:: template rebind_alloc< r_c_shortest_paths_label< Graph, Resource_Container > > LAlloc; typedef std::allocator_traits< LAlloc > LTraits; #endif LAlloc l_alloc; typedef boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > > Splabel; std::priority_queue< Splabel, std::vector< Splabel >, std::greater< Splabel > > unprocessed_labels; bool b_feasible = true; Splabel splabel_first_label = boost::allocate_shared< r_c_shortest_paths_label< Graph, Resource_Container > >(l_alloc, i_label_num++, rc, boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > >(), typename graph_traits< Graph >::edge_descriptor(), s); unprocessed_labels.push(splabel_first_label); std::vector< std::list< Splabel > > vec_vertex_labels_data( num_vertices(g)); iterator_property_map< typename std::vector< std::list< Splabel > >::iterator, VertexIndexMap > vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map); vec_vertex_labels[s].push_back(splabel_first_label); typedef std::vector< typename std::list< Splabel >::iterator > vec_last_valid_positions_for_dominance_data_type; vec_last_valid_positions_for_dominance_data_type vec_last_valid_positions_for_dominance_data(num_vertices(g)); iterator_property_map< typename vec_last_valid_positions_for_dominance_data_type::iterator, VertexIndexMap > vec_last_valid_positions_for_dominance( vec_last_valid_positions_for_dominance_data.begin(), vertex_index_map); BGL_FORALL_VERTICES_T(v, g, Graph) { put(vec_last_valid_positions_for_dominance, v, vec_vertex_labels[v].begin()); } std::vector< size_t > vec_last_valid_index_for_dominance_data( num_vertices(g), 0); iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap > vec_last_valid_index_for_dominance( vec_last_valid_index_for_dominance_data.begin(), vertex_index_map); std::vector< bool > b_vec_vertex_already_checked_for_dominance_data( num_vertices(g), false); iterator_property_map< std::vector< bool >::iterator, VertexIndexMap > b_vec_vertex_already_checked_for_dominance( b_vec_vertex_already_checked_for_dominance_data.begin(), vertex_index_map); while (!unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g)) { Splabel cur_label = unprocessed_labels.top(); unprocessed_labels.pop(); vis.on_label_popped(*cur_label, g); // an Splabel object in unprocessed_labels and the respective // Splabel object in the respective list of // vec_vertex_labels share their embedded r_c_shortest_paths_label // object to avoid memory leaks, dominated r_c_shortest_paths_label // objects are marked and deleted when popped from // unprocessed_labels, as they can no longer be deleted at the end // of the function; only the Splabel object in unprocessed_labels // still references the r_c_shortest_paths_label object this is also // for efficiency, because the else branch is executed only if there // is a chance that extending the label leads to new undominated // labels, which in turn is possible only if the label to be // extended is undominated if (!cur_label->b_is_dominated) { typename boost::graph_traits< Graph >::vertex_descriptor i_cur_resident_vertex = cur_label->resident_vertex; std::list< Splabel >& list_labels_cur_vertex = get(vec_vertex_labels, i_cur_resident_vertex); if (list_labels_cur_vertex.size() >= 2 && vec_last_valid_index_for_dominance[i_cur_resident_vertex] < list_labels_cur_vertex.size()) { typename std::list< Splabel >::iterator outer_iter = list_labels_cur_vertex.begin(); bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = false; while (outer_iter != list_labels_cur_vertex.end()) { Splabel cur_outer_splabel = *outer_iter; typename std::list< Splabel >::iterator inner_iter = outer_iter; if (!b_outer_iter_at_or_beyond_last_valid_pos_for_dominance && outer_iter == get(vec_last_valid_positions_for_dominance, i_cur_resident_vertex)) b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true; if (!get(b_vec_vertex_already_checked_for_dominance, i_cur_resident_vertex) || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance) { ++inner_iter; } else { inner_iter = get(vec_last_valid_positions_for_dominance, i_cur_resident_vertex); ++inner_iter; } bool b_outer_iter_erased = false; while (inner_iter != list_labels_cur_vertex.end()) { Splabel cur_inner_splabel = *inner_iter; if (dominance(cur_outer_splabel ->cumulated_resource_consumption, cur_inner_splabel ->cumulated_resource_consumption)) { typename std::list< Splabel >::iterator buf = inner_iter; ++inner_iter; list_labels_cur_vertex.erase(buf); if (cur_inner_splabel->b_is_processed) { cur_inner_splabel.reset(); } else cur_inner_splabel->b_is_dominated = true; continue; } else ++inner_iter; if (dominance(cur_inner_splabel ->cumulated_resource_consumption, cur_outer_splabel ->cumulated_resource_consumption)) { typename std::list< Splabel >::iterator buf = outer_iter; ++outer_iter; list_labels_cur_vertex.erase(buf); b_outer_iter_erased = true; if (cur_outer_splabel->b_is_processed) { cur_outer_splabel.reset(); } else cur_outer_splabel->b_is_dominated = true; break; } } if (!b_outer_iter_erased) ++outer_iter; } if (list_labels_cur_vertex.size() > 1) put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex, (--(list_labels_cur_vertex.end()))); else put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex, list_labels_cur_vertex.begin()); put(b_vec_vertex_already_checked_for_dominance, i_cur_resident_vertex, true); put(vec_last_valid_index_for_dominance, i_cur_resident_vertex, list_labels_cur_vertex.size() - 1); } } if (!b_all_pareto_optimal_solutions && cur_label->resident_vertex == t) { // the devil don't sleep if (cur_label->b_is_dominated) { cur_label.reset(); } while (unprocessed_labels.size()) { Splabel l = unprocessed_labels.top(); unprocessed_labels.pop(); // delete only dominated labels, because nondominated labels // are deleted at the end of the function if (l->b_is_dominated) { l.reset(); } } break; } if (!cur_label->b_is_dominated) { cur_label->b_is_processed = true; vis.on_label_not_dominated(*cur_label, g); typename graph_traits< Graph >::vertex_descriptor cur_vertex = cur_label->resident_vertex; typename graph_traits< Graph >::out_edge_iterator oei, oei_end; for (boost::tie(oei, oei_end) = out_edges(cur_vertex, g); oei != oei_end; ++oei) { b_feasible = true; Splabel new_label = boost::allocate_shared< r_c_shortest_paths_label< Graph, Resource_Container > >( l_alloc, i_label_num++, cur_label->cumulated_resource_consumption, cur_label, *oei, target(*oei, g)); b_feasible = ref(g, new_label->cumulated_resource_consumption, new_label->p_pred_label->cumulated_resource_consumption, new_label->pred_edge); if (!b_feasible) { vis.on_label_not_feasible(*new_label, g); new_label.reset(); } else { vis.on_label_feasible(*new_label, g); vec_vertex_labels[new_label->resident_vertex].push_back( new_label); unprocessed_labels.push(new_label); } } } else { vis.on_label_dominated(*cur_label, g); cur_label.reset(); } } std::list< Splabel > dsplabels = get(vec_vertex_labels, t); typename std::list< Splabel >::const_iterator csi = dsplabels.begin(); typename std::list< Splabel >::const_iterator csi_end = dsplabels.end(); // if d could be reached from o if (!dsplabels.empty()) { for (; csi != csi_end; ++csi) { std::vector< typename graph_traits< Graph >::edge_descriptor > cur_pareto_optimal_path; boost::shared_ptr< r_c_shortest_paths_label< Graph, Resource_Container > > p_cur_label = *csi; pareto_optimal_resource_containers.push_back( p_cur_label->cumulated_resource_consumption); while (p_cur_label->num != 0) { cur_pareto_optimal_path.push_back(p_cur_label->pred_edge); p_cur_label = p_cur_label->p_pred_label; // assertion b_is_valid beyond this point is not correct if // the domination function requires resource levels to be // strictly greater than existing values // // Example // Customers // id min_arrival max_departure // 2 0 974 // 3 0 972 // 4 0 964 // 5 678 801 // // Path A: 2-3-4-5 (times: 0-16-49-84-678) // Path B: 3-2-4-5 (times: 0-18-51-62-678) // The partial path 3-2-4 dominates the other partial path // 2-3-4, though the path 3-2-4-5 does not strictly dominate // the path 2-3-4-5 } pareto_optimal_solutions.push_back(cur_pareto_optimal_path); if (!b_all_pareto_optimal_solutions) break; } } BGL_FORALL_VERTICES_T(i, g, Graph) { std::list< Splabel >& list_labels_cur_vertex = vec_vertex_labels[i]; typename std::list< Splabel >::iterator si = list_labels_cur_vertex.begin(); const typename std::list< Splabel >::iterator si_end = list_labels_cur_vertex.end(); for (; si != si_end; ++si) { (*si).reset(); } } } // r_c_shortest_paths_dispatch } // detail // default_r_c_shortest_paths_visitor struct struct default_r_c_shortest_paths_visitor { template < class Label, class Graph > void on_label_popped(const Label&, const Graph&) { } template < class Label, class Graph > void on_label_feasible(const Label&, const Graph&) { } template < class Label, class Graph > void on_label_not_feasible(const Label&, const Graph&) { } template < class Label, class Graph > void on_label_dominated(const Label&, const Graph&) { } template < class Label, class Graph > void on_label_not_dominated(const Label&, const Graph&) { } template < class Queue, class Graph > bool on_enter_loop(const Queue& queue, const Graph& graph) { return true; } }; // default_r_c_shortest_paths_visitor // default_r_c_shortest_paths_allocator typedef std::allocator< int > default_r_c_shortest_paths_allocator; // default_r_c_shortest_paths_allocator // r_c_shortest_paths functions (handle/interface) // first overload: // - return all pareto-optimal solutions // - specify Label_Allocator and Visitor arguments template < class Graph, class VertexIndexMap, class EdgeIndexMap, class Resource_Container, class Resource_Extension_Function, class Dominance_Function, class Label_Allocator, class Visitor > void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map, const EdgeIndexMap& edge_index_map, typename graph_traits< Graph >::vertex_descriptor s, typename graph_traits< Graph >::vertex_descriptor t, // each inner vector corresponds to a pareto-optimal path std::vector< std::vector< typename graph_traits< Graph >::edge_descriptor > >& pareto_optimal_solutions, std::vector< Resource_Container >& pareto_optimal_resource_containers, // to initialize the first label/resource container // and to carry the type information const Resource_Container& rc, const Resource_Extension_Function& ref, const Dominance_Function& dominance, // to specify the memory management strategy for the labels Label_Allocator la, Visitor vis) { r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t, pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc, ref, dominance, la, vis); } // second overload: // - return only one pareto-optimal solution // - specify Label_Allocator and Visitor arguments template < class Graph, class VertexIndexMap, class EdgeIndexMap, class Resource_Container, class Resource_Extension_Function, class Dominance_Function, class Label_Allocator, class Visitor > void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map, const EdgeIndexMap& edge_index_map, typename graph_traits< Graph >::vertex_descriptor s, typename graph_traits< Graph >::vertex_descriptor t, std::vector< typename graph_traits< Graph >::edge_descriptor >& pareto_optimal_solution, Resource_Container& pareto_optimal_resource_container, // to initialize the first label/resource container // and to carry the type information const Resource_Container& rc, const Resource_Extension_Function& ref, const Dominance_Function& dominance, // to specify the memory management strategy for the labels Label_Allocator la, Visitor vis) { // each inner vector corresponds to a pareto-optimal path std::vector< std::vector< typename graph_traits< Graph >::edge_descriptor > > pareto_optimal_solutions; std::vector< Resource_Container > pareto_optimal_resource_containers; r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t, pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc, ref, dominance, la, vis); if (!pareto_optimal_solutions.empty()) { pareto_optimal_solution = pareto_optimal_solutions[0]; pareto_optimal_resource_container = pareto_optimal_resource_containers[0]; } } // third overload: // - return all pareto-optimal solutions // - use default Label_Allocator and Visitor template < class Graph, class VertexIndexMap, class EdgeIndexMap, class Resource_Container, class Resource_Extension_Function, class Dominance_Function > void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map, const EdgeIndexMap& edge_index_map, typename graph_traits< Graph >::vertex_descriptor s, typename graph_traits< Graph >::vertex_descriptor t, // each inner vector corresponds to a pareto-optimal path std::vector< std::vector< typename graph_traits< Graph >::edge_descriptor > >& pareto_optimal_solutions, std::vector< Resource_Container >& pareto_optimal_resource_containers, // to initialize the first label/resource container // and to carry the type information const Resource_Container& rc, const Resource_Extension_Function& ref, const Dominance_Function& dominance) { r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t, pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc, ref, dominance, default_r_c_shortest_paths_allocator(), default_r_c_shortest_paths_visitor()); } // fourth overload: // - return only one pareto-optimal solution // - use default Label_Allocator and Visitor template < class Graph, class VertexIndexMap, class EdgeIndexMap, class Resource_Container, class Resource_Extension_Function, class Dominance_Function > void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map, const EdgeIndexMap& edge_index_map, typename graph_traits< Graph >::vertex_descriptor s, typename graph_traits< Graph >::vertex_descriptor t, std::vector< typename graph_traits< Graph >::edge_descriptor >& pareto_optimal_solution, Resource_Container& pareto_optimal_resource_container, // to initialize the first label/resource container // and to carry the type information const Resource_Container& rc, const Resource_Extension_Function& ref, const Dominance_Function& dominance) { // each inner vector corresponds to a pareto-optimal path std::vector< std::vector< typename graph_traits< Graph >::edge_descriptor > > pareto_optimal_solutions; std::vector< Resource_Container > pareto_optimal_resource_containers; r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t, pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc, ref, dominance, default_r_c_shortest_paths_allocator(), default_r_c_shortest_paths_visitor()); if (!pareto_optimal_solutions.empty()) { pareto_optimal_solution = pareto_optimal_solutions[0]; pareto_optimal_resource_container = pareto_optimal_resource_containers[0]; } } // r_c_shortest_paths // check_r_c_path function template < class Graph, class Resource_Container, class Resource_Extension_Function > void check_r_c_path(const Graph& g, const std::vector< typename graph_traits< Graph >::edge_descriptor >& ed_vec_path, const Resource_Container& initial_resource_levels, // if true, computed accumulated final resource levels must // be equal to desired_final_resource_levels // if false, computed accumulated final resource levels must // be less than or equal to desired_final_resource_levels bool b_result_must_be_equal_to_desired_final_resource_levels, const Resource_Container& desired_final_resource_levels, Resource_Container& actual_final_resource_levels, const Resource_Extension_Function& ref, bool& b_is_a_path_at_all, bool& b_feasible, bool& b_correctly_extended, typename graph_traits< Graph >::edge_descriptor& ed_last_extended_arc) { size_t i_size_ed_vec_path = ed_vec_path.size(); std::vector< typename graph_traits< Graph >::edge_descriptor > buf_path; if (i_size_ed_vec_path == 0) b_feasible = true; else { if (i_size_ed_vec_path == 1 || target(ed_vec_path[0], g) == source(ed_vec_path[1], g)) buf_path = ed_vec_path; else for (size_t i = i_size_ed_vec_path; i > 0; --i) buf_path.push_back(ed_vec_path[i - 1]); for (size_t i = 0; i < i_size_ed_vec_path - 1; ++i) { if (target(buf_path[i], g) != source(buf_path[i + 1], g)) { b_is_a_path_at_all = false; b_feasible = false; b_correctly_extended = false; return; } } } b_is_a_path_at_all = true; b_feasible = true; b_correctly_extended = false; Resource_Container current_resource_levels = initial_resource_levels; actual_final_resource_levels = current_resource_levels; for (size_t i = 0; i < i_size_ed_vec_path; ++i) { ed_last_extended_arc = buf_path[i]; b_feasible = ref(g, actual_final_resource_levels, current_resource_levels, buf_path[i]); current_resource_levels = actual_final_resource_levels; if (!b_feasible) return; } if (b_result_must_be_equal_to_desired_final_resource_levels) b_correctly_extended = actual_final_resource_levels == desired_final_resource_levels ? true : false; else { if (actual_final_resource_levels < desired_final_resource_levels || actual_final_resource_levels == desired_final_resource_levels) b_correctly_extended = true; } } // check_path } // namespace #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP