Dijkstra, bin_heap, fib_heap added to the doc.
1 @node The Full Feature Graph Class
2 @section The Full Feature Graph Class
3 @cindex Full Feature Graph Class
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.
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
13 @subsection Declaration
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.
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.
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.
40 for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum;
43 Using @code{NodeIt} the last line looks like this.
46 for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum;
53 for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum;
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
66 @c @mref{Graph-NodeIterator,@code{EdgeIterator}}
67 @mref{Graph-NodeIterator , EdgeIterator}
69 @code{EdgeIt} requires the graph structure itself for most of the
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
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.
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.
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.
99 @subsection Member Functions
101 @subsubsection Constructors
103 @deftypefun { } Graph::Graph ()
104 The default constructor.
107 @c @deftypefun { } Graph::Graph (Graph@tie{}&)
108 @deftypefun { } Graph::Graph (Graph &)
109 The copy constructor.
112 @subsubsection Graph Maintenence Operations
114 @deftypefun NodeIt Graph::addNode ()
115 Adds a new node to the graph and returns a @code{NodeIt} pointing to it.
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.
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.
127 @deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIt} @var{e}})
128 Deletes the edge @var{n}.
131 @deftypefun void Graph::clear ()
132 Deletes all edges and nodes from the graph.
135 @deftypefun int Graph::nodeNum ()
136 Returns the number of the nodes in the graph.
137 ??? Is it necessary???
140 @subsubsection NodeIt Operations
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 ???
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 ???
157 @subsubsection EdgeIt Operations
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 ???
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
174 list. These functions give back the first elements of these
175 lists. The exact behavior depends on the type of @var{e}.
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.
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.
185 If there are no such edges, @var{e} will be invalid.
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}
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
200 ??? What should be the return value ???
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 ???
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.
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}.
228 @code{bNode(e)} is the other end of the edge.
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.
235 @c ???It is implemented in an other way now. (Member function <-> Graph global)???
240 @c @deftypevar int from
241 @c the tail of the created edge.