COIN-OR::LEMON - Graph Library

Changeset 923:acbef5dd0e65 in lemon-0.x


Ignore:
Timestamp:
09/29/04 21:02:26 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1234
Message:

more docs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_wrapper.h

    r921 r923  
    3636
    3737  /// \addtogroup gwrappers
    38   /// A main parts of LEMON are the different graph structures,
     38  /// The main parts of LEMON are the different graph structures,
    3939  /// generic graph algorithms, graph concepts which couple these, and
    4040  /// graph wrappers. While the previous ones are more or less clear, the
     
    100100  ///parts of the lib. Use them at you own risk.
    101101  ///
    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.
    104109  ///
    105110  ///\author Marton Makai
     
    237242  ///parts of the lib. Use them at you own risk.
    238243  ///
    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 node-set
     254  /// \f$V\f$ and edge-set
     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
    242261  ///\author Marton Makai
    243262  template<typename Graph>
     
    315334  ///
    316335  /// This wrapper shows a graph with filtered node-set and
    317   /// edge-set. Given a bool-valued map on the node-set and one on
    318   /// the edge-set 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  /// edge-set.
     337  /// Given a bool-valued map on the node-set and one on
     338  /// the edge-set 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 node-iterator cares only the filter
     341  /// on the node-set, and the edge-iterators care only the filter on the
     342  /// edge-set.
     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.
    323370  ///
    324371  ///\author Marton Makai
     
    612659  ///parts of the lib. Use them at you own risk.
    613660  ///
    614   /// Suppose that for a directed graph $G=(V, A)$,
    615   /// two bool valued maps on the edge-set,
    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 edge-set,
     665  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
     666  /// SubBidirGraphWrapper implements the graph structure with node-set
     667  /// \f$V\f$ and edge-set
     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$.
    619669  /// The purpose of writing + instead of union is because parallel
    620   /// edges can arose.
     670  /// edges can arise. (Similarly, antiparallel edges also can arise).
    621671  /// In other words, a subgraph of the bidirected graph obtained, which
    622672  /// 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
    624677  /// forward_filter is everywhere false and the backward_filter is
    625678  /// everywhere true. We note that for sake of efficiency,
     
    633686  /// As wrappers usually, the SubBidirGraphWrapper implements the
    634687  /// 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.
    638689  template<typename Graph,
    639690           typename ForwardFilterMap, typename BackwardFilterMap>
Note: See TracChangeset for help on using the changeset viewer.