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 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 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 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; 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 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& edgeset) deba@1842: : Parent(*edgeset.graph) { } deba@1842: NodeMap(const ListEdgeSetBase& edgeset, const _Value& value) deba@1842: : Parent(*edgeset.graph, value) { } deba@1842: }; deba@1842: deba@1842: }; deba@1842: deba@1866: /// \ingroup semi_adaptors 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 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@1866: /// \ingroup semi_adaptors 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 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@1866: virtual void erase(const std::vector& nodes) { deba@1866: for (int i = 0; i < nodes.size(); ++i) { deba@1866: _edgeset.eraseNode(nodes[i]); deba@1866: } deba@1866: Parent::erase(nodes); deba@1866: } 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