1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_LIST_UGRAPH_H |
|
20 #define LEMON_LIST_UGRAPH_H |
|
21 |
|
22 ///\ingroup graphs |
|
23 ///\file |
|
24 ///\brief ListUGraph classes. |
|
25 |
|
26 #include <lemon/list_graph.h> |
|
27 #include <lemon/bits/base_extender.h> |
|
28 #include <lemon/bits/ugraph_extender.h> |
|
29 |
|
30 #include <vector> |
|
31 #include <list> |
|
32 |
|
33 namespace lemon { |
|
34 |
|
35 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > |
|
36 ExtendedListUGraphBase; |
|
37 |
|
38 /// \ingroup graphs |
|
39 |
|
40 ///An undirected list graph class. |
|
41 |
|
42 ///This is a simple and fast erasable undirected graph implementation. |
|
43 /// |
|
44 ///It conforms to the |
|
45 ///\ref concept::UGraph "UGraph" concept. |
|
46 /// |
|
47 ///\sa concept::UGraph. |
|
48 /// |
|
49 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() |
|
50 ///haven't been implemented yet. |
|
51 /// |
|
52 class ListUGraph : public ExtendedListUGraphBase { |
|
53 public: |
|
54 typedef ExtendedListUGraphBase Parent; |
|
55 /// \brief Add a new node to the graph. |
|
56 /// |
|
57 /// \return the new node. |
|
58 /// |
|
59 Node addNode() { return Parent::addNode(); } |
|
60 |
|
61 /// \brief Add a new edge to the graph. |
|
62 /// |
|
63 /// Add a new edge to the graph with source node \c s |
|
64 /// and target node \c t. |
|
65 /// \return the new undirected edge. |
|
66 UEdge addEdge(const Node& s, const Node& t) { |
|
67 return Parent::addEdge(s, t); |
|
68 } |
|
69 /// \brief Changes the target of \c e to \c n |
|
70 /// |
|
71 /// Changes the target of \c e to \c n |
|
72 /// |
|
73 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
|
74 /// referencing the changed edge remain |
|
75 /// valid. However <tt>InEdge</tt>'s are invalidated. |
|
76 void changeTarget(UEdge e, Node n) { |
|
77 Parent::changeTarget(e,n); |
|
78 } |
|
79 /// Changes the source of \c e to \c n |
|
80 /// |
|
81 /// Changes the source of \c e to \c n |
|
82 /// |
|
83 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
|
84 ///referencing the changed edge remain |
|
85 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
|
86 void changeSource(UEdge e, Node n) { |
|
87 Parent::changeSource(e,n); |
|
88 } |
|
89 /// \brief Contract two nodes. |
|
90 /// |
|
91 /// This function contracts two nodes. |
|
92 /// |
|
93 /// Node \p b will be removed but instead of deleting |
|
94 /// its neighboring edges, they will be joined to \p a. |
|
95 /// The last parameter \p r controls whether to remove loops. \c true |
|
96 /// means that loops will be removed. |
|
97 /// |
|
98 /// \note The <tt>Edge</tt>s |
|
99 /// referencing a moved edge remain |
|
100 /// valid. |
|
101 void contract(Node a, Node b, bool r = true) { |
|
102 for(IncEdgeIt e(*this, b); e!=INVALID;) { |
|
103 IncEdgeIt f = e; ++f; |
|
104 if (r && runningNode(e) == a) { |
|
105 erase(e); |
|
106 } else if (source(e) == b) { |
|
107 changeSource(e, a); |
|
108 } else { |
|
109 changeTarget(e, a); |
|
110 } |
|
111 e = f; |
|
112 } |
|
113 erase(b); |
|
114 } |
|
115 }; |
|
116 |
|
117 } //namespace lemon |
|
118 |
|
119 |
|
120 #endif |
|