1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/flf-graph.texi Tue Jan 20 11:21:42 2004 +0000
1.3 @@ -0,0 +1,227 @@
1.4 +@node The Full Feature Graph Class
1.5 +@section The Full Feature Graph Class
1.6 +@cindex Full Feature Graph Class
1.7 +
1.8 +This section describes what an imaginary full feature graph class knows.
1.9 +The set of features provided by a real graph implementation is typically
1.10 +a subset of the features below.
1.11 +
1.12 +On the other hand, each graph algorithm requires the underlying graph
1.13 +structure to provide a certain (typically small) set of features in order
1.14 +to be able to run.
1.15 +
1.16 +@subsection Declaration
1.17 +
1.18 +@deftp {Class} {class Graph}
1.19 +@code{Graph} is the imaginary @emph{full feature graph class}.
1.20 +@code{G} denotes the instance of this class in the exaples below.
1.21 +@c Each node and edge has a user defined data sturcure
1.22 +@c @var{N} and @var{E} statically attached to it.
1.23 +@end deftp
1.24 +
1.25 +@subsection Types
1.26 +
1.27 +@deftp {Type} Graph::NodeType
1.28 +@deftpx {Type} Graph::EdgeType
1.29 +The type of the data stored statically for each node and edge.
1.30 +@end deftp
1.31 +
1.32 +@anchor{Graph-NodeIterator}
1.33 +@deftp {Type} Graph::NodePoint
1.34 +@deftpx {Type} Graph::NodeIterator
1.35 +These types points a node uniquely. The difference between the
1.36 +@code{NodePoint} and the @code{NodeIterator} is that @code{NodePoint}
1.37 +requires the graph structure itself for most of the operations.
1.38 +For examples using iterators you can go through all nodes as follows.
1.39 +@quotation
1.40 +@verbatim
1.41 +Graph G;
1.42 +int nodenum=0;
1.43 +for(Graph::NodeIterator n(G);n.Valid();++n) ++nodenum;
1.44 +@end verbatim
1.45 +@end quotation
1.46 +Using @code{NodePoint} the last line looks like this.
1.47 +@quotation
1.48 +@verbatim
1.49 +for(MyGraph::NodePoint n(G);n.Valid();n=G.Next(n)) ++nodenum;
1.50 +@end verbatim
1.51 +@end quotation
1.52 +or
1.53 +@quotation
1.54 +@verbatim
1.55 +MyGraph::NodePoint n;
1.56 +for(G.GetFirst(n);G.Valid(n);G.GoNext(n)) ++nodenum;
1.57 +@end verbatim
1.58 +@end quotation
1.59 +@end deftp
1.60 +
1.61 +@deftp {Type} Graph::EdgePoint
1.62 +@deftpx {Type} Graph::InEdgePoint
1.63 +@deftpx {Type} Graph::OutEdgePoint
1.64 +@deftpx {Type} Graph::BiEdgePoint
1.65 +@deftpx {Type} Graph::SymEdgePoint
1.66 +Each of these types points an edge uniquely. The difference between the
1.67 +@code{EdgePoint} and the
1.68 +@c @mref{Graph-NodeIterator,@code{EdgeIterator}}
1.69 +@mref{Graph-NodeIterator , EdgeIterator}
1.70 +series is that
1.71 +@code{EdgePoint} requires the graph structure itself for most of the
1.72 +operations.
1.73 +@end deftp
1.74 +
1.75 +@anchor{Graph-EdgeIterator}
1.76 +@deftp {Type} Graph::EdgeIterator
1.77 +@deftpx {Type} Graph::InEdgeIterator
1.78 +@deftpx {Type} Graph::OutEdgeIterator
1.79 +@deftpx {Type} Graph::BiEdgeIterator
1.80 +@deftpx {Type} Graph::SymEdgeIterator
1.81 +@deftpx {Type} Graph::AllEdgeIterator
1.82 +Each of these types points an edge uniquely. The difference between the
1.83 +@code{EdgePoint} and the @code{EdgeIterator} series is that
1.84 +@code{EdgePoint} requires the graph structure itself for most of the
1.85 +operations.
1.86 +
1.87 +For the @code{EdgeIterator} types you can use operator @code{++}
1.88 +(both the prefix and the posfix one) to obtain the next edge.
1.89 +@end deftp
1.90 +
1.91 +@deftp {Type} Graph::NodeMap
1.92 +@deftpx {Type} Graph::EdgeMap
1.93 +There are the default property maps for the edges and the nodes.
1.94 +@end deftp
1.95 +
1.96 +
1.97 +@subsection Member Functions
1.98 +
1.99 +@subsubsection Constructors
1.100 +
1.101 +
1.102 +@deftypefun { } Graph::Graph ()
1.103 +The default constructor.
1.104 +@end deftypefun
1.105 +
1.106 +@deftypefun { } Graph::Graph (Graph@tie{}&)
1.107 +The copy constructor. Not yet implemented.
1.108 +@end deftypefun
1.109 +
1.110 +@subsubsection Graph Maintenence Operations
1.111 +
1.112 +@deftypefun NodeIterator Graph::AddNode ()
1.113 +Adds a new node to the graph and returns a @code{NodeIterator} pointing to it.
1.114 +@end deftypefun
1.115 +
1.116 +@deftypefun EdgeIterator Graph::AddEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}})
1.117 +Adds a new edge with tail @var{from} and head @var{to} to the graph
1.118 +and returns an @code{EdgeIterator} pointing to it.
1.119 +@end deftypefun
1.120 +
1.121 +@deftypefun void Graph::Delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}})
1.122 +Deletes the node @var{n}. It also deletes the adjacent edges.
1.123 +@end deftypefun
1.124 +
1.125 +@deftypefun void Graph::Delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}})
1.126 +Deletes the edge @var{n}.
1.127 +@end deftypefun
1.128 +
1.129 +@deftypefun void Graph::Clean ()
1.130 +Deletes all edges and nodes from the graph.
1.131 +@end deftypefun
1.132 +
1.133 +@deftypefun int Graph::NodeNum ()
1.134 +Returns the number of the nodes in the graph.
1.135 +@end deftypefun
1.136 +
1.137 +@subsubsection NodePoint Operations
1.138 +
1.139 +@deftypefun NodePoint Graph::GetFirst (NodePoint &@var{n})
1.140 +@deftypefunx NodePoint Graph::Next (const NodePoint @var{n})
1.141 +@deftypefunx {NodePoint &} Graph::GoNext (NodePoint &@var{n})
1.142 +The nodes in the graph forms a list. @code{GetFirst(n)} sets @var{n} to
1.143 +be the first node. @code{Next(n)} gives back the subsequent
1.144 +node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it
1.145 +might be faster. ??? What should be the return value ???
1.146 +@end deftypefun
1.147 +
1.148 +@deftypefun bool Graph::Valid (NodePoint &@var{e})
1.149 +@deftypefunx bool NodePoint::Valid ()
1.150 +These functions check if and NodePoint is valid or not.
1.151 +??? Which one should be implemented ???
1.152 +@end deftypefun
1.153 +
1.154 +@subsubsection EdgePoint Operations
1.155 +
1.156 +@deftypefun AllEdgePoint Graph::GetFirst (const AllEdgePoint & @var{e})
1.157 +@deftypefunx AllEdgePoint Graph::Next (const AllEdgePoint @var{n})
1.158 +@deftypefunx {AllEdgePoint &} Graph::GoNext (AllEdgePoint &@var{n})
1.159 +With these functions you can go though all the edges of the graph.
1.160 +??? What should be the return value ???
1.161 +@end deftypefun
1.162 +
1.163 +@deftypefun InEdgePoint Graph::GetFirst (const InEdgePoint & @var{e}, const NodePoint @var{n})
1.164 +@deftypefunx OutEdgePoint Graph::GetFirst (const OutEdgePoint & @var{e}, const NodePoint @var{n})
1.165 +@deftypefunx SymEdgePoint Graph::GetFirst (const SymEdgePoint & @var{e}, const NodePoint @var{n})
1.166 +The edges leaving from, arriving at or adjacent with a node forms a
1.167 +list. These functions give back the first elements of these
1.168 +lists. The exact behavior depends on the type of @var{e}.
1.169 +
1.170 +If @var{e} is an @code{InEdgePoint} or an @code{OutEdgePoint} then
1.171 +@code{GetFirst} sets @var{e} to be the first incoming or outgoing edge
1.172 +of the node @var{n}, respectively.
1.173 +
1.174 +If @var{e} is a @code{SymEdgePoint} then
1.175 +@code{GetFirst} sets @var{e} to be the first incoming if there exists one
1.176 +otherwise the first outgoing edge.
1.177 +
1.178 +If there are no such edges, @var{e} will be invalid.
1.179 +
1.180 +@end deftypefun
1.181 +
1.182 +@deftypefun InEdgePoint Graph::Next (const InEdgePoint @var{e})
1.183 +@deftypefunx OutEdgePoint Graph::Next (const OutEdgePoint @var{e})
1.184 +@deftypefunx SymEdgePoint Graph::Next (const SymEdgePoint @var{e})
1.185 +These functions give back the edge that follows @var{e}
1.186 +@end deftypefun
1.187 +
1.188 +@deftypefun {InEdgePoint &} Graph::GoNext (InEdgePoint &@var{e})
1.189 +@deftypefunx {OutEdgePoint &} Graph::GoNext (OutEdgePoint &@var{e})
1.190 +@deftypefunx {SymEdgePoint &} Graph::GoNext (SymEdgePoint &@var{e})
1.191 +@code{G.GoNext(e)} is equivalent to @code{e=G.Next(e)}, though it
1.192 +might be faster.
1.193 +??? What should be the return value ???
1.194 +@end deftypefun
1.195 +
1.196 +@deftypefun bool Graph::Valid (EdgePoint &@var{e})
1.197 +@deftypefunx bool EdgePoint::Valid ()
1.198 +These functions check if and EdgePoint is valid or not.
1.199 +??? Which one should be implemented ???
1.200 +@end deftypefun
1.201 +
1.202 +@deftypefun NodePoint Graph::From (const EdgePoint @var{e})
1.203 +@deftypefunx NodePoint Graph::To (const EdgePoint @var{e})
1.204 +@deftypefunx NodePoint Graph::ANode (const InEdgePoint @var{e})
1.205 +@deftypefunx NodePoint Graph::ANode (const OutEdgePoint @var{e})
1.206 +@deftypefunx NodePoint Graph::ANode (const SymEdgePoint @var{e})
1.207 +@deftypefunx NodePoint Graph::BNode (const InEdgePoint @var{e})
1.208 +@deftypefunx NodePoint Graph::BNode (const OutEdgePoint @var{e})
1.209 +@deftypefunx NodePoint Graph::BNode (const SymEdgePoint @var{e})
1.210 +There queries give back the two endpoints of the edge @var{e}. For a
1.211 +directed edge @var{e}, @code{From(e)} and @code{To(e)} is its tail and
1.212 +its head, respectively. For an undirected @var{e}, they are two
1.213 +endpoints, but you should not rely on which end is which.
1.214 +
1.215 +@code{ANode(e)} is the node which @var{e} is bounded to, i.e. it is
1.216 +equal to @code{From(e)} if @var{e} is an @code{OutEdgePoint} and
1.217 +@code{To(e)} if @var{e} is an @code{InEdgePoint}. If @var{e} is a
1.218 +@code{SymEdgePoint} and it or its first preceding edge was created by
1.219 +@code{GetFirst(e,n)}, then @code{ANode(e)} is equal to @var{n}.
1.220 +
1.221 +@code{BNode(e)} is the other end of the edge.
1.222 +
1.223 +???It it implemented in an other way now. (Member function <-> Graph global)???
1.224 +@end deftypefun
1.225 +
1.226 +
1.227 +
1.228 +@c @deftypevar int from
1.229 +@c the tail of the created edge.
1.230 +@c @end deftypevar