RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_EDGE_SET_H

#define LEMON_EDGE_SET_H

#include <lemon/core.h>

#include <lemon/bits/edge_set_extender.h>

/// \ingroup graphs

/// \file

/// \brief ArcSet and EdgeSet classes.

///

/// Graphs which use another graph's node-set as own.

namespace lemon {

  template <typename GR>

  class ListArcSetBase {

  public:

    typedef typename GR::Node Node;

    typedef typename GR::NodeIt NodeIt;

  protected:

    struct NodeT {

      int first_out, first_in;

      NodeT() : first_out(-1), first_in(-1) {}

    };

    typedef typename ItemSetTraits<GR, Node>::

    template Map<NodeT>::Type NodesImplBase;

    NodesImplBase* _nodes;

    struct ArcT {

      Node source, target;

      int next_out, next_in;

      int prev_out, prev_in;

      ArcT() : prev_out(-1), prev_in(-1) {}

    };

    std::vector<ArcT> arcs;

    int first_arc;

    int first_free_arc;

    const GR* _graph;

    void initalize(const GR& graph, NodesImplBase& nodes) {

      _graph = &graph;

      _nodes = &nodes;

    }

  public:

    class Arc {

      friend class ListArcSetBase<GR>;

    protected:

      Arc(int _id) : id(_id) {}

      int id;

    public:

      Arc() {}

      Arc(Invalid) : id(-1) {}

      bool operator==(const Arc& arc) const { return id == arc.id; }

      bool operator!=(const Arc& arc) const { return id != arc.id; }

      bool operator<(const Arc& arc) const { return id < arc.id; }

    };

    ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}

    Arc addArc(const Node& u, const Node& v) {

      int n;

      if (first_free_arc == -1) {

        n = arcs.size();

        arcs.push_back(ArcT());

      } else {

        n = first_free_arc;

        first_free_arc = arcs[first_free_arc].next_in;

      }

      arcs[n].next_in = (*_nodes)[v].first_in;

      if ((*_nodes)[v].first_in != -1) {

        arcs[(*_nodes)[v].first_in].prev_in = n;

      }

      (*_nodes)[v].first_in = n;

      arcs[n].next_out = (*_nodes)[u].first_out;

      if ((*_nodes)[u].first_out != -1) {

        arcs[(*_nodes)[u].first_out].prev_out = n;

      }

      (*_nodes)[u].first_out = n;

      arcs[n].source = u;

      arcs[n].target = v;

      return Arc(n);

    }

