[18] | 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 | |
---|
[203] | 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 |
---|
[18] | 28 | |
---|
| 29 | @anchor{Graph-NodeIterator} |
---|
[70] | 30 | @deftp {Type} Graph::NodeIt |
---|
[203] | 31 | @c @deftpx {Type} Graph::NodeIterator |
---|
[18] | 32 | These types points a node uniquely. The difference between the |
---|
[70] | 33 | @code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt} |
---|
[18] | 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; |
---|
[70] | 40 | for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum; |
---|
[18] | 41 | @end verbatim |
---|
| 42 | @end quotation |
---|
[70] | 43 | Using @code{NodeIt} the last line looks like this. |
---|
[18] | 44 | @quotation |
---|
| 45 | @verbatim |
---|
[70] | 46 | for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum; |
---|
[18] | 47 | @end verbatim |
---|
| 48 | @end quotation |
---|
| 49 | or |
---|
| 50 | @quotation |
---|
| 51 | @verbatim |
---|
[70] | 52 | MyGraph::NodeIt n; |
---|
| 53 | for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum; |
---|
[18] | 54 | @end verbatim |
---|
| 55 | @end quotation |
---|
| 56 | @end deftp |
---|
| 57 | |
---|
[70] | 58 | @deftp {Type} Graph::EdgeIt |
---|
| 59 | @deftpx {Type} Graph::InEdgeIt |
---|
| 60 | @deftpx {Type} Graph::OutEdgeIt |
---|
[203] | 61 | @deftpx {Type} Graph::EachEdgeIt |
---|
| 62 | @c @deftpx {Type} Graph::BiEdgeIt |
---|
| 63 | @c @deftpx {Type} Graph::SymEdgeIt |
---|
[18] | 64 | Each of these types points an edge uniquely. The difference between the |
---|
[70] | 65 | @code{EdgeIt} and the |
---|
[18] | 66 | @c @mref{Graph-NodeIterator,@code{EdgeIterator}} |
---|
| 67 | @mref{Graph-NodeIterator , EdgeIterator} |
---|
| 68 | series is that |
---|
[70] | 69 | @code{EdgeIt} requires the graph structure itself for most of the |
---|
[18] | 70 | operations. |
---|
| 71 | @end deftp |
---|
| 72 | |
---|
| 73 | @anchor{Graph-EdgeIterator} |
---|
[203] | 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. |
---|
[18] | 84 | |
---|
[203] | 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 |
---|
[18] | 88 | |
---|
[203] | 89 | @deftp {Type} Graph::NodeMap<typename T> |
---|
| 90 | @deftpx {Type} Graph::EdgeMap<typename T> |
---|
[18] | 91 | There are the default property maps for the edges and the nodes. |
---|
| 92 | @end deftp |
---|
| 93 | |
---|
[203] | 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 |
---|
[18] | 98 | |
---|
| 99 | @subsection Member Functions |
---|
| 100 | |
---|
| 101 | @subsubsection Constructors |
---|
| 102 | |
---|
| 103 | @deftypefun { } Graph::Graph () |
---|
| 104 | The default constructor. |
---|
| 105 | @end deftypefun |
---|
| 106 | |
---|
[26] | 107 | @c @deftypefun { } Graph::Graph (Graph@tie{}&) |
---|
| 108 | @deftypefun { } Graph::Graph (Graph &) |
---|
[203] | 109 | The copy constructor. |
---|
[18] | 110 | @end deftypefun |
---|
| 111 | |
---|
| 112 | @subsubsection Graph Maintenence Operations |
---|
| 113 | |
---|
[203] | 114 | @deftypefun NodeIt Graph::addNode () |
---|
| 115 | Adds a new node to the graph and returns a @code{NodeIt} pointing to it. |
---|
[18] | 116 | @end deftypefun |
---|
| 117 | |
---|
[203] | 118 | @deftypefun EdgeIt Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIt} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIt} @var{to}}) |
---|
[18] | 119 | Adds a new edge with tail @var{from} and head @var{to} to the graph |
---|
[203] | 120 | and returns an @code{EdgeIt} pointing to it. |
---|
[18] | 121 | @end deftypefun |
---|
| 122 | |
---|
[203] | 123 | @deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIt} @var{n}}) |
---|
[18] | 124 | Deletes the node @var{n}. It also deletes the adjacent edges. |
---|
| 125 | @end deftypefun |
---|
| 126 | |
---|
[203] | 127 | @deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIt} @var{e}}) |
---|
[18] | 128 | Deletes the edge @var{n}. |
---|
| 129 | @end deftypefun |
---|
| 130 | |
---|
[203] | 131 | @deftypefun void Graph::clear () |
---|
[18] | 132 | Deletes all edges and nodes from the graph. |
---|
| 133 | @end deftypefun |
---|
| 134 | |
---|
[70] | 135 | @deftypefun int Graph::nodeNum () |
---|
[18] | 136 | Returns the number of the nodes in the graph. |
---|
[203] | 137 | ??? Is it necessary??? |
---|
[18] | 138 | @end deftypefun |
---|
| 139 | |
---|
[70] | 140 | @subsubsection NodeIt Operations |
---|
[18] | 141 | |
---|
[203] | 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 |
---|
[18] | 148 | might be faster. ??? What should be the return value ??? |
---|
| 149 | @end deftypefun |
---|
| 150 | |
---|
[70] | 151 | @deftypefun bool Graph::valid (NodeIt &@var{e}) |
---|
[203] | 152 | @c @deftypefunx bool NodeIt::valid () |
---|
[70] | 153 | These functions check if and NodeIt is valid or not. |
---|
[203] | 154 | @c ??? Which one should be implemented ??? |
---|
[18] | 155 | @end deftypefun |
---|
| 156 | |
---|
[70] | 157 | @subsubsection EdgeIt Operations |
---|
[18] | 158 | |
---|
[203] | 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}) |
---|
[18] | 162 | With these functions you can go though all the edges of the graph. |
---|
[203] | 163 | @c ??? What should be the return value ??? |
---|
[18] | 164 | @end deftypefun |
---|
| 165 | |
---|
[203] | 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 |
---|
[18] | 174 | list. These functions give back the first elements of these |
---|
| 175 | lists. The exact behavior depends on the type of @var{e}. |
---|
| 176 | |
---|
[70] | 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 |
---|
[18] | 179 | of the node @var{n}, respectively. |
---|
| 180 | |
---|
[203] | 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. |
---|
[18] | 184 | |
---|
| 185 | If there are no such edges, @var{e} will be invalid. |
---|
| 186 | |
---|
| 187 | @end deftypefun |
---|
| 188 | |
---|
[70] | 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}) |
---|
[18] | 192 | These functions give back the edge that follows @var{e} |
---|
| 193 | @end deftypefun |
---|
| 194 | |
---|
[70] | 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 |
---|
[18] | 199 | might be faster. |
---|
| 200 | ??? What should be the return value ??? |
---|
| 201 | @end deftypefun |
---|
| 202 | |
---|
[70] | 203 | @deftypefun bool Graph::valid (EdgeIt &@var{e}) |
---|
| 204 | @deftypefunx bool EdgeIt::valid () |
---|
| 205 | These functions check if and EdgeIt is valid or not. |
---|
[18] | 206 | ??? Which one should be implemented ??? |
---|
| 207 | @end deftypefun |
---|
| 208 | |
---|
[70] | 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}) |
---|
[18] | 217 | There queries give back the two endpoints of the edge @var{e}. For a |
---|
[70] | 218 | directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and |
---|
[18] | 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 | |
---|
[70] | 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}. |
---|
[18] | 227 | |
---|
[70] | 228 | @code{bNode(e)} is the other end of the edge. |
---|
[18] | 229 | |
---|
[203] | 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)??? |
---|
[18] | 236 | @end deftypefun |
---|
| 237 | |
---|
| 238 | |
---|
| 239 | |
---|
| 240 | @c @deftypevar int from |
---|
| 241 | @c the tail of the created edge. |
---|
| 242 | @c @end deftypevar |
---|