source:lemon-0.x/doc/flf-graph.texi@19:3151a1026db9

Last change on this file since 19:3151a1026db9 was 18:7c88989ea45b, checked in by Alpar Juttner, 19 years ago

A documentation proposal using texinfo.

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