Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tests / test_simple_paths.py @ 5cef0f13

History | View | Annotate | Download (17.3 KB)

1
import random
2

    
3
from nose.tools import assert_equal
4
from nose.tools import assert_false
5
from nose.tools import assert_raises
6
from nose.tools import assert_true
7
from nose.tools import raises
8

    
9
import networkx as nx
10
from networkx import convert_node_labels_to_integers as cnlti
11
from networkx.algorithms.simple_paths import _bidirectional_dijkstra
12
from networkx.algorithms.simple_paths import _bidirectional_shortest_path
13
from networkx.utils import arbitrary_element
14

    
15

    
16
class TestIsSimplePath(object):
17
    """Unit tests for the
18
    :func:`networkx.algorithms.simple_paths.is_simple_path` function.
19

20
    """
21

    
22
    def test_empty_list(self):
23
        """Tests that the empty list is not a valid path, since there
24
        should be a one-to-one correspondence between paths as lists of
25
        nodes and paths as lists of edges.
26

27
        """
28
        G = nx.trivial_graph()
29
        assert_false(nx.is_simple_path(G, []))
30

    
31
    def test_trivial_path(self):
32
        """Tests that the trivial path, a path of length one, is
33
        considered a simple path in a graph.
34

35
        """
36
        G = nx.trivial_graph()
37
        assert_true(nx.is_simple_path(G, [0]))
38

    
39
    def test_trivial_nonpath(self):
40
        """Tests that a list whose sole element is an object not in the
41
        graph is not considered a simple path.
42

43
        """
44
        G = nx.trivial_graph()
45
        assert_false(nx.is_simple_path(G, ['not a node']))
46

    
47
    def test_simple_path(self):
48
        G = nx.path_graph(2)
49
        assert_true(nx.is_simple_path(G, [0, 1]))
50

    
51
    def test_non_simple_path(self):
52
        G = nx.path_graph(2)
53
        assert_false(nx.is_simple_path(G, [0, 1, 0]))
54

    
55
    def test_cycle(self):
56
        G = nx.cycle_graph(3)
57
        assert_false(nx.is_simple_path(G, [0, 1, 2, 0]))
58

    
59
    def test_missing_node(self):
60
        G = nx.path_graph(2)
61
        assert_false(nx.is_simple_path(G, [0, 2]))
62

    
63
    def test_directed_path(self):
64
        G = nx.DiGraph([(0, 1), (1, 2)])
65
        assert_true(nx.is_simple_path(G, [0, 1, 2]))
66

    
67
    def test_directed_non_path(self):
68
        G = nx.DiGraph([(0, 1), (1, 2)])
69
        assert_false(nx.is_simple_path(G, [2, 1, 0]))
70

    
71
    def test_directed_cycle(self):
72
        G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])
73
        assert_false(nx.is_simple_path(G, [0, 1, 2, 0]))
74

    
75
    def test_multigraph(self):
76
        G = nx.MultiGraph([(0, 1), (0, 1)])
77
        assert_true(nx.is_simple_path(G, [0, 1]))
78

    
79
    def test_multidigraph(self):
80
        G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 0), (1, 0)])
81
        assert_true(nx.is_simple_path(G, [0, 1]))
82

    
83

    
84
# Tests for all_simple_paths
85
def test_all_simple_paths():
86
    G = nx.path_graph(4)
87
    paths = nx.all_simple_paths(G, 0, 3)
88
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 2, 3)})
89

    
90

    
91
def test_all_simple_paths_with_two_targets_emits_two_paths():
92
    G = nx.path_graph(4)
93
    G.add_edge(2, 4)
94
    paths = nx.all_simple_paths(G, 0, [3, 4])
95
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 2, 3), (0, 1, 2, 4)})
96

    
97

    
98
def test_digraph_all_simple_paths_with_two_targets_emits_two_paths():
99
    G = nx.path_graph(4, create_using=nx.DiGraph())
100
    G.add_edge(2, 4)
101
    paths = nx.all_simple_paths(G, 0, [3, 4])
