549 FlowMap* flow; |
549 FlowMap* flow; |
550 const CapacityMap* capacity; |
550 const CapacityMap* capacity; |
551 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
551 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
552 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
552 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
553 typedef typename AugGraph::Edge AugEdge; |
553 typedef typename AugGraph::Edge AugEdge; |
|
554 typename Graph::NodeMap<int> used; //0 |
554 |
555 |
555 public: |
556 public: |
556 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : |
557 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : |
557 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { } |
558 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } |
558 bool augmentOnShortestPath() { |
559 bool augmentOnShortestPath() { |
559 AugGraph res_graph(*G, *flow, *capacity); |
560 AugGraph res_graph(*G, *flow, *capacity); |
560 bool _augment=false; |
561 bool _augment=false; |
561 |
562 |
562 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
563 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
563 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
564 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
564 typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
565 typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
565 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
566 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
566 if (S->get(s)) { |
567 if ((S->get(s)) && (used.get(s)<1) ) { |
567 Number u=0; |
568 //Number u=0; |
568 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
569 //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
569 u+=flow->get(e); |
570 //u+=flow->get(e); |
570 if (u<1) { |
571 //if (u<1) { |
571 res_bfs.pushAndSetReached(s); |
572 res_bfs.pushAndSetReached(s); |
572 pred.set(s, AugEdge(INVALID)); |
573 pred.set(s, AugEdge(INVALID)); |
573 } |
574 //} |
574 } |
575 } |
575 } |
576 } |
576 |
577 |
577 typename AugGraph::NodeMap<Number> free(res_graph); |
578 typename AugGraph::NodeMap<Number> free(res_graph); |
578 |
579 |
588 free.set(w, std::min(free.get(v), res_graph.free(e))); |
589 free.set(w, std::min(free.get(v), res_graph.free(e))); |
589 } else { |
590 } else { |
590 free.set(w, res_graph.free(e)); |
591 free.set(w, res_graph.free(e)); |
591 } |
592 } |
592 n=res_graph.head(e); |
593 n=res_graph.head(e); |
593 if (T->get(n)) { |
594 if (T->get(n) && (used.get(n)<1) ) { |
594 Number u=0; |
595 //Number u=0; |
595 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
596 //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
596 u+=flow->get(f); |
597 //u+=flow->get(f); |
597 if (u<1) { |
598 //if (u<1) { |
598 _augment=true; |
599 _augment=true; |
599 break; |
600 break; |
600 } |
601 //} |
601 } |
602 } |
602 } |
603 } |
603 |
604 |
604 ++res_bfs; |
605 ++res_bfs; |
605 } //end of searching augmenting path |
606 } //end of searching augmenting path |
606 |
607 |
607 if (_augment) { |
608 if (_augment) { |
608 //Node n=t; |
609 //Node n=t; |
|
610 used.set(n, 1); //mind2 vegen jav |
609 Number augment_value=free.get(n); |
611 Number augment_value=free.get(n); |
610 while (res_graph.valid(pred.get(n))) { |
612 while (res_graph.valid(pred.get(n))) { |
611 AugEdge e=pred.get(n); |
613 AugEdge e=pred.get(n); |
612 res_graph.augment(e, augment_value); |
614 res_graph.augment(e, augment_value); |
613 n=res_graph.tail(e); |
615 n=res_graph.tail(e); |
614 } |
616 } |
|
617 used.set(n, 1); //mind2 vegen jav |
615 } |
618 } |
616 |
619 |
617 return _augment; |
620 return _augment; |
618 } |
621 } |
619 |
622 |