gtl/src/st_number.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   st_number.cpp
0005 //
0006 //==========================================================================
0007 // $Id: st_number.cpp,v 1.10 2001/11/07 13:58:11 pick Exp $
0008
0009 #include <GTL/st_number.h>
0010
0011 #include <cassert>
0012
0013 #ifdef __GTL_MSVCC
0014 #   ifdef _DEBUG
0015 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0016 #   error SEARCH NOT ENABLED
0017 #   endif
0018 #   define new DEBUG_NEW
0019 #   undef THIS_FILE
0020     static char THIS_FILE[] = __FILE__;
0021 #   endif   // _DEBUG
0022 #endif  // __GTL_MSVCC
0023
0024 __GTL_BEGIN_NAMESPACE
0025
0026 pathfinder::pathfinder (const graph& G, edge st, node s)
0027 {
0028     node t = s.opposite (st);
0029     dfs_num.init (G, 0);
0030     low_num.init (G);
0031     tree.init (G, list<edge>());
0032     back.init (G, list<edge>());
0033     forward.init (G, list<edge>());
0034
0035     //
0036     // There is a problem with node/edge maps of iterators with Visual C++
0037     // which I don´t fully understand at the moment. Anyway the init for the
0038     // maps below is only needed to allocate memory, which is done anyway, when
0039     // values are assigned to it.
0040     //
0041
0042 #ifndef __GTL_MSVCC
0043     to_low.init (G);
0044     to_father.init (G);
0045     pos.init (G);
0046 #endif
0047
0048     used.init (G,0);
0049     act_dfs_num  = 1;
0050     new_nodes = G.number_of_nodes();
0051     is_biconn = true;
0052
0053     //
0054     // Do DFS with biconnectivity extensions.
0055     //
0056
0057     dfs_num[t] = act_dfs_num++;
0058     low_num[t] = dfs_num[t];
0059     new_nodes--;
0060
0061     dfs_sub (s, t);
0062
0063     if (new_nodes != 0) {
0064     is_biconn = false;
0065     }
0066
0067     used[t] = used[s] = 1;
0068 }
0069
0070
0071 void pathfinder::dfs_sub (node& curr, node& father)
0072 {
0073     low_num[curr] = dfs_num[curr] = act_dfs_num++;
0074     new_nodes--;
0075
0076     node::adj_edges_iterator it = curr.adj_edges_begin();
0077     node::adj_edges_iterator end = curr.adj_edges_end();
0078
0079     while (it != end) {
0080     edge adj = *it;
0081     node opp = curr.opposite(adj);
0082
0083     if (dfs_num[opp] == 0) {
0084
0085         list<edge>::iterator tmp =
0086         tree[curr].insert (tree[curr].end(), adj);
0087         to_father[opp] = tmp;
0088
0089         dfs_sub (opp, curr);
0090
0091         if (low_num[opp] < low_num[curr]) {
0092         low_num[curr] = low_num[opp];
0093         to_low[curr] = tmp;
0094         }
0095
0096         if (low_num[opp] >= dfs_num[curr]) {
0097         is_biconn = false;
0098         }
0099
0100     } else if (opp != father && dfs_num[opp] < dfs_num[curr]) {
0101         list<edge>::iterator back_pos =
0102         back[curr].insert (back[curr].end(), adj);
0103         list<edge>::iterator forward_pos =
0104         forward[opp].insert (forward[opp].end(), adj);
0105         pos[adj] = pos_pair (forward_pos, back_pos);
0106
0107         if (dfs_num[opp] < low_num[curr]) {
0108         low_num[curr] = dfs_num[opp];
0109         to_low[curr] = back_pos;
0110         }
0111     }
0112
0113     ++it;
0114     }
0115 }
0116
0117
0118 //--------------------------------------------------------------------------
0119 //   ITERATOR
0120 //--------------------------------------------------------------------------
0121
0122 pathfinder::const_iterator::const_iterator (pathfinder& _pf, node n) :
0123     pf (_pf)
0124 {
0125     if (!pf.back[n].empty()) {
0126     edge back = pf.back[n].front();
0127     curr = n.opposite (back);
0128     pf.used[curr] = 1;
0129     pf.back[n].pop_front();
0130     pf.forward[curr].erase (pf.pos[back].first);
0131     state = END;
0132
0133     } else if (!pf.tree[n].empty()) {
0134     curr = n.opposite (pf.tree[n].front());
0135     pf.used[curr] = 1;
0136     pf.tree[n].pop_front();
0137     state = DOWN;
0138
0139     } else if (!pf.forward[n].empty()) {
0140     edge forward = pf.forward[n].front();
0141     curr = n.opposite (forward);
0142     pf.forward[n].pop_front();
0143     pf.back[curr].erase (pf.pos[forward].second);
0144
0145     if (pf.used[curr]) {
0146         state = END;
0147     } else {
0148         pf.used[curr] = 1;
0149         state = UP;
0150     }
0151     }
0152 }
0153
0154 pathfinder::const_iterator& pathfinder::const_iterator::operator++ ()
0155 {
0156     list<edge>::iterator tmp;
0157     edge adj;
0158     node opp;
0159
0160     switch (state) {
0161     case END :
0162         curr = node();
0163         break;
0164
0165     case UP :
0166         tmp = pf.to_father[curr];
0167         curr = curr.opposite (*tmp);
0168         pf.tree[curr].erase (tmp);
0169
0170         if (pf.used[curr]) {
0171         state = END;
0172         } else {
0173         pf.used[curr] = 1;
0174         }
0175
0176         break;
0177
0178     case DOWN :
0179         tmp = pf.to_low[curr];
0180         adj = *tmp;
0181         opp = curr.opposite (adj);
0182
0183         if (pf.used[opp]) {
0184         pf.forward[opp].erase (pf.pos[adj].first);
0185         pf.back[curr].erase (tmp);
0186         state = END;
0187         } else {
0188         pf.tree[curr].erase (tmp);
0189         pf.used[opp] = 1;
0190         }
0191
0192         curr = opp;
0193         break;
0194
0195     default:
0196         assert (0);
0197     }
0198
0199     return *this;
0200 }
0201
0202
0203 pathfinder::const_iterator pathfinder::const_iterator::operator++ (int)
0204 {
0205     const_iterator tmp = *this;
0206     operator++();
0207     return tmp;
0208 }
0209
0210
0211 //--------------------------------------------------------------------------
0212 //   ST-NUMBER
0213 //--------------------------------------------------------------------------
0214
0215 int st_number::check (graph& G)
0216 {
0217     if (G.is_directed()) return GTL_ERROR;
0218
0219     pf = new pathfinder (G, st, s);
0220
0221     return pf->is_valid() ? GTL_OK : GTL_ERROR;
0222 }
0223
0224
0225 int st_number::run (graph& G)
0226 {
0227     list<node> order;
0228     node t = s.opposite (st);
0229     order.push_back (t);
0230     node tmp = s;
0231     pathfinder::const_iterator end = pf->end ();
0232     int act_st = 1;
0233
0234     while (tmp != t) {
0235     pathfinder::const_iterator it = pf->path (tmp);
0236     list<node>::iterator pos;
0237
0238     if (it == end) {
0239         st_num[tmp] = act_st++;
0240         st_ord.push_back(tmp);
0241         tmp = order.back();
0242         order.pop_back();
0243
0244     } else {
0245         pos = order.end();
0246
0247         while (it != end) {
0248         pos = order.insert (pos, *it);
0249         ++it;
0250         }
0251
0252         order.erase (pos);
0253     }
0254     }
0255
0256     st_num[t] = act_st;
0257     st_ord.push_back (t);
0258
0259     delete pf;
0260
0261     return GTL_OK;
0262 }
0263
0264 __GTL_END_NAMESPACE
0265
0266 //--------------------------------------------------------------------------
0267 //   end of file
0268 //--------------------------------------------------------------------------