102
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 2, 3), (0, 1, 2, 4)})
103

    
104

    
105
def test_all_simple_paths_with_two_targets_cutoff():
106
    G = nx.path_graph(4)
107
    G.add_edge(2, 4)
108
    paths = nx.all_simple_paths(G, 0, [3, 4], cutoff=3)
109
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 2, 3), (0, 1, 2, 4)})
110

    
111

    
112
def test_digraph_all_simple_paths_with_two_targets_cutoff():
113
    G = nx.path_graph(4, create_using=nx.DiGraph())
114
    G.add_edge(2, 4)
115
    paths = nx.all_simple_paths(G, 0, [3, 4], cutoff=3)
116
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 2, 3), (0, 1, 2, 4)})
117

    
118

    
119
def test_all_simple_paths_with_two_targets_in_line_emits_two_paths():
120
    G = nx.path_graph(4)
121
    paths = nx.all_simple_paths(G, 0, [2, 3])
122
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 2), (0, 1, 2, 3)})
123

    
124

    
125
def test_all_simple_paths_ignores_cycle():
126
    G = nx.cycle_graph(3, create_using=nx.DiGraph())
127
    G.add_edge(1, 3)
128
    paths = nx.all_simple_paths(G, 0, 3)
129
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 3)})
130

    
131

    
132
def test_all_simple_paths_with_two_targets_inside_cycle_emits_two_paths():
133
    G = nx.cycle_graph(3, create_using=nx.DiGraph())
134
    G.add_edge(1, 3)
135
    paths = nx.all_simple_paths(G, 0, [2, 3])
136
    assert_equal(set(tuple(p) for p in paths), {(0, 1, 2), (0, 1, 3)})
137

    
138

    
139
def test_all_simple_paths_source_target():
140
    G = nx.path_graph(4)
141
    paths = nx.all_simple_paths(G, 1, 1)
142
    assert_equal(paths, [])
143

    
144

    
145
def test_all_simple_paths_cutoff():
146
    G = nx.complete_graph(4)
147
    paths = nx.all_simple_paths(G, 0, 1, cutoff=1)
148
    assert_equal(set(tuple(p) for p in paths), {(0, 1)})
149
    paths = nx.all_simple_paths(G, 0, 1, cutoff=2)
150
    assert_equal(set(tuple(p) for p in paths), {(0, 1), (0, 2, 1), (0, 3, 1)})
151

    
152

    
153
def test_all_simple_paths_on_non_trivial_graph():
154
    ''' you may need to draw this graph to make sure it is reasonable '''
155
    G = nx.path_graph(5, create_using=nx.DiGraph())
156
    G.add_edges_from([(0, 5), (1, 5), (1, 3), (5, 4), (4, 2), (4, 3)])
157
    paths = nx.all_simple_paths(G, 1, [2, 3])
158
    assert_equal(set(tuple(p) for p in paths), {
159
        (1, 2), (1, 3, 4, 2), (1, 5, 4, 2), (1, 3), (1, 2, 3), (1, 5, 4, 3),
160
        (1, 5, 4, 2, 3)})
161
    paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=3)
162
    assert_equal(set(tuple(p) for p in paths), {
163
        (1, 2), (1, 3, 4, 2), (1, 5, 4, 2), (1, 3), (1, 2, 3), (1, 5, 4, 3)})
164
    paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=2)
165
    assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 3), (1, 2, 3)})
166

    
167

    
168
def test_all_simple_paths_multigraph():
169
    G = nx.MultiGraph([(1, 2), (1, 2)])
170
    paths = nx.all_simple_paths(G, 1, 1)
171
    assert_equal(paths, [])
172
    nx.add_path(G, [3, 1, 10, 2])
173
    paths = list(nx.all_simple_paths(G, 1, 2))
174
    assert_equal(len(paths), 3)
175
    assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 2), (1, 10, 2)})
176

    
177

    
178
def test_all_simple_paths_multigraph_with_cutoff():
179
    G = nx.MultiGraph([(1, 2), (1, 2), (1, 10), (10, 2)])
180
    paths = list(nx.all_simple_paths(G, 1, 2, cutoff=1))
