Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1# ------------------------------------------------------------------------------ 

2# Copyright (C) 2012-2017 Guillaume Sagnol 

3# Copyright (C) 2018-2019 Maximilian Stahlberg 

4# 

5# This file is part of PICOS. 

6# 

7# PICOS is free software: you can redistribute it and/or modify it under the 

8# terms of the GNU General Public License as published by the Free Software 

9# Foundation, either version 3 of the License, or (at your option) any later 

10# version. 

11# 

12# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY 

13# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 

14# A PARTICULAR PURPOSE. See the GNU General Public License for more details. 

15# 

16# You should have received a copy of the GNU General Public License along with 

17# this program. If not, see <http://www.gnu.org/licenses/>. 

18# ------------------------------------------------------------------------------ 

19 

20"""Implementation of :class:`FlowConstraint`.""" 

21 

22from collections import namedtuple 

23 

24from ..apidoc import api_end, api_start 

25from ..caching import cached_property 

26from .constraint import Constraint, ConstraintConversion 

27 

28_API_START = api_start(globals()) 

29# ------------------------------- 

30 

31 

32class FlowConstraint(Constraint): 

33 """Network flow constraint. 

34 

35 .. note :: 

36 Unlike other :class:`~.constraint.Constraint` implementations, this one 

37 is instanciated by the user (via a wrapper function), so it is raising 

38 exceptions instead of making assertions. 

39 """ 

40 

41 class Conversion(ConstraintConversion): 

42 """Network flow constraint conversion.""" 

43 

44 @classmethod 

45 def predict(cls, subtype, options): 

46 """Implement :meth:`~.constraint.ConstraintConversion.predict`.""" 

47 from ..expressions import RealVariable 

48 from . import AffineConstraint 

49 

50 numNodes, numEdges, flowCons, hasCapacities = subtype 

51 V, E = numNodes, numEdges 

52 

53 # Capacity and non-negativity constraints. 

54 yield ("con", AffineConstraint.make_type(dim=1, eq=False), 

55 2*E if hasCapacities else E) 

56 

57 if len(flowCons) == 1: 

58 yield ("con", AffineConstraint.make_type(dim=1, eq=True), V - 1) 

59 else: 

60 for k in flowCons: 

61 yield ("var", RealVariable.make_var_type(dim=1, bnd=0), E) 

62 

63 for addition in cls.predict((V, E, (k,), False), options): 

64 yield addition 

65 

66 yield ("con", AffineConstraint.make_type(dim=1, eq=True), E) 

67 

68 @classmethod 

69 def convert(cls, con, options): 

70 """Implement :meth:`~.constraint.ConstraintConversion.convert`.""" 

71 from ..modeling import Problem 

72 P = Problem() 

73 return cls._convert(con, P) # Allow for recursion. 

74 

75 @classmethod 

76 def _convert(cls, con, P): 

77 from ..expressions import new_param, sum 

78 

79 G = con.graph 

80 f = con.f 

81 source = con.source 

82 sink = con.sink 

83 flow_value = con.flow_value 

84 capacity = con.capacity 

85 graphName = con.graphName 

86 

87 # Add capacity constraints. 

88 if capacity is not None: 

89 c = {} 

90 for v, w, data in G.edges(data=True): 

91 c[(v, w)] = data[capacity] 

92 c = new_param('c', c) 

93 

94 P.add_list_of_constraints([f[e] <= c[e] for e in G.edges()]) 

95 

96 # Add non-negativity constraints. 

97 P.add_list_of_constraints([f[e] >= 0 for e in G.edges()]) 

98 

99 # One source, one sink. 

100 if not isinstance(source, list) and not isinstance(sink, list): 

101 # Add flow conversation constrains. 

102 P.add_list_of_constraints([ 

103 sum([f[p, i] for p in G.predecessors(i)]) 

104 == sum([f[i, j] for j in G.successors(i)]) 

105 for i in G.nodes() if i != sink and i != source]) 

106 

107 # Source flow at S 

108 P.add_constraint( 

109 sum([f[p, source] for p in G.predecessors(source)]) 

110 + flow_value == 

111 sum([f[source, j] for j in G.successors(source)])) 

112 

113 # One source, multiple sinks. 

114 elif not isinstance(source, list): 

115 # Add flow conversation constrains. 

116 P.add_list_of_constraints([ 

117 sum([f[p, i] for p in G.predecessors(i)]) 

118 == sum([f[i, j] for j in G.successors(i)]) 

119 for i in G.nodes() if i not in sink and i != source]) 

