COIN-OR::LEMON - Graph Library

Changeset 335:999eb3cd7b49 in lemon-0.x


Ignore:
Timestamp:
04/16/04 10:26:00 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@454
Message:

jflsjfljskf

Location:
src
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/include/dijkstra.h

    r296 r335  
    187187        distance.set(v, oldvalue);
    188188       
    189         for(OutEdgeIt e = G.template first<OutEdgeIt>(v);
     189        { //FIXME this bracket is for e to be local
     190          OutEdgeIt e;
     191        for(G.first(e, v);
    190192            G.valid(e); G.next(e)) {
    191193          Node w=G.head(e);
     
    208210          }
    209211        }
     212      } //FIXME tis bracket
    210213      }
    211214  }
  • src/work/list_graph.h

    r309 r335  
    295295    //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
    296296
    297     template< typename It >
    298     It first() const {
    299       It e;
    300       first(e);
    301       return e;
    302     }
    303 
    304     template< typename It >
    305     It first(Node v) const {
    306       It e;
    307       first(e, v);
    308       return e;
    309     }
     297//     template< typename It >
     298//     It first() const {
     299//       It e;
     300//       first(e);
     301//       return e;
     302//     }
     303
     304//     template< typename It >
     305//     It first(Node v) const {
     306//       It e;
     307//       first(e, v);
     308//       return e;
     309//     }
    310310
    311311    bool valid(Node n) const { return n.valid(); }
     
    353353
    354354    void clear() {
    355       while (first<NodeIt>().valid()) erase(first<NodeIt>());
     355      NodeIt e;
     356      while (this->valid(first(e))) erase(e);
     357      //while (first<NodeIt>().valid()) erase(first<NodeIt>());
    356358    }
    357359
  • src/work/marci/graph_wrapper.h

    r330 r335  
    77namespace hugo {
    88
     9  /// Graph wrappers
     10
     11  /// The main parts of HUGOlib are the different graph structures,
     12  /// generic graph algorithms, graph concepts which couple these, and
     13  /// graph wrappers. While the previous ones are more or less clear, the
     14  /// latter notion needs further explanation.
     15  /// Graph wrappers are graph classes which serve for considering graph
     16  /// structures in different ways. A short example makes the notion much more
     17  /// clear.
     18  /// Suppose that we have an instance \code g \endcode of a directed graph
     19  /// type say \code ListGraph \endcode and an algorithm
     20  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
     21  /// is needed to run on the reversed oriented graph.
     22  /// It can be expensive (in time or in memory usage) to copy
     23  /// \code g \endcode with the reversed orientation.
     24  /// Thus, a wrapper class
     25  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
     26  /// The code looks as follows
     27  /// \code
     28  /// ListGraph g;
     29  /// RevGraphWrapper<ListGraph> rgw(g);
     30  /// int result=algorithm(rgw);
     31  /// \endcode
     32  /// After running the algorithm, the original graph \code g \endcode
     33  /// is untouched. Thus the above used graph wrapper is to consider the
     34  /// original graph with reversed orientation.
     35  /// This techniques gives rise to an elegant code, and
     36  /// based on stable graph wrappers, complex algorithms can be
     37  /// implemented easily.
     38  /// In flow, circulation and bipartite matching problems, the residual
     39  /// graph is of particualar significance. Combining a wrapper impleneting
     40  /// this, shortest path algorithms and mimimum mean cycle algorithms,
     41  /// a range of weighted and cardinality optimization algorithms can be
     42  /// obtained. For lack of space, for other examples,
     43  /// the interested user is referred to the detailed domumentation of graph
     44  /// wrappers.
     45  /// The behavior of graph wrappers are very different. Some of them keep
     46  /// capabilities of the original graph while in other cases this would be
     47  /// meaningless. This means that the concepts that they are model of depend
     48  /// on the graph wrapper, and the wrapped graph(s).
     49  /// If an edge of \code rgw \endcode is deleted, this is carried out by
     50  /// deleting the corresponding edge of \code g \endcode. But for a residual
     51  /// graph, this operation has no sense.
     52  /// Let we stand one more example here to simplify your work.
     53  /// wrapper class
     54  /// \code template<typename Graph> class RevGraphWrapper; \endcode
     55  /// has constructor
     56  /// \code RevGraphWrapper(Graph& _g); \endcode.
     57  /// This means that in a situation,
     58  /// when a \code const ListGraph& \endcode reference to a graph is given,
     59  /// then it have to be instatiated with Graph=const ListGraph.
     60  /// \code
     61  /// int algorithm1(const ListGraph& g) {
     62  ///   RevGraphWrapper<const ListGraph> rgw(g);
     63  ///   return algorithm2(rgw);
     64  /// }
     65  /// \endcode
    966  template<typename Graph>
    1067  class GraphWrapper {
     
    110167    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    111168//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
    112     template< typename It > It first() const {
    113       It e; this->first(e); return e; }
    114 
    115     template< typename It > It first(const Node& v) const {
    116       It e; this->first(e, v); return e; }
     169//     template< typename It > It first() const {
     170//       It e; this->first(e); return e; }
     171
     172//     template< typename It > It first(const Node& v) const {
     173//       It e; this->first(e, v); return e; }
    117174
    118175    Node head(const Edge& e) const {
     
    275332  };
    276333
    277   //Subgraph on the same node-set and partial edge-set
     334  /// Wrapper for hiding nodes and edges from a graph.
     335 
     336  /// This wrapper shows a graph with filtered node-set and
     337  /// edge-set. The quick brown fox iterators jumps over
     338  /// the lazy dog nodes or edges if the values for them are false
     339  /// in the bool maps.
    278340  template<typename Graph, typename NodeFilterMap,
    279341           typename EdgeFilterMap>
     
    484546    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
    485547
    486     template< typename It > It first() const {
    487       It e; this->first(e); return e; }
    488    
    489     template< typename It > It first(const Node& v) const {
    490       It e; this->first(e, v); return e; }
     548//     template< typename It > It first() const {
     549//       It e; this->first(e); return e; }
     550   
     551//     template< typename It > It first(const Node& v) const {
     552//       It e; this->first(e, v); return e; }
    491553  };
    492554
     
    743805    }
    744806
    745     template<typename I> I& first(I& i) const { graph->first(i); return i; }
    746     template<typename I, typename P> I& first(I& i, const P& p) const {
    747       graph->first(i, p); return i; }
     807//     template<typename I> I& first(I& i) const { graph->first(i); return i; }
     808//     template<typename I, typename P> I& first(I& i, const P& p) const {
     809//       graph->first(i, p); return i; }
    748810
    749811    NodeIt& next(NodeIt& n) const {
     
    769831
    770832//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
    771     template< typename It > It first() const {
    772       It e; this->first(e); return e; }
    773 
    774     template< typename It > It first(const Node& v) const {
    775       It e; this->first(e, v); return e; }
     833//     template< typename It > It first() const {
     834//       It e; this->first(e); return e; }
     835
     836//     template< typename It > It first(const Node& v) const {
     837//       It e; this->first(e, v); return e; }
    776838
    777839//    Node head(const Edge& e) const { return gw.head(e); }
     
    12521314   
    12531315
    1254     template< typename It >
    1255     It first() const {
    1256       It e;
    1257       first(e);
    1258       return e;
    1259     }
    1260 
    1261     template< typename It >
    1262     It first(Node v) const {
    1263       It e;
    1264       first(e, v);
    1265       return e;
    1266     }
     1316//     template< typename It >
     1317//     It first() const {
     1318//       It e;
     1319//       first(e);
     1320//       return e;
     1321//     }
     1322
     1323//     template< typename It >
     1324//     It first(Node v) const {
     1325//       It e;
     1326//       first(e, v);
     1327//       return e;
     1328//     }
    12671329
    12681330    Node tail(Edge e) const {
     
    18011863//     }
    18021864   
    1803     template< typename It > It first() const {
    1804       It e; this->first(e); return e; }
    1805    
    1806     template< typename It > It first(const Node& v) const {
    1807       It e; this->first(e, v); return e; }
     1865//     template< typename It > It first() const {
     1866//       It e; this->first(e); return e; }
     1867   
     1868//     template< typename It > It first(const Node& v) const {
     1869//       It e; this->first(e, v); return e; }
    18081870
    18091871    void erase(const OutEdgeIt& e) const {
Note: See TracChangeset for help on using the changeset viewer.