00001 #ifndef ADJACENCYVECTORIMPL_H
00002 #define ADJACENCYVECTORIMPL_H
00003
00004 #include <Utilities/mersenneTwister.h>
00005 #include <vector>
00006
00007 template<typename Vtype, typename Etype>
00008 class AVNode;
00009 template<typename Vtype, typename Etype>
00010 class AVEdge;
00011
00012 template<typename Vtype, typename Etype>
00013 class AdjacencyVectorImpl
00014 {
00015 public:
00016
00017 typedef unsigned int SizeType;
00018 typedef typename std::vector< AVNode< Vtype, Etype> >::iterator NodeIterator;
00019 typedef typename std::vector< AVEdge< Vtype, Etype> >::iterator EdgeIterator;
00020 typedef SizeType* NodeDescriptor;
00021 typedef typename std::pair<SizeType, SizeType>* EdgeDescriptor;
00022
00023 AdjacencyVectorImpl()
00024 {
00025 }
00026
00027 ~AdjacencyVectorImpl()
00028 {
00029 NodeIterator end = m_nodes.end();
00030 EdgeIterator e, end_edges;
00031
00032 for( NodeIterator u = m_nodes.begin(); u != end; ++u)
00033 {
00034 delete u->getDescriptor();
00035 end_edges = u->m_edges.end();
00036 for( e = u->m_edges.begin(); e != end_edges; ++e)
00037 {
00038 delete e->getDescriptor();
00039 }
00040 }
00041 }
00042
00043 const NodeDescriptor& insertNode()
00044 {
00045 m_auxNodeDescriptor = new SizeType( m_nodes.size());
00046
00047 AVNode<Vtype,Etype> newNode;
00048 m_nodes.push_back( newNode);
00049 m_auxNodeIterator = m_nodes.end() - 1;
00050 m_auxNodeIterator->setDescriptor(m_auxNodeDescriptor);
00051 return m_auxNodeDescriptor;
00052 }
00053
00054 const EdgeDescriptor& insertEdge( const NodeDescriptor& uD, const NodeDescriptor& vD)
00055 {
00056 NodeIterator u = getNodeIterator( uD);
00057 NodeIterator v = getNodeIterator( vD);
00058
00059 AVEdge<Vtype, Etype> newEdge;
00060 newEdge.m_adjacentNode = v - m_nodes.begin();
00061 (*u).m_edges.push_back( newEdge);
00062 newEdge.m_adjacentNode = u - m_nodes.begin();
00063 (*v).m_backEdges.push_back( newEdge);
00064
00065 EdgeIterator e = u->m_edges.end() - 1;
00066 EdgeIterator k = v->m_backEdges.end() - 1;
00067
00068 e->m_oppositeEdge = k - v->m_backEdges.begin();
00069 k->m_oppositeEdge = e - u->m_edges.begin();
00070 e->m_isBackEdge = false;
00071 k->m_isBackEdge = true;
00072
00073 m_auxEdgeDescriptor = new std::pair<SizeType,SizeType>( u - m_nodes.begin(), e - u->m_edges.begin());
00074 e->setDescriptor(m_auxEdgeDescriptor);
00075 k->setDescriptor(m_auxEdgeDescriptor);
00076
00077 return m_auxEdgeDescriptor;
00078 }
00079
00080 void eraseNode( NodeDescriptor& descriptor)
00081 {
00082 NodeIterator u = getNodeIterator( descriptor);
00083 EdgeIterator e, k, end;
00084
00085 end = endEdges(u);
00086 for( EdgeIterator e = beginEdges(u); e!= end; ++e)
00087 {
00088 eraseEdge( (*e).id);
00089 }
00090
00091 end = endBackEdges(u);
00092 for( EdgeIterator e = beginBackEdges(u); e!= end; ++e)
00093 {
00094 k = getOppositeIterator( e);
00095 eraseEdge( (*k).id);
00096 }
00097
00098 delete descriptor;
00099 descriptor = 0;
00100
00101 NodeIterator v;
00102 NodeIterator end_nodes = m_nodes.end();
00103 for( v = m_nodes.erase(u); v != end_nodes; ++v)
00104 {
00105 sanitiseNode( v);
00106 }
00107 }
00108
00109 void eraseEdge( EdgeDescriptor& descriptor)
00110 {
00111 EdgeIterator e = getEdgeIterator(descriptor);
00112 NodeIterator v = m_nodes.begin()+ e->m_adjacentNode;
00113 EdgeIterator k = v->m_backEdges.begin() + e->m_oppositeEdge;
00114 NodeIterator u = m_nodes.begin()+ k->m_adjacentNode;
00115
00116 EdgeIterator f,h,end;
00117 end = (*v).m_backEdges.end();
00118 for( f = (*v).m_backEdges.erase(k); f != end; ++f)
00119 {
00120 --(f->getDescriptor()->second);
00121 h = getOppositeEdgeIterator( f);
00122 --(h->m_adjacentNode);
00123 }
00124
00125 end = (*u).m_edges.end();
00126 for( f = (*u).m_edges.erase(e); f != end; ++f)
00127 {
00128 --(f->getDescriptor()->second);
00129 h = getOppositeEdgeIterator( f);
00130 --(h->m_adjacentNode);
00131 }
00132
00133 delete descriptor;
00134 descriptor = 0;
00135 }
00136
00137 void sanitiseNode( const NodeIterator& u)
00138 {
00139 SizeType position =*(u->getDescriptor());
00140 --position;
00141 *(u->getDescriptor()) = position;
00142
00143 EdgeIterator end,k;
00144 NodeIterator adjacentNode;
00145 SizeType adjacentNodePosition;
00146
00147 end = u->m_edges.end();
00148 for( EdgeIterator e = u->m_edges.begin(); e != end; ++e)
00149 {
00150 e->getDescriptor()->first = position;
00151 if( e->m_adjacentNode < position) continue;
00152
00153 --(e->m_adjacentNode);
00154 k = getOppositeEdgeIterator( e);
00155 k.m_adjacentNode = position;
00156 }
00157
00158 end = u->m_backEdges.end();
00159 for( EdgeIterator e = u->m_backEdges.begin(); e != end; ++e)
00160 {
00161 e->getDescriptor()->first = position;
00162 if( e->m_adjacentNode < position) continue;
00163
00164 --(e->m_adjacentNode);
00165 k = getOppositeEdgeIterator( e);
00166 k.m_adjacentNode = position;
00167 }
00168 }
00169
00170 const NodeIterator& beginNodes()
00171 {
00172 m_auxNodeIterator = m_nodes.begin();
00173 return m_auxNodeIterator;
00174 }
00175
00176 const NodeIterator& endNodes()
00177 {
00178 m_auxNodeIterator = m_nodes.end();
00179 return m_auxNodeIterator;
00180 }
00181
00182 const EdgeIterator& beginEdges( const NodeIterator& u)
00183 {
00184 m_auxEdgeIterator = u->m_edges.begin();
00185 return m_auxEdgeIterator;
00186 }
00187
00188 const EdgeIterator& endEdges( const NodeIterator& u)
00189 {
00190 m_auxEdgeIterator = u->m_edges.end();
00191 return m_auxEdgeIterator;
00192 }
00193
00194 const EdgeIterator& beginBackEdges( const NodeIterator& u)
00195 {
00196 m_auxEdgeIterator = u->m_backEdges.begin();
00197 return m_auxEdgeIterator;
00198 }
00199
00200 const EdgeIterator& endBackEdges( const NodeIterator& u)
00201 {
00202 m_auxEdgeIterator = u->m_backEdges.end();
00203 return m_auxEdgeIterator;
00204 }
00205
00206 const NodeIterator& chooseNode()
00207 {
00208 double random = m_random.getRandomNormalizedDouble();
00209 SizeType pos = m_nodes.size() * random;
00210
00211 m_auxNodeIterator = m_nodes.begin() + pos;
00212 return m_auxNodeIterator;
00213 }
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225 const EdgeIterator& getEdgeIterator( const EdgeDescriptor& descriptor)
00226 {
00227 m_auxEdgeIterator = (m_nodes.begin() + descriptor->first)->m_edges.begin() + descriptor->second;
00228 return m_auxEdgeIterator;
00229 }
00230
00231 const NodeIterator& getNodeIterator( const NodeDescriptor& descriptor)
00232 {
00233 m_auxNodeIterator = m_nodes.begin()+(*descriptor);
00234 return m_auxNodeIterator;
00235 }
00236
00237 const NodeIterator& getAdjacentNodeIterator( const EdgeIterator& e)
00238 {
00239 m_auxNodeIterator = m_nodes.begin() + e->m_adjacentNode;
00240 return m_auxNodeIterator;
00241 }
00242
00243 const EdgeIterator& getOppositeEdgeIterator( const EdgeIterator& e)
00244 {
00245 if( !isBackEdge(e))
00246 {
00247 m_auxEdgeIterator = m_nodes[ e->m_adjacentNode].m_backEdges.begin() + e->m_oppositeEdge;
00248 return m_auxEdgeIterator;
00249 }
00250 m_auxEdgeIterator = m_nodes[ e->m_adjacentNode].m_edges.begin() + e->m_oppositeEdge;
00251 return m_auxEdgeIterator;
00252 }
00253
00254 const bool& isBackEdge( const EdgeIterator& e) const
00255 {
00256 return e->m_isBackEdge;
00257 }
00258
00259 bool edgeExists( const EdgeDescriptor& descriptor)
00260 {
00261 return descriptor != 0;
00262 }
00263
00264 bool nodeExists( const NodeDescriptor& descriptor)
00265 {
00266 return descriptor != 0;
00267 }
00268
00269 const NodeIterator& nilNode()
00270 {
00271 m_auxNodeIterator = m_nodes.end();
00272 return m_auxNodeIterator;
00273 }
00274
00275 const EdgeIterator& nilEdge()
00276 {
00277 m_auxEdgeIterator = (*m_nodes.begin()).m_edges.end();
00278 return m_auxEdgeIterator;
00279 }
00280
00281 private:
00282 std::vector< AVNode< Vtype, Etype> > m_nodes;
00283 NodeIterator m_auxNodeIterator;
00284 EdgeIterator m_auxEdgeIterator;
00285 NodeDescriptor m_auxNodeDescriptor;
00286 EdgeDescriptor m_auxEdgeDescriptor;
00287 MersenneTwister m_random;
00288 };
00289
00290 template<typename Vtype, typename Etype>
00291 class AVEdge : public GraphElement< Etype, typename AdjacencyVectorImpl<Vtype,Etype>::EdgeDescriptor>
00292 {
00293
00294 public:
00295 typedef typename AdjacencyVectorImpl<Vtype,Etype>::EdgeDescriptor EdgeDescriptor;
00296 typedef typename AdjacencyVectorImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;
00297 typedef typename AdjacencyVectorImpl<Vtype,Etype>::SizeType SizeType;
00298
00299 AVEdge( unsigned int init = 0): GraphElement< Etype, EdgeDescriptor>()
00300 {
00301 }
00302
00303 AVEdge( NodeDescriptor adjacentNode , EdgeDescriptor oppositeEdge , NodeDescriptor descriptor = 0, Etype data = Etype()):
00304 GraphElement< Etype, EdgeDescriptor>(descriptor),
00305 m_adjacentNode(adjacentNode),
00306 m_oppositeEdge(oppositeEdge)
00307 {
00308 }
00309
00310 SizeType m_adjacentNode;
00311 SizeType m_oppositeEdge;
00312 bool m_isBackEdge;
00313 };
00314
00315 template<typename Vtype, typename Etype>
00316 class AVNode : public GraphElement< Vtype, typename AdjacencyVectorImpl<Vtype,Etype>::NodeDescriptor>
00317 {
00318 public:
00319 typedef typename AdjacencyVectorImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;
00320
00321 AVNode():GraphElement< Vtype, NodeDescriptor>()
00322 {
00323 }
00324
00325 AVNode( NodeDescriptor descriptor):GraphElement< Vtype, NodeDescriptor>(descriptor)
00326 {
00327 }
00328
00329 std::vector< AVEdge< Vtype, Etype> > m_edges;
00330 std::vector< AVEdge< Vtype, Etype> > m_backEdges;
00331 };
00332
00333
00334
00335 #endif //ADJACENCYVECTORIMPL_H