Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/nagamochi_ibaraki.h
changeset 2387 317b9a88c350
parent 2376 0ed45a6c74b1
child 2391 14a343be7a5a
equal deleted inserted replaced
2:35e5dcdced80 3:941ff2924281 
   436     /// Sets the heap and the cross reference used by algorithm.
 
   436     /// Sets the heap and the cross reference used by algorithm.
 
   437     /// If you don't use this function before calling \ref run(),
 
   437     /// If you don't use this function before calling \ref run(),
 
   438     /// it will allocate one. The destuctor deallocates this
 
   438     /// it will allocate one. The destuctor deallocates this
 
   439     /// automatically allocated map, of course.
 
   439     /// automatically allocated map, of course.
 
   440     /// \return <tt> (*this) </tt>
 
   440     /// \return <tt> (*this) </tt>
 
   441     MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
 
   441     MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
 
   442       if(local_heap_cross_ref) {
 
   442       if(local_heap_cross_ref) {
 
   443 	delete _heap_cross_ref;
 
   443 	delete _heap_cross_ref;
 
   444 	local_heap_cross_ref = false;
 
   444 	local_heap_cross_ref = false;
 
   445       }
 
   445       }
 
   446       _heap_cross_ref = &crossRef;
 
   446       _heap_cross_ref = &cr;
 
   447       if(local_heap) {
 
   447       if(local_heap) {
 
   448 	delete _heap;
 
   448 	delete _heap;
 
   449 	local_heap = false;
 
   449 	local_heap = false;
 
   450       }
 
   450       }
 
   451       _heap = &heap;
 
   451       _heap = &hp;
 
   452       return *this;
 
   452       return *this;
 
   453     }
 
   453     }
 
   454 
   454 
   455   private:
 
   455   private:
 
   456 
   456 
  1166     /// Sets the heap and the cross reference used by algorithm.
 
  1166     /// Sets the heap and the cross reference used by algorithm.
 
  1167     /// If you don't use this function before calling \ref run(),
 
  1167     /// If you don't use this function before calling \ref run(),
 
  1168     /// it will allocate one. The destuctor deallocates this
 
  1168     /// it will allocate one. The destuctor deallocates this
 
  1169     /// automatically allocated heap and cross reference, of course.
 
  1169     /// automatically allocated heap and cross reference, of course.
 
  1170     /// \return <tt> (*this) </tt>
 
  1170     /// \return <tt> (*this) </tt>
 
  1171     NagamochiIbaraki &heap(Heap& heap, HeapCrossRef &crossRef)
 
  1171     NagamochiIbaraki &heap(Heap& hp, HeapCrossRef &cr)
 
  1172     {
 
  1172     {
 
  1173       if (local_heap_cross_ref) {
 
  1173       if (local_heap_cross_ref) {
 
  1174 	delete _heap_cross_ref;
 
  1174 	delete _heap_cross_ref;
 
  1175 	local_heap_cross_ref=false;
 
  1175 	local_heap_cross_ref=false;
 
  1176       }
 
  1176       }
 
  1177       _heap_cross_ref = &crossRef;
 
  1177       _heap_cross_ref = &cr;
 
  1178       if (local_heap) {
 
  1178       if (local_heap) {
 
  1179 	delete _heap;
 
  1179 	delete _heap;
 
  1180 	local_heap=false;
 
  1180 	local_heap=false;
 
  1181       }
 
  1181       }
 
  1182       _heap = &heap;
 
  1182       _heap = &hp;
 
  1183       return *this;
 
  1183       return *this;
 
  1184     }
 
  1184     }
 
  1185 
  1185 
  1186     /// \brief Sets the aux graph.
 
  1186     /// \brief Sets the aux graph.
 
  1187     ///
 
  1187     ///
 
  1316             sep = nodes.size();
 
  1316             sep = nodes.size();
 
  1317           }
 
  1317           }
 
  1318         }
 
  1318         }
 
  1319       }
 
  1319       }
 
  1320 
  1320 
  1321       if ((int)nodes.size() < _node_num) {
 
  1321       if (int(nodes.size()) < _node_num) {
 
  1322         _aux_graph->clear();
 
  1322         _aux_graph->clear();
 
  1323         _node_num = 1;
 
  1323         _node_num = 1;
 
  1324         _cut.clear();
 
  1324         _cut.clear();
 
  1325         for (int i = 0; i < (int)nodes.size(); ++i) {
 
  1325         for (int i = 0; i < int(nodes.size()); ++i) {
 
  1326           typename Graph::Node n = (*_first)[nodes[i]];
 
  1326           typename Graph::Node n = (*_first)[nodes[i]];
 
  1327           while (n != INVALID) {
 
  1327           while (n != INVALID) {
 
  1328             _cut.push_back(n);
 
  1328             _cut.push_back(n);
 
  1329             n = (*_next)[n];
 
  1329             n = (*_next)[n];
 
  1330           }
 
  1330           }
 
  1358         if (_edge_cut[e] >= emc) {
 
  1358         if (_edge_cut[e] >= emc) {
 
  1359           ufe.join(_aux_graph->source(e), _aux_graph->target(e));
 
  1359           ufe.join(_aux_graph->source(e), _aux_graph->target(e));
 
  1360         }
 
  1360         }
 
  1361       }
 
  1361       }
 
  1362 
  1362 
  1363       if (ufe.size((typename Ufe::ClassIt)(ufe)) == _node_num) {
 
  1363       typedef typename Ufe::ClassIt UfeCIt;
 
       
  1364       if (ufe.size(UfeCIt(ufe)) == _node_num) {
 
  1364         _aux_graph->clear();
 
  1365         _aux_graph->clear();
 
  1365         _node_num = 1;
 
  1366         _node_num = 1;
 
  1366         return true;
 
  1367         return true;
 
  1367       }
 
  1368       }
 
  1368       
  1369       
  1370 
  1371 
  1371       typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
 
  1372       typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
 
  1372       for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) {
 
  1373       for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) {
 
  1373         if (ufe.size(c) == 1) continue;
 
  1374         if (ufe.size(c) == 1) continue;
 
  1374         for (typename Ufe::ItemIt r(ufe, c); r != INVALID; ++r) {
 
  1375         for (typename Ufe::ItemIt r(ufe, c); r != INVALID; ++r) {
 
  1375           if ((Node)r == (Node)c) continue;
 
  1376           if (static_cast<Node>(r) == static_cast<Node>(c)) continue;
 
  1376           _next->set((*_last)[c], (*_first)[r]);
 
  1377           _next->set((*_last)[c], (*_first)[r]);
 
  1377           _last->set(c, (*_last)[r]);
 
  1378           _last->set(c, (*_last)[r]);
 
  1378           remnodes.push_back(r);
 
  1379           remnodes.push_back(r);
 
  1379           --_node_num;
 
  1380           --_node_num;
 
  1380         }
 
  1381         }
 
  1405         info.capacity = (*_aux_capacity)[e];
 
  1406         info.capacity = (*_aux_capacity)[e];
 
  1406         addedges.push_back(info);
 
  1407         addedges.push_back(info);
 
  1407         remedges.push_back(e);
 
  1408         remedges.push_back(e);
 
  1408       }
 
  1409       }
 
  1409 
  1410 
  1410       for (int i = 0; i < (int)remedges.size(); ++i) {
 
  1411       for (int i = 0; i < int(remedges.size()); ++i) {
 
  1411         _aux_graph->erase(remedges[i]);
 
  1412         _aux_graph->erase(remedges[i]);
 
  1412       }
 
  1413       }
 
  1413 
  1414 
  1414       sort(addedges.begin(), addedges.end(), EdgeInfoLess());
 
  1415       sort(addedges.begin(), addedges.end(), EdgeInfoLess());
 
  1415 
  1416 
  1416       {
 
  1417       {
 
  1417         int i = 0;
 
  1418         int i = 0;
 
  1418         while (i < (int)addedges.size()) {
 
  1419         while (i < int(addedges.size())) {
 
  1419           Node sn = addedges[i].source;
 
  1420           Node sn = addedges[i].source;
 
  1420           Node tn = addedges[i].target;
 
  1421           Node tn = addedges[i].target;
 
  1421           Value ec = addedges[i].capacity;
 
  1422           Value ec = addedges[i].capacity;
 
  1422           ++i;
 
  1423           ++i;
 
  1423           while (i < (int)addedges.size() && 
  1424           while (i < int(addedges.size()) && 
  1424                  sn == addedges[i].source && tn == addedges[i].target) {
 
  1425                  sn == addedges[i].source && tn == addedges[i].target) {
 
  1425             ec += addedges[i].capacity;
 
  1426             ec += addedges[i].capacity;
 
  1426             ++i;
 
  1427             ++i;
 
  1427           }
 
  1428           }
 
  1428           typename AuxGraph::UEdge ne = _aux_graph->addEdge(sn, tn);
 
  1429           typename AuxGraph::UEdge ne = _aux_graph->addEdge(sn, tn);
 
  1440         
  1441         
  1441         (*_aux_cut_value)[c] = cutvalue;
 
  1442         (*_aux_cut_value)[c] = cutvalue;
 
  1442         
  1443         
  1443       }
 
  1444       }
 
  1444 
  1445 
  1445       for (int i = 0; i < (int)remnodes.size(); ++i) {
 
  1446       for (int i = 0; i < int(remnodes.size()); ++i) {
 
  1446         _aux_graph->erase(remnodes[i]);
 
  1447         _aux_graph->erase(remnodes[i]);
 
  1447       }
 
  1448       }
 
  1448 
  1449 
  1449       return _node_num == 1;
 
  1450       return _node_num == 1;
 
  1450     }
 
  1451     }
 
  1498     /// It sets the nodes of one of the two partitions to true in
 
  1499     /// It sets the nodes of one of the two partitions to true in
 
  1499     /// the given BoolNodeMap. The map contains a valid cut if the
 
  1500     /// the given BoolNodeMap. The map contains a valid cut if the
 
  1500     /// map have been set false previously. 
  1501     /// map have been set false previously. 
  1501     template <typename NodeMap>
 
  1502     template <typename NodeMap>
 
  1502     Value quickMinCut(NodeMap& nodeMap) const { 
  1503     Value quickMinCut(NodeMap& nodeMap) const { 
  1503       for (int i = 0; i < (int)_cut.size(); ++i) {
 
  1504       for (int i = 0; i < int(_cut.size()); ++i) {
 
  1504         nodeMap.set(_cut[i], true);
 
  1505         nodeMap.set(_cut[i], true);
 
  1505       }
 
  1506       }
 
  1506       return minCut();
 
  1507       return minCut();
 
  1507     }
 
  1508     }
 
  1508 
  1509
lemon-0.x