1372 std::vector<typename AuxGraph::Node> remnodes; |
1372 std::vector<typename AuxGraph::Node> remnodes; |
1373 |
1373 |
1374 typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID); |
1374 typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID); |
1375 for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) { |
1375 for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) { |
1376 if (ufe.size(c) == 1) continue; |
1376 if (ufe.size(c) == 1) continue; |
|
1377 Node cn = ufe.item(c); |
1377 for (typename Ufe::ItemIt r(ufe, c); r != INVALID; ++r) { |
1378 for (typename Ufe::ItemIt r(ufe, c); r != INVALID; ++r) { |
1378 if (static_cast<Node>(r) == static_cast<Node>(c)) continue; |
1379 if (static_cast<Node>(r) == static_cast<Node>(cn)) continue; |
1379 _next->set((*_last)[c], (*_first)[r]); |
1380 _next->set((*_last)[cn], (*_first)[r]); |
1380 _last->set(c, (*_last)[r]); |
1381 _last->set(cn, (*_last)[r]); |
1381 remnodes.push_back(r); |
1382 remnodes.push_back(r); |
1382 --_node_num; |
1383 --_node_num; |
1383 } |
1384 } |
1384 } |
1385 } |
1385 |
1386 |
1386 std::vector<EdgeInfo> addedges; |
1387 std::vector<EdgeInfo> addedges; |
1387 std::vector<UEdge> remedges; |
1388 std::vector<UEdge> remedges; |
1388 |
1389 |
1389 for (typename AuxGraph::UEdgeIt e(*_aux_graph); |
1390 for (typename AuxGraph::UEdgeIt e(*_aux_graph); |
1390 e != INVALID; ++e) { |
1391 e != INVALID; ++e) { |
1391 Node sn = ufe.find(_aux_graph->source(e)); |
1392 int sc = ufe.find(_aux_graph->source(e)); |
1392 Node tn = ufe.find(_aux_graph->target(e)); |
1393 int tc = ufe.find(_aux_graph->target(e)); |
1393 if ((ufe.size(sn) == 1 && ufe.size(tn) == 1)) { |
1394 if ((ufe.size(sc) == 1 && ufe.size(tc) == 1)) { |
1394 continue; |
1395 continue; |
1395 } |
1396 } |
1396 if (sn == tn) { |
1397 if (sc == tc) { |
1397 remedges.push_back(e); |
1398 remedges.push_back(e); |
1398 continue; |
1399 continue; |
1399 } |
1400 } |
|
1401 Node sn = ufe.item(sc); |
|
1402 Node tn = ufe.item(tc); |
|
1403 |
1400 EdgeInfo info; |
1404 EdgeInfo info; |
1401 if (sn < tn) { |
1405 if (sn < tn) { |
1402 info.source = sn; |
1406 info.source = sn; |
1403 info.target = tn; |
1407 info.target = tn; |
1404 } else { |
1408 } else { |
1433 } |
1437 } |
1434 } |
1438 } |
1435 |
1439 |
1436 for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) { |
1440 for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) { |
1437 if (ufe.size(c) == 1) continue; |
1441 if (ufe.size(c) == 1) continue; |
|
1442 Node cn = ufe.item(c); |
1438 Value cutvalue = 0; |
1443 Value cutvalue = 0; |
1439 for (typename AuxGraph::IncEdgeIt e(*_aux_graph, c); |
1444 for (typename AuxGraph::IncEdgeIt e(*_aux_graph, cn); |
1440 e != INVALID; ++e) { |
1445 e != INVALID; ++e) { |
1441 cutvalue += (*_aux_capacity)[e]; |
1446 cutvalue += (*_aux_capacity)[e]; |
1442 } |
1447 } |
1443 |
1448 |
1444 (*_aux_cut_value)[c] = cutvalue; |
1449 (*_aux_cut_value)[cn] = cutvalue; |
1445 |
1450 |
1446 } |
1451 } |
1447 |
1452 |
1448 for (int i = 0; i < int(remnodes.size()); ++i) { |
1453 for (int i = 0; i < int(remnodes.size()); ++i) { |
1449 _aux_graph->erase(remnodes[i]); |
1454 _aux_graph->erase(remnodes[i]); |