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