Generikus binaris kupac implementacio.
Alap demo file mukodesenek bemutatasahoz.
1 @node The Full Feature Graph Class
2 @section The Full Feature Graph Class
3 @cindex Full Feature Graph Class
5 This section describes what an imaginary full feature graph class knows.
6 The set of features provided by a real graph implementation is typically
7 a subset of the features below.
9 On the other hand, each graph algorithm requires the underlying graph
10 structure to provide a certain (typically small) set of features in order
13 @subsection Declaration
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.
24 @deftp {Type} Graph::NodeType
25 @deftpx {Type} Graph::EdgeType
26 The type of the data stored statically for each node and edge.
29 @anchor{Graph-NodeIterator}
30 @deftp {Type} Graph::NodePoint
31 @deftpx {Type} Graph::NodeIterator
32 These types points a node uniquely. The difference between the
33 @code{NodePoint} and the @code{NodeIterator} is that @code{NodePoint}
34 requires the graph structure itself for most of the operations.
35 For examples using iterators you can go through all nodes as follows.
40 for(Graph::NodeIterator n(G);n.Valid();++n) ++nodenum;
43 Using @code{NodePoint} the last line looks like this.
46 for(MyGraph::NodePoint n(G);n.Valid();n=G.Next(n)) ++nodenum;
53 for(G.GetFirst(n);G.Valid(n);G.GoNext(n)) ++nodenum;
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
63 Each 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}
68 @code{EdgePoint} requires the graph structure itself for most of the
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
79 Each 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
84 For the @code{EdgeIterator} types you can use operator @code{++}
85 (both the prefix and the posfix one) to obtain the next edge.
88 @deftp {Type} Graph::NodeMap
89 @deftpx {Type} Graph::EdgeMap
90 There are the default property maps for the edges and the nodes.
94 @subsection Member Functions
96 @subsubsection Constructors
99 @deftypefun { } Graph::Graph ()
100 The default constructor.
103 @c @deftypefun { } Graph::Graph (Graph@tie{}&)
104 @deftypefun { } Graph::Graph (Graph &)
105 The copy constructor. Not yet implemented.
108 @subsubsection Graph Maintenence Operations
110 @deftypefun NodeIterator Graph::AddNode ()
111 Adds a new node to the graph and returns a @code{NodeIterator} pointing to it.
114 @deftypefun EdgeIterator Graph::AddEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}})
115 Adds a new edge with tail @var{from} and head @var{to} to the graph
116 and returns an @code{EdgeIterator} pointing to it.
119 @deftypefun void Graph::Delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}})
120 Deletes the node @var{n}. It also deletes the adjacent edges.
123 @deftypefun void Graph::Delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}})
124 Deletes the edge @var{n}.
127 @deftypefun void Graph::Clean ()
128 Deletes all edges and nodes from the graph.
131 @deftypefun int Graph::NodeNum ()
132 Returns the number of the nodes in the graph.
135 @subsubsection NodePoint Operations
137 @deftypefun NodePoint Graph::GetFirst (NodePoint &@var{n})
138 @deftypefunx NodePoint Graph::Next (const NodePoint @var{n})
139 @deftypefunx {NodePoint &} Graph::GoNext (NodePoint &@var{n})
140 The nodes in the graph forms a list. @code{GetFirst(n)} sets @var{n} to
141 be the first node. @code{Next(n)} gives back the subsequent
142 node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it
143 might be faster. ??? What should be the return value ???
146 @deftypefun bool Graph::Valid (NodePoint &@var{e})
147 @deftypefunx bool NodePoint::Valid ()
148 These functions check if and NodePoint is valid or not.
149 ??? Which one should be implemented ???
152 @subsubsection EdgePoint Operations
154 @deftypefun AllEdgePoint Graph::GetFirst (const AllEdgePoint & @var{e})
155 @deftypefunx AllEdgePoint Graph::Next (const AllEdgePoint @var{n})
156 @deftypefunx {AllEdgePoint &} Graph::GoNext (AllEdgePoint &@var{n})
157 With these functions you can go though all the edges of the graph.
158 ??? What should be the return value ???
161 @deftypefun InEdgePoint Graph::GetFirst (const InEdgePoint & @var{e}, const NodePoint @var{n})
162 @deftypefunx OutEdgePoint Graph::GetFirst (const OutEdgePoint & @var{e}, const NodePoint @var{n})
163 @deftypefunx SymEdgePoint Graph::GetFirst (const SymEdgePoint & @var{e}, const NodePoint @var{n})
164 The edges leaving from, arriving at or adjacent with a node forms a
165 list. These functions give back the first elements of these
166 lists. The exact behavior depends on the type of @var{e}.
168 If @var{e} is an @code{InEdgePoint} or an @code{OutEdgePoint} then
169 @code{GetFirst} sets @var{e} to be the first incoming or outgoing edge
170 of the node @var{n}, respectively.
172 If @var{e} is a @code{SymEdgePoint} then
173 @code{GetFirst} sets @var{e} to be the first incoming if there exists one
174 otherwise the first outgoing edge.
176 If there are no such edges, @var{e} will be invalid.
180 @deftypefun InEdgePoint Graph::Next (const InEdgePoint @var{e})
181 @deftypefunx OutEdgePoint Graph::Next (const OutEdgePoint @var{e})
182 @deftypefunx SymEdgePoint Graph::Next (const SymEdgePoint @var{e})
183 These functions give back the edge that follows @var{e}
186 @deftypefun {InEdgePoint &} Graph::GoNext (InEdgePoint &@var{e})
187 @deftypefunx {OutEdgePoint &} Graph::GoNext (OutEdgePoint &@var{e})
188 @deftypefunx {SymEdgePoint &} Graph::GoNext (SymEdgePoint &@var{e})
189 @code{G.GoNext(e)} is equivalent to @code{e=G.Next(e)}, though it
191 ??? What should be the return value ???
194 @deftypefun bool Graph::Valid (EdgePoint &@var{e})
195 @deftypefunx bool EdgePoint::Valid ()
196 These functions check if and EdgePoint is valid or not.
197 ??? Which one should be implemented ???
200 @deftypefun NodePoint Graph::From (const EdgePoint @var{e})
201 @deftypefunx NodePoint Graph::To (const EdgePoint @var{e})
202 @deftypefunx NodePoint Graph::ANode (const InEdgePoint @var{e})
203 @deftypefunx NodePoint Graph::ANode (const OutEdgePoint @var{e})
204 @deftypefunx NodePoint Graph::ANode (const SymEdgePoint @var{e})
205 @deftypefunx NodePoint Graph::BNode (const InEdgePoint @var{e})
206 @deftypefunx NodePoint Graph::BNode (const OutEdgePoint @var{e})
207 @deftypefunx NodePoint Graph::BNode (const SymEdgePoint @var{e})
208 There queries give back the two endpoints of the edge @var{e}. For a
209 directed edge @var{e}, @code{From(e)} and @code{To(e)} is its tail and
210 its head, respectively. For an undirected @var{e}, they are two
211 endpoints, but you should not rely on which end is which.
213 @code{ANode(e)} is the node which @var{e} is bounded to, i.e. it is
214 equal to @code{From(e)} if @var{e} is an @code{OutEdgePoint} and
215 @code{To(e)} if @var{e} is an @code{InEdgePoint}. If @var{e} is a
216 @code{SymEdgePoint} and it or its first preceding edge was created by
217 @code{GetFirst(e,n)}, then @code{ANode(e)} is equal to @var{n}.
219 @code{BNode(e)} is the other end of the edge.
221 ???It it implemented in an other way now. (Member function <-> Graph global)???
226 @c @deftypevar int from
227 @c the tail of the created edge.