# source:lemon-0.x/doc/flf-graph.texi@70:851ca9a60e90

Last change on this file since 70:851ca9a60e90 was 70:851ca9a60e90, checked in by Alpar Juttner, 16 years ago

.

File size: 7.8 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::NodeIt
31@deftpx {Type} Graph::NodeIterator
32These types points a node uniquely. The difference between the
33@code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt}
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{NodeIt} the last line looks like this.
44@quotation
45@verbatim
46for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum;
47@end verbatim
48@end quotation
49or
50@quotation
51@verbatim
52MyGraph::NodeIt 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::EdgeIt
59@deftpx {Type} Graph::InEdgeIt
60@deftpx {Type} Graph::OutEdgeIt
61@deftpx {Type} Graph::BiEdgeIt
62@deftpx {Type} Graph::SymEdgeIt
63Each of these types points an edge uniquely. The difference between the
64@code{EdgeIt} and the
65@c @mref{Graph-NodeIterator,@code{EdgeIterator}}
66@mref{Graph-NodeIterator , EdgeIterator}
67series is that
68@code{EdgeIt} 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::EachEdgeIterator
79Each of these types points an edge uniquely. The difference between the
80@code{EdgeIt} and the @code{EdgeIterator} series is that
81@code{EdgeIt} 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@c @deftypefun { } Graph::Graph (Graph@tie{}&)
104@deftypefun { } Graph::Graph (Graph &)
105The copy constructor. Not yet implemented.
106@end deftypefun
107
108@subsubsection Graph Maintenence Operations
109
111Adds a new node to the graph and returns a @code{NodeIterator} pointing to it.
112@end deftypefun
113
114@deftypefun EdgeIterator Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}})
115Adds a new edge with tail @var{from} and head @var{to} to the graph
116and returns an @code{EdgeIterator} pointing to it.
117@end deftypefun
118
119@deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}})
120Deletes the node @var{n}. It also deletes the adjacent edges.
121@end deftypefun
122
123@deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}})
124Deletes the edge @var{n}.
125@end deftypefun
126
127@deftypefun void Graph::clean ()
128Deletes all edges and nodes from the graph.
129@end deftypefun
130
131@deftypefun int Graph::nodeNum ()
132Returns the number of the nodes in the graph.
133@end deftypefun
134
135@subsubsection NodeIt Operations
136
137@deftypefun NodeIt Graph::getFirst (NodeIt &@var{n})
138@deftypefunx NodeIt Graph::next (const NodeIt @var{n})
139@deftypefunx {NodeIt &} Graph::goNext (NodeIt &@var{n})
140The nodes in the graph forms a list. @code{GetFirst(n)} sets @var{n} to
141be the first node. @code{next(n)} gives back the subsequent
142node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it
143might be faster.  ??? What should be the return value ???
144@end deftypefun
145
146@deftypefun bool Graph::valid (NodeIt &@var{e})
147@deftypefunx bool NodeIt::valid ()
148These functions check if and NodeIt is valid or not.
149??? Which one should be implemented ???
150@end deftypefun
151
152@subsubsection EdgeIt Operations
153
154@deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e})
155@deftypefunx EachEdgeIt Graph::next (const EachEdgeIt @var{n})
156@deftypefunx {EachEdgeIt &} Graph::goNext (EachEdgeIt &@var{n})
157With these functions you can go though all the edges of the graph.
158??? What should be the return value ???
159@end deftypefun
160
161@deftypefun InEdgeIt Graph::getFirst (const InEdgeIt & @var{e}, const NodeIt @var{n})
162@deftypefunx OutEdgeIt Graph::getFirst (const OutEdgeIt & @var{e}, const NodeIt @var{n})
163@deftypefunx SymEdgeIt Graph::getFirst (const SymEdgeIt & @var{e}, const NodeIt @var{n})
164The edges leaving from, arriving at or adjacent with a node forms a
165list.  These functions give back the first elements of these
166lists. The exact behavior depends on the type of @var{e}.
167
168If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then
169@code{getFirst} sets @var{e} to be the first incoming or outgoing edge
170of the node @var{n}, respectively.
171
172If @var{e} is a @code{SymEdgeIt} then
173@code{getFirst} sets @var{e} to be the first incoming if there exists one
174otherwise the first outgoing edge.
175
176If there are no such edges, @var{e} will be invalid.
177
178@end deftypefun
179
180@deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e})
181@deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e})
182@deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e})
183These functions give back the edge that follows @var{e}
184@end deftypefun
185
186@deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e})
187@deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e})
188@deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e})
189@code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it
190might be faster.
191??? What should be the return value ???
192@end deftypefun
193
194@deftypefun bool Graph::valid (EdgeIt &@var{e})
195@deftypefunx bool EdgeIt::valid ()
196These functions check if and EdgeIt is valid or not.
197??? Which one should be implemented ???
198@end deftypefun
199
200@deftypefun NodeIt Graph::tail (const EdgeIt @var{e})
201@deftypefunx NodeIt Graph::head (const EdgeIt @var{e})
202@deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e})
203@deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e})
204@deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e})
205@deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e})
206@deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e})
207@deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e})
208There queries give back the two endpoints of the edge @var{e}.  For a
209directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and
210its head, respectively. For an undirected @var{e}, they are two
211endpoints, but you should not rely on which end is which.
212
213@code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is
214equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and
215@code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a
216@code{SymEdgeIt} and it or its first preceding edge was created by
217@code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}.
218
219@code{bNode(e)} is the other end of the edge.
220
221???It is implemented in an other way now. (Member function <-> Graph global)???
222@end deftypefun
223
224
225
226@c @deftypevar int from
227@c  the tail of the created edge.
228@c @end deftypevar
Note: See TracBrowser for help on using the repository browser.