maxflow_pp.h

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file maxflow_pp.h

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   maxflow_pp.h
//
//==========================================================================
// $Id: maxflow_pp.h,v 1.5 2003/01/31 08:15:05 chris Exp $

#ifndef GTL_MAXFLOW_PP_H
#define GTL_MAXFLOW_PP_H

#include <GTL/GTL.h>
#include <GTL/graph.h>
#include <GTL/node_map.h>
#include <GTL/edge_map.h>
#include <GTL/algorithm.h>

#include <queue>

__GTL_BEGIN_NAMESPACE

class GTL_EXTERN maxflow_pp : public algorithm
{
public:
    maxflow_pp();

    virtual ~maxflow_pp();

    void set_vars(const edge_map<double>& edge_capacity);

    void set_vars(
        const edge_map<double>& edge_capacity, 
        const node& net_source, const node& net_target);

    virtual int check(graph& G);

    int run(graph& G);

    double get_max_flow(const edge& e) const;

    double get_max_flow() const;

    double get_rem_cap(const edge& e) const;

    virtual void reset();
protected:
    enum {TARGET_FROM_SOURCE_REACHABLE = 2, TARGET_FROM_SOURCE_NOT_REACHABLE = 3};

    bool artif_source_target;

    bool set_vars_executed;

    double max_graph_flow;

    node net_source;

    node net_target;

    list<edge> edges_not_org;

    edge_map<bool> edge_org;

    edge_map<bool> back_edge_exists;

    edge_map<edge> back_edge;

    edge_map<double> edge_capacity;

    edge_map<double> edge_max_flow;

    edge_map<double> flow_update;

    list<edge> full_edges;
                
    list<node> temp_unvisible_nodes;
                
    list<edge> temp_unvisible_edges;
                
    void create_artif_source_target(graph& G);

    void prepare_run(const graph& G);

    int leveling(graph& G);

    void hide_unreachable_nodes(graph& G);

    void store_temp_unvisible_edges(const node& cur_node);

    void min_throughput_node(const graph& G, node& min_tp_node, double& min_value);

    double comp_min_throughput(const node cur_node) const;

    void get_sp_ahead(const graph& G, const node& start_node, 
        node_map<edge>& last_edge);

    void get_sp_backwards(const graph& G, const node& start_node, 
        node_map<edge>& prev_edge);

    void push(graph& G, const node& start_node, const double flow_value);

    void pull(graph& G, const node& start_node, const double flow_value);

    void comp_rem_net(graph& G);

    void single_edge_update(graph& G, edge cur_edge);

    double extra_charge_ahead(const node& start_node, const 
        node_map<edge>& last_edge) const;

    double extra_charge_backwards(const node& start_node, 
        const node_map<edge>& prev_edge) const;

    void create_back_edge(graph& G, const edge& org_edge);

    void comp_max_flow(const graph& G);

    void restore_graph(graph& G);
private:
};

__GTL_END_NAMESPACE

#endif // GTL_MAXFLOW_PP_H

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------