BreadthFirstSearch#

class BreadthFirstSearch#

Bases: Algorithm[Graph | DiGraph, GraphSize, TraversalGraph]

Breadth First Search algorithm.

__init__()#

Methods

`__init__`()
`get_worst_case_arguments`(input_size)	Generate a graph with input_size.nodes nodes and input_size.edges edges and search for element that is not present in the graph.
`increment_n_ops`([increment])	Convenience method to increment n_ops count of the given complexity object.
`reset_n_ops`()	Convenience method to reset n_ops count of the given complexity object.
`run_algorithm`(input_instance[, ...])	Run function of the breadth first search (BFS) algorithm.

Attributes

`algorithm_family`	rtype: `AlgorithmFamily`
`algorithm_properties`	rtype: `AlgorithmProperties`
`average_case_time_complexity`	rtype: `str`
`best_case_description`	rtype: `str`
`best_case_time_complexity`	rtype: `str`
`is_deterministic`	rtype: `bool`
`n_ops`	rtype: `int`
`name`	rtype: `str`
`space_complexity`	rtype: `str`
`worst_case_description`	rtype: `str`
`worst_case_time_complexity`	rtype: `str`

property algorithm_family: AlgorithmFamily#

Return type:: AlgorithmFamily

property algorithm_properties: AlgorithmProperties#

Return type:: AlgorithmProperties

property average_case_time_complexity: str#

Return type:: str

property best_case_description: str#

Return type:: str

property best_case_time_complexity: str#

Return type:: str

get_worst_case_arguments(input_size)#

Generate a graph with input_size.nodes nodes and input_size.edges edges and search for element that is not present in the graph. The graph instance starts as a star graph, sequentially adding new star roots until desired number of edges is reached or until the graph is fully connected.

Parameters:: input_size (GraphSize) – Tuple of n_nodes, n_edges with desired graph size.
Returns:: run_algorithm_kwargs – A dictionary with the created graph as ‘input_instance’ value and ‘element_to_search’ which is not present in the graph.
Return type:: dict[str, Any]

increment_n_ops(increment=1)#

Convenience method to increment n_ops count of the given complexity object.

Return type:: None

property is_deterministic: bool#

Return type:: bool

property n_ops: int#

Return type:: int

property name: str#

Return type:: str

reset_n_ops()#

Convenience method to reset n_ops count of the given complexity object.

Return type:: None

run_algorithm(input_instance, verbosity_level=0, root=NoNode, element_to_search=NoNode, *args, **kwargs)#

Run function of the breadth first search (BFS) algorithm.

Parameters:

input_instance (Graph | DiGraph) – Graph in which to run the search.
verbosity_level (int (default 0)) – Select the amount of information to print throughout run of the algorithm. One of 0, 1, 2 with 0 referring to no printing, 1 leading to print of the traversal order nodes at the end and 2 meaning also print the traversal order nodes after every expanded node.
root (Node | NoNode (default NoNode())) – Root node to start the traversal from. If not given, go in order of input_instance.nodes. If more connected components are present in the graph, they are also traversed in order corresponding to input_instance.nodes.
element_to_search (Node | NoNode (default NoNode())) – Element to look for in the graph. If not given, whole graph is traversed.
*args (Any) – Additional arguments passed to the algorithm.
**kwargs (Any) – Additional keyword arguments passed to the algorithm.

Returns:

result – Returns True in the first index if the element was found in the graph or if no element was given for search. Also returns a new tree graph with node order corresponding to the order of traversal.

Return type:

tuple[bool, TraversalGraph]

property space_complexity: str#

Return type:: str

property worst_case_description: str#

Return type:: str

property worst_case_time_complexity: str#

Return type:: str