gtl/src/edge.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   edge.cpp
0005 //
0006 //==========================================================================
0007 // $Id: edge.cpp,v 1.17 2001/11/07 13:58:09 pick Exp $
0008
0009 #include <GTL/node_data.h>
0010 #include <GTL/edge_data.h>
0011 #include <cassert>
0012 #include <iostream>
0013
0014 #ifdef __GTL_MSVCC
0015 #   ifdef _DEBUG
0016 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0017 #   error SEARCH NOT ENABLED
0018 #   endif
0019 #   define new DEBUG_NEW
0020 #   undef THIS_FILE
0021     static char THIS_FILE[] = __FILE__;
0022 #   endif   // _DEBUG
0023 #endif  // __GTL_MSVCC
0024
0025 __GTL_BEGIN_NAMESPACE
0026
0027 //--------------------------------------------------------------------------
0028 //   edge
0029 //--------------------------------------------------------------------------
0030
0031 edge::edge() :
0032     data(0)
0033 {
0034 }
0035
0036 GTL_EXTERN ostream& operator<< (ostream& os, const edge& e) {
0037     if (e != edge ()) {
0038     return os << e.source() << "-->" << e.target();
0039     } else {
0040     return os << "UNDEF";
0041     }
0042 }
0043
0044 node edge::source() const
0045 {
0046     return data->nodes[0].front();
0047 }
0048
0049 node edge::target() const
0050 {
0051     return data->nodes[1].front();
0052 }
0053
0054 void edge::change_source (node new_source) {
0055     //
0056     // First delete this edge from source's adjacency list
0057     // and clear the list of sources
0058     //
0059
0060     list<node>::iterator the_nodes = data->nodes[0].begin();
0061     list<node>::iterator the_nodes_end = data->nodes[0].end();
0062
0063     while(the_nodes != the_nodes_end)
0064     {
0065     (*the_nodes).data->edges[1].erase (data->adj_pos[0].front());
0066     data->adj_pos[0].pop_front();
0067
0068     the_nodes = data->nodes[0].erase (the_nodes);
0069     }
0070
0071     //
0072     // Just to be sure :)
0073     //
0074
0075     assert (data->nodes[0].empty());
0076     assert (data->adj_pos[0].empty());
0077
0078     //
0079     // insert this edge in the list of outgoing edges of new_source
0080     //
0081
0082     data->adj_pos[0].push_back(new_source.data->edges[1].insert (
0083     new_source.data->edges[1].end(), *this));
0084
0085     //
0086     // make new_source a source of this node.
0087     //
0088
0089     data->nodes[0].push_back (new_source);
0090 }
0091
0092
0093 void edge::change_target (node new_target) {
0094     //
0095     // First delete this edge from target's adjacency list
0096     // and clear the list of targets
0097     //
0098
0099     list<node>::iterator the_nodes = data->nodes[1].begin();
0100     list<node>::iterator the_nodes_end = data->nodes[1].end();
0101
0102     while(the_nodes != the_nodes_end)
0103     {
0104     (*the_nodes).data->edges[0].erase (data->adj_pos[1].front());
0105     data->adj_pos[1].pop_front();
0106
0107     the_nodes = data->nodes[1].erase (the_nodes);
0108     }
0109
0110     //
0111     // Just to be sure :)
0112     //
0113
0114     assert (data->nodes[1].empty());
0115     assert (data->adj_pos[1].empty());
0116
0117     //
0118     // insert this edge in the list of incoming edges of new_target
0119     //
0120
0121     data->adj_pos[1].push_back(new_target.data->edges[0].insert (
0122     new_target.data->edges[0].end(), *this));
0123
0124     //
0125     // make new_target a target of this node.
0126     //
0127
0128     data->nodes[1].push_back (new_target);
0129 }
0130
0131
0132 void edge::reverse ()
0133 {
0134     //
0135     // First delete this edge from all adjacency lists
0136     //
0137
0138     list<node>::iterator the_nodes = data->nodes[0].begin();
0139     list<node>::iterator the_nodes_end = data->nodes[0].end();
0140
0141     while(the_nodes != the_nodes_end)
0142     {
0143     (*the_nodes).data->edges[1].erase (data->adj_pos[0].front());
0144     data->adj_pos[0].pop_front();
0145
0146     ++the_nodes;
0147     }
0148
0149     the_nodes = data->nodes[1].begin();
0150     the_nodes_end = data->nodes[1].end();
0151
0152     while(the_nodes != the_nodes_end)
0153     {
0154     (*the_nodes).data->edges[0].erase (data->adj_pos[1].front());
0155     data->adj_pos[1].pop_front();
0156
0157     ++the_nodes;
0158     }
0159
0160     //
0161     // Now the lists of positions in the adjacency - lists should be empty
0162     //
0163
0164     assert (data->adj_pos[0].empty());
0165     assert (data->adj_pos[1].empty());
0166
0167     //
0168     // Now insert this edge reversed
0169     //
0170
0171     the_nodes = data->nodes[1].begin();
0172     the_nodes_end = data->nodes[1].end();
0173
0174     while(the_nodes != the_nodes_end)
0175     {
0176     data->adj_pos[0].push_back((*the_nodes).data->edges[1].insert (
0177         (*the_nodes).data->edges[1].end(), *this));
0178
0179     ++the_nodes;
0180     }
0181
0182     the_nodes = data->nodes[0].begin();
0183     the_nodes_end = data->nodes[0].end();
0184
0185     while(the_nodes != the_nodes_end)
0186     {
0187     data->adj_pos[1].push_back((*the_nodes).data->edges[0].insert (
0188         (*the_nodes).data->edges[0].end(), *this));
0189
0190     ++the_nodes;
0191     }
0192
0193     //
0194     // swap nodes[0] and nodes[1]
0195     //
0196
0197     list<node> tmp = data->nodes[0];
0198     data->nodes[0] = data->nodes[1];
0199     data->nodes[1] = tmp;
0200 }
0201
0202
0203
0204 list<node> edge::sources() const
0205 {
0206     return data->nodes[0];
0207 }
0208
0209 list<node> edge::targets() const
0210 {
0211     return data->nodes[1];
0212 }
0213
0214 int edge::id() const
0215 {
0216     return data->id;
0217 }
0218
0219 bool edge::is_hidden () const
0220 {
0221     return data->hidden;
0222 }
0223
0224 void edge::remove_from(int where) const
0225 {
0226     list<node>::iterator the_nodes = data->nodes[where].begin();
0227     list<node>::iterator the_nodes_end = data->nodes[where].end();
0228
0229     list<list<edge>::iterator>::iterator the_adj_pos =
0230     data->adj_pos[where].begin();
0231
0232     while(the_nodes != the_nodes_end)
0233     {
0234     the_nodes->data->edges[1-where].erase(*the_adj_pos);
0235
0236     ++the_nodes;
0237     ++the_adj_pos;
0238     }
0239 }
0240
0241 const node& edge::opposite(node n) const
0242 {
0243     // not implemented for hypergraphs
0244     assert(data);
0245
0246     node& s = *(data->nodes[0].begin());
0247     if (n == s)
0248     return *(data->nodes[1].begin());
0249     else
0250     return s;
0251 }
0252
0253 GTL_EXTERN bool operator==(edge e1, edge e2)
0254 {
0255     return e1.data == e2.data;
0256 }
0257
0258 GTL_EXTERN bool operator!=(edge e1, edge e2)
0259 {
0260     return e1.data != e2.data;
0261 }
0262
0263 GTL_EXTERN bool operator<(edge e1, edge e2)
0264 {
0265     return e1.data < e2.data;
0266 }
0267
0268 __GTL_END_NAMESPACE
0269
0270 //--------------------------------------------------------------------------
0271 //   end of file
0272 //--------------------------------------------------------------------------