alpar@18: @node The Full Feature Graph Class alpar@18: @section The Full Feature Graph Class alpar@18: @cindex Full Feature Graph Class alpar@18: alpar@18: This section describes what an imaginary full feature graph class knows. alpar@18: The set of features provided by a real graph implementation is typically alpar@18: a subset of the features below. alpar@18: alpar@18: On the other hand, each graph algorithm requires the underlying graph alpar@18: structure to provide a certain (typically small) set of features in order alpar@18: to be able to run. alpar@18: alpar@18: @subsection Declaration alpar@18: alpar@18: @deftp {Class} {class Graph} alpar@18: @code{Graph} is the imaginary @emph{full feature graph class}. alpar@18: @code{G} denotes the instance of this class in the exaples below. alpar@18: @c Each node and edge has a user defined data sturcure alpar@18: @c @var{N} and @var{E} statically attached to it. alpar@18: @end deftp alpar@18: alpar@18: @subsection Types alpar@18: alpar@18: @deftp {Type} Graph::NodeType alpar@18: @deftpx {Type} Graph::EdgeType alpar@18: The type of the data stored statically for each node and edge. alpar@18: @end deftp alpar@18: alpar@18: @anchor{Graph-NodeIterator} alpar@70: @deftp {Type} Graph::NodeIt alpar@18: @deftpx {Type} Graph::NodeIterator alpar@18: These types points a node uniquely. The difference between the alpar@70: @code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt} alpar@18: requires the graph structure itself for most of the operations. alpar@18: For examples using iterators you can go through all nodes as follows. alpar@18: @quotation alpar@18: @verbatim alpar@18: Graph G; alpar@18: int nodenum=0; alpar@70: for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum; alpar@18: @end verbatim alpar@18: @end quotation alpar@70: Using @code{NodeIt} the last line looks like this. alpar@18: @quotation alpar@18: @verbatim alpar@70: for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum; alpar@18: @end verbatim alpar@18: @end quotation alpar@18: or alpar@18: @quotation alpar@18: @verbatim alpar@70: MyGraph::NodeIt n; alpar@70: for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum; alpar@18: @end verbatim alpar@18: @end quotation alpar@18: @end deftp alpar@18: alpar@70: @deftp {Type} Graph::EdgeIt alpar@70: @deftpx {Type} Graph::InEdgeIt alpar@70: @deftpx {Type} Graph::OutEdgeIt alpar@70: @deftpx {Type} Graph::BiEdgeIt alpar@70: @deftpx {Type} Graph::SymEdgeIt alpar@18: Each of these types points an edge uniquely. The difference between the alpar@70: @code{EdgeIt} and the alpar@18: @c @mref{Graph-NodeIterator,@code{EdgeIterator}} alpar@18: @mref{Graph-NodeIterator , EdgeIterator} alpar@18: series is that alpar@70: @code{EdgeIt} requires the graph structure itself for most of the alpar@18: operations. alpar@18: @end deftp alpar@18: alpar@18: @anchor{Graph-EdgeIterator} alpar@18: @deftp {Type} Graph::EdgeIterator alpar@18: @deftpx {Type} Graph::InEdgeIterator alpar@18: @deftpx {Type} Graph::OutEdgeIterator alpar@18: @deftpx {Type} Graph::BiEdgeIterator alpar@18: @deftpx {Type} Graph::SymEdgeIterator alpar@70: @deftpx {Type} Graph::EachEdgeIterator alpar@18: Each of these types points an edge uniquely. The difference between the alpar@70: @code{EdgeIt} and the @code{EdgeIterator} series is that alpar@70: @code{EdgeIt} requires the graph structure itself for most of the alpar@18: operations. alpar@18: alpar@18: For the @code{EdgeIterator} types you can use operator @code{++} alpar@18: (both the prefix and the posfix one) to obtain the next edge. alpar@18: @end deftp alpar@18: alpar@18: @deftp {Type} Graph::NodeMap alpar@18: @deftpx {Type} Graph::EdgeMap alpar@18: There are the default property maps for the edges and the nodes. alpar@18: @end deftp alpar@18: alpar@18: alpar@18: @subsection Member Functions alpar@18: alpar@18: @subsubsection Constructors alpar@18: alpar@18: alpar@18: @deftypefun { } Graph::Graph () alpar@18: The default constructor. alpar@18: @end deftypefun alpar@18: alpar@26: @c @deftypefun { } Graph::Graph (Graph@tie{}&) alpar@26: @deftypefun { } Graph::Graph (Graph &) alpar@18: The copy constructor. Not yet implemented. alpar@18: @end deftypefun alpar@18: alpar@18: @subsubsection Graph Maintenence Operations alpar@18: alpar@70: @deftypefun NodeIterator Graph::addNode () alpar@18: Adds a new node to the graph and returns a @code{NodeIterator} pointing to it. alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun EdgeIterator Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}}) alpar@18: Adds a new edge with tail @var{from} and head @var{to} to the graph alpar@18: and returns an @code{EdgeIterator} pointing to it. alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}}) alpar@18: Deletes the node @var{n}. It also deletes the adjacent edges. alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}}) alpar@18: Deletes the edge @var{n}. alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun void Graph::clean () alpar@18: Deletes all edges and nodes from the graph. alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun int Graph::nodeNum () alpar@18: Returns the number of the nodes in the graph. alpar@18: @end deftypefun alpar@18: alpar@70: @subsubsection NodeIt Operations alpar@18: alpar@70: @deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) alpar@70: @deftypefunx NodeIt Graph::next (const NodeIt @var{n}) alpar@70: @deftypefunx {NodeIt &} Graph::goNext (NodeIt &@var{n}) alpar@18: The nodes in the graph forms a list. @code{GetFirst(n)} sets @var{n} to alpar@70: be the first node. @code{next(n)} gives back the subsequent alpar@18: node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it alpar@18: might be faster. ??? What should be the return value ??? alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun bool Graph::valid (NodeIt &@var{e}) alpar@70: @deftypefunx bool NodeIt::valid () alpar@70: These functions check if and NodeIt is valid or not. alpar@18: ??? Which one should be implemented ??? alpar@18: @end deftypefun alpar@18: alpar@70: @subsubsection EdgeIt Operations alpar@18: alpar@70: @deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) alpar@70: @deftypefunx EachEdgeIt Graph::next (const EachEdgeIt @var{n}) alpar@70: @deftypefunx {EachEdgeIt &} Graph::goNext (EachEdgeIt &@var{n}) alpar@18: With these functions you can go though all the edges of the graph. alpar@18: ??? What should be the return value ??? alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun InEdgeIt Graph::getFirst (const InEdgeIt & @var{e}, const NodeIt @var{n}) alpar@70: @deftypefunx OutEdgeIt Graph::getFirst (const OutEdgeIt & @var{e}, const NodeIt @var{n}) alpar@70: @deftypefunx SymEdgeIt Graph::getFirst (const SymEdgeIt & @var{e}, const NodeIt @var{n}) alpar@18: The edges leaving from, arriving at or adjacent with a node forms a alpar@18: list. These functions give back the first elements of these alpar@18: lists. The exact behavior depends on the type of @var{e}. alpar@18: alpar@70: If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then alpar@70: @code{getFirst} sets @var{e} to be the first incoming or outgoing edge alpar@18: of the node @var{n}, respectively. alpar@18: alpar@70: If @var{e} is a @code{SymEdgeIt} then alpar@70: @code{getFirst} sets @var{e} to be the first incoming if there exists one alpar@18: otherwise the first outgoing edge. alpar@18: alpar@18: If there are no such edges, @var{e} will be invalid. alpar@18: alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e}) alpar@70: @deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e}) alpar@70: @deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e}) alpar@18: These functions give back the edge that follows @var{e} alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e}) alpar@70: @deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e}) alpar@70: @deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e}) alpar@70: @code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it alpar@18: might be faster. alpar@18: ??? What should be the return value ??? alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun bool Graph::valid (EdgeIt &@var{e}) alpar@70: @deftypefunx bool EdgeIt::valid () alpar@70: These functions check if and EdgeIt is valid or not. alpar@18: ??? Which one should be implemented ??? alpar@18: @end deftypefun alpar@18: alpar@70: @deftypefun NodeIt Graph::tail (const EdgeIt @var{e}) alpar@70: @deftypefunx NodeIt Graph::head (const EdgeIt @var{e}) alpar@70: @deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e}) alpar@70: @deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e}) alpar@70: @deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e}) alpar@70: @deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e}) alpar@70: @deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e}) alpar@70: @deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e}) alpar@18: There queries give back the two endpoints of the edge @var{e}. For a alpar@70: directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and alpar@18: its head, respectively. For an undirected @var{e}, they are two alpar@18: endpoints, but you should not rely on which end is which. alpar@18: alpar@70: @code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is alpar@70: equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and alpar@70: @code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a alpar@70: @code{SymEdgeIt} and it or its first preceding edge was created by alpar@70: @code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}. alpar@18: alpar@70: @code{bNode(e)} is the other end of the edge. alpar@18: alpar@70: ???It is implemented in an other way now. (Member function <-> Graph global)??? alpar@18: @end deftypefun alpar@18: alpar@18: alpar@18: alpar@18: @c @deftypevar int from alpar@18: @c the tail of the created edge. alpar@18: @c @end deftypevar