COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/flf-graph.texi @ 294:f0ff6981d4fd

Last change on this file since 294:f0ff6981d4fd was 203:fc4699a76a6f, checked in by Alpar Juttner, 20 years ago


File size: 8.3 KB
[18]1@node The Full Feature Graph Class
2@section The Full Feature Graph Class
3@cindex Full Feature Graph Class
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.
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.
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.
20@end deftp
22@subsection Types
[203]24@c @deftp {Type} Graph::NodeType
25@c @deftpx {Type} Graph::EdgeType
26@c The type of the data stored statically for each node and edge.
27@c @end deftp
[70]30@deftp {Type} Graph::NodeIt
[203]31@c @deftpx {Type} Graph::NodeIterator
[18]32These types points a node uniquely. The difference between the
[70]33@code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt}
[18]34requires the graph structure itself for most of the operations.
35For examples using iterators you can go through all nodes as follows.
38Graph G;
39int nodenum=0;
[70]40for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum;
[18]41@end verbatim
42@end quotation
[70]43Using @code{NodeIt} the last line looks like this.
[70]46for(Graph::NodeIt n(G);n.valid(); ++nodenum;
[18]47@end verbatim
48@end quotation
[70]52MyGraph::NodeIt n;
53for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum;
[18]54@end verbatim
55@end quotation
56@end deftp
[70]58@deftp {Type} Graph::EdgeIt
59@deftpx {Type} Graph::InEdgeIt
60@deftpx {Type} Graph::OutEdgeIt
[203]61@deftpx {Type} Graph::EachEdgeIt
62@c @deftpx {Type} Graph::BiEdgeIt
63@c @deftpx {Type} Graph::SymEdgeIt
[18]64Each of these types points an edge uniquely. The difference between the
[70]65@code{EdgeIt} and the
[18]66@c @mref{Graph-NodeIterator,@code{EdgeIterator}}
67@mref{Graph-NodeIterator , EdgeIterator}
68series is that
[70]69@code{EdgeIt} requires the graph structure itself for most of the
71@end deftp
[203]74@c @deftp {Type} Graph::EdgeIterator
75@c @deftpx {Type} Graph::InEdgeIterator
76@c @deftpx {Type} Graph::OutEdgeIterator
77@c @deftpx {Type} Graph::BiEdgeIterator
78@c @deftpx {Type} Graph::SymEdgeIterator
79@c @deftpx {Type} Graph::EachEdgeIterator
80@c Each of these types points an edge uniquely. The difference between the
81@c @code{EdgeIt} and the @code{EdgeIterator} series is that
82@c @code{EdgeIt} requires the graph structure itself for most of the
83@c operations.
[203]85@c For the @code{EdgeIterator} types you can use operator @code{++}
86@c (both the prefix and the posfix one) to obtain the next edge.
87@c @end deftp
[203]89@deftp {Type} Graph::NodeMap<typename T>
90@deftpx {Type} Graph::EdgeMap<typename T>
[18]91There are the default property maps for the edges and the nodes.
92@end deftp
[203]94@deftp {Type} Graph::DynNodeMap<typename T>
95@deftpx {Type} Graph::DynEdgeMap<typename T>
96There are the default @emph{dynamic} property maps for the edges and the nodes.
97@end deftp
99@subsection Member Functions
101@subsubsection Constructors
103@deftypefun { } Graph::Graph ()
104The default constructor.
105@end deftypefun
[26]107@c @deftypefun { } Graph::Graph (Graph@tie{}&)
108@deftypefun { } Graph::Graph (Graph &)
[203]109The copy constructor.
[18]110@end deftypefun
112@subsubsection Graph Maintenence Operations
[203]114@deftypefun NodeIt Graph::addNode ()
115Adds a new node to the graph and returns a @code{NodeIt} pointing to it.
[18]116@end deftypefun
[203]118@deftypefun EdgeIt Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIt} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIt} @var{to}})
[18]119Adds a new edge with tail @var{from} and head @var{to} to the graph
[203]120and returns an @code{EdgeIt} pointing to it.
[18]121@end deftypefun
[203]123@deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIt} @var{n}})
[18]124Deletes the node @var{n}. It also deletes the adjacent edges.
125@end deftypefun
[203]127@deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIt} @var{e}})
[18]128Deletes the edge @var{n}.
129@end deftypefun
[203]131@deftypefun void Graph::clear ()
[18]132Deletes all edges and nodes from the graph.
133@end deftypefun
[70]135@deftypefun int Graph::nodeNum ()
[18]136Returns the number of the nodes in the graph.
[203]137??? Is it necessary???
[18]138@end deftypefun
[70]140@subsubsection NodeIt Operations
[203]142@deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) const
143@deftypefunx NodeIt Graph::getNext (NodeIt @var{n}) const
144@deftypefunx {NodeIt &} Graph::next (NodeIt &@var{n})
145The nodes in the graph forms a list. @code{getFirst(n)} sets @var{n} to
146be the first node. @code{getNext(n)} gives back the subsequent
147node. @code{next(n)} is equivalent to @code{n=getNext(n)}, though it
[18]148might be faster.  ??? What should be the return value ???
149@end deftypefun
[70]151@deftypefun bool Graph::valid (NodeIt &@var{e})
[203]152@c @deftypefunx bool NodeIt::valid ()
[70]153These functions check if and NodeIt is valid or not.
[203]154@c ??? Which one should be implemented ???
[18]155@end deftypefun
[70]157@subsubsection EdgeIt Operations
[203]159@deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) const
160@deftypefunx EachEdgeIt Graph::getNext (EachEdgeIt @var{n}) const
161@deftypefunx {EachEdgeIt &} Graph::next (EachEdgeIt &@var{n})
[18]162With these functions you can go though all the edges of the graph.
[203]163@c ??? What should be the return value ???
[18]164@end deftypefun
[203]166@deftypefun InEdgeIt &Graph::getFirst (InEdgeIt & @var{e}, const NodeIt @var{n})
167@deftypefunx OutEdgeIt &Graph::getFirst (OutEdgeIt & @var{e}, const NodeIt @var{n})
168@c @deftypefunx SymEdgeIt &Graph::getFirst (SymEdgeIt & @var{e}, const NodeIt @var{n})
169The edges leaving from
171arriving at
172@c or adjacent with
173a node forms a
[18]174list.  These functions give back the first elements of these
175lists. The exact behavior depends on the type of @var{e}.
[70]177If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then
178@code{getFirst} sets @var{e} to be the first incoming or outgoing edge
[18]179of the node @var{n}, respectively.
[203]181@c If @var{e} is a @code{SymEdgeIt} then
182@c @code{getFirst} sets @var{e} to be the first incoming if there exists one
183@c otherwise the first outgoing edge.
185If there are no such edges, @var{e} will be invalid.
187@end deftypefun
[70]189@deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e})
190@deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e})
191@deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e})
[18]192These functions give back the edge that follows @var{e}
193@end deftypefun
[70]195@deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e})
196@deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e})
197@deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e})
198@code{G.goNext(e)} is equivalent to @code{}, though it
[18]199might be faster.
200??? What should be the return value ???
201@end deftypefun
[70]203@deftypefun bool Graph::valid (EdgeIt &@var{e})
204@deftypefunx bool EdgeIt::valid ()
205These functions check if and EdgeIt is valid or not.
[18]206??? Which one should be implemented ???
207@end deftypefun
[70]209@deftypefun NodeIt Graph::tail (const EdgeIt @var{e})
210@deftypefunx NodeIt Graph::head (const EdgeIt @var{e})
211@deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e})
212@deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e})
213@deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e})
214@deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e})
215@deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e})
216@deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e})
[18]217There queries give back the two endpoints of the edge @var{e}.  For a
[70]218directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and
[18]219its head, respectively. For an undirected @var{e}, they are two
220endpoints, but you should not rely on which end is which.
[70]222@code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is
223equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and
224@code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a
225@code{SymEdgeIt} and it or its first preceding edge was created by
226@code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}.
[70]228@code{bNode(e)} is the other end of the edge.
[203]230@deftypefun void Graph::setInvalid (EdgeIt &@var{e})
231@deftypefunx void Graph::setInvalid (EdgeIt &@var{e})
232These functions set the corresponding iterator to be invalid.
233@end deftypefun
235@c ???It is implemented in an other way now. (Member function <-> Graph global)???
[18]236@end deftypefun
240@c @deftypevar int from
241@c  the tail of the created edge.
242@c @end deftypevar
Note: See TracBrowser for help on using the repository browser.