Changeset 2457:8c791ee69a45 in lemon-0.x for lemon/network_simplex.h

Timestamp:

06/15/07 16:36:24 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3294

Message:

Improvments in min cost flow algorithms

• improved cycle cancelling

File:

• lemon/network_simplex.h (modified) (3 diffs)

lemon/network_simplex.h

@@ -276 +276 @@
 
       // Copying graph_ref to graph
+      graph.reserveNode(countNodes(graph_ref) + 1);
+      graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
       copyGraph(graph, graph_ref)
         .edgeMap(cost, _cost)
@@ -478 +480 @@
       parent[root] = INVALID;
       pred_edge[root] = INVALID;
-      depth[root] = supply[root] = potential[root] = 0;
+      depth[root] = 0;
+      supply[root] = 0;
+      potential[root] = 0;
 
       // Adding artificial edges to the graph and initializing the node
@@ -514 +518 @@
       // Initializing block_size for the edge block pivot rule
       int edge_num = countEdges(graph);
-      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 
+      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
                    edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
 #endif