//==========================================================================
//
//   maxflow_pp.h
//
//==========================================================================
// $Id: maxflow_pp.h,v 1.4 2000/01/05 16:32:37 raitner 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

/**
 * @short Maximum flow algorithm (Malhotra, Kumar, Maheshwari).
 */
class GTL_EXTERN maxflow_pp : public algorithm
{
public:
    /**
     * Default constructor. Enables only the calculation of
     * maximum flow.
     * 
     * @see algorithm#algorithm
     */
    maxflow_pp();

    /**
     * Destructor.
     * 
     * @see algorithm#~algorithm
     */
    virtual ~maxflow_pp();

    /**
     * Sets capacity of every edge for maximum flow calculation
     * where artificial start-node and end_node will be computed
     * automatically.
     *
     * @param <code>edge_capacity</code> capacity of every edge.
     */
    void set_vars(const edge_map<double>& edge_capacity);

    /**
     * Sets capacity of every edge for maximum flow calculation
     *
     * @param <code>edge_capacity</code> capacity of every edge.
     * @param <code>net_source</code> start-node.
     * @param <code>net_target</code> end-node.
     */
    void set_vars(
	const edge_map<double>& edge_capacity, 
	const node& net_source, const node& net_target);

    /**
     * Checks whether following preconditions are satisfied:
     * <ul>
     * <li> @ref maxflow_pp#set_vars has been executed before.
     * <li> only edge_capacities >= 0 are applied.
     * <li> <code>G</code> is directed.
     * <li> <code>G</code> is connected.
     * <li> <code>G</code> has at least one edge and two nodes.
     * <li> if not applied, start-nodes and end-nodes exists.
     * <li> if applied, start-node is not the same node as end-node.
     * </ul>
     * 
     * @param <code>G</code> graph
     * @return <code>algorithm::GTL_OK</code> on success 
     * <code>algorithm::GTL_ERROR</code>
     * otherwise
     * @see algorithm#check
     */
    virtual int check(graph& G);

    /**
     * Computes maximum flow of graph <code>G</code>.
     * 
     * @param <code>G</code> graph
     * @return <code>algorithm::GTL_OK</code> on success 
     * <code>algorithm::GTL_ERROR</code>
     * otherwise 
     * @see algorithm#run
     */
    int run(graph& G);

    /**
     * Returns the maximum flow of an edge.
     *
     * @param <code>e</code> edge of a graph G
     * @return maximum flow value.
     */
    double get_max_flow(const edge& e) const;

    /**
     * Returns the maximum flow of the whole graph G.
     *
     * @return maximum flow value.
     */
    double get_max_flow() const;

    /**
     * Returns the remaining free capacity of an edge.
     *
     * @param <code>e</code> edge of a graph G
     * @return remaining capacity.
     */
    double get_rem_cap(const edge& e) const;

    /**
     * Resets maximum flow algorithm, i.e. prepares the
     * algorithm to be applied to another graph. 
     * @see algorithm#reset
     */
    virtual void reset();
protected:
    /**
     * @internal
     */
    enum {TARGET_FROM_SOURCE_REACHABLE = 2, TARGET_FROM_SOURCE_NOT_REACHABLE = 3};

    /**
     * @internal
     */
    bool artif_source_target;

    /**
     * @internal
     */
    bool set_vars_executed;

    /**
     * @internal
     */
    double max_graph_flow;

    /**
     * @internal
     */
    node net_source;

    /**
     * @internal
     */
    node net_target;

    /**
     * @internal edges to remove from G after run
     */
    list<edge> edges_not_org;

    /**
     * @internal original edge or inserted back edge
     */
    edge_map<bool> edge_org;

    /**
     * @internal
     */
    edge_map<bool> back_edge_exists;

    /**
     * @internal every edge knows its back edge
     */
    edge_map<edge> back_edge;

    /**
     * @internal
     */
    edge_map<double> edge_capacity;

    /**
     * @internal
     */
    edge_map<double> edge_max_flow;

    /**
     * @internal
     */
    edge_map<double> flow_update;

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

    /**
     * @internal
     */
    void prepare_run(const graph& G);

    /**
     * @internal
     */
    int leveling(graph& G);

    /**
     * @internal
     */
    void hide_unreachable_nodes(graph& G);

    /**
     * @internal
     */
    void store_temp_unvisible_edges(const node& cur_node);

    /**
     * @internal
     */
    void min_throughput_node(const graph& G, node& min_tp_node, double& min_value);

    /**
     * @internal
     */
    double comp_min_throughput(const node cur_node) const;

    /**
     * @internal every node knows its predecessor then
     */
    void get_sp_ahead(const graph& G, const node& start_node, 
	node_map<edge>& last_edge);

    /**
     * @internal every node knows its successor then
     */
    void get_sp_backwards(const graph& G, const node& start_node, 
	node_map<edge>& prev_edge);

    /**
     * @internal
     */
    void push(graph& G, const node& start_node, const double flow_value);

    /**
     * @internal
     */
    void pull(graph& G, const node& start_node, const double flow_value);

    /**
     * @internal
     */
    void comp_rem_net(graph& G);

    /**
     * @internal
     */
    void single_edge_update(graph& G, edge cur_edge);

    /**
     * @internal
     */
    double extra_charge_ahead(const node& start_node, const 
	node_map<edge>& last_edge) const;

    /**
     * @internal
     */
    double extra_charge_backwards(const node& start_node, 
	const node_map<edge>& prev_edge) const;

    /**
     * @internal
     */
    void create_back_edge(graph& G, const edge& org_edge);

    /**
     * @internal
     */
    void comp_max_flow(const graph& G);

    /**
     * @internal
     */
    void restore_graph(graph& G);
private:
};

__GTL_END_NAMESPACE

#endif // GTL_MAXFLOW_PP_H

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

Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
Kdoc