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 | @deftp {Type} Graph::NodeType |
---|
25 | @deftpx {Type} Graph::EdgeType |
---|
26 | The type of the data stored statically for each node and edge. |
---|
27 | @end deftp |
---|
28 | |
---|
29 | @anchor{Graph-NodeIterator} |
---|
30 | @deftp {Type} Graph::NodeIt |
---|
31 | @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::BiEdgeIt |
---|
62 | @deftpx {Type} Graph::SymEdgeIt |
---|
63 | Each of these types points an edge uniquely. The difference between the |
---|
64 | @code{EdgeIt} and the |
---|
65 | @c @mref{Graph-NodeIterator,@code{EdgeIterator}} |
---|
66 | @mref{Graph-NodeIterator , EdgeIterator} |
---|
67 | series is that |
---|
68 | @code{EdgeIt} requires the graph structure itself for most of the |
---|
69 | operations. |
---|
70 | @end deftp |
---|
71 | |
---|
72 | @anchor{Graph-EdgeIterator} |
---|
73 | @deftp {Type} Graph::EdgeIterator |
---|
74 | @deftpx {Type} Graph::InEdgeIterator |
---|
75 | @deftpx {Type} Graph::OutEdgeIterator |
---|
76 | @deftpx {Type} Graph::BiEdgeIterator |
---|
77 | @deftpx {Type} Graph::SymEdgeIterator |
---|
78 | @deftpx {Type} Graph::EachEdgeIterator |
---|
79 | Each of these types points an edge uniquely. The difference between the |
---|
80 | @code{EdgeIt} and the @code{EdgeIterator} series is that |
---|
81 | @code{EdgeIt} requires the graph structure itself for most of the |
---|
82 | operations. |
---|
83 | |
---|
84 | For the @code{EdgeIterator} types you can use operator @code{++} |
---|
85 | (both the prefix and the posfix one) to obtain the next edge. |
---|
86 | @end deftp |
---|
87 | |
---|
88 | @deftp {Type} Graph::NodeMap |
---|
89 | @deftpx {Type} Graph::EdgeMap |
---|
90 | There are the default property maps for the edges and the nodes. |
---|
91 | @end deftp |
---|
92 | |
---|
93 | |
---|
94 | @subsection Member Functions |
---|
95 | |
---|
96 | @subsubsection Constructors |
---|
97 | |
---|
98 | |
---|
99 | @deftypefun { } Graph::Graph () |
---|
100 | The default constructor. |
---|
101 | @end deftypefun |
---|
102 | |
---|
103 | @c @deftypefun { } Graph::Graph (Graph@tie{}&) |
---|
104 | @deftypefun { } Graph::Graph (Graph &) |
---|
105 | The copy constructor. Not yet implemented. |
---|
106 | @end deftypefun |
---|
107 | |
---|
108 | @subsubsection Graph Maintenence Operations |
---|
109 | |
---|
110 | @deftypefun NodeIterator Graph::addNode () |
---|
111 | Adds a new node to the graph and returns a @code{NodeIterator} pointing to it. |
---|
112 | @end deftypefun |
---|
113 | |
---|
114 | @deftypefun EdgeIterator Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}}) |
---|
115 | Adds a new edge with tail @var{from} and head @var{to} to the graph |
---|
116 | and returns an @code{EdgeIterator} pointing to it. |
---|
117 | @end deftypefun |
---|
118 | |
---|
119 | @deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}}) |
---|
120 | Deletes the node @var{n}. It also deletes the adjacent edges. |
---|
121 | @end deftypefun |
---|
122 | |
---|
123 | @deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}}) |
---|
124 | Deletes the edge @var{n}. |
---|
125 | @end deftypefun |
---|
126 | |
---|
127 | @deftypefun void Graph::clean () |
---|
128 | Deletes all edges and nodes from the graph. |
---|
129 | @end deftypefun |
---|
130 | |
---|
131 | @deftypefun int Graph::nodeNum () |
---|
132 | Returns the number of the nodes in the graph. |
---|
133 | @end deftypefun |
---|
134 | |
---|
135 | @subsubsection NodeIt Operations |
---|
136 | |
---|
137 | @deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) |
---|
138 | @deftypefunx NodeIt Graph::next (const NodeIt @var{n}) |
---|
139 | @deftypefunx {NodeIt &} Graph::goNext (NodeIt &@var{n}) |
---|
140 | The nodes in the graph forms a list. @code{GetFirst(n)} sets @var{n} to |
---|
141 | be the first node. @code{next(n)} gives back the subsequent |
---|
142 | node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it |
---|
143 | might be faster. ??? What should be the return value ??? |
---|
144 | @end deftypefun |
---|
145 | |
---|
146 | @deftypefun bool Graph::valid (NodeIt &@var{e}) |
---|
147 | @deftypefunx bool NodeIt::valid () |
---|
148 | These functions check if and NodeIt is valid or not. |
---|
149 | ??? Which one should be implemented ??? |
---|
150 | @end deftypefun |
---|
151 | |
---|
152 | @subsubsection EdgeIt Operations |
---|
153 | |
---|
154 | @deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) |
---|
155 | @deftypefunx EachEdgeIt Graph::next (const EachEdgeIt @var{n}) |
---|
156 | @deftypefunx {EachEdgeIt &} Graph::goNext (EachEdgeIt &@var{n}) |
---|
157 | With these functions you can go though all the edges of the graph. |
---|
158 | ??? What should be the return value ??? |
---|
159 | @end deftypefun |
---|
160 | |
---|
161 | @deftypefun InEdgeIt Graph::getFirst (const InEdgeIt & @var{e}, const NodeIt @var{n}) |
---|
162 | @deftypefunx OutEdgeIt Graph::getFirst (const OutEdgeIt & @var{e}, const NodeIt @var{n}) |
---|
163 | @deftypefunx SymEdgeIt Graph::getFirst (const SymEdgeIt & @var{e}, const NodeIt @var{n}) |
---|
164 | The edges leaving from, arriving at or adjacent with a node forms a |
---|
165 | list. These functions give back the first elements of these |
---|
166 | lists. The exact behavior depends on the type of @var{e}. |
---|
167 | |
---|
168 | If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then |
---|
169 | @code{getFirst} sets @var{e} to be the first incoming or outgoing edge |
---|
170 | of the node @var{n}, respectively. |
---|
171 | |
---|
172 | If @var{e} is a @code{SymEdgeIt} then |
---|
173 | @code{getFirst} sets @var{e} to be the first incoming if there exists one |
---|
174 | otherwise the first outgoing edge. |
---|
175 | |
---|
176 | If there are no such edges, @var{e} will be invalid. |
---|
177 | |
---|
178 | @end deftypefun |
---|
179 | |
---|
180 | @deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e}) |
---|
181 | @deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e}) |
---|
182 | @deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e}) |
---|
183 | These functions give back the edge that follows @var{e} |
---|
184 | @end deftypefun |
---|
185 | |
---|
186 | @deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e}) |
---|
187 | @deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e}) |
---|
188 | @deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e}) |
---|
189 | @code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it |
---|
190 | might be faster. |
---|
191 | ??? What should be the return value ??? |
---|
192 | @end deftypefun |
---|
193 | |
---|
194 | @deftypefun bool Graph::valid (EdgeIt &@var{e}) |
---|
195 | @deftypefunx bool EdgeIt::valid () |
---|
196 | These functions check if and EdgeIt is valid or not. |
---|
197 | ??? Which one should be implemented ??? |
---|
198 | @end deftypefun |
---|
199 | |
---|
200 | @deftypefun NodeIt Graph::tail (const EdgeIt @var{e}) |
---|
201 | @deftypefunx NodeIt Graph::head (const EdgeIt @var{e}) |
---|
202 | @deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e}) |
---|
203 | @deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e}) |
---|
204 | @deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e}) |
---|
205 | @deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e}) |
---|
206 | @deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e}) |
---|
207 | @deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e}) |
---|
208 | There queries give back the two endpoints of the edge @var{e}. For a |
---|
209 | directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and |
---|
210 | its head, respectively. For an undirected @var{e}, they are two |
---|
211 | endpoints, but you should not rely on which end is which. |
---|
212 | |
---|
213 | @code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is |
---|
214 | equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and |
---|
215 | @code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a |
---|
216 | @code{SymEdgeIt} and it or its first preceding edge was created by |
---|
217 | @code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}. |
---|
218 | |
---|
219 | @code{bNode(e)} is the other end of the edge. |
---|
220 | |
---|
221 | ???It is implemented in an other way now. (Member function <-> Graph global)??? |
---|
222 | @end deftypefun |
---|
223 | |
---|
224 | |
---|
225 | |
---|
226 | @c @deftypevar int from |
---|
227 | @c the tail of the created edge. |
---|
228 | @c @end deftypevar |
---|