Changeset 923:acbef5dd0e65 in lemon0.x for src
 Timestamp:
 09/29/04 21:02:26 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1234
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r921 r923 36 36 37 37 /// \addtogroup gwrappers 38 /// Amain parts of LEMON are the different graph structures,38 /// The main parts of LEMON are the different graph structures, 39 39 /// generic graph algorithms, graph concepts which couple these, and 40 40 /// graph wrappers. While the previous ones are more or less clear, the … … 100 100 ///parts of the lib. Use them at you own risk. 101 101 /// 102 ///This is the base type for the Graph Wrappers. 103 ///\todo Some more docs... 102 /// This is the base type for most of LEMON graph wrappers. 103 /// This class implements a trivial graph wrapper i.e. it only wraps the 104 /// functions and types of the graph. The purpose of this class is to 105 /// make easier implementing graph wrappers. E.g. if a wrapper is 106 /// considered which differs from the wrapped graph only in some of its 107 /// functions or types, then it can be derived from GraphWrapper, and only the 108 /// differences should be implemented. 104 109 /// 105 110 ///\author Marton Makai … … 237 242 ///parts of the lib. Use them at you own risk. 238 243 /// 239 /// A graph wrapper which reverses the orientation of the edges. 240 /// Thus \c Graph have to be a directed graph type. 241 /// 244 /// Let \f$G=(V, A)\f$ be a directed graph and 245 /// suppose that a graph instange \c g of type 246 /// \c ListGraph implements \f$G\f$. 247 /// \code 248 /// ListGraph g; 249 /// \endcode 250 /// For each directed edge 251 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 252 /// reversing its orientation. 253 /// Then RevGraphWrapper implements the graph structure with nodeset 254 /// \f$V\f$ and edgeset 255 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 256 /// reversing the orientation of its edges. The following code shows how 257 /// such an instance can be constructed. 258 /// \code 259 /// RevGraphWrapper<ListGraph> gw(g); 260 /// \endcode 242 261 ///\author Marton Makai 243 262 template<typename Graph> … … 315 334 /// 316 335 /// This wrapper shows a graph with filtered nodeset and 317 /// edgeset. Given a boolvalued map on the nodeset and one on 318 /// the edgeset of the graphs, the iterators show only the objects 319 /// having true value. 320 /// The quick brown fox iterators jump over 321 /// the lazy dog nodes or edges if their values for are false in the 322 /// corresponding bool maps. 336 /// edgeset. 337 /// Given a boolvalued map on the nodeset and one on 338 /// the edgeset of the graph, the iterators show only the objects 339 /// having true value. We have to note that this does not mean that an 340 /// induced subgraph is obtained, the nodeiterator cares only the filter 341 /// on the nodeset, and the edgeiterators care only the filter on the 342 /// edgeset. 343 /// \code 344 /// typedef SmartGraph Graph; 345 /// Graph g; 346 /// typedef Graph::Node Node; 347 /// typedef Graph::Edge Edge; 348 /// Node u=g.addNode(); //node of id 0 349 /// Node v=g.addNode(); //node of id 1 350 /// Node e=g.addEdge(u, v); //edge of id 0 351 /// Node f=g.addEdge(v, u); //edge of id 1 352 /// Graph::NodeMap<bool> nm(g, true); 353 /// nm.set(u, false); 354 /// Graph::EdgeMap<bool> em(g, true); 355 /// em.set(e, false); 356 /// typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW; 357 /// SubGW gw(g, nm, em); 358 /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 359 /// std::cout << ":)" << std::endl; 360 /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 361 /// \endcode 362 /// The output of the above code is the following. 363 /// \code 364 /// 1 365 /// :) 366 /// 1 367 /// \endcode 368 /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to 369 /// \c Graph::Node that is why \c g.id(n) can be applied. 323 370 /// 324 371 ///\author Marton Makai … … 612 659 ///parts of the lib. Use them at you own risk. 613 660 /// 614 /// Suppose that for a directed graph $G=(V, A)$, 615 /// two bool valued maps on the edgeset, 616 /// $forward_filter$, and $backward_filter$ 617 /// is given, and we are dealing with the directed graph 618 /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$. 661 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 662 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 663 /// reversing its orientation. We are given moreover two bool valued 664 /// maps on the edgeset, 665 /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 666 /// SubBidirGraphWrapper implements the graph structure with nodeset 667 /// \f$V\f$ and edgeset 668 /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$. 619 669 /// The purpose of writing + instead of union is because parallel 620 /// edges can ar ose.670 /// edges can arise. (Similarly, antiparallel edges also can arise). 621 671 /// In other words, a subgraph of the bidirected graph obtained, which 622 672 /// is given by orienting the edges of the original graph in both directions. 623 /// An example for such a construction is the \c RevGraphWrapper where the 673 /// As the oppositely directed edges are logically different, 674 /// the maps are able to attach different values for them. 675 /// 676 /// An example for such a construction is \c RevGraphWrapper where the 624 677 /// forward_filter is everywhere false and the backward_filter is 625 678 /// everywhere true. We note that for sake of efficiency, … … 633 686 /// As wrappers usually, the SubBidirGraphWrapper implements the 634 687 /// above mentioned graph structure without its physical storage, 635 /// that is the whole stuff eats constant memory. 636 /// As the oppositely directed edges are logically different, 637 /// the maps are able to attach different values for them. 688 /// that is the whole stuff is stored in constant memory. 638 689 template<typename Graph, 639 690 typename ForwardFilterMap, typename BackwardFilterMap>
Note: See TracChangeset
for help on using the changeset viewer.