source: lemon-0.x/lemon/edge_set.h @ 1962:c1c3a0fae8a1

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * 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/bits/erasable_graph_extender.h>
#include <lemon/bits/clearable_graph_extender.h>
#include <lemon/bits/extendable_graph_extender.h>
#include <lemon/bits/iterable_graph_extender.h>
#include <lemon/bits/alteration_notifier.h>
#include <lemon/bits/default_map.h>
#include <lemon/bits/graph_extender.h>

/// \ingroup graphs
/// \file
/// \brief EdgeSet classes.
///
/// Graphs which use another graph's node-set as own. 

namespace lemon {

  template <typename _Graph>
  class ListEdgeSetBase {
  public:

    typedef _Graph Graph;
    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;

  protected:

    struct NodeT {
      int first_out, first_in;
      NodeT() : first_out(-1), first_in(-1) {}
    };

    typedef typename Graph::template NodeMap<NodeT> NodesImplBase;

    NodesImplBase* nodes;

    struct EdgeT {
      Node source, target;
      int next_out, next_in;
      int prev_out, prev_in;
      EdgeT() : prev_out(-1), prev_in(-1) {}
    };

    std::vector<EdgeT> edges;

    int first_edge;
    int first_free_edge;

    const Graph* graph;

    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
      graph = &_graph;
      nodes = &_nodes;
    }
    
  public:

