1.1 --- a/lemon/list_graph.h Wed Jun 28 16:27:44 2006 +0000
1.2 +++ b/lemon/list_graph.h Fri Jun 30 12:14:36 2006 +0000
1.3 @@ -21,13 +21,10 @@
1.4
1.5 ///\ingroup graphs
1.6 ///\file
1.7 -///\brief ListGraph, ListUGraph classes.
1.8 +///\brief ListGraph class.
1.9
1.10 -#include <lemon/bits/base_extender.h>
1.11 #include <lemon/bits/graph_extender.h>
1.12
1.13 -#include <lemon/error.h>
1.14 -
1.15 #include <vector>
1.16 #include <list>
1.17
1.18 @@ -309,8 +306,7 @@
1.19
1.20 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1.21
1.22 - /// \addtogroup graphs
1.23 - /// @{
1.24 + /// \ingroup graphs
1.25
1.26 ///A list graph class.
1.27
1.28 @@ -705,454 +701,6 @@
1.29
1.30 };
1.31
1.32 - ///@}
1.33 -
1.34 - /**************** Undirected List Graph ****************/
1.35 -
1.36 - typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1.37 - ExtendedListUGraphBase;
1.38 -
1.39 - /// \addtogroup graphs
1.40 - /// @{
1.41 -
1.42 - ///An undirected list graph class.
1.43 -
1.44 - ///This is a simple and fast erasable undirected graph implementation.
1.45 - ///
1.46 - ///It conforms to the
1.47 - ///\ref concept::UGraph "UGraph" concept.
1.48 - ///
1.49 - ///\sa concept::UGraph.
1.50 - ///
1.51 - ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
1.52 - ///haven't been implemented yet.
1.53 - ///
1.54 - class ListUGraph : public ExtendedListUGraphBase {
1.55 - public:
1.56 - typedef ExtendedListUGraphBase Parent;
1.57 - /// \brief Add a new node to the graph.
1.58 - ///
1.59 - /// \return the new node.
1.60 - ///
1.61 - Node addNode() { return Parent::addNode(); }
1.62 -
1.63 - /// \brief Add a new edge to the graph.
1.64 - ///
1.65 - /// Add a new edge to the graph with source node \c s
1.66 - /// and target node \c t.
1.67 - /// \return the new undirected edge.
1.68 - UEdge addEdge(const Node& s, const Node& t) {
1.69 - return Parent::addEdge(s, t);
1.70 - }
1.71 - /// \brief Changes the target of \c e to \c n
1.72 - ///
1.73 - /// Changes the target of \c e to \c n
1.74 - ///
1.75 - /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
1.76 - /// referencing the changed edge remain
1.77 - /// valid. However <tt>InEdge</tt>'s are invalidated.
1.78 - void changeTarget(UEdge e, Node n) {
1.79 - Parent::changeTarget(e,n);
1.80 - }
1.81 - /// Changes the source of \c e to \c n
1.82 - ///
1.83 - /// Changes the source of \c e to \c n
1.84 - ///
1.85 - ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
1.86 - ///referencing the changed edge remain
1.87 - ///valid. However <tt>OutEdge</tt>'s are invalidated.
1.88 - void changeSource(UEdge e, Node n) {
1.89 - Parent::changeSource(e,n);
1.90 - }
1.91 - /// \brief Contract two nodes.
1.92 - ///
1.93 - /// This function contracts two nodes.
1.94 - ///
1.95 - /// Node \p b will be removed but instead of deleting
1.96 - /// its neighboring edges, they will be joined to \p a.
1.97 - /// The last parameter \p r controls whether to remove loops. \c true
1.98 - /// means that loops will be removed.
1.99 - ///
1.100 - /// \note The <tt>Edge</tt>s
1.101 - /// referencing a moved edge remain
1.102 - /// valid.
1.103 - void contract(Node a, Node b, bool r = true) {
1.104 - for(IncEdgeIt e(*this, b); e!=INVALID;) {
1.105 - IncEdgeIt f = e; ++f;
1.106 - if (r && runningNode(e) == a) {
1.107 - erase(e);
1.108 - } else if (source(e) == b) {
1.109 - changeSource(e, a);
1.110 - } else {
1.111 - changeTarget(e, a);
1.112 - }
1.113 - e = f;
1.114 - }
1.115 - erase(b);
1.116 - }
1.117 - };
1.118 -
1.119 -
1.120 - class ListBpUGraphBase {
1.121 - public:
1.122 -
1.123 - class NodeSetError : public LogicError {
1.124 - virtual const char* exceptionName() const {
1.125 - return "lemon::ListBpUGraph::NodeSetError";
1.126 - }
1.127 - };
1.128 -
1.129 - protected:
1.130 -
1.131 - struct NodeT {
1.132 - int first_edge, prev, next;
1.133 - };
1.134 -
1.135 - struct UEdgeT {
1.136 - int aNode, prev_out, next_out;
1.137 - int bNode, prev_in, next_in;
1.138 - };
1.139 -
1.140 - std::vector<NodeT> aNodes;
1.141 - std::vector<NodeT> bNodes;
1.142 -
1.143 - std::vector<UEdgeT> edges;
1.144 -
1.145 - int first_anode;
1.146 - int first_free_anode;
1.147 -
1.148 - int first_bnode;
1.149 - int first_free_bnode;
1.150 -
1.151 - int first_free_edge;
1.152 -
1.153 - public:
1.154 -
1.155 - class Node {
1.156 - friend class ListBpUGraphBase;
1.157 - protected:
1.158 - int id;
1.159 -
1.160 - explicit Node(int _id) : id(_id) {}
1.161 - public:
1.162 - Node() {}
1.163 - Node(Invalid) { id = -1; }
1.164 - bool operator==(const Node i) const {return id==i.id;}
1.165 - bool operator!=(const Node i) const {return id!=i.id;}
1.166 - bool operator<(const Node i) const {return id<i.id;}
1.167 - };
1.168 -
1.169 - class UEdge {
1.170 - friend class ListBpUGraphBase;
1.171 - protected:
1.172 - int id;
1.173 -
1.174 - explicit UEdge(int _id) { id = _id;}
1.175 - public:
1.176 - UEdge() {}
1.177 - UEdge (Invalid) { id = -1; }
1.178 - bool operator==(const UEdge i) const {return id==i.id;}
1.179 - bool operator!=(const UEdge i) const {return id!=i.id;}
1.180 - bool operator<(const UEdge i) const {return id<i.id;}
1.181 - };
1.182 -
1.183 - ListBpUGraphBase()
1.184 - : first_anode(-1), first_free_anode(-1),
1.185 - first_bnode(-1), first_free_bnode(-1),
1.186 - first_free_edge(-1) {}
1.187 -
1.188 - void firstANode(Node& node) const {
1.189 - node.id = first_anode != -1 ? (first_anode << 1) : -1;
1.190 - }
1.191 - void nextANode(Node& node) const {
1.192 - node.id = aNodes[node.id >> 1].next;
1.193 - }
1.194 -
1.195 - void firstBNode(Node& node) const {
1.196 - node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1.197 - }
1.198 - void nextBNode(Node& node) const {
1.199 - node.id = bNodes[node.id >> 1].next;
1.200 - }
1.201 -
1.202 - void first(Node& node) const {
1.203 - if (first_anode != -1) {
1.204 - node.id = (first_anode << 1);
1.205 - } else if (first_bnode != -1) {
1.206 - node.id = (first_bnode << 1) + 1;
1.207 - } else {
1.208 - node.id = -1;
1.209 - }
1.210 - }
1.211 - void next(Node& node) const {
1.212 - if (aNode(node)) {
1.213 - node.id = aNodes[node.id >> 1].next;
1.214 - if (node.id == -1) {
1.215 - if (first_bnode != -1) {
1.216 - node.id = (first_bnode << 1) + 1;
1.217 - }
1.218 - }
1.219 - } else {
1.220 - node.id = bNodes[node.id >> 1].next;
1.221 - }
1.222 - }
1.223 -
1.224 - void first(UEdge& edge) const {
1.225 - int aNodeId = first_anode;
1.226 - while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1.227 - aNodeId = aNodes[aNodeId].next != -1 ?
1.228 - aNodes[aNodeId].next >> 1 : -1;
1.229 - }
1.230 - if (aNodeId != -1) {
1.231 - edge.id = aNodes[aNodeId].first_edge;
1.232 - } else {
1.233 - edge.id = -1;
1.234 - }
1.235 - }
1.236 - void next(UEdge& edge) const {
1.237 - int aNodeId = edges[edge.id].aNode >> 1;
1.238 - edge.id = edges[edge.id].next_out;
1.239 - if (edge.id == -1) {
1.240 - aNodeId = aNodes[aNodeId].next != -1 ?
1.241 - aNodes[aNodeId].next >> 1 : -1;
1.242 - while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1.243 - aNodeId = aNodes[aNodeId].next != -1 ?
1.244 - aNodes[aNodeId].next >> 1 : -1;
1.245 - }
1.246 - if (aNodeId != -1) {
1.247 - edge.id = aNodes[aNodeId].first_edge;
1.248 - } else {
1.249 - edge.id = -1;
1.250 - }
1.251 - }
1.252 - }
1.253 -
1.254 - void firstFromANode(UEdge& edge, const Node& node) const {
1.255 - LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1.256 - edge.id = aNodes[node.id >> 1].first_edge;
1.257 - }
1.258 - void nextFromANode(UEdge& edge) const {
1.259 - edge.id = edges[edge.id].next_out;
1.260 - }
1.261 -
1.262 - void firstFromBNode(UEdge& edge, const Node& node) const {
1.263 - LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1.264 - edge.id = bNodes[node.id >> 1].first_edge;
1.265 - }
1.266 - void nextFromBNode(UEdge& edge) const {
1.267 - edge.id = edges[edge.id].next_in;
1.268 - }
1.269 -
1.270 - static int id(const Node& node) {
1.271 - return node.id;
1.272 - }
1.273 - static Node nodeFromId(int id) {
1.274 - return Node(id);
1.275 - }
1.276 - int maxNodeId() const {
1.277 - return aNodes.size() > bNodes.size() ?
1.278 - aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1.279 - }
1.280 -
1.281 - static int id(const UEdge& edge) {
1.282 - return edge.id;
1.283 - }
1.284 - static UEdge uEdgeFromId(int id) {
1.285 - return UEdge(id);
1.286 - }
1.287 - int maxUEdgeId() const {
1.288 - return edges.size();
1.289 - }
1.290 -
1.291 - static int aNodeId(const Node& node) {
1.292 - return node.id >> 1;
1.293 - }
1.294 - static Node fromANodeId(int id) {
1.295 - return Node(id << 1);
1.296 - }
1.297 - int maxANodeId() const {
1.298 - return aNodes.size();
1.299 - }
1.300 -
1.301 - static int bNodeId(const Node& node) {
1.302 - return node.id >> 1;
1.303 - }
1.304 - static Node fromBNodeId(int id) {
1.305 - return Node((id << 1) + 1);
1.306 - }
1.307 - int maxBNodeId() const {
1.308 - return bNodes.size();
1.309 - }
1.310 -
1.311 - Node aNode(const UEdge& edge) const {
1.312 - return Node(edges[edge.id].aNode);
1.313 - }
1.314 - Node bNode(const UEdge& edge) const {
1.315 - return Node(edges[edge.id].bNode);
1.316 - }
1.317 -
1.318 - static bool aNode(const Node& node) {
1.319 - return (node.id & 1) == 0;
1.320 - }
1.321 -
1.322 - static bool bNode(const Node& node) {
1.323 - return (node.id & 1) == 1;
1.324 - }
1.325 -
1.326 - Node addANode() {
1.327 - int aNodeId;
1.328 - if (first_free_anode == -1) {
1.329 - aNodeId = aNodes.size();
1.330 - aNodes.push_back(NodeT());
1.331 - } else {
1.332 - aNodeId = first_free_anode;
1.333 - first_free_anode = aNodes[first_free_anode].next;
1.334 - }
1.335 - if (first_anode != -1) {
1.336 - aNodes[aNodeId].next = first_anode << 1;
1.337 - aNodes[first_anode].prev = aNodeId << 1;
1.338 - } else {
1.339 - aNodes[aNodeId].next = -1;
1.340 - }
1.341 - aNodes[aNodeId].prev = -1;
1.342 - first_anode = aNodeId;
1.343 - aNodes[aNodeId].first_edge = -1;
1.344 - return Node(aNodeId << 1);
1.345 - }
1.346 -
1.347 - Node addBNode() {
1.348 - int bNodeId;
1.349 - if (first_free_bnode == -1) {
1.350 - bNodeId = bNodes.size();
1.351 - bNodes.push_back(NodeT());
1.352 - } else {
1.353 - bNodeId = first_free_bnode;
1.354 - first_free_bnode = bNodes[first_free_bnode].next;
1.355 - }
1.356 - if (first_bnode != -1) {
1.357 - bNodes[bNodeId].next = (first_bnode << 1) + 1;
1.358 - bNodes[first_bnode].prev = (bNodeId << 1) + 1;
1.359 - } else {
1.360 - bNodes[bNodeId].next = -1;
1.361 - }
1.362 - first_bnode = bNodeId;
1.363 - bNodes[bNodeId].first_edge = -1;
1.364 - return Node((bNodeId << 1) + 1);
1.365 - }
1.366 -
1.367 - UEdge addEdge(const Node& source, const Node& target) {
1.368 - LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1.369 - int edgeId;
1.370 - if (first_free_edge != -1) {
1.371 - edgeId = first_free_edge;
1.372 - first_free_edge = edges[edgeId].next_out;
1.373 - } else {
1.374 - edgeId = edges.size();
1.375 - edges.push_back(UEdgeT());
1.376 - }
1.377 - if ((source.id & 1) == 0) {
1.378 - edges[edgeId].aNode = source.id;
1.379 - edges[edgeId].bNode = target.id;
1.380 - } else {
1.381 - edges[edgeId].aNode = target.id;
1.382 - edges[edgeId].bNode = source.id;
1.383 - }
1.384 - edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1.385 - edges[edgeId].prev_out = -1;
1.386 - if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1.387 - edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1.388 - }
1.389 - aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1.390 - edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1.391 - edges[edgeId].prev_in = -1;
1.392 - if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1.393 - edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1.394 - }
1.395 - bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1.396 - return UEdge(edgeId);
1.397 - }
1.398 -
1.399 - void erase(const Node& node) {
1.400 - if (aNode(node)) {
1.401 - int aNodeId = node.id >> 1;
1.402 - if (aNodes[aNodeId].prev != -1) {
1.403 - aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
1.404 - } else {
1.405 - first_anode = aNodes[aNodeId].next >> 1;
1.406 - }
1.407 - if (aNodes[aNodeId].next != -1) {
1.408 - aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
1.409 - }
1.410 - aNodes[aNodeId].next = first_free_anode;
1.411 - first_free_anode = aNodeId;
1.412 - } else {
1.413 - int bNodeId = node.id >> 1;
1.414 - if (bNodes[bNodeId].prev != -1) {
1.415 - bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
1.416 - } else {
1.417 - first_bnode = bNodes[bNodeId].next >> 1;
1.418 - }
1.419 - if (bNodes[bNodeId].next != -1) {
1.420 - bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
1.421 - }
1.422 - bNodes[bNodeId].next = first_free_bnode;
1.423 - first_free_bnode = bNodeId;
1.424 - }
1.425 - }
1.426 -
1.427 - void erase(const UEdge& edge) {
1.428 -
1.429 - if (edges[edge.id].prev_out != -1) {
1.430 - edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1.431 - } else {
1.432 - aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1.433 - }
1.434 - if (edges[edge.id].next_out != -1) {
1.435 - edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1.436 - }
1.437 -
1.438 - if (edges[edge.id].prev_in != -1) {
1.439 - edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1.440 - } else {
1.441 - bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1.442 - }
1.443 - if (edges[edge.id].next_in != -1) {
1.444 - edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1.445 - }
1.446 -
1.447 - edges[edge.id].next_out = first_free_edge;
1.448 - first_free_edge = edge.id;
1.449 - }
1.450 -
1.451 - void clear() {
1.452 - aNodes.clear();
1.453 - bNodes.clear();
1.454 - edges.clear();
1.455 - first_anode = -1;
1.456 - first_free_anode = -1;
1.457 - first_bnode = -1;
1.458 - first_free_bnode = -1;
1.459 - first_free_edge = -1;
1.460 - }
1.461 -
1.462 - };
1.463 -
1.464 -
1.465 - typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
1.466 -
1.467 - /// \ingroup graphs
1.468 - ///
1.469 - /// \brief A smart bipartite undirected graph class.
1.470 - ///
1.471 - /// This is a bipartite undirected graph implementation.
1.472 - /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
1.473 - /// concept.
1.474 - /// \sa concept::BpUGraph.
1.475 - ///
1.476 - class ListBpUGraph : public ExtendedListBpUGraphBase {};
1.477 -
1.478 -
1.479 - /// @}
1.480 } //namespace lemon
1.481
1.482