Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/euler.py: 14%

1"""

2Eulerian circuits and graphs.

3"""

4from itertools import combinations

6import networkx as nx

8from ..utils import arbitrary_element, not_implemented_for

10__all__ = [

11 "is_eulerian",

12 "eulerian_circuit",

13 "eulerize",

14 "is_semieulerian",

15 "has_eulerian_path",

16 "eulerian_path",

17]

20@nx._dispatch

21def is_eulerian(G):

22 """Returns True if and only if `G` is Eulerian.

24 A graph is *Eulerian* if it has an Eulerian circuit. An *Eulerian

25 circuit* is a closed walk that includes each edge of a graph exactly

26 once.

28 Graphs with isolated vertices (i.e. vertices with zero degree) are not

29 considered to have Eulerian circuits. Therefore, if the graph is not

30 connected (or not strongly connected, for directed graphs), this function

31 returns False.

33 Parameters

34 ----------

35 G : NetworkX graph

36 A graph, either directed or undirected.

38 Examples

39 --------

40 >>> nx.is_eulerian(nx.DiGraph({0: [3], 1: [2], 2: [3], 3: [0, 1]}))

41 True

42 >>> nx.is_eulerian(nx.complete_graph(5))

43 True

44 >>> nx.is_eulerian(nx.petersen_graph())

45 False

47 If you prefer to allow graphs with isolated vertices to have Eulerian circuits,

48 you can first remove such vertices and then call `is_eulerian` as below example shows.

50 >>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])

51 >>> G.add_node(3)

52 >>> nx.is_eulerian(G)

53 False

55 >>> G.remove_nodes_from(list(nx.isolates(G)))

56 >>> nx.is_eulerian(G)

57 True

60 """

61 if G.is_directed():

62 # Every node must have equal in degree and out degree and the

63 # graph must be strongly connected

64 return all(

65 G.in_degree(n) == G.out_degree(n) for n in G

66 ) and nx.is_strongly_connected(G)

67 # An undirected Eulerian graph has no vertices of odd degree and

68 # must be connected.

69 return all(d % 2 == 0 for v, d in G.degree()) and nx.is_connected(G)

72@nx._dispatch

73def is_semieulerian(G):

74 """Return True iff `G` is semi-Eulerian.

76 G is semi-Eulerian if it has an Eulerian path but no Eulerian circuit.

78 See Also

79 --------

80 has_eulerian_path

81 is_eulerian

82 """

83 return has_eulerian_path(G) and not is_eulerian(G)

86def _find_path_start(G):

87 """Return a suitable starting vertex for an Eulerian path.

89 If no path exists, return None.

90 """

91 if not has_eulerian_path(G):

92 return None

94 if is_eulerian(G):

95 return arbitrary_element(G)

97 if G.is_directed():

98 v1, v2 = (v for v in G if G.in_degree(v) != G.out_degree(v))

99 # Determines which is the 'start' node (as opposed to the 'end')

100 if G.out_degree(v1) > G.in_degree(v1):

101 return v1

102 else:

103 return v2

104

105 else:

106 # In an undirected graph randomly choose one of the possibilities

107 start = [v for v in G if G.degree(v) % 2 != 0][0]

108 return start

109

110

111def _simplegraph_eulerian_circuit(G, source):

112 if G.is_directed():

113 degree = G.out_degree

114 edges = G.out_edges

115 else:

116 degree = G.degree

117 edges = G.edges

118 vertex_stack = [source]

119 last_vertex = None

120 while vertex_stack:

121 current_vertex = vertex_stack[-1]

122 if degree(current_vertex) == 0:

123 if last_vertex is not None:

124 yield (last_vertex, current_vertex)

125 last_vertex = current_vertex

126 vertex_stack.pop()

127 else:

128 _, next_vertex = arbitrary_element(edges(current_vertex))

129 vertex_stack.append(next_vertex)

130 G.remove_edge(current_vertex, next_vertex)

131

132

133def _multigraph_eulerian_circuit(G, source):

134 if G.is_directed():

135 degree = G.out_degree

136 edges = G.out_edges

137 else:

138 degree = G.degree

139 edges = G.edges

140 vertex_stack = [(source, None)]

141 last_vertex = None

142 last_key = None

143 while vertex_stack:

144 current_vertex, current_key = vertex_stack[-1]

145 if degree(current_vertex) == 0:

146 if last_vertex is not None:

147 yield (last_vertex, current_vertex, last_key)

148 last_vertex, last_key = current_vertex, current_key

149 vertex_stack.pop()

150 else:

151 triple = arbitrary_element(edges(current_vertex, keys=True))

152 _, next_vertex, next_key = triple

153 vertex_stack.append((next_vertex, next_key))

154 G.remove_edge(current_vertex, next_vertex, next_key)

155

156

157@nx._dispatch

158def eulerian_circuit(G, source=None, keys=False):