120 

121 for k in range(0, len(sink)): 

122 # Sink flow at T 

123 P.add_constraint( 

124 sum([f[p, sink[k]] for p in G.predecessors(sink[k])]) 

125 == sum([f[sink[k], j] for j in G.successors(sink[k])]) 

126 + flow_value[k]) 

127 

128 # Multiple sources, one sink. 

129 elif not isinstance(sink, list): 

130 # Add flow conversation constrains. 

131 P.add_list_of_constraints([ 

132 sum([f[p, i] for p in G.predecessors(i)]) 

133 == sum([f[i, j] for j in G.successors(i)]) 

134 for i in G.nodes() if i not in source and i != sink]) 

135 

136 for k in range(0, len(source)): 

137 # Source flow at T 

138 P.add_constraint(sum( 

139 [f[p, source[k]] for p in G.predecessors(source[k])]) 

140 + flow_value[k] == 

141 sum([f[source[k], j] for j in G.successors(source[k])])) 

142 

143 # Multiple sources, multiple sinks. 

144 # TODO: Recursion adds redundant non-negativity constraints. 

145 elif isinstance(sink, list) and isinstance(source, list): 

146 SS = list(set(source)) 

147 TT = list(set(sink)) 

148 

149 if len(SS) <= len(TT): 

150 ftmp = {} 

151 for s in SS: 

152 ftmp[s] = {} 

153 sinks_from_s = [ 

154 t for (i, t) in enumerate(sink) if source[i] == s] 

155 values_from_s = [v for (i, v) 

156 in enumerate(flow_value) if source[i] == s] 

157 

158 for e in G.edges(): 

159 ftmp[s][e] = P.add_variable( 

160 '__f[{0}][{1}]'.format(s, e), 1) 

161 

162 # Immediately convert another FlowConstraint so that the 

163 # reformulation created from this conversion doesn't 

164 # need to be run twice in a row. 

165 cls._convert(cls( 

166 G, ftmp[s], source=s, sink=sinks_from_s, 

167 flow_value=values_from_s, graphName=graphName), P) 

168 

169 P.add_list_of_constraints([ 

170 f[e] == sum([ftmp[s][e] for s in SS]) 

171 for e in G.edges()]) 

172 else: 

173 ftmp = {} 

174 for t in TT: 

175 ftmp[t] = {} 

176 sources_to_t = [ 

177 s for (i, s) in enumerate(source) if sink[i] == t] 

178 values_to_t = [v for (i, v) in enumerate(flow_value) 

179 if sink[i] == t] 

180 

181 for e in G.edges(): 

182 ftmp[t][e] = P.add_variable( 

183 '__f[{0}][{1}]'.format(t, e), 1) 

184 

185 # Immediately convert another FlowConstraint so that the 

186 # reformulation created from this conversion doesn't 

187 # need to be run twice in a row. 

188 cls._convert(cls( 

189 G, ftmp[t], source=sources_to_t, sink=t, 

190 flow_value=values_to_t, graphName=graphName), P) 

191 

192 P.add_list_of_constraints([ 

193 f[e] == sum([ftmp[t][e] for t in TT]) 

194 for e in G.edges()]) 

195 

196 else: 

197 assert False, "Dijkstra-IF fallthrough." 

198 

199 return P 

200 

201 def __init__( 

202 self, G, f, source, sink, flow_value, capacity=None, graphName=""): 

203 """Construct a network flow constraint. 

204 

205 :param G: A directed graph. 

206 :type G: `networkx DiGraph <http://networkx.lanl.gov/index.html>`_. 

207 

208 :param dict f: A dictionary of variables indexed by the edges of ``G``. 

209 

210 :param source: Either a node of ``G`` or a list of nodes in case of a 

211 multi-source flow. 

212 

213 :param sink: Either a node of ``G`` or a list of nodes in case of a 

214 multi-sink flow. 

215 

216 :param flow_value: The value of the flow, or a list of values in case of 

217 a single-source/multi-sink flow. In the latter case, the values 

218 represent the demands of each sink (resp. of each source for a 

219 multi-source/single-sink flow). The values can be either constants 

220 or :class:`~picos.expressions.AffineExpression`. 

221 

222 :param capacity: Either ``None`` or a string. If this is a string, it 

223 indicates the key of the edge dictionaries of ``G`` that is used for 

224 the capacity of the links. Otherwise, edges have an unbounded 

225 capacity. 

226 

227 :param str graphName: Name of the graph as used in the string 

228 representation of the constraint. 

229 """ 