181
    assert_equal(len(paths), 2)
182
    assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 2)})
183

    
184

    
185
def test_all_simple_paths_directed():
186
    G = nx.DiGraph()
187
    nx.add_path(G, [1, 2, 3])
188
    nx.add_path(G, [3, 2, 1])
189
    paths = nx.all_simple_paths(G, 1, 3)
190
    assert_equal(set(tuple(p) for p in paths), {(1, 2, 3)})
191

    
192

    
193
def test_all_simple_paths_empty():
194
    G = nx.path_graph(4)
195
    paths = nx.all_simple_paths(G, 0, 3, cutoff=2)
196
    assert_equal(list(paths), [])
197

    
198

    
199
def test_all_simple_paths_corner_cases():
200
    assert_equal(list(nx.all_simple_paths(nx.empty_graph(2), 0, 0)), [])
201
    assert_equal(list(nx.all_simple_paths(nx.empty_graph(2), 0, 1)), [])
202
    assert_equal(list(nx.all_simple_paths(nx.path_graph(9), 0, 8, 0)), [])
203

    
204

    
205
def hamiltonian_path(G, source):
206
    source = arbitrary_element(G)
207
    neighbors = set(G[source]) - set([source])
208
    n = len(G)
209
    for target in neighbors:
210
        for path in nx.all_simple_paths(G, source, target):
211
            if len(path) == n:
212
                yield path
213

    
214

    
215
def test_hamiltonian_path():
216
    from itertools import permutations
217
    G = nx.complete_graph(4)
218
    paths = [list(p) for p in hamiltonian_path(G, 0)]
219
    exact = [[0] + list(p) for p in permutations([1, 2, 3], 3)]
220
    assert_equal(sorted(paths), sorted(exact))
221

    
222

    
223
def test_cutoff_zero():
224
    G = nx.complete_graph(4)
225
    paths = nx.all_simple_paths(G, 0, 3, cutoff=0)
226
    assert_equal(list(list(p) for p in paths), [])
227
    paths = nx.all_simple_paths(nx.MultiGraph(G), 0, 3, cutoff=0)
228
    assert_equal(list(list(p) for p in paths), [])
229

    
230

    
231
@raises(nx.NodeNotFound)
232
def test_source_missing():
233
    G = nx.Graph()
234
    nx.add_path(G, [1, 2, 3])
235
    paths = list(nx.all_simple_paths(nx.MultiGraph(G), 0, 3))
236

    
237

    
238
@raises(nx.NodeNotFound)
239
def test_target_missing():
240
    G = nx.Graph()
241
    nx.add_path(G, [1, 2, 3])
242
    paths = list(nx.all_simple_paths(nx.MultiGraph(G), 1, 4))
243

    
244

    
245
# Tests for shortest_simple_paths
246
def test_shortest_simple_paths():
247
    G = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
248
    paths = nx.shortest_simple_paths(G, 1, 12)
249
    assert_equal(next(paths), [1, 2, 3, 4, 8, 12])
250
    assert_equal(next(paths), [1, 5, 6, 7, 8, 12])
251
    assert_equal([len(path) for path in nx.shortest_simple_paths(G, 1, 12)],
252
                 sorted([len(path) for path in nx.all_simple_paths(G, 1, 12)]))
253

    
254

    
255
def test_shortest_simple_paths_directed():
256
    G = nx.cycle_graph(7, create_using=nx.DiGraph())
257
    paths = nx.shortest_simple_paths(G, 0, 3)
258
    assert_equal([path for path in paths], [[0, 1, 2, 3]])
259

    
260

    
261
def test_Greg_Bernstein():
262
    g1 = nx.Graph()
263
    g1.add_nodes_from(["N0", "N1", "N2", "N3", "N4"])
264
    g1.add_edge("N4", "N1", weight=10.0, capacity=50, name="L5")
265
    g1.add_edge("N4", "N0", weight=7.0, capacity=40, name="L4")
266
    g1.add_edge("N0", "N1", weight=10.0, capacity=45, name="L1")
