00001
00010 #ifndef __iterator_hpp
00011 #define __iterator_hpp
00012
00013 #include"graph.hpp"
00014 #include<stack>
00015 #include<queue>
00016 #include<list>
00017
00018 namespace graphgen{
00019
00020
00022
00023
00031 class undirected_graph::isequence{
00032 const undirected_graph& graph;
00033 vertex_type vertex;
00034
00035 public:
00037 isequence( const undirected_graph& g )
00038 : graph(g), vertex(0)
00039 {}
00040
00042 vertex_type operator*() const{
00043 return vertex;
00044 }
00045
00047 isequence& operator++() {
00048 ++vertex;
00049 return *this;
00050 }
00051
00056 bool operator==( const isequence& rhs ) const{
00057 return ((vertex==rhs.vertex) && (&graph==&(rhs.graph)));
00058 }
00059
00064 bool valid() const{
00065 return (vertex < graph.nv());
00066 }
00067
00073 link_type via() const{ return null_link; }
00074 };
00075
00076
00081 class undirected_graph::ineighbors{
00082 const undirected_graph& graph;
00083 vertex_type start;
00084 link_type via_link;
00085
00086 public:
00088 ineighbors( const undirected_graph& g, vertex_type v )
00089 :graph(g), start(v), via_link( graph.out_link(v) ) {}
00090
00092 vertex_type operator*() const{
00093 return graph.target( via_link );
00094 }
00095
00097 ineighbors& operator++(){
00098 via_link = graph.next_out_link(via_link);
00099 return *this;
00100 }
00101
00106 bool operator==( const ineighbors& rhs ){
00107 return (( &graph == &rhs.graph ) && ( via_link == rhs.via_link ));
00108 }
00109
00114 link_type via() const {
00115 return via_link;
00116 }
00117
00122 bool valid() const{
00123 return (via_link != null_link );
00124 }
00125 };
00126
00127
00128
00139 class undirected_graph::ibreadth{
00140 const undirected_graph& graph;
00141
00142 vertex_type vertex;
00143
00144 std::queue< link_type, std::list<link_type> > queue;
00145 std::vector<unsigned int> visited;
00146
00147 public:
00151 ibreadth( const undirected_graph& g, vertex_type root )
00152 : graph(g), vertex(root),
00153 queue(), visited(graph.nv(), 0)
00154 {
00155 queue.push(null_link);
00156 visited[root]=1;
00157 }
00158
00160 ibreadth( const undirected_graph& g )
00161 : graph(g), vertex(0), queue(), visited(graph.nv(),0)
00162 {
00163 queue.push(null_link);
00164 visited[vertex]=1;
00165 }
00166
00168 vertex_type operator*(){
00169 return vertex;
00170 }
00171
00173 ibreadth& operator++(){
00174
00175 link_type out = graph.out_link(vertex);
00176 while( out != null_link ){
00177 if( !visited[graph.target( out )] ){
00178 queue.push(out);
00179 }
00180 out = graph.next_out_link(out);
00181 }
00182
00183
00184 while( !queue.empty() && visited[vertex] ){
00185 queue.pop();
00186 if( queue.empty() ) break;
00187 vertex = graph.target( queue.front() );
00188 }
00189
00190 if( queue.empty() ) return *this;
00191
00192
00193 visited[vertex] = visited[graph.source(queue.front())]+1;
00194
00195 return *this;
00196 }
00197
00204 bool operator==( ibreadth& rhs ){
00205 return ( &graph == &(rhs.graph) ) && ( vertex == rhs.vertex );
00206 }
00207
00211 link_type via() const {
00212 return queue.front();
00213 }
00214
00219 unsigned int distance(){ return visited[vertex]-1; }
00220
00225 bool valid() const{
00226 return !queue.empty();
00227 }
00228 };
00229
00230
00231
00238 class undirected_graph::idepth{
00239 const undirected_graph& graph;
00240
00241 vertex_type vertex;
00242
00243 std::stack< vertex_type, std::list<link_type> > stack;
00244 std::vector<bool> visited;
00245
00246 public:
00248 idepth( const undirected_graph& g, vertex_type root )
00249 : graph(g), vertex(root),
00250 stack(), visited( graph.nv(), false )
00251 {
00252 stack.push(null_link);
00253 }
00254
00256 idepth( const undirected_graph& g )
00257 : graph(g), vertex(0),
00258 stack(), visited( graph.nv(), false )
00259 {
00260 stack.push(null_link);
00261 }
00262
00264 vertex_type operator*() const{
00265 return vertex;
00266 }
00267
00269 idepth& operator++(){
00270
00271 stack.pop();
00272 visited[vertex] = true;
00273
00274
00275 link_type out = graph.out_link(vertex);
00276 while( out != null_link ){
00277 if( !visited[graph.target( out )] )stack.push(out);
00278
00279 out = graph.next_out_link(out);
00280 }
00281
00282
00283 if( stack.empty() ) return *this;
00284
00285 vertex=graph.target(stack.top());
00286
00287 while( !stack.empty() && visited[vertex] ){
00288 stack.pop(); if( stack.empty() ) break;
00289 vertex = graph.target( stack.top() );
00290 }
00291
00292 return *this;
00293 }
00294
00301 bool operator==( idepth& rhs ) const{
00302 return (&graph == &(rhs.graph)) && (vertex == rhs.vertex);
00303 }
00304
00306 link_type via() const {
00307 return stack.top();
00308 }
00309
00311 bool valid() const{
00312 return !stack.empty();
00313 }
00314 };
00315
00316
00322 class undirected_graph::ilinks {
00323 typedef undirected_graph G;
00324
00325 const G& graph;
00326
00327 int index;
00328
00329 public:
00330
00331
00333 ilinks(const G& g): graph(g), index(0) {};
00334
00336 ilinks(const G& g, int i): graph(g), index(i) {};
00337
00339 ilinks& operator++(){ index++; return *this; }
00340
00342 ilinks& operator--(){ index--; return *this; }
00343
00345 bool valid(){ return (index>=0 && index<graph.links_.n()); }
00346
00348 link_type operator[](int i){ return graph.links_[i]*2; }
00349
00351 link_type operator*(){ return graph.links_[index]*2; }
00352 };
00353
00354
00355 }
00356
00357 #endif