159 """Returns an iterator over the edges of an Eulerian circuit in `G`.

160

161 An *Eulerian circuit* is a closed walk that includes each edge of a

162 graph exactly once.

163

164 Parameters

165 ----------

166 G : NetworkX graph

167 A graph, either directed or undirected.

168

169 source : node, optional

170 Starting node for circuit.

171

172 keys : bool

173 If False, edges generated by this function will be of the form

174 ``(u, v)``. Otherwise, edges will be of the form ``(u, v, k)``.

175 This option is ignored unless `G` is a multigraph.

176

177 Returns

178 -------

179 edges : iterator

180 An iterator over edges in the Eulerian circuit.

181

182 Raises

183 ------

184 NetworkXError

185 If the graph is not Eulerian.

186

187 See Also

188 --------

189 is_eulerian

190

191 Notes

192 -----

193 This is a linear time implementation of an algorithm adapted from [1]_.

194

195 For general information about Euler tours, see [2]_.

196

197 References

198 ----------

199 .. [1] J. Edmonds, E. L. Johnson.

200 Matching, Euler tours and the Chinese postman.

201 Mathematical programming, Volume 5, Issue 1 (1973), 111-114.

202 .. [2] https://en.wikipedia.org/wiki/Eulerian_path

203

204 Examples

205 --------

206 To get an Eulerian circuit in an undirected graph::

207

208 >>> G = nx.complete_graph(3)

209 >>> list(nx.eulerian_circuit(G))

210 [(0, 2), (2, 1), (1, 0)]

211 >>> list(nx.eulerian_circuit(G, source=1))

212 [(1, 2), (2, 0), (0, 1)]

213

214 To get the sequence of vertices in an Eulerian circuit::

215

216 >>> [u for u, v in nx.eulerian_circuit(G)]

217 [0, 2, 1]

218

219 """

220 if not is_eulerian(G):

221 raise nx.NetworkXError("G is not Eulerian.")

222 if G.is_directed():

223 G = G.reverse()

224 else:

225 G = G.copy()

226 if source is None:

227 source = arbitrary_element(G)

228 if G.is_multigraph():

229 for u, v, k in _multigraph_eulerian_circuit(G, source):

230 if keys:

231 yield u, v, k

232 else:

233 yield u, v

234 else:

235 yield from _simplegraph_eulerian_circuit(G, source)

236

237

238@nx._dispatch

239def has_eulerian_path(G, source=None):

240 """Return True iff `G` has an Eulerian path.

241

242 An Eulerian path is a path in a graph which uses each edge of a graph

243 exactly once. If `source` is specified, then this function checks

244 whether an Eulerian path that starts at node `source` exists.

245

246 A directed graph has an Eulerian path iff:

247 - at most one vertex has out_degree - in_degree = 1,

248 - at most one vertex has in_degree - out_degree = 1,

249 - every other vertex has equal in_degree and out_degree,

250 - and all of its vertices belong to a single connected

251 component of the underlying undirected graph.

252

253 If `source` is not None, an Eulerian path starting at `source` exists if no

254 other node has out_degree - in_degree = 1. This is equivalent to either

255 there exists an Eulerian circuit or `source` has out_degree - in_degree = 1

256 and the conditions above hold.

257

258 An undirected graph has an Eulerian path iff:

259 - exactly zero or two vertices have odd degree,

260 - and all of its vertices belong to a single connected component.

261

262 If `source` is not None, an Eulerian path starting at `source` exists if

263 either there exists an Eulerian circuit or `source` has an odd degree and the

264 conditions above hold.

265

266 Graphs with isolated vertices (i.e. vertices with zero degree) are not considered

267 to have an Eulerian path. Therefore, if the graph is not connected (or not strongly

268 connected, for directed graphs), this function returns False.

269

270 Parameters

271 ----------

272 G : NetworkX Graph

273 The graph to find an euler path in.

274

275 source : node, optional

276 Starting node for path.

277

278 Returns

279 -------

280 Bool : True if G has an Eulerian path.

281

282 Examples

283 --------

284 If you prefer to allow graphs with isolated vertices to have Eulerian path,

285 you can first remove such vertices and then call `has_eulerian_path` as below example shows.

286

287 >>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])

288 >>> G.add_node(3)

289 >>> nx.has_eulerian_path(G)

290 False

291

292 >>> G.remove_nodes_from(list(nx.isolates(G)))

293 >>> nx.has_eulerian_path(G)

294 True

295

296 See Also

297 --------

298 is_eulerian

299 eulerian_path

300 """

301 if nx.is_eulerian(G):

302 return True

303

304 if G.is_directed():

305 ins = G.in_degree

306 outs = G.out_degree

307 # Since we know it is not eulerian, outs - ins must be 1 for source

308 if source is not None and outs[source] - ins[source] != 1:

309 return False

310

311 unbalanced_ins = 0

312 unbalanced_outs = 0

313 for v in G:

314 if ins[v] - outs[v] == 1:

315 unbalanced_ins += 1

316 elif outs[v] - ins[v] == 1:

317 unbalanced_outs += 1

318 elif ins[v] != outs[v]:

319 return False

320

321 return (

322 unbalanced_ins <= 1 and unbalanced_outs <= 1 and nx.is_weakly_connected(G)

323 )

