Changeset 186:47cd1716870e in lemon0.x for src/work
 Timestamp:
 03/15/04 17:30:20 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@262
 Location:
 src/work/alpar
 Files:

 1 added
 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/emptygraph.h
r183 r186 13 13 /// An empty graph class. 14 14 15 /// This class provides all the common features of a grap fstructure,16 /// however completely without implementations orreal data structures15 /// This class provides all the common features of a graph structure, 16 /// however completely without implementations and real data structures 17 17 /// behind the interface. 18 18 /// All graph algorithms should compile with this class, but it will not … … 32 32 /// The base type of the node iterators. 33 33 34 /// This \c Nodeis the base type of each node iterators,34 /// This is the base type of each node iterators, 35 35 /// thus each kind of node iterator will convert to this. 36 36 class Node { … … 59 59 60 60 /// This iterator goes through each node. 61 62 /// This iterator goes through each node. 63 /// Its usage is quite simple, for example you can count the number 64 /// of nodes in graph \c G of type \c Graph like this: 65 /// \code 66 ///int count=0; 67 ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; 68 /// \endcode 61 69 class NodeIt : public Node { 62 70 public: … … 92 100 }; 93 101 94 /// This iterator goes trought the outgoing edges of a certain graph. 102 /// This iterator goes trought the outgoing edges of a node. 103 104 /// This iterator goes trought the \e outgoing edges of a certain node 105 /// of a graph. 106 /// Its usage is quite simple, for example you can count the number 107 /// of outgoing edges of a node \c n 108 /// in graph \c G of type \c Graph as follows. 109 /// \code 110 ///int count=0; 111 ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++; 112 /// \endcode 95 113 96 114 class OutEdgeIt : public Edge { … … 110 128 }; 111 129 130 /// This iterator goes trought the incoming edges of a node. 131 132 /// This iterator goes trought the \e incoming edges of a certain node 133 /// of a graph. 134 /// Its usage is quite simple, for example you can count the number 135 /// of outgoing edges of a node \c n 136 /// in graph \c G of type \c Graph as follows. 137 /// \code 138 ///int count=0; 139 ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++; 140 /// \endcode 141 112 142 class InEdgeIt : public Edge { 113 143 public: … … 120 150 }; 121 151 // class SymEdgeIt : public Edge {}; 152 153 /// This iterator goes through each edge. 154 155 /// This iterator goes through each edge of a graph. 156 /// Its usage is quite simple, for example you can count the number 157 /// of edges in a graph \c G of type \c Graph as follows: 158 /// \code 159 ///int count=0; 160 ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; 161 /// \endcode 122 162 class EdgeIt : public Edge { 123 163 public: … … 174 214 175 215 /// Checks if a node iterator is valid 216 217 ///\todo Maybe, it would be better if iterator converted to 218 ///bool directly, as Jacint prefers. 176 219 bool valid(const Node) const { return true;} 177 220 /// Checks if an edge iterator is valid 221 222 ///\todo Maybe, it would be better if iterator converted to 223 ///bool directly, as Jacint prefers. 178 224 bool valid(const Edge) const { return true;} 179 225 … … 195 241 196 242 /// \return the new node. 243 /// 197 244 Node addNode() { return INVALID;} 198 245 ///Add a new edge to the graph. … … 228 275 229 276 230 ///Read/write map of the nodes to type \c T. 231 277 ///Read/write/reference map of the nodes to type \c T. 278 279 ///Read/write/reference map of the nodes to type \c T. 280 /// \sa MemoryMapSkeleton 232 281 /// \todo We may need copy constructor 233 282 /// \todo We may need conversion from other nodetype … … 263 312 }; 264 313 265 ///Read/write map of the edges to type \c T. 266 267 ///Read/write map of the edges to type \c T. 268 ///It behaves exactly the same way as \ref NodeMap. 314 ///Read/write/reference map of the edges to type \c T. 315 316 ///Read/write/reference map of the edges to type \c T. 317 ///It behaves exactly in the same way as \ref NodeMap. 318 /// \sa NodeMap 319 /// \sa MemoryMapSkeleton 320 /// \todo We may need copy constructor 321 /// \todo We may need conversion from other edgetype 322 /// \todo We may need operator= 269 323 template<class T> class EdgeMap 270 324 { 
src/work/alpar/smart_graph.h
r185 r186 13 13 class SymSmartGraph; 14 14 15 // template<typename T> class SymSmartGraph::SymEdgeMap; 16 15 ///A smart graph class. 16 17 ///This is a simple and fast graph implementation. 18 ///It is also quite memory efficient, but at the price 19 ///that <b> it does not support node and edge deletion</b>. 20 ///Apart from this it conforms to the graph interface documented under 21 ///the description of \ref GraphSkeleton. 22 ///\sa \ref GraphSkeleton. 17 23 class SmartGraph { 18 24 … … 56 62 // protected: 57 63 // HELPME: 58 p ublic:64 protected: 59 65 ///\bug It must be public because of SymEdgeMap. 60 66 /// … … 100 106 int edgeNum() const { return edges.size(); } //FIXME: What is this? 101 107 108 ///\bug This function does something different than 109 ///its name would suggests... 102 110 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? 111 ///\bug This function does something different than 112 ///its name would suggests... 103 113 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? 104 114 105 106 115 Node tail(Edge e) const { return edges[e.n].tail; } 107 116 Node head(Edge e) const { return edges[e.n].head; } … … 481 490 ///The purpose of this graph structure is to handle graphs 482 491 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair 483 ///of oppositely directed edges. You can define edge maps which 484 ///stores a common value for the edge pairs. The usual edge maps can be used 492 ///of oppositely directed edges. 493 ///There is a new edge map type called 494 ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap" 495 ///that complements this 496 ///feature by 497 ///storing shared values for the edge pairs. The usual 498 ///\ref GraphSkeleton::EdgeMap "EdgeMap" 499 ///can be used 485 500 ///as well. 486 501 /// 487 ///The oppositely directed edge can also be obtained easily. 502 ///The oppositely directed edge can also be obtained easily 503 ///using \ref opposite. 504 ///\warning It shares the similarity with \ref SmartGraph that 505 ///it is not possible to delete edges or nodes from the graph. 506 //\sa \ref SmartGraph. 488 507 489 508 class SymSmartGraph : public SmartGraph 490 509 { 491 510 public: 511 template<typename T> class SymEdgeMap; 512 template<typename T> friend class SymEdgeMap; 513 492 514 SymSmartGraph() : SmartGraph() { } 493 515 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } … … 499 521 } 500 522 523 ///The oppositely directed edge. 524 525 ///Returns the oppositely directed 526 ///pair of the edge \c e. 501 527 Edge opposite(Edge e) const 502 528 { … … 506 532 } 507 533 534 ///Common data storage for the edge pairs. 535 536 ///This map makes it possible to store data shared by the oppositely 537 ///directed pairs of edges. 508 538 template <typename T> class SymEdgeMap : public DynMapBase<Edge> 509 539 { … … 514 544 typedef Edge KeyType; 515 545 516 SymEdgeMap(const S martGraph &_G) :546 SymEdgeMap(const SymSmartGraph &_G) : 517 547 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2) 518 548 { 519 G>dyn_edge_maps.push_back(this);520 } 521 SymEdgeMap(const S martGraph &_G,const T &t) :549 static_cast<const SymSmartGraph*>(G)>dyn_edge_maps.push_back(this); 550 } 551 SymEdgeMap(const SymSmartGraph &_G,const T &t) : 522 552 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t) 523 553 { … … 551 581 if(G) { 552 582 std::vector<DynMapBase<Edge>* >::iterator i; 553 for(i=G>dyn_edge_maps.begin(); 554 i!=G>dyn_edge_maps.end() && *i!=this; ++i) ; 583 for(i=static_cast<const SymSmartGraph*>(G)>dyn_edge_maps.begin(); 584 i!=static_cast<const SymSmartGraph*>(G)>dyn_edge_maps.end() 585 && *i!=this; ++i) ; 555 586 //if(*i==this) G>dyn_edge_maps.erase(i); //Way too slow... 556 587 //A better way to do that: (Is this really important?) 557 588 if(*i==this) { 558 *i= G>dyn_edge_maps.back();559 G>dyn_edge_maps.pop_back();589 *i=static_cast<const SymSmartGraph*>(G)>dyn_edge_maps.back(); 590 static_cast<const SymSmartGraph*>(G)>dyn_edge_maps.pop_back(); 560 591 } 561 592 }
Note: See TracChangeset
for help on using the changeset viewer.