This repository has been archived by the owner on Jun 1, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
netgen_edit.py
387 lines (330 loc) · 17.3 KB
/
netgen_edit.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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
"""Scripts for editing trilevel network interdiction game NETGEN files.
This file includes a variety of small programs for generating and editing
NETGEN files for use as computational trials. For the most part these files are
meant to follow the standard NETGEN format as described in:
D. Klingman, A. Napier, and J. Stutz. NETGEN: A program for generating
large scale capacitated assignment, transportation, and minimum cost flow
network problems. Management Science, 20(5):814-821, 1974.
The output files include additional information for defining interdependencies
and defensible/destructible arc sets.
The following scripts are included:
call_netgen() -- Calls a standalone NETGEN .exe to generate an
interdependent network instance.
generate_trials() -- Generates a set of trials with identical parameters
but different random seeds.
convert_file() -- Converts an MCNFLI NETGEN file into the format required
for the trilevel extension.
convert_folder() -- Converts all MCNFLI NETGEN files in a folder into the
format required for the trilevel extension.
generate_converted_trials() -- Generates a set of converted trial files
with identical parameters but different random seeds.
"""
import math
import os
import random
#==============================================================================
def call_netgen(file, nodes, arcs, itype, inum, seed=None, sources=None,
sinks=None, costs=(0, 100), supply=None,
capacities=(100, 500)):
"""Calls a local standalone NETGEN .exe file to generate a trial.
This requires the presence of a file called "netgen.exe" in the local
directory. This file is based on the NETGEN implementation from the MCNFLI
project, and generates interdependent network instances with no information
regarding the trilevel network interdiction game extension, which will be
added to the file by the other scripts in this file.
Requires the following positional arguments:
file -- Name of the output file (excluding the file extension).
nodes -- Number of nodes.
arcs -- Number of arcs.
itype -- Interdependency type (0 for parent nodes, 1 for parent arcs).
inum -- Number of interdependencies.
Accepts the following optional keyword arguments:
seed -- Integer RNG seed for NETGEN. Defaults to a random seed.
sources -- Number of source nodes. Defaults to 20% of all nodes
(rounded up).
sinks -- Number of sink nodes. Defaults to 20% of all nodes (rounded
up).
costs -- Tuple of arc cost lower bound and upper bound. Defaults to
(0, 100).
supply -- Total supply value across all source nodes. Defaults to
10,000 per 256 nodes (rounded up).
capacities -- Tuple of arc capacity lower bound and upper bound.
Defaults to (100, 500).
"""
# Set unspecified RNG seed to one based on the system time
if seed == None:
seed = int(10e8 * random.random())
# Set unspecified sources and sinks
if sources == None:
sources = math.ceil(0.2 * nodes)
if sinks == None:
sinks = math.ceil(0.2 * nodes)
# Set unspecified total supply
if supply == None:
supply = math.ceil(10000 * (nodes / 256))
# Call the NETGEN program and return the exit code
return os.system("netgen.exe "+file+".min "+str(seed)+" "+str(nodes)+" "+
str(sources)+" "+str(sinks)+" "+str(arcs)+" "+
str(costs[0])+" "+str(costs[1])+" "+str(supply)+
" 0 0 100 100 "+str(capacities[0])+" "+str(capacities[1])+
" "+str(itype)+" "+str(inum))
#==============================================================================
def generate_trials(file, num, nodes, arcs, itype, inum, sources=None,
sinks=None, costs=(0, 100), supply=None,
capacities=(100, 500)):
"""Generates a set of trials using the same parameters.
This function acts as a driver for call_netgen() to generate a set of
trials using the same set of parameters but different random seeds.
Requires the following positional arguments:
file -- Base name of the output file (excluding the file extension).
All generated trials will be given the specified name followed by a
unique number.
num -- Number of files to generate.
nodes -- Number of nodes.
arcs -- Number of arcs.
itype -- Interdependency type (0 for parent nodes, 1 for parent arcs).
inum -- Number of interdependencies.
Accepts the following optional keyword arguments:
sources -- Number of source nodes. Defaults to 20% of all nodes
(rounded up).
sinks -- Number of sink nodes. Defaults to 20% of all nodes (rounded
up).
costs -- Tuple of arc cost lower bound and upper bound. Defaults to
(0, 100).
supply -- Total supply value across all source nodes. Defaults to
10,000 per 256 nodes (rounded up).
capacities -- Tuple of arc capacity lower bound and upper bound.
Defaults to (100, 500).
"""
# Set unspecified sources and sinks
if sources == None:
sources = math.ceil(0.2 * nodes)
if sinks == None:
sinks = math.ceil(0.2 * nodes)
# Set unspecified total supply
if supply == None:
supply = 10000 * math.ceil(nodes / 256)
# Main loop
i = 1
while i <= num:
# Generate file name by concatenating a number
fname = file + str(i).zfill(math.ceil(math.log10(num+1)))
# Use call_netgen() to generate a trial with an unspecified seed
code = call_netgen(fname, nodes, arcs, itype, inum, sources=sources,
sinks=sinks, costs=costs, supply=supply, capacities=capacities)
# If return code indicates unsuccessful execution, repeat loop
if code != 0:
continue
print("File "+str(i)+" / "+str(num)+" generated.")
i += 1
#==============================================================================
def convert_file(file, defnum, attnum, defset=[], attset=[], temp="save.tmp",
nonsink=False):
"""Converts an MCNFLI problem file into a trilevel game problem file.
The file format for the trilevel network interdiction game is almost
completely identical to that of the standard interdependent network file,
except that we add comment lines to explain the new attributes, we add
defense and attack bounds to the objective line, and we add sets of
defensible and destructible arcs to the end of the file.
Requires the following positional arguments:
file -- Full name of the file to be converted (including the file
extension).
defnum -- Number of arcs that can be defended during Stage 1.
attnum -- Number of arcs that can be attacked during Stage 2.
Accepts the following optional keyword arguments:
defset -- List of defensible arc IDs (beginning at index 1). Defaults
to the empty list, which is treated as allowing all arcs to be
defended.
attset -- List of destructible arc IDs (beginning at index 1). Defaults
to the empty list, which is treated as allowing all arcs to be
destroyed. All defensible arcs are assumed to be attackable, so
only arcs that can be attacked but not defended need be listed.
temp -- Name of a temporary file used during the file conversion
process. Defaults to "save.tmp". As a temporary file this only
really needs to be changed if that name is already in use within
the same directory.
nonsink -- An option for automatically making all arcs defensible and
destructible except for the artificailly created arcs for networks
with nodes as parents. If True, and if the network uses nodes as
parents, then defset and attset will be automatically set to
include all non-artificial arcs. Defaults to False.
"""
dset = defset # defensible arc set
aset = attset # destructible arc set
# Override given arc sets if automatically generating nonsink arcs
if nonsink == True:
dset = []
aset = []
# Read input file while writing edited copy to a temporary file
with open(file, 'r') as fin:
with open(temp, 'w') as fout:
i = 0 # current line number
a = 1 # current arc number
for line in fin:
i += 1
# Write edited contents for specific lines
if (i == 2) and (line[0] == 'c'):
# Replace interdependent network comment
print("c Modified to generate trilevel interdiction",
file=fout)
print("c games on interdependent networks", file=fout)
elif (i == 23) and (line[0] == 'c'):
# Add trilevel game information at end of comments
print("c Interdiction Game Moves -", file=fout)
print("c Defense Limit: "+str(defnum), file=fout)
print("c Attack Limit: "+str(attnum), file=fout)
if len(dset) > 0:
print("c Defensible Arc Set: "+str(len(defset)),
file=fout)
elif nonsink == True:
print("c Defensible Arc Set: Nonsink", file=fout)
else:
print("c Defensible Arc Set: All", file=fout)
if len(aset) > 0:
print("c Attackable Arc Set: "+str(len(attset)),
file=fout)
elif nonsink == True:
print("c Attackable Arc Set: Nonsink", file=fout)
else:
print("c Attackable Arc Set: All", file=fout)
print(line[:-1], file=fout)
elif line[0] == 'p':
# Add defense/attack limits to end of objective line
print(line[:-1]+" "+str(defnum)+" "+str(attnum), file=fout)
else:
# Otherwise copy the line exactly
print(line[:-1], file=fout)
# Record nonsink arcs (which have a head listed as 0)
if nonsink == True:
if line[0] == 'a':
if int(line.split()[2]) != 0:
dset.append(a)
a += 1
# Add additional lines for the defensible and destructible arc sets
if len(dset) > 0:
for a in dset:
print("d "+str(a), file=fout)
if len(aset) > 0:
for a in attset:
print("r "+str(a), file=fout)
print("File contents written to temporary file.")
# Overwrite original file with temporary file
with open(temp, 'r') as fin:
with open(file, 'w') as fout:
for line in fin:
print(line[:-1], file=fout)
print("Input file overwritten.")
# Delete temporary file
os.remove(temp)
print("Temporary file deleted.")
#==============================================================================
def convert_folder(folder, defnum, attnum, defset=[], attset=[],
temp="save.tmp", nonsink=False):
"""Converts a folder of MCNFLI problem files into trilevel game files.
Applies convert_file() to all .min files in a specified directory. Only the
top level of the specified folder will be affected, not any of its
subfolders.
Requires the following positional arguments:
folder -- Name of the folder whose contents should be converted.
defnum -- Number of arcs that can be defended during Stage 1.
attnum -- Number of arcs that can be attacked during Stage 2.
Accepts the following optional keyword arguments:
defset -- List of defensible arc IDs (beginning at index 1). Defaults
to the empty list, which is treated as allowing all arcs to be
defended.
attset -- List of destructible arc IDs (beginning at index 1). Defaults
to the empty list, which is treated as allowing all arcs to be
destroyed. All defensible arcs are assumed to be attackable, so
only arcs that can be attacked but not defended need be listed.
temp -- Name of a temporary file used during the file conversion
process. Defaults to "save.tmp". As a temporary file this only
really needs to be changed if that name is already in use within
the specified directory.
nonsink -- An option for automatically making all arcs defensible and
destructible except for the artificailly created arcs for networks
with nodes as parents. If True, and if the network uses nodes as
parents, then defset and attset will be automatically set to
include all non-artificial arcs. Defaults to False.
"""
# Get list of file names in the specified folder
for (_, _, files) in os.walk(folder):
break
num = len(files) # number of files to process
# Process each file
i = 1
for f in files:
convert_file(folder+"/"+f, defnum, attnum, defset=defset,
attset=attset, temp=temp, nonsink=nonsink)
print("File "+str(i)+" / "+str(num)+" processed.")
i += 1
#==============================================================================
def generate_converted_trials(file, num, nodes, arcs, itype, inum, defnum,
attnum, sources=None, sinks=None, costs=(0, 100),
supply=None, capacities=(100, 500), defset=[],
attset=[], temp="save.tmp", nonsink=False):
"""Generates a set of converted trials using the same parameters.
Similar to generate_trials(), except that it immediately processes all new
files using convert_file().
Requires the following positional arguments:
file -- Base name of the output file (excluding the file extension).
All generated trials will be given the specified name followed by a
unique number.
num -- Number of files to generate.
nodes -- Number of nodes.
arcs -- Number of arcs.
itype -- Interdependency type (0 for parent nodes, 1 for parent arcs).
inum -- Number of interdependencies.
defnum -- Number of arcs that can be defended during Stage 1.
attnum -- Number of arcs that can be attacked during Stage 2.
Accepts the following optional keyword arguments:
sources -- Number of source nodes. Defaults to 20% of all nodes
(rounded up).
sinks -- Number of sink nodes. Defaults to 20% of all nodes (rounded
up).
costs -- Tuple of arc cost lower bound and upper bound. Defaults to
(0, 100).
supply -- Total supply value across all source nodes. Defaults to
10,000 per 256 nodes (rounded up).
capacities -- Tuple of arc capacity lower bound and upper bound.
Defaults to (100, 500).
defset -- List of defensible arc IDs (beginning at index 1). Defaults
to the empty list, which is treated as allowing all arcs to be
defended.
attset -- List of destructible arc IDs (beginning at index 1). Defaults
to the empty list, which is treated as allowing all arcs to be
destroyed. All defensible arcs are assumed to be attackable, so
only arcs that can be attacked but not defended need be listed.
temp -- Name of a temporary file used during the file conversion
process. Defaults to "save.tmp". As a temporary file this only
really needs to be changed if that name is already in use within
the same directory.
nonsink -- An option for automatically making all arcs defensible and
destructible except for the artificailly created arcs for networks
with nodes as parents. If True, and if the network uses nodes as
parents, then defset and attset will be automatically set to
include all non-artificial arcs. Defaults to False.
"""
# Set unspecified sources and sinks
if sources == None:
sources = math.ceil(0.2 * nodes)
if sinks == None:
sinks = math.ceil(0.2 * nodes)
# Set unspecified total supply
if supply == None:
supply = 10000 * math.ceil(nodes / 256)
# Main loop
i = 1
while i <= num:
# Generate file name by concatenating a number
fname = file + str(i).zfill(math.ceil(math.log10(num+1)))
# Use call_netgen() to generate a trial with an unspecified seed
code = call_netgen(fname, nodes, arcs, itype, inum, sources=sources,
sinks=sinks, costs=costs, supply=supply, capacities=capacities)
# If return code indicates unsuccessful execution, repeat loop
if code != 0:
continue
# Use convert_file() to convert the new file
convert_file(fname+".min", defnum, attnum, defset=defset,
attset=attset, temp=temp, nonsink=nonsink)
print("File "+str(i)+" / "+str(num)+" generated.")
i += 1