324 else:

325 # We know it is not eulerian, so degree of source must be odd.

326 if source is not None and G.degree[source] % 2 != 1:

327 return False

328

329 # Sum is 2 since we know it is not eulerian (which implies sum is 0)

330 return sum(d % 2 == 1 for v, d in G.degree()) == 2 and nx.is_connected(G)

331

332

333@nx._dispatch

334def eulerian_path(G, source=None, keys=False):

335 """Return an iterator over the edges of an Eulerian path in `G`.

336

337 Parameters

338 ----------

339 G : NetworkX Graph

340 The graph in which to look for an eulerian path.

341 source : node or None (default: None)

342 The node at which to start the search. None means search over all

343 starting nodes.

344 keys : Bool (default: False)

345 Indicates whether to yield edge 3-tuples (u, v, edge_key).

346 The default yields edge 2-tuples

347

348 Yields

349 ------

350 Edge tuples along the eulerian path.

351

352 Warning: If `source` provided is not the start node of an Euler path

353 will raise error even if an Euler Path exists.

354 """

355 if not has_eulerian_path(G, source):

356 raise nx.NetworkXError("Graph has no Eulerian paths.")

357 if G.is_directed():

358 G = G.reverse()

359 if source is None or nx.is_eulerian(G) is False:

360 source = _find_path_start(G)

361 if G.is_multigraph():

362 for u, v, k in _multigraph_eulerian_circuit(G, source):

363 if keys:

364 yield u, v, k

365 else:

366 yield u, v

367 else:

368 yield from _simplegraph_eulerian_circuit(G, source)

369 else:

370 G = G.copy()

371 if source is None:

372 source = _find_path_start(G)

373 if G.is_multigraph():

374 if keys:

375 yield from reversed(

376 [(v, u, k) for u, v, k in _multigraph_eulerian_circuit(G, source)]

377 )

378 else:

379 yield from reversed(

380 [(v, u) for u, v, k in _multigraph_eulerian_circuit(G, source)]

381 )

382 else:

383 yield from reversed(

384 [(v, u) for u, v in _simplegraph_eulerian_circuit(G, source)]

385 )

386

387

388@not_implemented_for("directed")

389@nx._dispatch

390def eulerize(G):

391 """Transforms a graph into an Eulerian graph.

392

393 If `G` is Eulerian the result is `G` as a MultiGraph, otherwise the result is a smallest

394 (in terms of the number of edges) multigraph whose underlying simple graph is `G`.

395

396 Parameters

397 ----------

398 G : NetworkX graph

399 An undirected graph

400

401 Returns

402 -------

403 G : NetworkX multigraph

404

405 Raises

406 ------

407 NetworkXError

408 If the graph is not connected.

409

410 See Also

411 --------

412 is_eulerian

413 eulerian_circuit

414

415 References

416 ----------

417 .. [1] J. Edmonds, E. L. Johnson.

418 Matching, Euler tours and the Chinese postman.

419 Mathematical programming, Volume 5, Issue 1 (1973), 111-114.

420 .. [2] https://en.wikipedia.org/wiki/Eulerian_path

421 .. [3] http://web.math.princeton.edu/math_alive/5/Notes1.pdf

422

423 Examples

424 --------

425 >>> G = nx.complete_graph(10)

426 >>> H = nx.eulerize(G)

427 >>> nx.is_eulerian(H)

428 True

429

430 """

431 if G.order() == 0:

432 raise nx.NetworkXPointlessConcept("Cannot Eulerize null graph")

433 if not nx.is_connected(G):

434 raise nx.NetworkXError("G is not connected")

435 odd_degree_nodes = [n for n, d in G.degree() if d % 2 == 1]

436 G = nx.MultiGraph(G)

437 if len(odd_degree_nodes) == 0:

438 return G

439

440 # get all shortest paths between vertices of odd degree

441 odd_deg_pairs_paths = [

442 (m, {n: nx.shortest_path(G, source=m, target=n)})

443 for m, n in combinations(odd_degree_nodes, 2)

444 ]

445

446 # use the number of vertices in a graph + 1 as an upper bound on

447 # the maximum length of a path in G

448 upper_bound_on_max_path_length = len(G) + 1

449

450 # use "len(G) + 1 - len(P)",

451 # where P is a shortest path between vertices n and m,

452 # as edge-weights in a new graph

453 # store the paths in the graph for easy indexing later

454 Gp = nx.Graph()

455 for n, Ps in odd_deg_pairs_paths:

456 for m, P in Ps.items():

457 if n != m:

458 Gp.add_edge(

459 m, n, weight=upper_bound_on_max_path_length - len(P), path=P

460 )

461

462 # find the minimum weight matching of edges in the weighted graph

463 best_matching = nx.Graph(list(nx.max_weight_matching(Gp)))

464

465 # duplicate each edge along each path in the set of paths in Gp

466 for m, n in best_matching.edges():

467 path = Gp[m][n]["path"]

468 G.add_edges_from(nx.utils.pairwise(path))

469 return G