267
    g1.add_edge("N3", "N0", weight=10.0, capacity=50, name="L0")
268
    g1.add_edge("N2", "N3", weight=12.0, capacity=30, name="L2")
269
    g1.add_edge("N1", "N2", weight=15.0, capacity=42, name="L3")
270
    solution = [['N1', 'N0', 'N3'], ['N1', 'N2', 'N3'], ['N1', 'N4', 'N0', 'N3']]
271
    result = list(nx.shortest_simple_paths(g1, 'N1', 'N3', weight='weight'))
272
    assert_equal(result, solution)
273

    
274

    
275
def test_weighted_shortest_simple_path():
276
    def cost_func(path):
277
        return sum(G.adj[u][v]['weight'] for (u, v) in zip(path, path[1:]))
278

    
279
    G = nx.complete_graph(5)
280
    weight = {(u, v): random.randint(1, 100) for (u, v) in G.edges()}
281
    nx.set_edge_attributes(G, weight, 'weight')
282
    cost = 0
283
    for path in nx.shortest_simple_paths(G, 0, 3, weight='weight'):
284
        this_cost = cost_func(path)
285
        assert_true(cost <= this_cost)
286
        cost = this_cost
287

    
288

    
289
def test_directed_weighted_shortest_simple_path():
290
    def cost_func(path):
291
        return sum(G.adj[u][v]['weight'] for (u, v) in zip(path, path[1:]))
292

    
293
    G = nx.complete_graph(5)
294
    G = G.to_directed()
295
    weight = {(u, v): random.randint(1, 100) for (u, v) in G.edges()}
296
    nx.set_edge_attributes(G, weight, 'weight')
297
    cost = 0
298
    for path in nx.shortest_simple_paths(G, 0, 3, weight='weight'):
299
        this_cost = cost_func(path)
300
        assert_true(cost <= this_cost)
301
        cost = this_cost
302

    
303

    
304
def test_weighted_shortest_simple_path_issue2427():
305
    G = nx.Graph()
306
    G.add_edge('IN', 'OUT', weight=2)
307
    G.add_edge('IN', 'A', weight=1)
308
    G.add_edge('IN', 'B', weight=2)
309
    G.add_edge('B', 'OUT', weight=2)
310
    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight="weight")),
311
                 [['IN', 'OUT'], ['IN', 'B', 'OUT']])
312
    G = nx.Graph()
313
    G.add_edge('IN', 'OUT', weight=10)
314
    G.add_edge('IN', 'A', weight=1)
315
    G.add_edge('IN', 'B', weight=1)
316
    G.add_edge('B', 'OUT', weight=1)
317
    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight="weight")),
318
                 [['IN', 'B', 'OUT'], ['IN', 'OUT']])
319

    
320

    
321
def test_directed_weighted_shortest_simple_path_issue2427():
322
    G = nx.DiGraph()
323
    G.add_edge('IN', 'OUT', weight=2)
324
    G.add_edge('IN', 'A', weight=1)
325
    G.add_edge('IN', 'B', weight=2)
326
    G.add_edge('B', 'OUT', weight=2)
327
    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight="weight")),
328
                 [['IN', 'OUT'], ['IN', 'B', 'OUT']])
329
    G = nx.DiGraph()
330
    G.add_edge('IN', 'OUT', weight=10)
331
    G.add_edge('IN', 'A', weight=1)
332
    G.add_edge('IN', 'B', weight=1)
333
    G.add_edge('B', 'OUT', weight=1)
334
    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight="weight")),
335
                 [['IN', 'B', 'OUT'], ['IN', 'OUT']])
336

    
337

    
338
def test_weight_name():
339
    G = nx.cycle_graph(7)
340
    nx.set_edge_attributes(G, 1, 'weight')
341
    nx.set_edge_attributes(G, 1, 'foo')
342
    G.adj[1][2]['foo'] = 7
343
    paths = list(nx.shortest_simple_paths(G, 0, 3, weight='foo'))
344
    solution = [[0, 6, 5, 4, 3], [0, 1, 2, 3]]
345
    assert_equal(paths, solution)
