gtl/src/node.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   node.cpp
0005 //
0006 //==========================================================================
0007 // $Id: node.cpp,v 1.18 2001/11/07 13:58:10 pick Exp $
0008
0009 #include <GTL/node_data.h>
0010 #include <GTL/edge_data.h>
0011 #include <GTL/graph.h>
0012 #include <GTL/bfs.h>
0013
0014 #include <cassert>
0015 #include <iostream>
0016
0017 #ifdef __GTL_MSVCC
0018 #   ifdef _DEBUG
0019 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0020 #   error SEARCH NOT ENABLED
0021 #   endif
0022 #   define new DEBUG_NEW
0023 #   undef THIS_FILE
0024     static char THIS_FILE[] = __FILE__;
0025 #   endif   // _DEBUG
0026 #endif  // __GTL_MSVCC
0027
0028 __GTL_BEGIN_NAMESPACE
0029
0030 node::node() :
0031     data(0)
0032 {
0033 }
0034
0035 GTL_EXTERN ostream& operator<< (ostream& os, const node& n) {
0036     if (n != node()) {
0037     return os << "[" << n.id() << "]";
0038     } else {
0039     return os << "[ UNDEF ]";
0040     }
0041 }
0042
0043 node::adj_nodes_iterator node::adj_nodes_begin() const
0044 {
0045     return node::adj_nodes_iterator(*this, true);
0046 }
0047
0048 node::adj_nodes_iterator node::adj_nodes_end() const
0049 {
0050     return node::adj_nodes_iterator(*this, false);
0051 }
0052
0053 node::adj_edges_iterator node::adj_edges_begin() const
0054 {
0055     return node::adj_edges_iterator(*this, true);
0056 }
0057
0058 node::adj_edges_iterator node::adj_edges_end() const
0059 {
0060     return node::adj_edges_iterator(*this, false);
0061 }
0062
0063 node::inout_edges_iterator node::inout_edges_begin() const
0064 {
0065     return node::inout_edges_iterator(*this, true);
0066 }
0067
0068 node::inout_edges_iterator node::inout_edges_end() const
0069 {
0070     return node::inout_edges_iterator(*this, false);
0071 }
0072
0073 node::in_edges_iterator node::in_edges_begin() const
0074 {
0075     return data->edges[0].begin();
0076 }
0077
0078 node::in_edges_iterator node::in_edges_end() const
0079 {
0080     return data->edges[0].end();
0081 }
0082
0083 node::out_edges_iterator node::out_edges_begin() const
0084 {
0085     return data->edges[1].begin();
0086 }
0087
0088 node::out_edges_iterator node::out_edges_end() const
0089 {
0090     return data->edges[1].end();
0091 }
0092
0093 int node::degree() const
0094 {
0095     return outdeg() + indeg();
0096 }
0097
0098 int node::outdeg() const
0099 {
0100     return data->edges[1].size();
0101 }
0102
0103 int node::indeg() const
0104 {
0105     return data->edges[0].size();
0106 }
0107
0108 int node::id() const
0109 {
0110     return data->id;
0111 }
0112
0113 bool node::is_directed() const
0114 {
0115     return data->owner->is_directed();
0116 }
0117
0118 bool node::is_undirected() const
0119 {
0120     return data->owner->is_undirected();
0121 }
0122
0123 const node& node::opposite(edge e) const
0124 {
0125     // not implemented for hypergraphs
0126     assert(e.data);
0127
0128     node& s = *(e.data->nodes[0].begin());
0129     if (*this == s)
0130     return *(e.data->nodes[1].begin());
0131     else
0132     return s;
0133 }
0134
0135 list<node> node::opposites(edge) const
0136 {
0137     // not implemented yet
0138     return list<node>(); // to avoid compiler warnings
0139 }
0140
0141 bool node::is_hidden () const
0142 {
0143     return data->hidden;
0144 }
0145
0146 int node::excentricity() const
0147 {
0148     bfs b;
0149     b.start_node(*this);
0150     b.calc_level(true);
0151     b.run(*data->owner);
0152
0153     node last_node = *(--b.end());
0154
0155     return b.level(last_node);
0156 }
0157
0158 GTL_EXTERN bool operator==(node v1, node v2)
0159 {
0160     return v1.data == v2.data;
0161 }
0162
0163 GTL_EXTERN bool operator!=(node v1, node v2)
0164 {
0165     return v1.data != v2.data;
0166 }
0167
0168 GTL_EXTERN bool operator<(node v1, node v2)
0169 {
0170     return v1.data < v2.data;
0171 }
0172
0173 //--------------------------------------------------------------------------
0174 //   adj_edges_iterator
0175 //--------------------------------------------------------------------------
0176
0177 node::adj_edges_iterator::adj_edges_iterator()
0178 {
0179 }
0180
0181 node::adj_edges_iterator::adj_edges_iterator(node n, bool start)
0182 {
0183     // iterators that are used everytime
0184     last_edge[0] = n.out_edges_end();
0185     last_edge[1] = n.in_edges_end();
0186     directed  = n.is_directed();
0187     if (!directed)
0188     {
0189     begin_edge[0] = n.out_edges_begin();
0190     begin_edge[1] = n.in_edges_begin();
0191     }
0192
0193     // set at start or end
0194     if (start)
0195     {
0196     inout = 0;
0197     akt_edge[0] = n.out_edges_begin();
0198     if (!directed)
0199     {
0200         akt_edge[1] = n.in_edges_begin();
0201         if (akt_edge[0] == last_edge[0])
0202         inout = 1;
0203     }
0204     }
0205     else
0206     {
0207     inout = directed ? 0 : 1;
0208     akt_edge[0] = n.out_edges_end();
0209     if (!directed)
0210         akt_edge[1] = n.in_edges_end();
0211     }
0212 }
0213
0214 bool node::adj_edges_iterator::operator==(const
0215                       node::adj_edges_iterator& i) const
0216 {
0217     return i.akt_edge[i.inout] == akt_edge[inout];
0218 }
0219
0220 bool node::adj_edges_iterator::operator!=(const
0221                       node::adj_edges_iterator& i) const
0222 {
0223     return i.akt_edge[i.inout] != akt_edge[inout];
0224 }
0225
0226 node::adj_edges_iterator& node::adj_edges_iterator::operator++()
0227 {
0228     if (directed)
0229     ++akt_edge[inout];
0230     else
0231     {
0232     if (inout == 0)
0233     {
0234         ++akt_edge[0];
0235         if (akt_edge[0] == last_edge[0])
0236         ++inout;
0237     }
0238     else // inout == 1
0239     {
0240         if (akt_edge[1] == last_edge[1])
0241         {
0242         inout = 0;
0243         akt_edge[0] = begin_edge[0];
0244         akt_edge[1] = begin_edge[1];
0245         if (begin_edge[0] == last_edge[0])
0246             inout = 1;
0247         }
0248         else
0249         ++akt_edge[inout];
0250     }
0251     }
0252     return *this;
0253 }
0254
0255 node::adj_edges_iterator node::adj_edges_iterator::operator++(int)
0256 {
0257     node::adj_edges_iterator tmp = *this;
0258     operator++();
0259     return tmp;
0260 }
0261
0262 node::adj_edges_iterator& node::adj_edges_iterator::operator--()
0263 {
0264     if (!directed && inout == 1 && akt_edge[1] == begin_edge[1])
0265     inout = 0;
0266     --akt_edge[inout];
0267     return *this;
0268 }
0269
0270 node::adj_edges_iterator node::adj_edges_iterator::operator--(int)
0271 {
0272     node::adj_edges_iterator tmp = *this;
0273     operator--();
0274     return tmp;
0275 }
0276
0277 const edge& node::adj_edges_iterator::operator*() const
0278 {
0279     return *akt_edge[inout];
0280 }
0281
0282 const edge* node::adj_edges_iterator::operator->() const
0283 {
0284     return akt_edge[inout].operator->();
0285 }
0286
0287 //--------------------------------------------------------------------------
0288 //   inout_edges_iterator
0289 //--------------------------------------------------------------------------
0290
0291 node::inout_edges_iterator::inout_edges_iterator()
0292 {
0293 }
0294
0295 node::inout_edges_iterator::inout_edges_iterator(node n, bool start)
0296 {
0297     // iterators that are used everytime
0298     last_edge = n.in_edges_end();
0299     begin_edge  = n.out_edges_begin();
0300
0301     // set at start or end
0302     if (start)
0303     {
0304     inout = 0;
0305     akt_edge[0] = n.in_edges_begin();
0306     akt_edge[1] = n.out_edges_begin();
0307     if (akt_edge[0] == last_edge)
0308         inout = 1;
0309     }
0310     else
0311     {
0312     inout = 1;
0313     akt_edge[0] = n.in_edges_end();
0314     akt_edge[1] = n.out_edges_end();
0315     }
0316 }
0317
0318 bool node::inout_edges_iterator::operator==(const
0319                          node::inout_edges_iterator& i) const
0320 {
0321     return i.akt_edge[i.inout] == akt_edge[inout];
0322 }
0323
0324 bool node::inout_edges_iterator::operator!=(const
0325                      node::inout_edges_iterator& i) const
0326 {
0327     return i.akt_edge[i.inout] != akt_edge[inout];
0328 }
0329
0330 node::inout_edges_iterator& node::inout_edges_iterator::operator++()
0331 {
0332     ++akt_edge[inout];
0333     if ((akt_edge[inout] == last_edge) && (inout==0))
0334         ++inout;
0335     return *this;
0336 }
0337
0338 node::inout_edges_iterator node::inout_edges_iterator::operator++(int)
0339 {
0340     node::inout_edges_iterator tmp = *this;
0341     operator++();
0342     return tmp;
0343 }
0344
0345 node::inout_edges_iterator& node::inout_edges_iterator::operator--()
0346 {
0347     if (inout == 1 && (akt_edge[1] == begin_edge))
0348     inout = 0;
0349     --akt_edge[inout];
0350     return *this;
0351 }
0352
0353 node::inout_edges_iterator node::inout_edges_iterator::operator--(int)
0354 {
0355     node::inout_edges_iterator tmp = *this;
0356     operator--();
0357     return tmp;
0358 }
0359
0360 const edge& node::inout_edges_iterator::operator*() const
0361 {
0362     return *akt_edge[inout];
0363 }
0364
0365 const edge* node::inout_edges_iterator::operator->() const
0366 {
0367     return akt_edge[inout].operator->();
0368 }
0369
0370 //--------------------------------------------------------------------------
0371 //   adj_nodes_iterator
0372 //--------------------------------------------------------------------------
0373
0374 node::adj_nodes_iterator::adj_nodes_iterator()
0375 {
0376 }
0377
0378 node::adj_nodes_iterator::adj_nodes_iterator(const node& n, bool start)
0379 {
0380     int_node = n;
0381     if (start)
0382     akt_edge = n.adj_edges_begin();
0383     else
0384     akt_edge = n.adj_edges_end();
0385 }
0386
0387 bool node::adj_nodes_iterator::operator==(const
0388                       node::adj_nodes_iterator& i) const
0389 {
0390     return i.akt_edge == akt_edge;
0391 }
0392
0393 bool node::adj_nodes_iterator::operator!=(const
0394                       node::adj_nodes_iterator& i) const
0395 {
0396     return i.akt_edge != akt_edge;
0397 }
0398
0399 node::adj_nodes_iterator& node::adj_nodes_iterator::operator++()
0400 {
0401     ++akt_edge;
0402     return *this;
0403 }
0404
0405 node::adj_nodes_iterator node::adj_nodes_iterator::operator++(int)
0406 {
0407     node::adj_nodes_iterator tmp = *this;
0408     operator++();
0409     return tmp;
0410 }
0411
0412 node::adj_nodes_iterator& node::adj_nodes_iterator::operator--()
0413 {
0414     --akt_edge;
0415     return *this;
0416 }
0417
0418 node::adj_nodes_iterator node::adj_nodes_iterator::operator--(int)
0419 {
0420     node::adj_nodes_iterator tmp = *this;
0421     operator--();
0422     return tmp;
0423 }
0424
0425 const node& node::adj_nodes_iterator::operator*() const
0426 {
0427     return int_node.opposite(*akt_edge);
0428 }
0429
0430 const node* node::adj_nodes_iterator::operator->() const
0431 {
0432     return &(int_node.opposite(*akt_edge));
0433 }
0434
0435 __GTL_END_NAMESPACE
0436
0437 //--------------------------------------------------------------------------
0438 //   end of file
0439 //--------------------------------------------------------------------------