    void erase(const Arc& arc) {

      int n = arc.id;

      if (arcs[n].prev_in != -1) {

        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;

      } else {

        (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;

      }

      if (arcs[n].next_in != -1) {

        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;

      }

      if (arcs[n].prev_out != -1) {

        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;

      } else {

        (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;

      }

      if (arcs[n].next_out != -1) {

        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;

      }

    }

    void clear() {

      Node node;

      for (first(node); node != INVALID; next(node)) {

        (*_nodes)[node].first_in = -1;

        (*_nodes)[node].first_out = -1;

      }

      arcs.clear();

      first_arc = -1;

      first_free_arc = -1;

    }

    void first(Node& node) const {

      _graph->first(node);

    }

    void next(Node& node) const {

      _graph->next(node);

    }

    void first(Arc& arc) const {

      Node node;

      first(node);

      while (node != INVALID && (*_nodes)[node].first_in == -1) {

        next(node);

      }

      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;

    }

    void next(Arc& arc) const {

      if (arcs[arc.id].next_in != -1) {

        arc.id = arcs[arc.id].next_in;

      } else {

        Node node = arcs[arc.id].target;

        next(node);

        while (node != INVALID && (*_nodes)[node].first_in == -1) {

          next(node);

        }

        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;

      }

    }

    void firstOut(Arc& arc, const Node& node) const {

      arc.id = (*_nodes)[node].first_out;

    }

    void nextOut(Arc& arc) const {

      arc.id = arcs[arc.id].next_out;

    }

    void firstIn(Arc& arc, const Node& node) const {

    /// \brief Constructor of the ArcSet.

    ///

    /// Constructor of the ArcSet.

    ListArcSet(const GR& graph) : _nodes(graph, *this) {

      Parent::initalize(graph, _nodes);

    }

    /// \brief Add a new arc to the digraph.

    ///

    /// Add a new arc to the digraph with source node \c s

    /// and target node \c t.

    /// \return The new arc.

    Arc addArc(const Node& s, const Node& t) {

      return Parent::addArc(s, t);

    }

    /// \brief Erase an arc from the digraph.

    ///

    /// Erase an arc \c a from the digraph.

    void erase(const Arc& a) {

      return Parent::erase(a);

    }

  };

  template <typename GR>

  class ListEdgeSetBase {

  public:

    typedef typename GR::Node Node;

    typedef typename GR::NodeIt NodeIt;

  protected:

    struct NodeT {

      int first_out;

      NodeT() : first_out(-1) {}

    };

    typedef typename ItemSetTraits<GR, Node>::

    template Map<NodeT>::Type NodesImplBase;

    NodesImplBase* _nodes;

    struct ArcT {

      Node target;

      int prev_out, next_out;

      ArcT() : prev_out(-1), next_out(-1) {}

    };

    std::vector<ArcT> arcs;

    int first_arc;

    int first_free_arc;

    const GR* _graph;

    void initalize(const GR& graph, NodesImplBase& nodes) {

      _graph = &graph;

      _nodes = &nodes;

    }

  public:

    class Edge {

      friend class ListEdgeSetBase;

    protected:

      int id;

      explicit Edge(int _id) { id = _id;}

    public:

      Edge() {}

      Edge (Invalid) { id = -1; }

      bool operator==(const Edge& arc) const {return id == arc.id;}

      bool operator!=(const Edge& arc) const {return id != arc.id;}

      bool operator<(const Edge& arc) const {return id < arc.id;}

    };

    class Arc {

      friend class ListEdgeSetBase;

    protected:

      Arc(int _id) : id(_id) {}

      int id;

    public:

      operator Edge() const { return edgeFromId(id / 2); }

      Arc() {}

      Arc(Invalid) : id(-1) {}

      bool operator==(const Arc& arc) const { return id == arc.id; }

      bool operator!=(const Arc& arc) const { return id != arc.id; }

      bool operator<(const Arc& arc) const { return id < arc.id; }

    };

    ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}

    Edge addEdge(const Node& u, const Node& v) {

      int n;

      if (first_free_arc == -1) {

        n = arcs.size();

        arcs.push_back(ArcT());

        arcs.push_back(ArcT());

      } else {

        n = first_free_arc;

        first_free_arc = arcs[n].next_out;

      }

      arcs[n].target = u;

      arcs[n | 1].target = v;

      arcs[n].next_out = (*_nodes)[v].first_out;

      if ((*_nodes)[v].first_out != -1) {

        arcs[(*_nodes)[v].first_out].prev_out = n;

      }

      (*_nodes)[v].first_out = n;

      arcs[n].prev_out = -1;

      if ((*_nodes)[u].first_out != -1) {

        arcs[(*_nodes)[u].first_out].prev_out = (n | 1);

      }

      arcs[n | 1].next_out = (*_nodes)[u].first_out;

      (*_nodes)[u].first_out = (n | 1);

      arcs[n | 1].prev_out = -1;

      return Edge(n / 2);

    }

    void erase(const Edge& arc) {

      int n = arc.id * 2;

      if (arcs[n].next_out != -1) {

        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;

      }

      if (arcs[n].prev_out != -1) {

        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;

      } else {

        (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;

      }

      if (arcs[n | 1].next_out != -1) {

        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;

      }

      if (arcs[n | 1].prev_out != -1) {

        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;

      } else {

        (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;

      }

      arcs[n].next_out = first_free_arc;

      first_free_arc = n;

    }

    void clear() {

      Node node;

      for (first(node); node != INVALID; next(node)) {

        (*_nodes)[node].first_out = -1;

      }

      arcs.clear();

      first_arc = -1;

      first_free_arc = -1;

    }

    void first(Node& node) const {

      _graph->first(node);

    }

    void next(Node& node) const {

      _graph->next(node);

    }

    void first(Arc& arc) const {

      Node node;

      first(node);

      while (node != INVALID && (*_nodes)[node].first_out == -1) {

        next(node);

      }

      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;

    }

    void next(Arc& arc) const {

      if (arcs[arc.id].next_out != -1) {

        arc.id = arcs[arc.id].next_out;

      } else {

        Node node = arcs[arc.id ^ 1].target;

        next(node);

        while(node != INVALID && (*_nodes)[node].first_out == -1) {

          next(node);

        }

      }

      virtual void erase(const std::vector<Node>& nodes) {

        for (int i = 0; i < int(nodes.size()); ++i) {

          _arcset.eraseNode(nodes[i]);

        }

        Parent::erase(nodes);

      }

      virtual void clear() {

        _arcset.clearNodes();

        Parent::clear();

      }

    private:

      ListEdgeSet& _arcset;

    };

    NodesImpl _nodes;

  public:

    /// \brief Constructor of the EdgeSet.

    ///

    /// Constructor of the EdgeSet.

    ListEdgeSet(const GR& graph) : _nodes(graph, *this) {

      Parent::initalize(graph, _nodes);

    }

    /// \brief Add a new edge to the graph.

    ///

    /// Add a new edge to the graph with node \c u

    /// and node \c v endpoints.

    /// \return The new edge.

    Edge addEdge(const Node& u, const Node& v) {

      return Parent::addEdge(u, v);

    }

    /// \brief Erase an edge from the graph.

    ///

    /// Erase the edge \c e from the graph.

    void erase(const Edge& e) {

      return Parent::erase(e);

    }

  };

  template <typename GR>

  class SmartArcSetBase {

  public:

    typedef typename GR::Node Node;

    typedef typename GR::NodeIt NodeIt;

  protected:

    struct NodeT {

      int first_out, first_in;

      NodeT() : first_out(-1), first_in(-1) {}

    };

    typedef typename ItemSetTraits<GR, Node>::

    template Map<NodeT>::Type NodesImplBase;

    NodesImplBase* _nodes;

    struct ArcT {

      Node source, target;

      int next_out, next_in;

      ArcT() {}

    };

    std::vector<ArcT> arcs;

    const GR* _graph;

    void initalize(const GR& graph, NodesImplBase& nodes) {

      _graph = &graph;

      _nodes = &nodes;

    }

  public:

    class Arc {

      friend class SmartArcSetBase<GR>;

    protected:

      Arc(int _id) : id(_id) {}

      int id;

    public:

      Arc() {}

      Arc(Invalid) : id(-1) {}

      bool operator==(const Arc& arc) const { return id == arc.id; }

      bool operator!=(const Arc& arc) const { return id != arc.id; }

      bool operator<(const Arc& arc) const { return id < arc.id; }

    };

    SmartArcSetBase() {}

    Arc addArc(const Node& u, const Node& v) {

      int n = arcs.size();

      arcs.push_back(ArcT());

      arcs[n].next_in = (*_nodes)[v].first_in;

      (*_nodes)[v].first_in = n;

      arcs[n].next_out = (*_nodes)[u].first_out;

      (*_nodes)[u].first_out = n;

      arcs[n].source = u;

      arcs[n].target = v;

      return Arc(n);

    }

    void clear() {

      Node node;

      for (first(node); node != INVALID; next(node)) {

        (*_nodes)[node].first_in = -1;

        (*_nodes)[node].first_out = -1;

      }

      arcs.clear();

    }

    void first(Node& node) const {

      _graph->first(node);

    }

    void next(Node& node) const {

      _graph->next(node);

    }

    void first(Arc& arc) const {

      arc.id = arcs.size() - 1;

    }

    void next(Arc& arc) const {

      --arc.id;

    }

    void firstOut(Arc& arc, const Node& node) const {

      arc.id = (*_nodes)[node].first_out;

    }

    void nextOut(Arc& arc) const {

      arc.id = arcs[arc.id].next_out;

    }

    void firstIn(Arc& arc, const Node& node) const {

      arc.id = (*_nodes)[node].first_in;

    }

    void nextIn(Arc& arc) const {

      arc.id = arcs[arc.id].next_in;

    }

    int id(const Node& node) const { return _graph->id(node); }

    int id(const Arc& arc) const { return arc.id; }

    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }

    Arc arcFromId(int ix) const { return Arc(ix); }

    int maxNodeId() const { return _graph->maxNodeId(); };

    int maxArcId() const { return arcs.size() - 1; }

    Node source(const Arc& arc) const { return arcs[arc.id].source;}

    Node target(const Arc& arc) const { return arcs[arc.id].target;}

    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const {

      return _graph->notifier(Node());

    }

    template <typename V>

    class NodeMap : public GR::template NodeMap<V> {

      typedef typename GR::template NodeMap<V> Parent;

    public:

      explicit NodeMap(const SmartArcSetBase<GR>& arcset)

        : Parent(*arcset._graph) { }

      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)

        : Parent(*arcset._graph, value) { }

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

    /// \brief Constructor of the ArcSet.

    ///

    /// Constructor of the ArcSet.

    SmartArcSet(const GR& graph) : _nodes(graph, *this) {

      Parent::initalize(graph, _nodes);

    }

    /// \brief Add a new arc to the digraph.

    ///

    /// Add a new arc to the digraph with source node \c s

    /// and target node \c t.

    /// \return The new arc.

    Arc addArc(const Node& s, const Node& t) {

      return Parent::addArc(s, t);

    }

    /// \brief Validity check

    ///

    /// This functions gives back false if the ArcSet is

    /// invalidated. It occurs when a node in the underlying graph is

    /// erased and it is not isolated in the ArcSet.

    bool valid() const {

      return _nodes.attached();

    }

  };

  template <typename GR>

  class SmartEdgeSetBase {

  public:

    typedef typename GR::Node Node;

    typedef typename GR::NodeIt NodeIt;

  protected:

    struct NodeT {

      int first_out;

      NodeT() : first_out(-1) {}

    };

    typedef typename ItemSetTraits<GR, Node>::

    template Map<NodeT>::Type NodesImplBase;

    NodesImplBase* _nodes;

    struct ArcT {

      Node target;

      int next_out;

      ArcT() {}

    };

    std::vector<ArcT> arcs;

    const GR* _graph;

    void initalize(const GR& graph, NodesImplBase& nodes) {

      _graph = &graph;

      _nodes = &nodes;

    }

  public:

    class Edge {

      friend class SmartEdgeSetBase;

    protected:

      int id;

      explicit Edge(int _id) { id = _id;}

    public:

      Edge() {}

      Edge (Invalid) { id = -1; }

      bool operator==(const Edge& arc) const {return id == arc.id;}

      bool operator!=(const Edge& arc) const {return id != arc.id;}

      bool operator<(const Edge& arc) const {return id < arc.id;}

    };

    class Arc {

      friend class SmartEdgeSetBase;

    protected:

      Arc(int _id) : id(_id) {}

      int id;

    public:

      operator Edge() const { return edgeFromId(id / 2); }

      Arc() {}

      Arc(Invalid) : id(-1) {}

      bool operator==(const Arc& arc) const { return id == arc.id; }

      bool operator!=(const Arc& arc) const { return id != arc.id; }

      bool operator<(const Arc& arc) const { return id < arc.id; }

    };

    SmartEdgeSetBase() {}

    Edge addEdge(const Node& u, const Node& v) {

      int n = arcs.size();

      arcs.push_back(ArcT());

      arcs.push_back(ArcT());

      arcs[n].target = u;

      arcs[n | 1].target = v;

      arcs[n].next_out = (*_nodes)[v].first_out;

      (*_nodes)[v].first_out = n;

      arcs[n | 1].next_out = (*_nodes)[u].first_out;

      (*_nodes)[u].first_out = (n | 1);

      return Edge(n / 2);

    }

    void clear() {

      Node node;

      for (first(node); node != INVALID; next(node)) {

        (*_nodes)[node].first_out = -1;

      }

      arcs.clear();

    }

    void first(Node& node) const {

      _graph->first(node);

    }

    void next(Node& node) const {

      _graph->next(node);

    }

    void first(Arc& arc) const {

      arc.id = arcs.size() - 1;

    }

    void next(Arc& arc) const {

      --arc.id;

    }

    void first(Edge& arc) const {

      arc.id = arcs.size() / 2 - 1;

    }

    void next(Edge& arc) const {

      --arc.id;

    }

    void firstOut(Arc& arc, const Node& node) const {

      arc.id = (*_nodes)[node].first_out;

    }

    void nextOut(Arc& arc) const {

      arc.id = arcs[arc.id].next_out;

    }

    void firstIn(Arc& arc, const Node& node) const {

      arc.id = (((*_nodes)[node].first_out) ^ 1);

      if (arc.id == -2) arc.id = -1;

    }

    void nextIn(Arc& arc) const {

      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);

      if (arc.id == -2) arc.id = -1;

    }

    void firstInc(Edge &arc, bool& dir, const Node& node) const {

      int de = (*_nodes)[node].first_out;

      if (de != -1 ) {

        arc.id = de / 2;

        dir = ((de & 1) == 1);

      } else {

        arc.id = -1;

        dir = true;

      }

    }

    void nextInc(Edge &arc, bool& dir) const {

      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);

      if (de != -1 ) {

        arc.id = de / 2;

        dir = ((de & 1) == 1);

      } else {

        arc.id = -1;

        dir = true;

      }

    }

    static bool direction(Arc arc) {

      return (arc.id & 1) == 1;

    }

    static Arc direct(Edge edge, bool dir) {

      return Arc(edge.id * 2 + (dir ? 1 : 0));

    }