deba@1842: /* -*- C++ -*-
deba@1842:  * lemon/edge_set.h - Part of LEMON, a generic C++ optimization library
deba@1842:  *
deba@1842:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1842:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1842:  *
deba@1842:  * Permission to use, modify and distribute this software is granted
deba@1842:  * provided that this copyright notice appears in all copies. For
deba@1842:  * precise terms see the accompanying LICENSE file.
deba@1842:  *
deba@1842:  * This software is provided "AS IS" with no warranty of any kind,
deba@1842:  * express or implied, and with no claim as to its suitability for any
deba@1842:  * purpose.
deba@1842:  *
deba@1842:  */
deba@1842: 
deba@1842: #ifndef LEMON_EDGE_SET_H
deba@1842: #define LEMON_EDGE_SET_H
deba@1842: 
deba@1842: /// \ingroup graphs
deba@1842: /// \file
deba@1842: /// \brief EdgeSet classes.
deba@1842: ///
deba@1842: /// Graphs which use another graph's node-set as own. 
deba@1842: 
deba@1842: namespace lemon {
deba@1842: 
deba@1842:   template <typename _Graph>
deba@1842:   class ListEdgeSetBase {
deba@1842:   public:
deba@1842: 
deba@1842:     typedef _Graph Graph;
deba@1842:     typedef typename Graph::Node Node;
deba@1842:     typedef typename Graph::NodeIt NodeIt;
deba@1842: 
deba@1842:   protected:
deba@1842: 
deba@1842:     struct NodeT {
deba@1842:       int first_out, first_in;
deba@1842:       NodeT() : first_out(-1), first_in(-1) {}
deba@1842:     };
deba@1842: 
deba@1842:     typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
deba@1842: 
deba@1842:     NodesImplBase* nodes;
deba@1842: 
deba@1842:     struct EdgeT {
deba@1842:       Node source, target;
deba@1842:       int next_out, next_in;
deba@1842:       int prev_out, prev_in;
deba@1842:       EdgeT() : prev_out(-1), prev_in(-1) {}
deba@1842:     };
deba@1842: 
deba@1842:     std::vector<EdgeT> edges;
deba@1842: 
deba@1842:     int first_edge;
deba@1842:     int first_free_edge;
deba@1842: 
deba@1842:     const Graph* graph;
deba@1842: 
deba@1842:     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@1842:       graph = &_graph;
deba@1842:       nodes = &_nodes;
deba@1842:     }
deba@1842:     
deba@1842:   public:
deba@1842: 
deba@1842:     class Edge {
deba@1842:       friend class ListEdgeSetBase<Graph>;
deba@1842:     protected:
deba@1842:       Edge(int _id) : id(_id) {}
deba@1842:       int id;
deba@1842:     public:
deba@1842:       Edge() {}
deba@1842:       Edge(Invalid) : id(-1) {}
deba@1842:       bool operator==(const Edge& edge) const { return id == edge.id; }
deba@1842:       bool operator!=(const Edge& edge) const { return id != edge.id; }
deba@1842:       bool operator<(const Edge& edge) const { return id < edge.id; }
deba@1842:     };
deba@1842: 
deba@1842:     ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} 
deba@1842: 
deba@1842:     Edge addEdge(const Node& source, const Node& target) {
deba@1842:       int n;
deba@1842:       if (first_free_edge == -1) {
deba@1842: 	n = edges.size();
deba@1842: 	edges.push_back(EdgeT());
deba@1842:       } else {
deba@1842: 	n = first_free_edge;
deba@1842: 	first_free_edge = edges[first_free_edge].next_in;
deba@1842:       }
deba@1842:       edges[n].next_in = (*nodes)[target].first_in;
deba@1842:       (*nodes)[target].first_in = n;
deba@1842:       edges[n].next_out = (*nodes)[source].first_out;
deba@1842:       (*nodes)[source].first_out = n;
deba@1842:       edges[n].source = source;
deba@1842:       edges[n].target = target;
deba@1842:       return Edge(n);
deba@1842:     }
deba@1842: 
deba@1842:     void erase(const Edge& edge) {
deba@1842:       int n = edge.id;
deba@1842:       if (edges[n].prev_in != -1) {
deba@1842: 	edges[edges[n].prev_in].next_in = edges[n].next_in;
deba@1842:       } else {
deba@1842: 	(*nodes)[edges[n].target].first_in = edges[n].next_in;
deba@1842:       }
deba@1842:       if (edges[n].next_in != -1) {
deba@1842: 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
deba@1842:       }
deba@1842: 
deba@1842:       if (edges[n].prev_out != -1) {
deba@1842: 	edges[edges[n].prev_out].next_out = edges[n].next_out;
deba@1842:       } else {
deba@1842: 	(*nodes)[edges[n].source].first_out = edges[n].next_out;
deba@1842:       }
deba@1842:       if (edges[n].next_out != -1) {
deba@1842: 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
deba@1842:       }
deba@1842:            
deba@1842:     }
deba@1842: 
deba@1842:     void clear() {
deba@1842:       edges.clear();
deba@1842:       first_edge = -1;
deba@1842:       first_free_edge = -1;
deba@1842:     }
deba@1842: 
deba@1842:     void first(Node& node) const {
deba@1842:       graph->first(node);
deba@1842:     }
deba@1842: 
deba@1842:     void next(Node& node) const {
deba@1842:       graph->next(node);
deba@1842:     }
deba@1842: 
deba@1842:     void first(Edge& edge) const {
deba@1842:       Node node;
deba@1842:       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
deba@1842: 	   next(node));
deba@1842:       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1842:     }
deba@1842: 
deba@1842:     void next(Edge& edge) const {
deba@1842:       if (edges[edge.id].next_in != -1) {
deba@1842: 	edge.id = edges[edge.id].next_in;
deba@1842:       } else {
deba@1842: 	Node node = edges[edge.id].target;
deba@1842: 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
deba@1842: 	     next(node));
deba@1842: 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1842:       }      
deba@1842:     }
deba@1842: 
deba@1842:     void firstOut(Edge& edge, const Node& node) const {
deba@1842:       edge.id = (*nodes)[node].first_out;    
deba@1842:     }
deba@1842:     
deba@1842:     void nextOut(Edge& edge) const {
deba@1842:       edge.id = edges[edge.id].next_out;        
deba@1842:     }
deba@1842: 
deba@1842:     void firstIn(Edge& edge, const Node& node) const {
deba@1842:       edge.id = (*nodes)[node].first_in;          
deba@1842:     }
deba@1842: 
deba@1842:     void nextIn(Edge& edge) const {
deba@1842:       edge.id = edges[edge.id].next_in;    
deba@1842:     }
deba@1842: 
deba@1842:     int id(const Node& node) const { return graph->id(node); }
deba@1842:     int id(const Edge& edge) const { return edge.id; }
deba@1842: 
deba@1842:     Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
deba@1842:     Edge edgeFromId(int id) const { return Edge(id); }
deba@1842: 
deba@1842:     int maxNodeId() const { return graph->maxId(Node()); };
deba@1842:     int maxEdgeId() const { return edges.size() - 1; }
deba@1842: 
deba@1842:     Node source(const Edge& edge) const { return edges[edge.id].source;}
deba@1842:     Node target(const Edge& edge) const { return edges[edge.id].target;}
deba@1842: 
deba@1842:     template <typename _Value>
deba@1842:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@1842:     public:
deba@1842:       typedef typename _Graph::template NodeMap<_Value> Parent;
deba@1842:       explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset) 
deba@1842: 	: Parent(*edgeset.graph) { }
deba@1842:       NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
deba@1842: 	: Parent(*edgeset.graph, value) { }
deba@1842:     };
deba@1842: 
deba@1842:   };
deba@1842: 
deba@1842:   /// \ingroup graphs
deba@1842:   ///
deba@1842:   /// \brief Graph using a node set of another graph and an
deba@1842:   /// own edge set.
deba@1842:   ///
deba@1842:   /// This structure can be used to establish another graph over a node set
deba@1842:   /// of an existing one. The node iterator will go through the nodes of the
deba@1842:   /// original graph.
deba@1842:   ///
deba@1842:   /// \param _Graph The type of the graph which shares its node set with 
deba@1842:   /// this class. Its interface must conform to the \ref concept::StaticGraph
deba@1842:   /// "StaticGraph" concept.
deba@1842:   ///
deba@1842:   /// In the edge extension and removing it conforms to the 
deba@1842:   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
deba@1842:   template <typename _Graph>
deba@1842:   class ListEdgeSet :
deba@1842:     public ErasableEdgeSetExtender<
deba@1842:     ClearableEdgeSetExtender<
deba@1842:     ExtendableEdgeSetExtender<
deba@1842:     MappableEdgeSetExtender<
deba@1842:     IterableGraphExtender<
deba@1842:     AlterableEdgeSetExtender<
deba@1842:     GraphExtender<
deba@1842:     ListEdgeSetBase<_Graph> > > > > > > > {
deba@1842: 
deba@1842:   public:
deba@1842: 
deba@1842:     typedef ErasableEdgeSetExtender<
deba@1842:       ClearableEdgeSetExtender<
deba@1842:       ExtendableEdgeSetExtender<
deba@1842:       MappableEdgeSetExtender<
deba@1842:       IterableGraphExtender<
deba@1842:       AlterableEdgeSetExtender<
deba@1842:       GraphExtender<
deba@1842:       ListEdgeSetBase<_Graph> > > > > > > > Parent;
deba@1842:     
deba@1842:     typedef typename Parent::Node Node;
deba@1842:     typedef typename Parent::Edge Edge;
deba@1842:     
deba@1842:     typedef _Graph Graph;
deba@1842: 
deba@1842: 
deba@1842:     typedef typename Parent::NodesImplBase NodesImplBase;
deba@1842: 
deba@1842:     void eraseNode(const Node& node) {
deba@1842:       Edge edge;
deba@1842:       Parent::firstOut(edge, node);
deba@1842:       while (edge != INVALID ) {
deba@1842: 	erase(edge);
deba@1842: 	Parent::firstOut(edge, node);
deba@1842:       } 
deba@1842: 
deba@1842:       Parent::firstIn(edge, node);
deba@1842:       while (edge != INVALID ) {
deba@1842: 	erase(edge);
deba@1842: 	Parent::firstIn(edge, node);
deba@1842:       }
deba@1842:     }
deba@1842:     
deba@1842:     void clearNodes() {
deba@1842:       Parent::clear();
deba@1842:     }
deba@1842: 
deba@1842:     class NodesImpl : public NodesImplBase {
deba@1842:     public:
deba@1842:       typedef NodesImplBase Parent;
deba@1842:       
deba@1842:       NodesImpl(const Graph& graph, ListEdgeSet& edgeset) 
deba@1842: 	: Parent(graph), _edgeset(edgeset) {}
deba@1842:       
deba@1842:     protected:
deba@1842: 
deba@1842:       virtual void erase(const Node& node) {
deba@1842: 	_edgeset.eraseNode(node);
deba@1842: 	Parent::erase(node);
deba@1842:       }
deba@1842:       virtual void clear() {
deba@1842: 	_edgeset.clearNodes();
deba@1842: 	Parent::clear();
deba@1842:       }
deba@1842: 
deba@1842:     private:
deba@1842:       ListEdgeSet& _edgeset;
deba@1842:     };
deba@1842: 
deba@1842:     NodesImpl nodes;
deba@1842:     
deba@1842:   public:
deba@1842: 
deba@1842:     /// \brief Constructor of the adaptor.
deba@1842:     /// 
deba@1842:     /// Constructor of the adaptor.
deba@1842:     ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@1842:       Parent::initalize(graph, nodes);
deba@1842:     }
deba@1842:     
deba@1842:   };
deba@1842: 
deba@1842:   /// \ingroup graphs
deba@1842:   ///
deba@1842:   /// \brief Graph using a node set of another graph and an
deba@1842:   /// own undir edge set.
deba@1842:   ///
deba@1842:   /// This structure can be used to establish another graph over a node set
deba@1842:   /// of an existing one. The node iterator will go through the nodes of the
deba@1842:   /// original graph.
deba@1842:   ///
deba@1842:   /// \param _Graph The type of the graph which shares its node set with 
deba@1842:   /// this class. Its interface must conform to the \ref concept::StaticGraph
deba@1842:   /// "StaticGraph" concept.
deba@1842:   ///
deba@1842:   /// In the edge extension and removing it conforms to the 
deba@1842:   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
deba@1842:   template <typename _Graph>
deba@1842:   class ListUndirEdgeSet :
deba@1842:     public ErasableUndirEdgeSetExtender<
deba@1842:     ClearableUndirEdgeSetExtender<
deba@1842:     ExtendableUndirEdgeSetExtender<
deba@1842:     MappableUndirEdgeSetExtender<
deba@1842:     IterableUndirGraphExtender<
deba@1842:     AlterableUndirEdgeSetExtender<
deba@1842:     UndirGraphExtender<
deba@1842:     ListEdgeSetBase<_Graph> > > > > > > > {
deba@1842: 
deba@1842:   public:
deba@1842: 
deba@1842:     typedef ErasableUndirEdgeSetExtender<
deba@1842:       ClearableUndirEdgeSetExtender<
deba@1842:       ExtendableUndirEdgeSetExtender<
deba@1842:       MappableUndirEdgeSetExtender<
deba@1842:       IterableUndirGraphExtender<
deba@1842:       AlterableUndirEdgeSetExtender<
deba@1842:       UndirGraphExtender<
deba@1842:       ListEdgeSetBase<_Graph> > > > > > > > Parent;
deba@1842:     
deba@1842:     typedef typename Parent::Node Node;
deba@1842:     typedef typename Parent::Edge Edge;
deba@1842:     
deba@1842:     typedef _Graph Graph;
deba@1842: 
deba@1842: 
deba@1842:     typedef typename Parent::NodesImplBase NodesImplBase;
deba@1842: 
deba@1842:     void eraseNode(const Node& node) {
deba@1842:       Edge edge;
deba@1842:       Parent::firstOut(edge, node);
deba@1842:       while (edge != INVALID ) {
deba@1842: 	erase(edge);
deba@1842: 	Parent::firstOut(edge, node);
deba@1842:       } 
deba@1842: 
deba@1842:     }
deba@1842:     
deba@1842:     void clearNodes() {
deba@1842:       Parent::clear();
deba@1842:     }
deba@1842: 
deba@1842:     class NodesImpl : public NodesImplBase {
deba@1842:     public:
deba@1842:       typedef NodesImplBase Parent;
deba@1842:       
deba@1842:       NodesImpl(const Graph& graph, ListUndirEdgeSet& edgeset) 
deba@1842: 	: Parent(graph), _edgeset(edgeset) {}
deba@1842:       
deba@1842:     protected:
deba@1842: 
deba@1842:       virtual void erase(const Node& node) {
deba@1842: 	_edgeset.eraseNode(node);
deba@1842: 	Parent::erase(node);
deba@1842:       }
deba@1842:       virtual void clear() {
deba@1842: 	_edgeset.clearNodes();
deba@1842: 	Parent::clear();
deba@1842:       }
deba@1842: 
deba@1842:     private:
deba@1842:       ListUndirEdgeSet& _edgeset;
deba@1842:     };
deba@1842: 
deba@1842:     NodesImpl nodes;
deba@1842:     
deba@1842:   public:
deba@1842: 
deba@1842:     /// \brief Constructor of the adaptor.
deba@1842:     /// 
deba@1842:     /// Constructor of the adaptor.
deba@1842:     ListUndirEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@1842:       Parent::initalize(graph, nodes);
deba@1842:     }
deba@1842:     
deba@1842:   };
deba@1842: 
deba@1842: }
deba@1842: 
deba@1842: #endif