346

    
347

    
348
@raises(nx.NodeNotFound)
349
def test_ssp_source_missing():
350
    G = nx.Graph()
351
    nx.add_path(G, [1, 2, 3])
352
    paths = list(nx.shortest_simple_paths(G, 0, 3))
353

    
354

    
355
@raises(nx.NodeNotFound)
356
def test_ssp_target_missing():
357
    G = nx.Graph()
358
    nx.add_path(G, [1, 2, 3])
359
    paths = list(nx.shortest_simple_paths(G, 1, 4))
360

    
361

    
362
@raises(nx.NetworkXNotImplemented)
363
def test_ssp_multigraph():
364
    G = nx.MultiGraph()
365
    nx.add_path(G, [1, 2, 3])
366
    paths = list(nx.shortest_simple_paths(G, 1, 4))
367

    
368

    
369
@raises(nx.NetworkXNoPath)
370
def test_ssp_source_missing():
371
    G = nx.Graph()
372
    nx.add_path(G, [0, 1, 2])
373
    nx.add_path(G, [3, 4, 5])
374
    paths = list(nx.shortest_simple_paths(G, 0, 3))
375

    
376

    
377
def test_bidirectional_shortest_path_restricted_cycle():
378
    cycle = nx.cycle_graph(7)
379
    length, path = _bidirectional_shortest_path(cycle, 0, 3)
380
    assert_equal(path, [0, 1, 2, 3])
381
    length, path = _bidirectional_shortest_path(cycle, 0, 3, ignore_nodes=[1])
382
    assert_equal(path, [0, 6, 5, 4, 3])
383

    
384

    
385
def test_bidirectional_shortest_path_restricted_wheel():
386
    wheel = nx.wheel_graph(6)
387
    length, path = _bidirectional_shortest_path(wheel, 1, 3)
388
    assert_true(path in [[1, 0, 3], [1, 2, 3]])
389
    length, path = _bidirectional_shortest_path(wheel, 1, 3, ignore_nodes=[0])
390
    assert_equal(path, [1, 2, 3])
391
    length, path = _bidirectional_shortest_path(wheel, 1, 3, ignore_nodes=[0, 2])
392
    assert_equal(path, [1, 5, 4, 3])
393
    length, path = _bidirectional_shortest_path(wheel, 1, 3,
394
                                                ignore_edges=[(1, 0), (5, 0), (2, 3)])
395
    assert_true(path in [[1, 2, 0, 3], [1, 5, 4, 3]])
396

    
397

    
398
def test_bidirectional_shortest_path_restricted_directed_cycle():
399
    directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
400
    length, path = _bidirectional_shortest_path(directed_cycle, 0, 3)
401
    assert_equal(path, [0, 1, 2, 3])
402
    assert_raises(
403
        nx.NetworkXNoPath,
404
        _bidirectional_shortest_path,
405
        directed_cycle,
406
        0, 3,
407
        ignore_nodes=[1],
408
    )
409
    length, path = _bidirectional_shortest_path(directed_cycle, 0, 3,
410
                                                ignore_edges=[(2, 1)])
411
    assert_equal(path, [0, 1, 2, 3])
412
    assert_raises(
413
        nx.NetworkXNoPath,
414
        _bidirectional_shortest_path,
415
        directed_cycle,
416
        0, 3,
417
        ignore_edges=[(1, 2)],
418
    )
419

    
420

    
421
def test_bidirectional_shortest_path_ignore():
422
    G = nx.Graph()
423
    nx.add_path(G, [1, 2])
424
    nx.add_path(G, [1, 3])
425
    nx.add_path(G, [1, 4])
426
    assert_raises(
427
        nx.NetworkXNoPath,
428
        _bidirectional_shortest_path,
429
        G,
430
        1, 2,
431
        ignore_nodes=[1],
432
    )
433
    assert_raises(
434
        nx.NetworkXNoPath,
435
        _bidirectional_shortest_path,
436
        G,
437
        1, 2,
438
        ignore_nodes=[2],
439
    )
440
    G = nx.Graph()
441
    nx.add_path(G, [1, 3])
