/* -*- C++ -*- * lemon/list_graph.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 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_LIST_GRAPH_H #define LEMON_LIST_GRAPH_H ///\ingroup graphs ///\file ///\brief ListGraph, SymListGraph classes. #include #include #include #include #include #include #include #include namespace lemon { class ListGraphBase { protected: struct NodeT { int first_in, first_out; int prev, next; }; struct EdgeT { int target, source; int prev_in, prev_out; int next_in, next_out; }; std::vector nodes; int first_node; int first_free_node; std::vector edges; int first_free_edge; public: typedef ListGraphBase Graph; class Node { friend class ListGraphBase; protected: int id; Node(int pid) { id = pid;} public: Node() {} Node (Invalid) { id = -1; } bool operator==(const Node& node) const {return id == node.id;} bool operator!=(const Node& node) const {return id != node.id;} bool operator<(const Node& node) const {return id < node.id;} }; class Edge { friend class ListGraphBase; protected: int id; Edge(int pid) { id = pid;} 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;} }; ListGraphBase() : nodes(), first_node(-1), first_free_node(-1), edges(), first_free_edge(-1) {} /// Maximum node ID. /// Maximum node ID. ///\sa id(Node) int maxId(Node = INVALID) const { return nodes.size()-1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxId(Edge = INVALID) const { return edges.size()-1; } Node source(Edge e) const { return edges[e.id].source; } Node target(Edge e) const { return edges[e.id].target; } void first(Node& node) const { node.id = first_node; } void next(Node& node) const { node.id = nodes[node.id].next; } void first(Edge& e) const { int n; for(n = first_node; n!=-1 && nodes[n].first_in == -1; n = nodes[n].next); e.id = (n == -1) ? -1 : nodes[n].first_in; } void next(Edge& edge) const { if (edges[edge.id].next_in != -1) { edge.id = edges[edge.id].next_in; } else { int n; for(n = nodes[edges[edge.id].target].next; n!=-1 && nodes[n].first_in == -1; n = nodes[n].next); edge.id = (n == -1) ? -1 : nodes[n].first_in; } } void firstOut(Edge &e, const Node& v) const { e.id = nodes[v.id].first_out; } void nextOut(Edge &e) const { e.id=edges[e.id].next_out; } void firstIn(Edge &e, const Node& v) const { e.id = nodes[v.id].first_in; } void nextIn(Edge &e) const { e.id=edges[e.id].next_in; } static int id(Node v) { return v.id; } static int id(Edge e) { return e.id; } static Node fromId(int id, Node) { return Node(id);} static Edge fromId(int id, Edge) { return Edge(id);} /// Adds a new node to the graph. /// \warning It adds the new node to the front of the list. /// (i.e. the lastly added node becomes the first.) Node addNode() { int n; if(first_free_node==-1) { n = nodes.size(); nodes.push_back(NodeT()); } else { n = first_free_node; first_free_node = nodes[n].next; } nodes[n].next = first_node; if(first_node != -1) nodes[first_node].prev = n; first_node = n; nodes[n].prev = -1; nodes[n].first_in = nodes[n].first_out = -1; return Node(n); } Edge addEdge(Node u, Node v) { int n; if (first_free_edge == -1) { n = edges.size(); edges.push_back(EdgeT()); } else { n = first_free_edge; first_free_edge = edges[n].next_in; } edges[n].source = u.id; edges[n].target = v.id; edges[n].next_out = nodes[u.id].first_out; if(nodes[u.id].first_out != -1) { edges[nodes[u.id].first_out].prev_out = n; } edges[n].next_in = nodes[v.id].first_in; if(nodes[v.id].first_in != -1) { edges[nodes[v.id].first_in].prev_in = n; } edges[n].prev_in = edges[n].prev_out = -1; nodes[u.id].first_out = nodes[v.id].first_in = n; return Edge(n); } void erase(const Node& node) { int n = node.id; if(nodes[n].next != -1) { nodes[nodes[n].next].prev = nodes[n].prev; } if(nodes[n].prev != -1) { nodes[nodes[n].prev].next = nodes[n].next; } else { first_node = nodes[n].next; } nodes[n].next = first_free_node; first_free_node = n; } void erase(const Edge& edge) { int n = edge.id; if(edges[n].next_in!=-1) { edges[edges[n].next_in].prev_in = edges[n].prev_in; } 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_out!=-1) { edges[edges[n].next_out].prev_out = edges[n].prev_out; } 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; } edges[n].next_in = first_free_edge; first_free_edge = n; } void clear() { edges.clear(); nodes.clear(); first_node = first_free_node = first_free_edge = -1; } protected: void _changeTarget(Edge e, Node n) { if(edges[e.id].next_in != -1) edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; if(edges[e.id].prev_in != -1) edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; else nodes[edges[e.id].target].first_in = edges[e.id].next_in; edges[e.id].target = n.id; edges[e.id].prev_in = -1; edges[e.id].next_in = nodes[n.id].first_in; nodes[n.id].first_in = e.id; } void _changeSource(Edge e, Node n) { if(edges[e.id].next_out != -1) edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; if(edges[e.id].prev_out != -1) edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; else nodes[edges[e.id].source].first_out = edges[e.id].next_out; edges[e.id].source = n.id; edges[e.id].prev_out = -1; edges[e.id].next_out = nodes[n.id].first_out; nodes[n.id].first_out = e.id; } }; typedef AlterableGraphExtender AlterableListGraphBase; typedef IterableGraphExtender IterableListGraphBase; typedef MappableGraphExtender MappableListGraphBase; typedef ExtendableGraphExtender ExtendableListGraphBase; typedef ClearableGraphExtender ClearableListGraphBase; typedef ErasableGraphExtender< ClearableGraphExtender< ExtendableGraphExtender< MappableGraphExtender< IterableGraphExtender< AlterableGraphExtender > > > > > ExtendedListGraphBase; /// \addtogroup graphs /// @{ ///A list graph class. ///This is a simple and fast erasable graph implementation. /// ///It addition that it conforms to the ///\ref concept::ErasableGraph "ErasableGraph" concept, ///it also provides several additional useful extra functionalities. ///\sa concept::ErasableGraph. class ListGraph : public ExtendedListGraphBase { public: /// Changes the target of \c e to \c n /// Changes the target of \c e to \c n /// ///\note The Edge's and OutEdge's ///referencing the changed edge remain ///valid. However InEdge's are invalidated. void changeTarget(Edge e, Node n) { _changeTarget(e,n); } /// Changes the source of \c e to \c n /// Changes the source of \c e to \c n /// ///\note The Edge's and InEdge's ///referencing the changed edge remain ///valid. However OutEdge's are invalidated. void changeSource(Edge e, Node n) { _changeSource(e,n); } /// Invert the direction of an edge. ///\note The Edge's ///referencing the changed edge remain ///valid. However OutEdge's and InEdge's are invalidated. void reverseEdge(Edge e) { Node t=target(e); _changeTarget(e,source(e)); _changeSource(e,t); } ///Using this it possible to avoid the superfluous memory allocation. ///Using this it possible to avoid the superfluous memory allocation. ///\todo more docs... void reserveEdge(int n) { edges.reserve(n); }; ///Contract two nodes. ///This function contracts two nodes. /// ///Node \p b will be removed but instead of deleting ///its neighboring edges, they will be joined to \p a. ///The last parameter \p r controls whether to remove loops. \c true ///means that loops will be removed. /// ///\note The Edges ///referencing a moved edge remain ///valid. However InEdge's and OutEdge's ///may be invalidated. void contract(Node a,Node b,bool r=true) { for(OutEdgeIt e(*this,b);e!=INVALID;) { OutEdgeIt f=e; ++f; if(r && target(e)==a) erase(e); else changeSource(e,a); e=f; } for(InEdgeIt e(*this,b);e!=INVALID;) { InEdgeIt f=e; ++f; if(r && source(e)==a) erase(e); else changeTarget(e,a); e=f; } erase(b); } ///Split a node. ///This function splits a node. First a new node is added to the graph, ///then the source of each outgoing edge of \c n is moved to this new node. ///If \c connect is \c true (this is the default value), then a new edge ///from \c n to the newly created node is also added. ///\return The newly created node. /// ///\note The Edges ///referencing a moved edge remain ///valid. However InEdge's and OutEdge's ///may be invalidated. ///\warning This functionality cannot be used together with the SnapShot ///feature. ///\todo It could be implemented in a bit faster way. Node split(Node n, bool connect = true) { Node b = addNode(); for(OutEdgeIt e(*this,n);e!=INVALID;) { OutEdgeIt f=e; ++f; changeSource(e,b); e=f; } if(connect) addEdge(n,b); return b; } ///Class to make a snapshot of the graph and to restrore to it later. ///Class to make a snapshot of the graph and to restrore to it later. /// ///The newly added nodes and edges can be removed using the ///restore() function. /// ///\warning Edge and node deletions cannot be restored. ///\warning SnapShots cannot be nested. ///\todo \c SnapShot or \c Snapshot? class SnapShot : protected AlterationNotifier::ObserverBase, protected AlterationNotifier::ObserverBase { protected: ListGraph *g; std::list added_nodes; std::list added_edges; bool active; virtual void add(const Node& n) { added_nodes.push_back(n); }; ///\bug Exception... /// virtual void erase(const Node&) { exit(1); } virtual void add(const Edge& n) { added_edges.push_back(n); }; ///\bug Exception... /// virtual void erase(const Edge&) { exit(1); } ///\bug What is this used for? /// virtual void build() {} ///\bug What is this used for? /// virtual void clear() {} void regist(ListGraph &_g) { g=&_g; AlterationNotifier::ObserverBase:: attach(g->getNotifier(Node())); AlterationNotifier::ObserverBase:: attach(g->getNotifier(Edge())); } void deregist() { AlterationNotifier::ObserverBase:: detach(); AlterationNotifier::ObserverBase:: detach(); g=0; } public: ///Default constructur. ///Default constructur. ///To actually make a snapshot you must call save(). /// SnapShot() : g(0) {} ///Constructor that immediately makes a snapshot. ///This constructor immediately makes a snapshot of the graph. ///\param _g The graph we make a snapshot of. SnapShot(ListGraph &_g) { regist(_g); } ///\bug Is it necessary? /// ~SnapShot() { if(g) deregist(); } ///Make a snapshot. ///Make a snapshot of the graph. /// ///This function can be called more than once. In case of a repeated ///call, the previous snapshot gets lost. ///\param _g The graph we make the snapshot of. void save(ListGraph &_g) { if(g!=&_g) { if(g) deregist(); regist(_g); } added_nodes.clear(); added_edges.clear(); } ///Undo the changes until the last snapshot. ///Undo the changes until last snapshot created by save(). /// ///\todo This function might be called undo(). void restore() { ListGraph &old_g=*g; deregist(); while(!added_edges.empty()) { old_g.erase(added_edges.front()); added_edges.pop_front(); } while(!added_nodes.empty()) { old_g.erase(added_nodes.front()); added_nodes.pop_front(); } } }; }; ///@} /**************** Undirected List Graph ****************/ typedef ErasableUndirGraphExtender< ClearableUndirGraphExtender< ExtendableUndirGraphExtender< MappableUndirGraphExtender< IterableUndirGraphExtender< AlterableUndirGraphExtender< UndirGraphExtender > > > > > > ExtendedUndirListGraphBase; /// \addtogroup graphs /// @{ ///An undirected list graph class. ///This is a simple and fast erasable undirected graph implementation. /// ///It conforms to the ///\ref concept::UndirGraph "UndirGraph" concept. /// ///\sa concept::UndirGraph. /// ///\todo SnapShot, reverseEdge(), changeTarget(), changeSource(), contract() ///haven't been implemented yet. /// class UndirListGraph : public ExtendedUndirListGraphBase { }; /// @} } //namespace lemon #endif