-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_fes.py
63 lines (45 loc) · 1.38 KB
/
test_fes.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import pytest
import networkx as nx
from macrogen.fes import eades, FES_Baharev, Eades
@pytest.fixture
def graph1():
"""
←
1 → 2 → 3 → 4 → 5
"""
G = nx.DiGraph()
nx.add_path(G, [1, 2, 3, 4, 5])
G.add_edge(3, 2)
return G
def test_all_sinks(graph1):
eades = Eades(graph1)
sinks = []
for sink in eades._exhaust_sinks():
eades.graph.remove_node(sink)
sinks.append(sink)
assert sinks == [5, 4]
def test_eades(graph1):
assert list(eades(graph1)) == [(3, 2)]
def test_baharev(graph1):
solver = FES_Baharev(graph1)
result = solver.solve()
assert set(result) == {(3, 2)} or set(result) == {(2, 3)}
def test_eades_ff():
g = nx.DiGraph()
nx.add_path(g, [1, 2, 3, 4, 5], weight=1)
g.add_edge(3, 2, weight=2)
result = Eades(g).solve()
assert set(result) == {(2, 3)}
solver = Eades(g, [(4, 5), (2, 3)])
result = set(solver.solve())
assert set(result) == {(3, 2)}
def test_baharev_ff():
g = nx.DiGraph()
nx.add_path(g, [1, 2, 3, 4, 5], weight=1)
g.add_edge(3, 2, weight=2)
# This would normally remove (2,3) since its more lightweight than (3,2):
result = FES_Baharev(g).solve()
assert set(result) == {(2, 3)}
# However, when we forbid this, the next best solution will occur:
result = FES_Baharev(g, [(2, 3)]).solve()
assert set(result) == {(3, 2)}