Changeset 2034:b71f8ff62046 in lemon0.x
 Timestamp:
 04/03/06 18:34:23 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2673
 Location:
 lemon
 Files:

 1 added
 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/Makefile.am
r2031 r2034 36 36 dag_shortest_path.h \ 37 37 edge_set.h \ 38 edmonds_karp.h \ 38 39 error.h \ 39 40 eps.h \ 
lemon/graph_adaptor.h
r2031 r2034 35 35 #include <lemon/bits/graph_extender.h> 36 36 37 #include <lemon/tolerance.h> 38 37 39 #include <iostream> 38 40 … … 72 74 public: 73 75 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { } 76 77 Graph& getGraph() { return *graph; } 78 const Graph& getGraph() const { return *graph; } 74 79 75 80 typedef typename Graph::Node Node; … … 1423 1428 } 1424 1429 1425 template<typename Graph, typename Number, 1426 typename CapacityMap, typename FlowMap> 1430 template<typename Graph, typename Number, 1431 typename CapacityMap, typename FlowMap, 1432 typename Tolerance = Tolerance<Number> > 1427 1433 class ResForwardFilter { 1428 1434 const CapacityMap* capacity; 1429 1435 const FlowMap* flow; 1436 Tolerance tolerance; 1430 1437 public: 1431 1438 typedef typename Graph::Edge Key; 1432 1439 typedef bool Value; 1433 1440 1434 ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 1435 : capacity(&_capacity), flow(&_flow) { } 1436 ResForwardFilter() : capacity(0), flow(0) { } 1441 ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow, 1442 const Tolerance& _tolerance = Tolerance()) 1443 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { } 1444 1445 ResForwardFilter(const Tolerance& _tolerance) 1446 : capacity(0), flow(0), tolerance(_tolerance) { } 1447 1448 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; } 1449 void setFlow(const FlowMap& _flow) { flow = &_flow; } 1450 1451 bool operator[](const typename Graph::Edge& e) const { 1452 return tolerance.less((*flow)[e], (*capacity)[e]); 1453 } 1454 }; 1455 1456 template<typename Graph, typename Number, 1457 typename CapacityMap, typename FlowMap, 1458 typename Tolerance = Tolerance<Number> > 1459 class ResBackwardFilter { 1460 const CapacityMap* capacity; 1461 const FlowMap* flow; 1462 Tolerance tolerance; 1463 public: 1464 typedef typename Graph::Edge Key; 1465 typedef bool Value; 1466 1467 ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow, 1468 const Tolerance& _tolerance = Tolerance()) 1469 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { } 1470 ResBackwardFilter(const Tolerance& _tolerance = Tolerance()) 1471 : capacity(0), flow(0), tolerance(_tolerance) { } 1437 1472 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; } 1438 1473 void setFlow(const FlowMap& _flow) { flow = &_flow; } 1439 1474 bool operator[](const typename Graph::Edge& e) const { 1440 return (Number((*flow)[e]) < Number((*capacity)[e])); 1441 } 1442 }; 1443 1444 template<typename Graph, typename Number, 1445 typename CapacityMap, typename FlowMap> 1446 class ResBackwardFilter { 1447 const CapacityMap* capacity; 1448 const FlowMap* flow; 1449 public: 1450 typedef typename Graph::Edge Key; 1451 typedef bool Value; 1452 1453 ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 1454 : capacity(&_capacity), flow(&_flow) { } 1455 ResBackwardFilter() : capacity(0), flow(0) { } 1456 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; } 1457 void setFlow(const FlowMap& _flow) { flow = &_flow; } 1458 bool operator[](const typename Graph::Edge& e) const { 1459 return (Number(0) < Number((*flow)[e])); 1475 return tolerance.less(0, Number((*flow)[e])); 1460 1476 } 1461 1477 }; … … 1498 1514 /// 1499 1515 template<typename Graph, typename Number, 1500 typename CapacityMap, typename FlowMap> 1516 typename CapacityMap, typename FlowMap, 1517 typename Tolerance = Tolerance<Number> > 1501 1518 class ResGraphAdaptor : 1502 1519 public EdgeSubGraphAdaptor< 1503 UndirGraphAdaptor< Graph>,1504 typename UndirGraphAdaptor< Graph>::template CombinedEdgeMap<1505 ResForwardFilter< Graph, Number, CapacityMap, FlowMap>,1506 ResBackwardFilter< Graph, Number, CapacityMap, FlowMap> > > {1507 public: 1508 1509 typedef UndirGraphAdaptor< Graph> UGraph;1510 1511 typedef ResForwardFilter< Graph, Number, CapacityMap, FlowMap>1520 UndirGraphAdaptor<const Graph>, 1521 typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap< 1522 ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>, 1523 ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > { 1524 public: 1525 1526 typedef UndirGraphAdaptor<const Graph> UGraph; 1527 1528 typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap> 1512 1529 ForwardFilter; 1513 1530 1514 typedef ResBackwardFilter< Graph, Number, CapacityMap, FlowMap>1531 typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> 1515 1532 BackwardFilter; 1516 1533 … … 1545 1562 public: 1546 1563 1547 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity, 1548 FlowMap& _flow) 1549 : Parent(), capacity(&_capacity), flow(&_flow), 1550 ugraph(_graph), 1551 forward_filter(_capacity, _flow), 1552 backward_filter(_capacity, _flow), 1553 edge_filter(forward_filter, backward_filter) { 1564 const Graph& getGraph() const { return ugraph.getGraph(); } 1565 1566 /// \brief Constructor of the residual graph. 1567 /// 1568 /// Constructor of the residual graph. The parameters are the graph type, 1569 /// the flow map, the capacity map and a tolerance object. 1570 ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity, 1571 FlowMap& _flow, const Tolerance& _tolerance = Tolerance()) 1572 : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph), 1573 forward_filter(_capacity, _flow, _tolerance), 1574 backward_filter(_capacity, _flow, _tolerance), 1575 edge_filter(forward_filter, backward_filter) 1576 { 1554 1577 Parent::setGraph(ugraph); 1555 1578 Parent::setEdgeFilterMap(edge_filter); … … 1558 1581 typedef typename Parent::Edge Edge; 1559 1582 1583 /// \brief Gives back the residual capacity of the edge. 1584 /// 1585 /// Gives back the residual capacity of the edge. 1586 Number rescap(const Edge& edge) const { 1587 if (UGraph::direction(edge)) { 1588 return (*capacity)[edge](*flow)[edge]; 1589 } else { 1590 return (*flow)[edge]; 1591 } 1592 } 1593 1594 /// \brief Augment on the given edge in the residual graph. 1595 /// 1596 /// Augment on the given edge in the residual graph. It increase 1597 /// or decrease the flow on the original edge depend on the direction 1598 /// of the residual edge. 1560 1599 void augment(const Edge& e, Number a) const { 1561 1600 if (UGraph::direction(e)) { 1562 flow>set(e, (*flow)[e]+a);1601 flow>set(e, (*flow)[e] + a); 1563 1602 } else { 1564 flow>set(e, (*flow)[e]a); 1565 } 1566 } 1567 1603 flow>set(e, (*flow)[e]  a); 1604 } 1605 } 1606 1607 /// \brief Returns the direction of the edge. 1608 /// 1609 /// Returns true when the edge is same oriented as the original edge. 1568 1610 static bool forward(const Edge& e) { 1569 1611 return UGraph::direction(e); 1570 1612 } 1571 1613 1614 /// \brief Returns the direction of the edge. 1615 /// 1616 /// Returns true when the edge is opposite oriented as the original edge. 1572 1617 static bool backward(const Edge& e) { 1573 1618 return !UGraph::direction(e); 1574 1619 } 1575 1620 1621 /// \brief Gives back the forward oriented residual edge. 1622 /// 1623 /// Gives back the forward oriented residual edge. 1576 1624 static Edge forward(const typename Graph::Edge& e) { 1577 1625 return UGraph::direct(e, true); 1578 1626 } 1579 1627 1628 /// \brief Gives back the backward oriented residual edge. 1629 /// 1630 /// Gives back the backward oriented residual edge. 1580 1631 static Edge backward(const typename Graph::Edge& e) { 1581 1632 return UGraph::direct(e, false); 1582 1633 } 1583 1584 1634 1585 1635 /// \brief Residual capacity map. … … 1596 1646 : res_graph(&_res_graph) {} 1597 1647 1598 Number operator[](const Edge& e) const { 1599 if (ResGraphAdaptor::direction(e)) 1600 return (*(res_graph>capacity))[e](*(res_graph>flow))[e]; 1601 else 1602 return (*(res_graph>flow))[e]; 1648 Number operator[](const Edge& e) const { 1649 return res_graph>rescap(e); 1603 1650 } 1604 1651
Note: See TracChangeset
for help on using the changeset viewer.