#16471: The Push-Relabel method for Maximum Flow
-------------------------------------+-------------------------------------
Reporter: foosterhof | Owner:
Type: enhancement | Status: new
Priority: minor | Milestone: sage-6.3
Component: graph theory | Resolution:
Keywords: maximum flow push | Merged in:
relabel | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | 7ad579b273adefec7fbd555d67ec1442e7fe4554
u/foosterhof/ticket/16471 | Stopgaps:
Dependencies: #16467, #16470 |
-------------------------------------+-------------------------------------
Changes (by foosterhof):
* commit: => 7ad579b273adefec7fbd555d67ec1442e7fe4554
Comment:
The commit implements the push_relabel method, which has an interface much
like the flow and _ford_fulkerson methods, except that it has 2 extra
optional arguments:
- use_global_relabeling: Whether or not to use the global relabeling
heuristic. Though theoretically very nice, as well as in practice, as
stated in some papers, it creates a huge overhead by needing to initialize
the Residual Graph. Not using it gave in my own testcases a generally
better result, meaning much faster.
- use_gap_relabeling: A nice heuristic with little overhead. It checks
for gaps in the labels that are used by the vertices. If label D is not
used, then any vertex with label d for D < d < n can never become active
again, so it is just relabeled to n then.
For those interested: This was my testsuite used:
{{{
def test_small_graphs(rangeList = xrange(2, 5)):
use_labels = False
value = True
total = 0
set_random_seed(5)
def test_graph(A):
count = 0
for s in xrange(0, n-1):
for t in xrange(0, n-1):
count += 1
if s != t and A.shortest_path(s, t) != []:
f1, G1 = A._ford_fulkerson(s, t, value_only=value,
use_edge_labels= use_labels)
f2, G2 = A.push_relabel(s, t, value_only=value,
use_edge_labels = use_labels)
if abs(f1-f2) > 10**(-14)*f1:
print 'Unequal Flows in graph; Ford-Fulkerson:',
f1, ' - Push-Relabel:', f2
return False, A, s, t
return True, None, None, count
for n in rangeList:
G = graphs.CompleteGraph(n)
E = G.edges()
for EP in powerset(E):
A = Graph(n, loops=False)
A.add_edges(EP)
if use_labels:
for e in A.edge_iterator():
A.set_edge_label(e[0],e[1], 1+random()*99)
good, A, s, t = test_graph(A)
if good:
total += t
else:
return False, A, s, t
E = G.to_directed().edges()
for EP in powerset(E):
A = DiGraph(n, loops=False)
A.add_edges(EP)
if use_labels:
for e in A.edge_iterator():
A.set_edge_label(e[0],e[1], 1+random()*99)
good, A, s, t = test_graph(A)
if good:
total += t
else:
return False, A, s, t
print 'Done with', n
print 'Done, total number of instances done:', total
return True, None, None, None
def test_random_graphs(size, probability, count):
for i in xrange(count):
G = digraphs.RandomDirectedGNP(size, probability)
if G.shortest_path(0, size-1) != []:
f1 = G._ford_fulkerson(0, size-1, use_edge_labels=True,
value_only=True)
f2 = G.push_relabel(0, size-1, use_edge_labels=True,
value_only=True)
if abs(f1-f2) > 10**(-14)*f1:
print 'Unequal Flows in graph; Ford-Fulkerson:', f1, ' -
Push-Relabel:', f2, ' - Absolute Error:', abs(f1-f2), ' - Relative
Error:', abs(f1-f2)/f1
def test(cmd, sort, num):
import cProfile, pstats, StringIO
pr = cProfile.Profile()
pr.run(cmd)
ps = pstats.Stats(pr).strip_dirs().sort_stats(sort).print_stats(num)
}}}
with the collowing calling code:
{{{
test("good, A, s, t = test_small_graphs([2, 3, 4])", 'cumulative',
int(10))
# NOTE: This test can run extremely long!!
prun(['cumulative'],[int(5)]).eval("test_small_graphs([5])", globals(),
locals())
# NOTE: This test can also run extremely long when all values (now
commented) are used.
for size in [10, 20, 50]: #, 100, 200, 500, 1000, 2000]:
for probability in [0.2, 0.4, 0.6, 0.8]:
count = 10000/size
prun(['cumulative'],[int(8)]).eval("test_random_graphs(" +
str(size) + "," + str(probability) + "," + str(count) + ")", globals(),
locals())
}}}
The testsuite could sure use some revamping, as for instance isomorphism
is now neglected, meaning alot of double work, but that is not relevant
for its results.
There are a few questions I have for people out there:
- Currently, there are quite some subroutines to push_relabel, such as
push, relabel, discharge, etc. I am not sure what is customary in Sage,
but since they are property of push_relabel, so to speak, I put them
inside the push_relabel code, rather than outside.
- As already stated in the ticket, this depends on two other tickets I
have submitted. Commits I made there are used in this code. I do have some
experience with git, but not with Trac, and therefor I had no idea how to
properly make sure that I could use them on my local computer, but that
they would not be committed to this ticket. I am sorry if this push
created duplicate code of the commits on the other tickets. Can anyone
explain to me how to properly do this? For now, I called
{{{
sage: dev.checkout(16471)
sage: dev.pull(16467)
sage: dev.pull(16470)
}}}
Is this correct, or is there perhaps a cleaner way to do this?
With kind regards,
Florian Oosterhof
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=cf3518442619a34790946a2075c22935189a1a62
cf35184]||{{{Added push_relabel and defaulted all methods that used "FF"
to "PR"}}}||
||[http://git.sagemath.org/sage.git/commit/?id=60c0c0f174063675c0ca75ffb32d69823727baac
60c0c0f]||{{{Added insert and remove methods, as well as redid internal
storage to become actual Doubly Linked List}}}||
||[http://git.sagemath.org/sage.git/commit/?id=50a8248219c09b5d97c86f61dcf259fdbdcd18f7
50a8248]||{{{Merge branch 'u/foosterhof/ticket/16467' of
git://trac.sagemath.org/sage into ticket/16471}}}||
||[http://git.sagemath.org/sage.git/commit/?id=c0dd8ff023c173451a4126f0b1742eb16692f2db
c0dd8ff]||{{{Added optional argument (default False) to report distance
along with vertex}}}||
||[http://git.sagemath.org/sage.git/commit/?id=c2915be207287e7d903b32d9d0154610e43e2719
c2915be]||{{{Merge branch 'u/foosterhof/ticket/16470' of
git://trac.sagemath.org/sage into ticket/16471}}}||
||[http://git.sagemath.org/sage.git/commit/?id=ea9e03f8feb4c1404676fd47fce89b736bcaf59a
ea9e03f]||{{{Fixed small errors}}}||
||[http://git.sagemath.org/sage.git/commit/?id=f8a86c0d85e36603fb45024ff14acde049cb0903
f8a86c0]||{{{Added is_empty method}}}||
||[http://git.sagemath.org/sage.git/commit/?id=ee43e8fcf1b417854c656f27cff367defe64528d
ee43e8f]||{{{Merge branch 'u/foosterhof/ticket/16467' of
git://trac.sagemath.org/sage into ticket/16471}}}||
||[http://git.sagemath.org/sage.git/commit/?id=7ad579b273adefec7fbd555d67ec1442e7fe4554
7ad579b]||{{{Fixed small error in usage of DoublyLinkedList}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/16471#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