230 if len(f) != len(G.edges()): 

231 raise ValueError( 

232 "The number of variables does not match the number of edges.") 

233 

234 if isinstance(sink, list) and len(sink) == 1: 

235 source = source[0] 

236 

237 if isinstance(sink, list) and len(sink) == 1: 

238 sink = sink[0] 

239 

240 if isinstance(source, list) and len(source) != len(flow_value): 

241 raise ValueError("The number of sources does not match the number " 

242 "of flow values.") 

243 

244 if isinstance(sink, list) and len(sink) != len(flow_value): 

245 raise ValueError("The number of sinks does not match the number " 

246 "of flow values.") 

247 

248 if isinstance(source, list) and isinstance(sink, list) \ 

249 and len(sink) != len(source): 

250 raise ValueError("The number of sinks does not match the number " 

251 "of sources.") 

252 

253 self.graph = G 

254 self.f = f 

255 self.source = source 

256 self.sink = sink 

257 self.flow_value = flow_value 

258 self.capacity = capacity 

259 self.graphName = graphName 

260 

261 # Build the string description. 

262 if isinstance(source, list): 

263 sourceStr = "(" + ",".join(source) + ")" 

264 else: 

265 sourceStr = str(source) 

266 

267 if isinstance(sink, list): 

268 sinkStr = "(" + ",".join(sink) + ")" 

269 else: 

270 sinkStr = str(sink) 

271 

272 if isinstance(flow_value, list): 

273 valueStr = "values " + ", ".join([v.string if hasattr(v, "string") 

274 else str(v) for v in flow_value]) 

275 else: 

276 valueStr = "value " + flow_value.string \ 

277 if hasattr(flow_value, "string") else str(flow_value) 

278 

279 self.comment = "{}{}-{}-flow{} has {}.".format( 

280 "Feasible " if capacity is not None else "", sourceStr, sinkStr, 

281 " in {}".format(graphName) if graphName else "", valueStr) 

282 

283 super(FlowConstraint, self).__init__("Flow") 

284 

285 Subtype = namedtuple("Subtype", 

286 ("lenV", "lenE", "flowCons", "hasCapacities")) 

287 

288 @classmethod 

289 def _cost(cls, subtype): 

290 return subtype.lenE # Somewhat arbitrary. 

291 

292 def _subtype(self): 

293 s = len(self.source) if isinstance(self.source, list) else 1 

294 t = len(self.sink) if isinstance(self.sink, list) else 1 

295 V = len(self.graph.nodes()) 

296 E = len(self.graph.edges()) 

297 

298 if s == 1 or t == 1: 

299 flowCons = (max(s, t),) 

300 else: 

301 flowCons = [] 

302 S, T = self.source, self.sink 

303 A, B = set(S), set(T) 

304 if len(A) > len(B): 

305 S, T = T, S 

306 A, B = B, A 

307 for s in A: 

308 flowCons.append(S.count(s)) 

309 flowCons = tuple(flowCons) 

310 

311 assert sum(flowCons) == max(s, t) 

312 

313 return self.Subtype(V, E, flowCons, self.capacity is not None) 

314 

315 def _expression_names(self): 

316 return 

317 yield 

318 

319 # HACK: The variables are not stored in named expressions but in a 

320 # dictionary. To make prediction work, they must be considered part 

321 # of the problem that the flow constraint was added to. 

322 @cached_property 

323 def mutables(self): # noqa 

324 return frozenset(self.f.values()) 

325 

326 # HACK: See above. 

327 def replace_mutables(self, mapping): # noqa 

328 f = {key: mapping[var] for key, var in self.f.items()} 

329 return FlowConstraint(self.graph, f, self.source, self.sink, 

330 self.flow_value, self.capacity, self.graphName) 

331 

332 def _str(self): 

333 return self.comment 

334 

335 def _get_slack(self): 

336 raise NotImplementedError 

337 

338 def draw(self): 

339 """Draw the graph.""" 

340 G = self.graph 

341 

342 import networkx as nx 

343 import matplotlib.pyplot as plt 

344 

345 pos = nx.spring_layout(G) 

346 edge_labels = dict([((u, v,), d["capacity"]) 

347 for u, v, d in G.edges(data=True)]) 

348 nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) 

349 nx.draw(G, pos) 

350 plt.show() 

351 

352 

353# -------------------------------------- 

354__all__ = api_end(_API_START, globals())