3.1 Sparsified vs. complete graphs as search space¶
This is used in the paper Flexible cable routing framework for wind farm collection system optimization.
[1]:
import fnmatch
from itertools import chain, pairwise, accumulate
from pathlib import Path
import urllib.request
import networkx as nx
import numpy as np
[2]:
from optiwindnet.svg import svgplot
from optiwindnet.interarraylib import G_from_S, L_from_site
from optiwindnet.mesh import make_planar_embedding
[3]:
# Additional python packages needed
import py7zr
import vrplib
[4]:
import matplotlib.pyplot as plt
%config InlineBackend.figure_formats = ['svg']
plt.rcParams['svg.fonttype'] = 'none'
style = Path('mplstyles/jupyter_dark.mplstyle')
style.is_file() and plt.style.use(style)
Data download¶
Queiroga, E., Sadykov, R., Uchoa, E., & Vidal, T. (2021, November 24). 10,000 optimal CVRP solutions for testing machine learning based heuristics. AAAI-22 Workshop on Machine Learning for Operations Research (ML4OR). https://openreview.net/forum?id=yHiMXKN6nTl
[5]:
# previously at: http://vrp.galgos.inf.puc-rio.br/media/com_vrp/instances/Vrp-Set-XML100.zip'
file_name = 'XML.7z'
# repository URL
url = 'https://galgos.inf.puc-rio.br/cvrplib/uploads/files/xml100/' + file_name
[6]:
dir_instances = Path('XML/instances/')
dir_solutions = Path('XML/solutions/')
[7]:
if dir_instances.is_dir() and dir_solutions.is_dir():
# Already extracted
instances = sorted(p.name for p in dir_instances.iterdir())
solutions = [
instance.replace('.vrp', '.sol')
for instance in instances
]
else:
if Path(file_name).is_file():
# Already downloaded
filehandle = open(file_name, 'rb')
else:
# Download from repository
filehandle, _ = urllib.request.urlretrieve(url)
with py7zr.SevenZipFile(filehandle, mode="r") as archive:
# Extract only the unitary-demand cases
archive_names = archive.getnames()
instances = fnmatch.filter(
archive_names,
dir_instances / "XML100_?11?_??.vrp",
)
solutions = fnmatch.filter(
archive_names,
dir_solutions / 'XML100_?11?_??.sol',
)
archive.extract(path='.', targets=instances + solutions)
instances = sorted(path.split('/')[-1] for path in instances)
solutions = [
instance.replace('.vrp', '.sol')
for instance in instances
]
[8]:
len(instances), len(solutions)
[8]:
(480, 480)
Definitions¶
[9]:
def check_rogues(solution, A):
rogues = []
branches = ([n - 1 for n in branch] for branch in solution['routes'])
for branch in branches:
for edge in pairwise(branch):
if edge not in A.edges:
rogues.append(edge)
return rogues
[10]:
def S_from_vrplib(solution, Sʹ):
'''
Beware: assumes a single depot!
'''
# create a topology graph S from the solution
S = nx.Graph(
T=Sʹ.graph['T'], R=Sʹ.graph['R'],
capacity=Sʹ.graph['capacity'],
has_loads=True,
objective=solution['cost'],
creator='vrplib',
)
branches = ([n - 1 for n in branch] for branch in solution['routes'])
for subtree_id, branch in enumerate(branches):
loads = range(len(branch), 0, -1)
S.add_nodes_from(((n, {'load': load})
for n, load in zip(branch, loads)),
subtree=subtree_id)
branch_roll = [-1] + branch[:-1]
reverses = tuple(u < v for u, v in zip(branch, branch_roll))
edgeD = ({'load': load, 'reverse': reverse}
for load, reverse in zip(loads, reverses))
S.add_edges_from(zip(branch_roll, branch, edgeD))
root_load = sum(S.nodes[n]['load'] for n in S.neighbors(-1))
S.nodes[-1]['load'] = root_load
return S
[11]:
def L_from_vrplib(instance):
R = len(instance['depot'])
T = instance['dimension'] - R
# make sure depots are numbered 0..M-1
assert all(depot == i for i, depot in enumerate(instance['depot']))
L = L_from_site(
B=4, border=np.arange(T, T + 4),
R=R, T=T, name=instance['name'],
VertexC=np.vstack((instance['node_coord'][R:],
[[0,0], [1000, 0], [1000, 1000], [0, 1000]],
instance['node_coord'][:R])),
)
L.graph['capacity'] = instance['capacity']
return L
Examine XML100 _11_¶
(i.e. random client positions, 1-demand)
[12]:
inst_id = '2115_07'
instance = vrplib.read_instance(dir_instances / f'XML100_{inst_id}.vrp')
solution = vrplib.read_solution(dir_solutions / f'XML100_{inst_id}.sol')
[13]:
instance.keys()
[13]:
dict_keys(['name', 'comment', 'type', 'dimension', 'edge_weight_type', 'capacity', 'node_coord', 'demand', 'depot', 'edge_weight'])
[14]:
solution.keys()
[14]:
dict_keys(['routes', 'cost'])
[15]:
L = L_from_vrplib(instance)
[16]:
svgplot(L)
[16]:
[17]:
P, A = make_planar_embedding(L)
[18]:
svgplot(A)
[18]:
[19]:
S = S_from_vrplib(solution, L)
[20]:
G = G_from_S(S, A)
[21]:
svgplot(G)
[21]:
Get Statistics!¶
[22]:
num_instances = 0
num_total_edges = 0
num_total_rogues = 0
edge_counts = []
problems = []
for solfile in solutions:
num_instances += 1
vrpfile = solfile.replace('.sol', '.vrp')
instance = vrplib.read_instance(dir_instances / vrpfile)
solution = vrplib.read_solution(dir_solutions / solfile)
L = L_from_vrplib(instance)
P, A = make_planar_embedding(L)
S = S_from_vrplib(solution, L)
num_feeders = S.degree[-1]
# num_edges = T.number_of_edges() - num_feeders
# num_total_edges += num_edges
num_edges = S.number_of_edges()
num_total_edges += num_edges
edge_counts.append(num_edges)
rogues = check_rogues(solution, A)
if rogues:
# print(rogues)
num_total_rogues += len(rogues)
G = G_from_S(S, A)
problems.append((solfile.split('/')[-1], rogues, svgplot(G)))
print(f'ROGUES ({len(rogues)}):', solfile)
else:
print('CLEAN:', solfile)
ROGUES (4): XML100_1111_01.sol
CLEAN: XML100_1111_02.sol
ROGUES (2): XML100_1111_03.sol
ROGUES (1): XML100_1111_04.sol
ROGUES (1): XML100_1111_05.sol
ROGUES (2): XML100_1111_06.sol
ROGUES (1): XML100_1111_07.sol
CLEAN: XML100_1111_08.sol
ROGUES (2): XML100_1111_09.sol
CLEAN: XML100_1111_10.sol
ROGUES (2): XML100_1111_11.sol
ROGUES (1): XML100_1111_12.sol
CLEAN: XML100_1111_13.sol
CLEAN: XML100_1111_14.sol
CLEAN: XML100_1111_15.sol
CLEAN: XML100_1111_16.sol
ROGUES (1): XML100_1111_17.sol
ROGUES (2): XML100_1111_18.sol
ROGUES (1): XML100_1111_19.sol
CLEAN: XML100_1111_20.sol
CLEAN: XML100_1111_21.sol
CLEAN: XML100_1111_22.sol
ROGUES (2): XML100_1111_23.sol
CLEAN: XML100_1111_24.sol
CLEAN: XML100_1111_25.sol
CLEAN: XML100_1111_26.sol
CLEAN: XML100_1111_27.sol
ROGUES (2): XML100_1112_01.sol
ROGUES (3): XML100_1112_02.sol
ROGUES (2): XML100_1112_03.sol
CLEAN: XML100_1112_04.sol
ROGUES (2): XML100_1112_05.sol
ROGUES (2): XML100_1112_06.sol
ROGUES (4): XML100_1112_07.sol
ROGUES (1): XML100_1112_08.sol
ROGUES (2): XML100_1112_09.sol
ROGUES (3): XML100_1112_10.sol
ROGUES (2): XML100_1112_11.sol
CLEAN: XML100_1112_12.sol
ROGUES (2): XML100_1112_13.sol
ROGUES (1): XML100_1112_14.sol
ROGUES (3): XML100_1112_15.sol
CLEAN: XML100_1112_16.sol
ROGUES (2): XML100_1112_17.sol
CLEAN: XML100_1112_18.sol
ROGUES (2): XML100_1112_19.sol
ROGUES (3): XML100_1112_20.sol
ROGUES (1): XML100_1112_21.sol
CLEAN: XML100_1112_22.sol
ROGUES (2): XML100_1112_23.sol
ROGUES (1): XML100_1112_24.sol
ROGUES (1): XML100_1112_25.sol
ROGUES (1): XML100_1112_26.sol
ROGUES (3): XML100_1112_27.sol
ROGUES (3): XML100_1113_01.sol
ROGUES (1): XML100_1113_02.sol
ROGUES (3): XML100_1113_03.sol
ROGUES (1): XML100_1113_04.sol
ROGUES (2): XML100_1113_05.sol
ROGUES (1): XML100_1113_06.sol
ROGUES (2): XML100_1113_07.sol
ROGUES (3): XML100_1113_08.sol
ROGUES (2): XML100_1113_09.sol
ROGUES (1): XML100_1113_10.sol
ROGUES (1): XML100_1113_11.sol
CLEAN: XML100_1113_12.sol
ROGUES (3): XML100_1113_13.sol
ROGUES (2): XML100_1113_14.sol
ROGUES (1): XML100_1113_15.sol
CLEAN: XML100_1113_16.sol
CLEAN: XML100_1113_17.sol
ROGUES (2): XML100_1113_18.sol
ROGUES (1): XML100_1113_19.sol
ROGUES (1): XML100_1113_20.sol
ROGUES (3): XML100_1113_21.sol
ROGUES (1): XML100_1113_22.sol
ROGUES (2): XML100_1113_23.sol
ROGUES (1): XML100_1113_24.sol
ROGUES (3): XML100_1113_25.sol
ROGUES (1): XML100_1113_26.sol
ROGUES (3): XML100_1113_27.sol
ROGUES (3): XML100_1114_01.sol
ROGUES (1): XML100_1114_02.sol
ROGUES (2): XML100_1114_03.sol
CLEAN: XML100_1114_04.sol
ROGUES (3): XML100_1114_05.sol
ROGUES (3): XML100_1114_06.sol
ROGUES (1): XML100_1114_07.sol
ROGUES (1): XML100_1114_08.sol
ROGUES (2): XML100_1114_09.sol
ROGUES (2): XML100_1114_10.sol
CLEAN: XML100_1114_11.sol
ROGUES (2): XML100_1114_12.sol
ROGUES (2): XML100_1114_13.sol
ROGUES (4): XML100_1114_14.sol
ROGUES (3): XML100_1114_15.sol
ROGUES (3): XML100_1114_16.sol
ROGUES (2): XML100_1114_17.sol
ROGUES (3): XML100_1114_18.sol
ROGUES (2): XML100_1114_19.sol
ROGUES (1): XML100_1114_20.sol
ROGUES (2): XML100_1114_21.sol
CLEAN: XML100_1114_22.sol
CLEAN: XML100_1114_23.sol
ROGUES (1): XML100_1114_24.sol
ROGUES (1): XML100_1114_25.sol
ROGUES (2): XML100_1114_26.sol
ROGUES (4): XML100_1114_27.sol
ROGUES (1): XML100_1115_01.sol
ROGUES (2): XML100_1115_02.sol
ROGUES (2): XML100_1115_03.sol
CLEAN: XML100_1115_04.sol
ROGUES (3): XML100_1115_05.sol
ROGUES (3): XML100_1115_06.sol
ROGUES (1): XML100_1115_07.sol
ROGUES (2): XML100_1115_08.sol
ROGUES (3): XML100_1115_09.sol
ROGUES (1): XML100_1115_10.sol
CLEAN: XML100_1115_11.sol
CLEAN: XML100_1115_12.sol
ROGUES (1): XML100_1115_13.sol
ROGUES (1): XML100_1115_14.sol
ROGUES (1): XML100_1115_15.sol
ROGUES (3): XML100_1115_16.sol
ROGUES (2): XML100_1115_17.sol
CLEAN: XML100_1115_18.sol
ROGUES (2): XML100_1115_19.sol
ROGUES (2): XML100_1115_20.sol
ROGUES (1): XML100_1115_21.sol
ROGUES (1): XML100_1115_22.sol
ROGUES (3): XML100_1115_23.sol
CLEAN: XML100_1115_24.sol
ROGUES (1): XML100_1115_25.sol
ROGUES (3): XML100_1115_26.sol
CLEAN: XML100_1115_27.sol
CLEAN: XML100_1116_01.sol
CLEAN: XML100_1116_02.sol
CLEAN: XML100_1116_03.sol
CLEAN: XML100_1116_04.sol
ROGUES (1): XML100_1116_05.sol
ROGUES (1): XML100_1116_06.sol
CLEAN: XML100_1116_07.sol
CLEAN: XML100_1116_08.sol
CLEAN: XML100_1116_09.sol
CLEAN: XML100_1116_10.sol
CLEAN: XML100_1116_11.sol
ROGUES (1): XML100_1116_12.sol
CLEAN: XML100_1116_13.sol
ROGUES (2): XML100_1116_14.sol
ROGUES (1): XML100_1116_15.sol
CLEAN: XML100_1116_16.sol
CLEAN: XML100_1116_17.sol
ROGUES (2): XML100_1116_18.sol
CLEAN: XML100_1116_19.sol
CLEAN: XML100_1116_20.sol
CLEAN: XML100_1116_21.sol
ROGUES (1): XML100_1116_22.sol
CLEAN: XML100_1116_23.sol
CLEAN: XML100_1116_24.sol
CLEAN: XML100_1116_25.sol
CLEAN: XML100_1116_26.sol
CLEAN: XML100_1116_27.sol
ROGUES (1): XML100_2111_01.sol
ROGUES (1): XML100_2111_02.sol
ROGUES (2): XML100_2111_03.sol
ROGUES (1): XML100_2111_04.sol
CLEAN: XML100_2111_05.sol
ROGUES (1): XML100_2111_06.sol
ROGUES (1): XML100_2111_07.sol
ROGUES (1): XML100_2111_08.sol
CLEAN: XML100_2111_09.sol
ROGUES (1): XML100_2111_10.sol
ROGUES (1): XML100_2111_11.sol
CLEAN: XML100_2111_12.sol
CLEAN: XML100_2111_13.sol
ROGUES (1): XML100_2111_14.sol
CLEAN: XML100_2111_15.sol
CLEAN: XML100_2111_16.sol
ROGUES (2): XML100_2111_17.sol
CLEAN: XML100_2111_18.sol
CLEAN: XML100_2111_19.sol
CLEAN: XML100_2111_20.sol
CLEAN: XML100_2111_21.sol
CLEAN: XML100_2111_22.sol
ROGUES (1): XML100_2111_23.sol
ROGUES (3): XML100_2111_24.sol
ROGUES (1): XML100_2111_25.sol
ROGUES (1): XML100_2111_26.sol
CLEAN: XML100_2111_27.sol
ROGUES (1): XML100_2112_01.sol
CLEAN: XML100_2112_02.sol
ROGUES (1): XML100_2112_03.sol
ROGUES (1): XML100_2112_04.sol
ROGUES (3): XML100_2112_05.sol
ROGUES (2): XML100_2112_06.sol
ROGUES (2): XML100_2112_07.sol
ROGUES (1): XML100_2112_08.sol
ROGUES (2): XML100_2112_09.sol
ROGUES (1): XML100_2112_10.sol
CLEAN: XML100_2112_11.sol
ROGUES (1): XML100_2112_12.sol
ROGUES (1): XML100_2112_13.sol
ROGUES (4): XML100_2112_14.sol
ROGUES (1): XML100_2112_15.sol
ROGUES (2): XML100_2112_16.sol
ROGUES (3): XML100_2112_17.sol
ROGUES (1): XML100_2112_18.sol
ROGUES (3): XML100_2112_19.sol
CLEAN: XML100_2112_20.sol
ROGUES (1): XML100_2112_21.sol
ROGUES (2): XML100_2112_22.sol
ROGUES (4): XML100_2112_23.sol
ROGUES (1): XML100_2112_24.sol
ROGUES (3): XML100_2112_25.sol
CLEAN: XML100_2112_26.sol
ROGUES (3): XML100_2112_27.sol
ROGUES (3): XML100_2113_01.sol
ROGUES (1): XML100_2113_02.sol
ROGUES (2): XML100_2113_03.sol
CLEAN: XML100_2113_04.sol
CLEAN: XML100_2113_05.sol
ROGUES (1): XML100_2113_06.sol
CLEAN: XML100_2113_07.sol
ROGUES (2): XML100_2113_08.sol
ROGUES (3): XML100_2113_09.sol
ROGUES (4): XML100_2113_10.sol
CLEAN: XML100_2113_11.sol
ROGUES (3): XML100_2113_12.sol
ROGUES (2): XML100_2113_13.sol
ROGUES (4): XML100_2113_14.sol
ROGUES (2): XML100_2113_15.sol
ROGUES (3): XML100_2113_16.sol
CLEAN: XML100_2113_17.sol
CLEAN: XML100_2113_18.sol
CLEAN: XML100_2113_19.sol
ROGUES (1): XML100_2113_20.sol
ROGUES (1): XML100_2113_21.sol
CLEAN: XML100_2113_22.sol
ROGUES (2): XML100_2113_23.sol
CLEAN: XML100_2113_24.sol
ROGUES (2): XML100_2113_25.sol
ROGUES (2): XML100_2113_26.sol
ROGUES (2): XML100_2113_27.sol
ROGUES (2): XML100_2114_01.sol
CLEAN: XML100_2114_02.sol
ROGUES (2): XML100_2114_03.sol
CLEAN: XML100_2114_04.sol
ROGUES (1): XML100_2114_05.sol
ROGUES (2): XML100_2114_06.sol
ROGUES (1): XML100_2114_07.sol
CLEAN: XML100_2114_08.sol
ROGUES (1): XML100_2114_09.sol
CLEAN: XML100_2114_10.sol
ROGUES (1): XML100_2114_11.sol
ROGUES (1): XML100_2114_12.sol
CLEAN: XML100_2114_13.sol
ROGUES (2): XML100_2114_14.sol
ROGUES (2): XML100_2114_15.sol
ROGUES (1): XML100_2114_16.sol
ROGUES (2): XML100_2114_17.sol
ROGUES (1): XML100_2114_18.sol
ROGUES (1): XML100_2114_19.sol
CLEAN: XML100_2114_20.sol
ROGUES (1): XML100_2114_21.sol
CLEAN: XML100_2114_22.sol
ROGUES (2): XML100_2114_23.sol
CLEAN: XML100_2114_24.sol
CLEAN: XML100_2114_25.sol
CLEAN: XML100_2114_26.sol
ROGUES (1): XML100_2114_27.sol
CLEAN: XML100_2115_01.sol
CLEAN: XML100_2115_02.sol
ROGUES (1): XML100_2115_03.sol
ROGUES (1): XML100_2115_04.sol
CLEAN: XML100_2115_05.sol
CLEAN: XML100_2115_06.sol
ROGUES (3): XML100_2115_07.sol
ROGUES (2): XML100_2115_08.sol
CLEAN: XML100_2115_09.sol
CLEAN: XML100_2115_10.sol
CLEAN: XML100_2115_11.sol
ROGUES (2): XML100_2115_12.sol
CLEAN: XML100_2115_13.sol
CLEAN: XML100_2115_14.sol
CLEAN: XML100_2115_15.sol
CLEAN: XML100_2115_16.sol
ROGUES (4): XML100_2115_17.sol
CLEAN: XML100_2115_18.sol
CLEAN: XML100_2115_19.sol
ROGUES (1): XML100_2115_20.sol
CLEAN: XML100_2115_21.sol
ROGUES (1): XML100_2115_22.sol
CLEAN: XML100_2115_23.sol
CLEAN: XML100_2115_24.sol
CLEAN: XML100_2115_25.sol
CLEAN: XML100_2115_26.sol
ROGUES (1): XML100_2115_27.sol
CLEAN: XML100_2116_01.sol
CLEAN: XML100_2116_02.sol
CLEAN: XML100_2116_03.sol
ROGUES (1): XML100_2116_04.sol
CLEAN: XML100_2116_05.sol
CLEAN: XML100_2116_06.sol
ROGUES (1): XML100_2116_07.sol
CLEAN: XML100_2116_08.sol
ROGUES (1): XML100_2116_09.sol
CLEAN: XML100_2116_10.sol
CLEAN: XML100_2116_11.sol
CLEAN: XML100_2116_12.sol
CLEAN: XML100_2116_13.sol
CLEAN: XML100_2116_14.sol
CLEAN: XML100_2116_15.sol
ROGUES (2): XML100_2116_16.sol
CLEAN: XML100_2116_17.sol
CLEAN: XML100_2116_18.sol
CLEAN: XML100_2116_19.sol
ROGUES (1): XML100_2116_20.sol
CLEAN: XML100_2116_21.sol
CLEAN: XML100_2116_22.sol
CLEAN: XML100_2116_23.sol
CLEAN: XML100_2116_24.sol
ROGUES (1): XML100_2116_25.sol
CLEAN: XML100_2116_26.sol
CLEAN: XML100_2116_27.sol
ROGUES (3): XML100_3111_01.sol
ROGUES (1): XML100_3111_02.sol
ROGUES (2): XML100_3111_03.sol
CLEAN: XML100_3111_04.sol
CLEAN: XML100_3111_05.sol
ROGUES (1): XML100_3111_06.sol
ROGUES (4): XML100_3111_07.sol
ROGUES (4): XML100_3111_08.sol
CLEAN: XML100_3111_09.sol
CLEAN: XML100_3111_10.sol
ROGUES (1): XML100_3111_11.sol
CLEAN: XML100_3111_12.sol
ROGUES (2): XML100_3111_13.sol
CLEAN: XML100_3111_14.sol
ROGUES (2): XML100_3111_15.sol
ROGUES (3): XML100_3111_16.sol
ROGUES (2): XML100_3111_17.sol
ROGUES (1): XML100_3111_18.sol
ROGUES (2): XML100_3111_19.sol
ROGUES (1): XML100_3111_20.sol
ROGUES (1): XML100_3111_21.sol
CLEAN: XML100_3111_22.sol
ROGUES (3): XML100_3111_23.sol
CLEAN: XML100_3111_24.sol
ROGUES (1): XML100_3111_25.sol
CLEAN: XML100_3111_26.sol
ROGUES (2): XML100_3112_01.sol
ROGUES (1): XML100_3112_02.sol
ROGUES (2): XML100_3112_03.sol
CLEAN: XML100_3112_04.sol
ROGUES (2): XML100_3112_05.sol
ROGUES (1): XML100_3112_06.sol
ROGUES (2): XML100_3112_07.sol
CLEAN: XML100_3112_08.sol
ROGUES (4): XML100_3112_09.sol
ROGUES (1): XML100_3112_10.sol
ROGUES (1): XML100_3112_11.sol
ROGUES (3): XML100_3112_12.sol
CLEAN: XML100_3112_13.sol
ROGUES (2): XML100_3112_14.sol
ROGUES (2): XML100_3112_15.sol
ROGUES (2): XML100_3112_16.sol
ROGUES (2): XML100_3112_17.sol
ROGUES (3): XML100_3112_18.sol
ROGUES (1): XML100_3112_19.sol
ROGUES (3): XML100_3112_20.sol
ROGUES (1): XML100_3112_21.sol
ROGUES (1): XML100_3112_22.sol
ROGUES (3): XML100_3112_23.sol
ROGUES (2): XML100_3112_24.sol
ROGUES (1): XML100_3112_25.sol
ROGUES (1): XML100_3112_26.sol
ROGUES (5): XML100_3113_01.sol
ROGUES (3): XML100_3113_02.sol
ROGUES (2): XML100_3113_03.sol
ROGUES (2): XML100_3113_04.sol
CLEAN: XML100_3113_05.sol
ROGUES (1): XML100_3113_06.sol
CLEAN: XML100_3113_07.sol
ROGUES (1): XML100_3113_08.sol
ROGUES (1): XML100_3113_09.sol
ROGUES (1): XML100_3113_10.sol
ROGUES (2): XML100_3113_11.sol
ROGUES (3): XML100_3113_12.sol
ROGUES (2): XML100_3113_13.sol
ROGUES (1): XML100_3113_14.sol
CLEAN: XML100_3113_15.sol
ROGUES (2): XML100_3113_16.sol
ROGUES (4): XML100_3113_17.sol
ROGUES (1): XML100_3113_18.sol
ROGUES (1): XML100_3113_19.sol
ROGUES (2): XML100_3113_20.sol
ROGUES (1): XML100_3113_21.sol
ROGUES (1): XML100_3113_22.sol
CLEAN: XML100_3113_23.sol
ROGUES (3): XML100_3113_24.sol
ROGUES (2): XML100_3113_25.sol
ROGUES (1): XML100_3113_26.sol
ROGUES (5): XML100_3114_01.sol
ROGUES (3): XML100_3114_02.sol
ROGUES (1): XML100_3114_03.sol
ROGUES (2): XML100_3114_04.sol
ROGUES (6): XML100_3114_05.sol
ROGUES (3): XML100_3114_06.sol
ROGUES (2): XML100_3114_07.sol
ROGUES (3): XML100_3114_08.sol
ROGUES (2): XML100_3114_09.sol
CLEAN: XML100_3114_10.sol
ROGUES (2): XML100_3114_11.sol
ROGUES (1): XML100_3114_12.sol
ROGUES (1): XML100_3114_13.sol
ROGUES (2): XML100_3114_14.sol
CLEAN: XML100_3114_15.sol
ROGUES (2): XML100_3114_16.sol
ROGUES (2): XML100_3114_17.sol
ROGUES (1): XML100_3114_18.sol
CLEAN: XML100_3114_19.sol
CLEAN: XML100_3114_20.sol
ROGUES (2): XML100_3114_21.sol
ROGUES (3): XML100_3114_22.sol
ROGUES (1): XML100_3114_23.sol
ROGUES (2): XML100_3114_24.sol
ROGUES (3): XML100_3114_25.sol
CLEAN: XML100_3114_26.sol
CLEAN: XML100_3115_01.sol
ROGUES (3): XML100_3115_02.sol
ROGUES (1): XML100_3115_03.sol
ROGUES (3): XML100_3115_04.sol
ROGUES (3): XML100_3115_05.sol
ROGUES (3): XML100_3115_06.sol
ROGUES (5): XML100_3115_07.sol
ROGUES (2): XML100_3115_08.sol
CLEAN: XML100_3115_09.sol
ROGUES (1): XML100_3115_10.sol
ROGUES (1): XML100_3115_11.sol
ROGUES (2): XML100_3115_12.sol
ROGUES (2): XML100_3115_13.sol
CLEAN: XML100_3115_14.sol
ROGUES (4): XML100_3115_15.sol
CLEAN: XML100_3115_16.sol
ROGUES (2): XML100_3115_17.sol
CLEAN: XML100_3115_18.sol
ROGUES (4): XML100_3115_19.sol
ROGUES (2): XML100_3115_20.sol
ROGUES (1): XML100_3115_21.sol
ROGUES (1): XML100_3115_22.sol
ROGUES (2): XML100_3115_23.sol
ROGUES (3): XML100_3115_24.sol
CLEAN: XML100_3115_25.sol
ROGUES (1): XML100_3115_26.sol
CLEAN: XML100_3116_01.sol
ROGUES (1): XML100_3116_02.sol
ROGUES (1): XML100_3116_03.sol
ROGUES (1): XML100_3116_04.sol
ROGUES (2): XML100_3116_05.sol
ROGUES (1): XML100_3116_06.sol
ROGUES (1): XML100_3116_07.sol
CLEAN: XML100_3116_08.sol
ROGUES (1): XML100_3116_09.sol
CLEAN: XML100_3116_10.sol
CLEAN: XML100_3116_11.sol
ROGUES (1): XML100_3116_12.sol
ROGUES (2): XML100_3116_13.sol
CLEAN: XML100_3116_14.sol
CLEAN: XML100_3116_15.sol
ROGUES (1): XML100_3116_16.sol
ROGUES (1): XML100_3116_17.sol
ROGUES (1): XML100_3116_18.sol
CLEAN: XML100_3116_19.sol
ROGUES (3): XML100_3116_20.sol
ROGUES (1): XML100_3116_21.sol
ROGUES (1): XML100_3116_22.sol
ROGUES (2): XML100_3116_23.sol
ROGUES (1): XML100_3116_24.sol
ROGUES (1): XML100_3116_25.sol
CLEAN: XML100_3116_26.sol
[23]:
rogue_counts = np.array([len(rogues) for _, rogues, _ in problems])
num_rogues_range = range(0, max(rogue_counts) + 1)
count_per_num_rogues = [sum(rogue_counts == num_rogues) for num_rogues in num_rogues_range]
count_per_num_rogues[0] = num_instances - len(problems)
[24]:
plt.bar(num_rogues_range, 100*np.array(count_per_num_rogues)/num_instances);
plt.xlabel('number of edges not included in the sparsified set $A$')
plt.ylabel('% of instances');
[25]:
bench_pct_per_num_rogues = 100*np.array(count_per_num_rogues)/num_instances
[26]:
with plt.style.context('pub_paperfarm'):
fig, ax = plt.subplots(figsize=(4.2, 0.4), frameon=True, facecolor='w')
values = list(chain(bench_pct_per_num_rogues[:4],
(sum(bench_pct_per_num_rogues[4:]),)))
tags = '0', '1', '2', '3', '4+'
colors = 'darkgreen', 'darkorange', 'royalblue', 'firebrick', 'darkorchid'
limits = list(accumulate(values, initial=0))
centers = [(a + b)/2 for a, b in pairwise(limits)]
ax.barh(0, values, left=limits[:-1], color=colors, edgecolor='white')
value_tags = [ax.text(x, 0, f'{v:.0f}%',
color='white', fontsize='small',
verticalalignment='center',
horizontalalignment='center') for v, x in zip(values, centers)]
label_tags = [ax.text(x, 0.7, s,
fontsize='large',
verticalalignment='center',
horizontalalignment='center') for s, x in zip(tags, centers)]
ax.axis(False)
ax.set_xlim(0, 100)
ax.figure.savefig('XML100_480_edges_not_in_A.pdf')
[27]:
# this counts feeders in num_total_edges
num_total_rogues/num_total_edges
[27]:
0.012416666666666666
Check the rogues >= 4 offenders¶
[28]:
for name, rogues, svg in problems:
if len(rogues) >= 4:
display(svg)
[ ]: