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