include/GTL/node.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   node.h
0005 //
0006 //==========================================================================
0007 // $Id: node.h,v 1.20 2003/11/27 13:36:56 raitner Exp $
0008
0009 #ifndef GTL_NODE_H
0010 #define GTL_NODE_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/edge.h>
0014
0015 #include <list>
0016
0017 __GTL_BEGIN_NAMESPACE
0018
0019 //--------------------------------------------------------------------------
0020 //   For MSVC 5.0 node.h has to be included before {node,edge}_data.h.
0021 //   So we only declare node_data here
0022 //--------------------------------------------------------------------------
0023
0024 class node_data;
0025
0026 //--------------------------------------------------------------------------
0027 // The first alternative is correct. The second one is a workaround
0028 // for compilers that don't support namespaces and use the SGI STL
0029 // (i.e. gcc/egcs)
0030 //--------------------------------------------------------------------------
0031
0032 #ifdef __GTL_USE_NAMESPACES
0033
0034 class node;
0035 typedef std::iterator<std::bidirectional_iterator_tag, edge> bi_iter_edge;
0036 typedef std::iterator<std::bidirectional_iterator_tag, node> bi_iter_node;
0037
0038 #else
0039
0040 class node;
0041 typedef bidirectional_iterator<edge,ptrdiff_t> bi_iter_edge;
0042 typedef bidirectional_iterator<node,ptrdiff_t> bi_iter_node;
0043
0044 #endif // __GTL_USE_NAMESPACES
0045
0046 //--------------------------------------------------------------------------
0047 //   nodes
0048 //--------------------------------------------------------------------------
0049
0050 /**
0051  * @short A node in a graph
0052  */
0053 class GTL_EXTERN node
0054 {
0055 public:
0056     /**
0057      * Default constructor. Creates an invalid node.
0058      * The only way to obtain a valid node is through @ref
0059      * graph#new_node Example:
0060      * <pre>
0061      *   graph g;
0062      *   node n;
0063      *
0064      *   n = g.new_node();
0065      * </pre>
0066      *
0067      * @see graph#new_node
0068      */
0069     node();
0070
0071     /**
0072      * Returns the degree of the node, i. e.
0073      * @ref node#outdeg + @ref node#indeg .
0074      */
0075     int degree() const;
0076
0077     /**
0078      * Returns the out degree of the node, i. e. the number of outgoing edges.
0079      */
0080     int outdeg() const;
0081
0082     /**
0083      * Returns the in degree of the node, i. e. the number of incoming edges.
0084      */
0085     int indeg() const;
0086
0087     /**
0088      * @internal
0089      */
0090     int id() const;
0091
0092     /**
0093      * Returns the node on the opposite side of <code>e</code>.
0094      *
0095      * @param e an edge incident to the node
0096      */
0097     const node& opposite(edge e) const;
0098
0099     /**
0100      * @internal
0101      */
0102     list<node> opposites(edge) const;
0103
0104     /**
0105      * Returns true iff node is hidden.
0106      *
0107      * @return true iff node is hidden.
0108      * @see graph#hide_edge
0109      * @see graph#restore_edge
0110      */
0111     bool is_hidden () const;
0112
0113     /**
0114      * Returns the excentricity of the node, i.e. the maximum graph-theoretic
0115      * distance to another node
0116      *
0117      * @return excentricity of node.
0118      */
0119     int excentricity() const;
0120
0121     //================================================== Iterator types
0122
0123     /**
0124      * @internal
0125      */
0126     typedef list<edge>::const_iterator in_edges_iterator;
0127     /**
0128      * @internal
0129      */
0130     typedef list<edge>::const_iterator out_edges_iterator;
0131
0132     /**
0133      * @internal
0134      */
0135     class inout_edges_iterator;
0136
0137     /**
0138      * @internal
0139      */
0140     class adj_nodes_iterator;
0141
0142     /**
0143      * @internal
0144      */
0145     class adj_edges_iterator;
0146
0147     //================================================== Iterators
0148
0149     /**
0150      * Iterate through all adjacent nodes.
0151      *
0152      * @return start for iteration through all adjacent nodes
0153      */
0154     adj_nodes_iterator adj_nodes_begin() const;
0155
0156     /**
0157      * Iterate through all adjacent nodes.
0158      *
0159      * @return end for iteration through all adjacent nodes
0160      */
0161     adj_nodes_iterator adj_nodes_end() const;
0162
0163     /**
0164      * Iterate through all adjacent edges.
0165      *
0166      * @return start for iteration through all adjacent edges
0167      */
0168     adj_edges_iterator adj_edges_begin() const;
0169
0170     /**
0171      * Iterate through all adjacent edges.
0172      *
0173      * @return end for iteration through all adjacent edges
0174      */
0175     adj_edges_iterator adj_edges_end() const;
0176
0177     /**
0178      * Iterate through all incoming edges.
0179      *
0180      * @return start for iteration through all incoming edges
0181      */
0182     in_edges_iterator in_edges_begin() const;
0183
0184     /**
0185      * Iterate through all incoming edges.
0186      *
0187      * @return end for iteration through all incoming edges
0188      */
0189     in_edges_iterator in_edges_end() const;
0190
0191     /**
0192      * Iterate through all outgoing edges.
0193      *
0194      * @return start for iteration through all outgoing edges
0195      */
0196     out_edges_iterator out_edges_begin() const;
0197
0198     /**
0199      * Iterate through all outgoing edges.
0200      *
0201      * @return end for iteration through all outgoing edges
0202      */
0203     out_edges_iterator out_edges_end() const;
0204
0205     /**
0206      * Iterate through all incoming <em>and</em> outgoing edges.
0207      *
0208      * @return start for iteration through all incoming and outgoing edges
0209      */
0210     inout_edges_iterator inout_edges_begin() const;
0211
0212     /**
0213      * Iterate through all incoming <em>and</em> outgoing edges.
0214      *
0215      * @return end for iteration through all incoming and outgoing edges
0216      */
0217     inout_edges_iterator inout_edges_end() const;
0218
0219     //================================================== Implementation
0220
0221 private:
0222     node_data *data;
0223
0224     bool is_directed() const;
0225     bool is_undirected() const;
0226
0227     friend class graph;
0228     friend class edge;
0229     friend class adj_edges_iterator;
0230
0231     GTL_EXTERN friend bool operator==(node, node);
0232     GTL_EXTERN friend bool operator!=(node, node);
0233     GTL_EXTERN friend bool operator<(node, node);
0234     GTL_EXTERN friend ostream& operator<< (ostream& os, const node& n);
0235 };
0236
0237
0238 /**
0239  * @short Iterator for adjacent edges of a node
0240  */
0241 class GTL_EXTERN node::adj_edges_iterator : public bi_iter_edge
0242 {
0243 public:
0244
0245     // constructor
0246     adj_edges_iterator();
0247     adj_edges_iterator(node, bool);
0248
0249     // comparibility
0250     bool operator==(const adj_edges_iterator&) const;
0251     bool operator!=(const adj_edges_iterator&) const;
0252
0253     // operators
0254     adj_edges_iterator &operator++();
0255     adj_edges_iterator operator++(int);
0256     adj_edges_iterator &operator--();
0257     adj_edges_iterator operator--(int);
0258
0259     // dereferencing
0260     const edge& operator*() const;
0261     const edge* operator->() const;
0262
0263 private:
0264     in_edges_iterator akt_edge[2], last_edge[2], begin_edge[2];
0265     int inout;     // in=0, out=1
0266     bool directed; // graph directed ??
0267 };
0268
0269 /**
0270  * @short Iterator for all incident edges of a node
0271  */
0272 class GTL_EXTERN node::inout_edges_iterator : public bi_iter_edge
0273 {
0274 public:
0275
0276     // constructor
0277     inout_edges_iterator();
0278     inout_edges_iterator(node n, bool start);
0279
0280     // comparibility
0281     bool operator==(const inout_edges_iterator&) const;
0282     bool operator!=(const inout_edges_iterator&) const;
0283
0284     // operators
0285     inout_edges_iterator &operator++();
0286     inout_edges_iterator operator++(int);
0287     inout_edges_iterator &operator--();
0288     inout_edges_iterator operator--(int);
0289
0290     // dereferencing
0291     const edge& operator*() const;
0292     const edge* operator->() const;
0293
0294 private:
0295     in_edges_iterator akt_edge[2], last_edge, begin_edge;
0296     int inout;     // in=0, out=1
0297 };
0298
0299 /**
0300  * @short Iterator for adjacent nodes of a node
0301  */
0302 class GTL_EXTERN node::adj_nodes_iterator : public bi_iter_node
0303 {
0304 public:
0305
0306     // constructor
0307     adj_nodes_iterator();
0308     adj_nodes_iterator(const node&, bool);
0309
0310     // comparibility
0311     bool operator==(const adj_nodes_iterator&) const;
0312     bool operator!=(const adj_nodes_iterator&) const;
0313
0314     // operators
0315     adj_nodes_iterator &operator++();
0316     adj_nodes_iterator operator++(int);
0317     adj_nodes_iterator &operator--();
0318     adj_nodes_iterator operator--(int);
0319
0320     // dereferencing
0321     const node& operator*() const;
0322     const node* operator->() const;
0323
0324 private:
0325     adj_edges_iterator akt_edge;
0326     node int_node;
0327 };
0328
0329
0330 __GTL_END_NAMESPACE
0331
0332 //--------------------------------------------------------------------------
0333 //   Iteration
0334 //--------------------------------------------------------------------------
0335
0336 // #define forall_adj_nodes(v,w)    GTL_FORALL(v,w,node::adj_nodes_iterator,adj_nodes_)
0337 #define forall_out_edges(e,v)   GTL_FORALL(e,v,node::out_edges_iterator,out_edges_)
0338 #define forall_in_edges(e,v)    GTL_FORALL(e,v,node::in_edges_iterator,in_edges_)
0339 #define forall_inout_edges(e,v) GTL_FORALL(e,v,node::inout_edges_iterator,inout_edges_)
0340 #define forall_adj_edges(e,v)   GTL_FORALL(e,v,node::adj_edges_iterator,adj_edges_)
0341
0342 #endif // GTL_NODE_H
0343
0344 //--------------------------------------------------------------------------
0345 //   end of file
0346 //--------------------------------------------------------------------------