    class Edge {
      friend class ListEdgeSetBase<Graph>;
    protected:
      Edge(int _id) : id(_id) {}
      int id;
    public:
      Edge() {}
      Edge(Invalid) : id(-1) {}
      bool operator==(const Edge& edge) const { return id == edge.id; }
      bool operator!=(const Edge& edge) const { return id != edge.id; }
      bool operator<(const Edge& edge) const { return id < edge.id; }
    };

    ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} 

    Edge addEdge(const Node& source, const Node& target) {
      int n;
      if (first_free_edge == -1) {
        n = edges.size();
        edges.push_back(EdgeT());
      } else {
        n = first_free_edge;
        first_free_edge = edges[first_free_edge].next_in;
      }
      edges[n].next_in = (*nodes)[target].first_in;
      if ((*nodes)[target].first_in != -1) {
        edges[(*nodes)[target].first_in].prev_in = n;
      }
      (*nodes)[target].first_in = n;
      edges[n].next_out = (*nodes)[source].first_out;
      if ((*nodes)[source].first_out != -1) {
        edges[(*nodes)[source].first_out].prev_out = n;
      }
      (*nodes)[source].first_out = n;
      edges[n].source = source;
      edges[n].target = target;
      return Edge(n);
    }

    void erase(const Edge& edge) {
      int n = edge.id;
      if (edges[n].prev_in != -1) {
        edges[edges[n].prev_in].next_in = edges[n].next_in;
      } else {
        (*nodes)[edges[n].target].first_in = edges[n].next_in;
      }
      if (edges[n].next_in != -1) {
        edges[edges[n].next_in].prev_in = edges[n].prev_in;
      }

      if (edges[n].prev_out != -1) {
        edges[edges[n].prev_out].next_out = edges[n].next_out;
      } else {
        (*nodes)[edges[n].source].first_out = edges[n].next_out;
      }
      if (edges[n].next_out != -1) {
        edges[edges[n].next_out].prev_out = edges[n].prev_out;
      }
           
    }

    void clear() {
      Node node;
      for (first(node); node != INVALID; next(node)) {
        (*nodes)[node].first_in = -1;
        (*nodes)[node].first_out = -1;
      }
      edges.clear();
      first_edge = -1;
      first_free_edge = -1;
    }

    void first(Node& node) const {
      graph->first(node);
    }

    void next(Node& node) const {
      graph->next(node);
    }

    void first(Edge& edge) const {
      Node node;
      for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
           next(node));
      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
    }

    void next(Edge& edge) const {
      if (edges[edge.id].next_in != -1) {
        edge.id = edges[edge.id].next_in;
      } else {
        Node node = edges[edge.id].target;
        for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
             next(node));
        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
      }      
    }

    void firstOut(Edge& edge, const Node& node) const {
      edge.id = (*nodes)[node].first_out;    
    }
    
    void nextOut(Edge& edge) const {
      edge.id = edges[edge.id].next_out;        
    }

    void firstIn(Edge& edge, const Node& node) const {
      edge.id = (*nodes)[node].first_in;          
    }

    void nextIn(Edge& edge) const {
      edge.id = edges[edge.id].next_in;    
    }

    int id(const Node& node) const { return graph->id(node); }
    int id(const Edge& edge) const { return edge.id; }

    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
    Edge edgeFromId(int id) const { return Edge(id); }

    int maxNodeId() const { return graph->maxNodeId(); };
    int maxEdgeId() const { return edges.size() - 1; }

    Node source(const Edge& edge) const { return edges[edge.id].source;}
    Node target(const Edge& edge) const { return edges[edge.id].target;}

    template <typename _Value>
    class NodeMap : public Graph::template NodeMap<_Value> {
    public:
      typedef typename _Graph::template NodeMap<_Value> Parent;
      explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset) 
        : Parent(*edgeset.graph) { }
      NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
        : Parent(*edgeset.graph, value) { }
    };

  };

  /// \ingroup semi_adaptors
  ///
  /// \brief Graph using a node set of another graph and an
  /// own edge set.
  ///
  /// This structure can be used to establish another graph over a node set
  /// of an existing one. The node iterator will go through the nodes of the
  /// original graph.
  ///
  /// \param _Graph The type of the graph which shares its node set with 
  /// this class. Its interface must conform to the \ref concept::StaticGraph
  /// "StaticGraph" concept.
  ///
  /// In the edge extension and removing it conforms to the 
  /// \ref concept::ErasableGraph "ErasableGraph" concept.
  template <typename _Graph>
  class ListEdgeSet :
    public ErasableEdgeSetExtender<
    ClearableEdgeSetExtender<
    ExtendableEdgeSetExtender<
    MappableEdgeSetExtender<
    IterableGraphExtender<
    AlterableEdgeSetExtender<
    GraphExtender<
    ListEdgeSetBase<_Graph> > > > > > > > {

  public:

    typedef ErasableEdgeSetExtender<
      ClearableEdgeSetExtender<
      ExtendableEdgeSetExtender<
      MappableEdgeSetExtender<
      IterableGraphExtender<
      AlterableEdgeSetExtender<
      GraphExtender<
      ListEdgeSetBase<_Graph> > > > > > > > Parent;
    
    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;
    
    typedef _Graph Graph;


    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {
      Edge edge;
      Parent::firstOut(edge, node);
      while (edge != INVALID ) {
        erase(edge);
        Parent::firstOut(edge, node);
      } 

      Parent::firstIn(edge, node);
      while (edge != INVALID ) {
        erase(edge);
        Parent::firstIn(edge, node);
      }
    }
    
    void clearNodes() {
      Parent::clear();
    }

    class NodesImpl : public NodesImplBase {
    public:
      typedef NodesImplBase Parent;
      
      NodesImpl(const Graph& graph, ListEdgeSet& edgeset) 
        : Parent(graph), _edgeset(edgeset) {}

      virtual ~NodesImpl() {}
      
    protected:

      virtual void erase(const Node& node) {
        _edgeset.eraseNode(node);
        Parent::erase(node);
      }
      virtual void erase(const std::vector<Node>& nodes) {
        for (int i = 0; i < (int)nodes.size(); ++i) {
          _edgeset.eraseNode(nodes[i]);
        }
        Parent::erase(nodes);
      }
      virtual void clear() {
        _edgeset.clearNodes();
        Parent::clear();
      }

    private:
      ListEdgeSet& _edgeset;
    };

    NodesImpl nodes;
    
  public:

    /// \brief Constructor of the adaptor.
    /// 
    /// Constructor of the adaptor.
    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
      Parent::initalize(graph, nodes);
    }
    
  };

  /// \ingroup semi_adaptors
  ///
  /// \brief Graph using a node set of another graph and an
  /// own uedge set.
  ///
  /// This structure can be used to establish another graph over a node set
  /// of an existing one. The node iterator will go through the nodes of the
  /// original graph.
  ///
  /// \param _Graph The type of the graph which shares its node set with 
  /// this class. Its interface must conform to the \ref concept::StaticGraph
  /// "StaticGraph" concept.
  ///
  /// In the edge extension and removing it conforms to the 
  /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
  template <typename _Graph>
  class ListUEdgeSet :
    public ErasableUEdgeSetExtender<
    ClearableUEdgeSetExtender<
    ExtendableUEdgeSetExtender<
    MappableUEdgeSetExtender<
    IterableUGraphExtender<
    AlterableUEdgeSetExtender<
    UGraphExtender<
    ListEdgeSetBase<_Graph> > > > > > > > {

  public:

    typedef ErasableUEdgeSetExtender<
      ClearableUEdgeSetExtender<
      ExtendableUEdgeSetExtender<
      MappableUEdgeSetExtender<
      IterableUGraphExtender<
      AlterableUEdgeSetExtender<
      UGraphExtender<
      ListEdgeSetBase<_Graph> > > > > > > > Parent;
    
    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;
    
    typedef _Graph Graph;


    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {
      Edge edge;
      Parent::firstOut(edge, node);
      while (edge != INVALID ) {
        erase(edge);
        Parent::firstOut(edge, node);
      } 

    }
    
    void clearNodes() {
      Parent::clear();
    }

    class NodesImpl : public NodesImplBase {
    public:
      typedef NodesImplBase Parent;
      
      NodesImpl(const Graph& graph, ListUEdgeSet& edgeset) 
        : Parent(graph), _edgeset(edgeset) {}

      virtual ~NodesImpl() {}
      
    protected:

      virtual void erase(const Node& node) {
        _edgeset.eraseNode(node);
        Parent::erase(node);
      }
      virtual void erase(const std::vector<Node>& nodes) {
        for (int i = 0; i < (int)nodes.size(); ++i) {
          _edgeset.eraseNode(nodes[i]);
        }
        Parent::erase(nodes);
      }
      virtual void clear() {
        _edgeset.clearNodes();
        Parent::clear();
      }

    private:
      ListUEdgeSet& _edgeset;
    };

    NodesImpl nodes;
    
  public:

    /// \brief Constructor of the adaptor.
    /// 
    /// Constructor of the adaptor.
    ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
      Parent::initalize(graph, nodes);
    }
    
  };

  template <typename _Graph>
  class SmartEdgeSetBase {
  public:

    typedef _Graph Graph;
    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;

  protected:

    struct NodeT {
      int first_out, first_in;
      NodeT() : first_out(-1), first_in(-1) {}
    };

    typedef typename Graph::template NodeMap<NodeT> NodesImplBase;

    NodesImplBase* nodes;

    struct EdgeT {
      Node source, target;
      int next_out, next_in;
      EdgeT() {}
    };

    std::vector<EdgeT> edges;

    const Graph* graph;

    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
      graph = &_graph;
      nodes = &_nodes;
    }
    
  public:

    class Edge {
      friend class SmartEdgeSetBase<Graph>;
    protected:
      Edge(int _id) : id(_id) {}
      int id;
    public:
      Edge() {}
      Edge(Invalid) : id(-1) {}
      bool operator==(const Edge& edge) const { return id == edge.id; }
      bool operator!=(const Edge& edge) const { return id != edge.id; }
      bool operator<(const Edge& edge) const { return id < edge.id; }
    };

    SmartEdgeSetBase() {} 

    Edge addEdge(const Node& source, const Node& target) {
      int n = edges.size();
      edges.push_back(EdgeT());
      edges[n].next_in = (*nodes)[target].first_in;
      (*nodes)[target].first_in = n;
      edges[n].next_out = (*nodes)[source].first_out;
      (*nodes)[source].first_out = n;
      edges[n].source = source;
      edges[n].target = target;
      return Edge(n);
    }

    void clear() {
      Node node;
      for (first(node); node != INVALID; next(node)) {
        (*nodes)[node].first_in = -1;
        (*nodes)[node].first_out = -1;
      }
      edges.clear();
    }

    void first(Node& node) const {
      graph->first(node);
    }

    void next(Node& node) const {
      graph->next(node);
    }

    void first(Edge& edge) const {
      edge.id = edges.size() - 1;
    }

    void next(Edge& edge) const {
      --edge.id;
    }

    void firstOut(Edge& edge, const Node& node) const {
      edge.id = (*nodes)[node].first_out;    
    }
    
    void nextOut(Edge& edge) const {
      edge.id = edges[edge.id].next_out;        
    }

    void firstIn(Edge& edge, const Node& node) const {
      edge.id = (*nodes)[node].first_in;          
    }

    void nextIn(Edge& edge) const {
      edge.id = edges[edge.id].next_in;    
    }

    int id(const Node& node) const { return graph->id(node); }
    int id(const Edge& edge) const { return edge.id; }

    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
    Edge edgeFromId(int id) const { return Edge(id); }

    int maxNodeId() const { return graph->maxNodeId(); };
    int maxEdgeId() const { return edges.size() - 1; }

    Node source(const Edge& edge) const { return edges[edge.id].source;}
    Node target(const Edge& edge) const { return edges[edge.id].target;}

    template <typename _Value>
    class NodeMap : public Graph::template NodeMap<_Value> {
    public:
      typedef typename _Graph::template NodeMap<_Value> Parent;
      explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset) 
        : Parent(*edgeset.graph) { }
      NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
        : Parent(*edgeset.graph, value) { }
    };

  };


  /// \ingroup semi_adaptors
  ///
  /// \brief Graph using a node set of another graph and an
  /// own edge set.
  ///
  /// This structure can be used to establish another graph over a node set
  /// of an existing one. The node iterator will go through the nodes of the
  /// original graph.
  ///
  /// \param _Graph The type of the graph which shares its node set with 
  /// this class. Its interface must conform to the \ref concept::StaticGraph
  /// "StaticGraph" concept.
  ///
  /// In the edge extension and removing it conforms to the 
  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
  template <typename _Graph>
  class SmartEdgeSet :
    public ClearableEdgeSetExtender<
    ExtendableEdgeSetExtender<
    MappableEdgeSetExtender<
    IterableGraphExtender<
    AlterableEdgeSetExtender<
    GraphExtender<
    SmartEdgeSetBase<_Graph> > > > > > > {

  public:

    typedef ClearableEdgeSetExtender<
      ExtendableEdgeSetExtender<
      MappableEdgeSetExtender<
      IterableGraphExtender<
      AlterableEdgeSetExtender<
      GraphExtender<
      SmartEdgeSetBase<_Graph> > > > > > > Parent;
    
    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;
    
    typedef _Graph Graph;

    class UnsupportedOperation : public LogicError {
    public:
      virtual const char* exceptionName() const {
        return "lemon::SmartEdgeSet::UnsupportedOperation";
      }
    };
    


  protected:

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node&) {
      throw UnsupportedOperation();
    }
    
    void clearNodes() {
      Parent::clear();
    }

    class NodesImpl : public NodesImplBase {
    public:
      typedef NodesImplBase Parent;
      
      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset) 
        : Parent(graph), _edgeset(edgeset) {}

      virtual ~NodesImpl() {}
      
    protected:

      virtual void erase(const Node& node) {
        _edgeset.eraseNode(node);
        Parent::erase(node);
      }
      virtual void erase(const std::vector<Node>& nodes) {
        for (int i = 0; i < (int)nodes.size(); ++i) {
          _edgeset.eraseNode(nodes[i]);
        }
        Parent::erase(nodes);
      }
      virtual void clear() {
        _edgeset.clearNodes();
        Parent::clear();
      }

    private:
      SmartEdgeSet& _edgeset;
    };

    NodesImpl nodes;
    
  public:

    /// \brief Constructor of the adaptor.
    /// 
    /// Constructor of the adaptor.
    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
      Parent::initalize(graph, nodes);
    }
    
  };

  /// \ingroup semi_adaptors
  ///
  /// \brief Graph using a node set of another graph and an
  /// own uedge set.
  ///
  /// This structure can be used to establish another graph over a node set
  /// of an existing one. The node iterator will go through the nodes of the
  /// original graph.
  ///
  /// \param _Graph The type of the graph which shares its node set with 
  /// this class. Its interface must conform to the \ref concept::StaticGraph
  /// "StaticGraph" concept.
  ///
  /// In the edge extension and removing it conforms to the 
  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
  template <typename _Graph>
  class SmartUEdgeSet :
    public ClearableUEdgeSetExtender<
    ExtendableUEdgeSetExtender<
    MappableUEdgeSetExtender<
    IterableUGraphExtender<
    AlterableUEdgeSetExtender<
    UGraphExtender<
    SmartEdgeSetBase<_Graph> > > > > > > {

  public:

    typedef ClearableUEdgeSetExtender<
      ExtendableUEdgeSetExtender<
      MappableUEdgeSetExtender<
      IterableUGraphExtender<
      AlterableUEdgeSetExtender<
      UGraphExtender<
      SmartEdgeSetBase<_Graph> > > > > > > Parent;
    
    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;
    
    typedef _Graph Graph;

    class UnsupportedOperation : public LogicError {
    public:
      virtual const char* exceptionName() const {
        return "lemon::SmartUEdgeSet::UnsupportedOperation";
      }
    };

  protected:

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node&) {
      throw UnsupportedOperation();
    }
    
    void clearNodes() {
      Parent::clear();
    }

    class NodesImpl : public NodesImplBase {
    public:
      typedef NodesImplBase Parent;
      
      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset) 
        : Parent(graph), _edgeset(edgeset) {}

      virtual ~NodesImpl() {}
      
    protected:

      virtual void erase(const Node& node) {
        _edgeset.eraseNode(node);
        Parent::erase(node);
      }
      virtual void erase(const std::vector<Node>& nodes) {
        for (int i = 0; i < (int)nodes.size(); ++i) {
          _edgeset.eraseNode(nodes[i]);
        }
        Parent::erase(nodes);
      }
      virtual void clear() {
        _edgeset.clearNodes();
        Parent::clear();
      }

    private:
      SmartUEdgeSet& _edgeset;
    };

    NodesImpl nodes;
    
  public:

    /// \brief Constructor of the adaptor.
    /// 
    /// Constructor of the adaptor.
    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
      Parent::initalize(graph, nodes);
    }
    
  };

}

#endif