Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (1.18 KB)

1
# test_beamsearch.py - unit tests for the beamsearch module
2
#
3
# Copyright 2016-2019 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Unit tests for the beam search functions."""
10
from unittest import TestCase
11

    
12
from nose.tools import assert_equal
13

    
14
import networkx as nx
15

    
16

    
17
def identity(x):
18
    return x
19

    
20

    
21
class TestBeamSearch(TestCase):
22
    """Unit tests for the beam search function."""
23

    
24
    def test_narrow(self):
25
        """Tests that a narrow beam width may cause an incomplete search."""
26
        # In this search, we enqueue only the neighbor 3 at the first
27
        # step, then only the neighbor 2 at the second step. Once at
28
        # node 2, the search chooses node 3, since it has a higher value
29
        # that node 1, but node 3 has already been visited, so the
30
        # search terminates.
31
        G = nx.cycle_graph(4)
32
        edges = nx.bfs_beam_edges(G, 0, identity, width=1)
33
        assert_equal(list(edges), [(0, 3), (3, 2)])
34

    
35
    def test_wide(self):
36
        G = nx.cycle_graph(4)
37
        edges = nx.bfs_beam_edges(G, 0, identity, width=2)
38
        assert_equal(list(edges), [(0, 3), (0, 1), (3, 2)])