442
    nx.add_path(G, [1, 4])
443
    nx.add_path(G, [3, 2])
444
    assert_raises(
445
        nx.NetworkXNoPath,
446
        _bidirectional_shortest_path,
447
        G,
448
        1, 2,
449
        ignore_nodes=[1, 2],
450
    )
451

    
452

    
453
def validate_path(G, s, t, soln_len, path):
454
    assert_equal(path[0], s)
455
    assert_equal(path[-1], t)
456
    assert_equal(soln_len, sum(G[u][v].get('weight', 1)
457
                               for u, v in zip(path[:-1], path[1:])))
458

    
459

    
460
def validate_length_path(G, s, t, soln_len, length, path):
461
    assert_equal(soln_len, length)
462
    validate_path(G, s, t, length, path)
463

    
464

    
465
def test_bidirectional_dijksta_restricted():
466
    XG = nx.DiGraph()
467
    XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5),
468
                                ('u', 'v', 1), ('u', 'x', 2),
469
                                ('v', 'y', 1), ('x', 'u', 3),
470
                                ('x', 'v', 5), ('x', 'y', 2),
471
                                ('y', 's', 7), ('y', 'v', 6)])
472

    
473
    XG3 = nx.Graph()
474
    XG3.add_weighted_edges_from([[0, 1, 2], [1, 2, 12],
475
                                 [2, 3, 1], [3, 4, 5],
476
                                 [4, 5, 1], [5, 0, 10]])
477
    validate_length_path(XG, 's', 'v', 9,
478
                         *_bidirectional_dijkstra(XG, 's', 'v'))
479
    validate_length_path(XG, 's', 'v', 10,
480
                         *_bidirectional_dijkstra(XG, 's', 'v', ignore_nodes=['u']))
481
    validate_length_path(XG, 's', 'v', 11,
482
                         *_bidirectional_dijkstra(XG, 's', 'v', ignore_edges=[('s', 'x')]))
483
    assert_raises(
484
        nx.NetworkXNoPath,
485
        _bidirectional_dijkstra,
486
        XG,
487
        's', 'v',
488
        ignore_nodes=['u'],
489
        ignore_edges=[('s', 'x')],
490
    )
491
    validate_length_path(XG3, 0, 3, 15, *_bidirectional_dijkstra(XG3, 0, 3))
492
    validate_length_path(XG3, 0, 3, 16,
493
                         *_bidirectional_dijkstra(XG3, 0, 3, ignore_nodes=[1]))
494
    validate_length_path(XG3, 0, 3, 16,
495
                         *_bidirectional_dijkstra(XG3, 0, 3, ignore_edges=[(2, 3)]))
496
    assert_raises(
497
        nx.NetworkXNoPath,
498
        _bidirectional_dijkstra,
499
        XG3,
500
        0, 3,
501
        ignore_nodes=[1],
502
        ignore_edges=[(5, 4)],
503
    )
504

    
505

    
506
@raises(nx.NetworkXNoPath)
507
def test_bidirectional_dijkstra_no_path():
508
    G = nx.Graph()
509
    nx.add_path(G, [1, 2, 3])
510
    nx.add_path(G, [4, 5, 6])
511
    path = _bidirectional_dijkstra(G, 1, 6)
512

    
513

    
514
def test_bidirectional_dijkstra_ignore():
515
    G = nx.Graph()
516
    nx.add_path(G, [1, 2, 10])
517
    nx.add_path(G, [1, 3, 10])
518
    assert_raises(
519
        nx.NetworkXNoPath,
520
        _bidirectional_dijkstra,
521
        G,
522
        1, 2,
523
        ignore_nodes=[1],
524
    )
525
    assert_raises(
526
        nx.NetworkXNoPath,
527
        _bidirectional_dijkstra,
528
        G,
529
        1, 2,
530
        ignore_nodes=[2],
531
    )
532
    assert_raises(
533
        nx.NetworkXNoPath,
534
        _bidirectional_dijkstra,
535
        G,
536
        1, 2,
537
        ignore_nodes=[1, 2],
538
    )