1 @node The Full Feature Graph Class |
|
2 @section The Full Feature Graph Class |
|
3 @cindex Full Feature Graph Class |
|
4 |
|
5 This section describes what an imaginary full feature graph class knows. |
|
6 The set of features provided by a real graph implementation is typically |
|
7 a subset of the features below. |
|
8 |
|
9 On the other hand, each graph algorithm requires the underlying graph |
|
10 structure to provide a certain (typically small) set of features in order |
|
11 to be able to run. |
|
12 |
|
13 @subsection Declaration |
|
14 |
|
15 @deftp {Class} {class Graph} |
|
16 @code{Graph} is the imaginary @emph{full feature graph class}. |
|
17 @code{G} denotes the instance of this class in the exaples below. |
|
18 @c Each node and edge has a user defined data sturcure |
|
19 @c @var{N} and @var{E} statically attached to it. |
|
20 @end deftp |
|
21 |
|
22 @subsection Types |
|
23 |
|
24 @c @deftp {Type} Graph::NodeType |
|
25 @c @deftpx {Type} Graph::EdgeType |
|
26 @c The type of the data stored statically for each node and edge. |
|
27 @c @end deftp |
|
28 |
|
29 @anchor{Graph-NodeIterator} |
|
30 @deftp {Type} Graph::NodeIt |
|
31 @c @deftpx {Type} Graph::NodeIterator |
|
32 These types points a node uniquely. The difference between the |
|
33 @code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt} |
|
34 requires the graph structure itself for most of the operations. |
|
35 For examples using iterators you can go through all nodes as follows. |
|
36 @quotation |
|
37 @verbatim |
|
38 Graph G; |
|
39 int nodenum=0; |
|
40 for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum; |
|
41 @end verbatim |
|
42 @end quotation |
|
43 Using @code{NodeIt} the last line looks like this. |
|
44 @quotation |
|
45 @verbatim |
|
46 for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum; |
|
47 @end verbatim |
|
48 @end quotation |
|
49 or |
|
50 @quotation |
|
51 @verbatim |
|
52 MyGraph::NodeIt n; |
|
53 for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum; |
|
54 @end verbatim |
|
55 @end quotation |
|
56 @end deftp |
|
57 |
|
58 @deftp {Type} Graph::EdgeIt |
|
59 @deftpx {Type} Graph::InEdgeIt |
|
60 @deftpx {Type} Graph::OutEdgeIt |
|
61 @deftpx {Type} Graph::EachEdgeIt |
|
62 @c @deftpx {Type} Graph::BiEdgeIt |
|
63 @c @deftpx {Type} Graph::SymEdgeIt |
|
64 Each of these types points an edge uniquely. The difference between the |
|
65 @code{EdgeIt} and the |
|
66 @c @mref{Graph-NodeIterator,@code{EdgeIterator}} |
|
67 @mref{Graph-NodeIterator , EdgeIterator} |
|
68 series is that |
|
69 @code{EdgeIt} requires the graph structure itself for most of the |
|
70 operations. |
|
71 @end deftp |
|
72 |
|
73 @anchor{Graph-EdgeIterator} |
|
74 @c @deftp {Type} Graph::EdgeIterator |
|
75 @c @deftpx {Type} Graph::InEdgeIterator |
|
76 @c @deftpx {Type} Graph::OutEdgeIterator |
|
77 @c @deftpx {Type} Graph::BiEdgeIterator |
|
78 @c @deftpx {Type} Graph::SymEdgeIterator |
|
79 @c @deftpx {Type} Graph::EachEdgeIterator |
|
80 @c Each of these types points an edge uniquely. The difference between the |
|
81 @c @code{EdgeIt} and the @code{EdgeIterator} series is that |
|
82 @c @code{EdgeIt} requires the graph structure itself for most of the |
|
83 @c operations. |
|
84 |
|
85 @c For the @code{EdgeIterator} types you can use operator @code{++} |
|
86 @c (both the prefix and the posfix one) to obtain the next edge. |
|
87 @c @end deftp |
|
88 |
|
89 @deftp {Type} Graph::NodeMap<typename T> |
|
90 @deftpx {Type} Graph::EdgeMap<typename T> |
|
91 There are the default property maps for the edges and the nodes. |
|
92 @end deftp |
|
93 |
|
94 @deftp {Type} Graph::DynNodeMap<typename T> |
|
95 @deftpx {Type} Graph::DynEdgeMap<typename T> |
|
96 There are the default @emph{dynamic} property maps for the edges and the nodes. |
|
97 @end deftp |
|
98 |
|
99 @subsection Member Functions |
|
100 |
|
101 @subsubsection Constructors |
|
102 |
|
103 @deftypefun { } Graph::Graph () |
|
104 The default constructor. |
|
105 @end deftypefun |
|
106 |
|
107 @c @deftypefun { } Graph::Graph (Graph@tie{}&) |
|
108 @deftypefun { } Graph::Graph (Graph &) |
|
109 The copy constructor. |
|
110 @end deftypefun |
|
111 |
|
112 @subsubsection Graph Maintenence Operations |
|
113 |
|
114 @deftypefun NodeIt Graph::addNode () |
|
115 Adds a new node to the graph and returns a @code{NodeIt} pointing to it. |
|
116 @end deftypefun |
|
117 |
|
118 @deftypefun EdgeIt Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIt} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIt} @var{to}}) |
|
119 Adds a new edge with tail @var{from} and head @var{to} to the graph |
|
120 and returns an @code{EdgeIt} pointing to it. |
|
121 @end deftypefun |
|
122 |
|
123 @deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIt} @var{n}}) |
|
124 Deletes the node @var{n}. It also deletes the adjacent edges. |
|
125 @end deftypefun |
|
126 |
|
127 @deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIt} @var{e}}) |
|
128 Deletes the edge @var{n}. |
|
129 @end deftypefun |
|
130 |
|
131 @deftypefun void Graph::clear () |
|
132 Deletes all edges and nodes from the graph. |
|
133 @end deftypefun |
|
134 |
|
135 @deftypefun int Graph::nodeNum () |
|
136 Returns the number of the nodes in the graph. |
|
137 ??? Is it necessary??? |
|
138 @end deftypefun |
|
139 |
|
140 @subsubsection NodeIt Operations |
|
141 |
|
142 @deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) const |
|
143 @deftypefunx NodeIt Graph::getNext (NodeIt @var{n}) const |
|
144 @deftypefunx {NodeIt &} Graph::next (NodeIt &@var{n}) |
|
145 The nodes in the graph forms a list. @code{getFirst(n)} sets @var{n} to |
|
146 be the first node. @code{getNext(n)} gives back the subsequent |
|
147 node. @code{next(n)} is equivalent to @code{n=getNext(n)}, though it |
|
148 might be faster. ??? What should be the return value ??? |
|
149 @end deftypefun |
|
150 |
|
151 @deftypefun bool Graph::valid (NodeIt &@var{e}) |
|
152 @c @deftypefunx bool NodeIt::valid () |
|
153 These functions check if and NodeIt is valid or not. |
|
154 @c ??? Which one should be implemented ??? |
|
155 @end deftypefun |
|
156 |
|
157 @subsubsection EdgeIt Operations |
|
158 |
|
159 @deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) const |
|
160 @deftypefunx EachEdgeIt Graph::getNext (EachEdgeIt @var{n}) const |
|
161 @deftypefunx {EachEdgeIt &} Graph::next (EachEdgeIt &@var{n}) |
|
162 With these functions you can go though all the edges of the graph. |
|
163 @c ??? What should be the return value ??? |
|
164 @end deftypefun |
|
165 |
|
166 @deftypefun InEdgeIt &Graph::getFirst (InEdgeIt & @var{e}, const NodeIt @var{n}) |
|
167 @deftypefunx OutEdgeIt &Graph::getFirst (OutEdgeIt & @var{e}, const NodeIt @var{n}) |
|
168 @c @deftypefunx SymEdgeIt &Graph::getFirst (SymEdgeIt & @var{e}, const NodeIt @var{n}) |
|
169 The edges leaving from |
|
170 or |
|
171 arriving at |
|
172 @c or adjacent with |
|
173 a node forms a |
|
174 list. These functions give back the first elements of these |
|
175 lists. The exact behavior depends on the type of @var{e}. |
|
176 |
|
177 If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then |
|
178 @code{getFirst} sets @var{e} to be the first incoming or outgoing edge |
|
179 of the node @var{n}, respectively. |
|
180 |
|
181 @c If @var{e} is a @code{SymEdgeIt} then |
|
182 @c @code{getFirst} sets @var{e} to be the first incoming if there exists one |
|
183 @c otherwise the first outgoing edge. |
|
184 |
|
185 If there are no such edges, @var{e} will be invalid. |
|
186 |
|
187 @end deftypefun |
|
188 |
|
189 @deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e}) |
|
190 @deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e}) |
|
191 @deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e}) |
|
192 These functions give back the edge that follows @var{e} |
|
193 @end deftypefun |
|
194 |
|
195 @deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e}) |
|
196 @deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e}) |
|
197 @deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e}) |
|
198 @code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it |
|
199 might be faster. |
|
200 ??? What should be the return value ??? |
|
201 @end deftypefun |
|
202 |
|
203 @deftypefun bool Graph::valid (EdgeIt &@var{e}) |
|
204 @deftypefunx bool EdgeIt::valid () |
|
205 These functions check if and EdgeIt is valid or not. |
|
206 ??? Which one should be implemented ??? |
|
207 @end deftypefun |
|
208 |
|
209 @deftypefun NodeIt Graph::tail (const EdgeIt @var{e}) |
|
210 @deftypefunx NodeIt Graph::head (const EdgeIt @var{e}) |
|
211 @deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e}) |
|
212 @deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e}) |
|
213 @deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e}) |
|
214 @deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e}) |
|
215 @deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e}) |
|
216 @deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e}) |
|
217 There queries give back the two endpoints of the edge @var{e}. For a |
|
218 directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and |
|
219 its head, respectively. For an undirected @var{e}, they are two |
|
220 endpoints, but you should not rely on which end is which. |
|
221 |
|
222 @code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is |
|
223 equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and |
|
224 @code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a |
|
225 @code{SymEdgeIt} and it or its first preceding edge was created by |
|
226 @code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}. |
|
227 |
|
228 @code{bNode(e)} is the other end of the edge. |
|
229 |
|
230 @deftypefun void Graph::setInvalid (EdgeIt &@var{e}) |
|
231 @deftypefunx void Graph::setInvalid (EdgeIt &@var{e}) |
|
232 These functions set the corresponding iterator to be invalid. |
|
233 @end deftypefun |
|
234 |
|
235 @c ???It is implemented in an other way now. (Member function <-> Graph global)??? |
|
236 @end deftypefun |
|
237 |
|
238 |
|
239 |
|
240 @c @deftypevar int from |
|
241 @c the tail of the created edge. |
|
242 @c @end deftypevar |
|