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