BfsAlgorithm

This class provides services that center around breadth first search (BFS).

Inheritance Hierarchy

BfsAlgorithm

Remarks

Note: Methods of this class work with instances of Graph. To run a breadth-first search on IGraph instances use Bfs instead.

Breadth first search starts at a given set of nodes and explores the neighboring nodes first, before visiting the next level neighbors.

A breadth first search run can be either directed or undirected. All methods require a list of nodes that are considered as the core nodes from which the breadth first search starts. These nodes can be identified either with a YNodeList or with a IDataProvider that returns true for core nodes and false for all other nodes. The output is given as an array of YNodeLists each of which contains the nodes of a particular layer.

Example for a BFS run. The marked node is the core node from which BFS starts while node labels indicate the resulting layers.

Type Details

yfiles module: algorithms
yfiles-umd modules: All layout modules, view-layout-bridge
Legacy UMD name: yfiles.algorithms.Bfs

Static Methods

getLayers

(graph: Graph, coreNodes: YNodeList) : YNodeList

Returns the layers of nodes calculated by a breadth first search.

Remarks

Note: This method works with instances of Graph. To run a breadth-first search on IGraph instances use Bfs instead.

The first of these layers contains all nodes within the given YNodeList. These nodes are the core nodes from which an undirected breadth first search to the other nodes starts.

In the i-th layer are previously unassigned nodes that are connected to nodes in the (i-1)-th layer.

Complexity

O(graph.N() + graph.E())

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the given graph
coreNodes - YNodeList: the list of core nodes from which the BFS starts

Returns

↪YNodeList[]: an array of YNodeLists each of which contains the nodes of a particular layer

getLayers

(graph: Graph, isCoreNode: IDataProvider) : YNodeList

Returns the layers of nodes constructed by a breadth first search.

Remarks

Note: This method works with instances of Graph. To run a breadth-first search on IGraph instances use Bfs instead.

The first of these layers contains all nodes for which the given IDataProvider returns true. These nodes are the core nodes from which an undirected breadth first search to the other nodes starts.

In the i-th layer are previously unassigned nodes that are connected to nodes in the (i-1)-th layer.

Preconditions

isCoreNode.getBool(node) defined for all nodes in graph

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the given graph

isCoreNode - IDataProvider

the IDataProvider that contains the nodes from which the BFS starts; core nodes are marked with a true value

Domain	YNode
Values	boolean	`true` if the node is a core node, `false` otherwise

Returns

↪YNodeList[]: an array of YNodeLists each of which contains the nodes of a particular layer

getLayers

(graph: Graph, isCoreNode: IDataProvider, layerIDMap: INodeMap) : YNodeList

Returns the layers of nodes constructed by a breadth first search.

Remarks

Note: This method works with instances of Graph. To run a breadth-first search on IGraph instances use Bfs instead.

The first of these layers contains all nodes for which the given IDataProvider returns true. These nodes are the core nodes from which an undirected breadth first search to the other nodes starts. The algorithm fills the provided INodeMap with an integer indicating the layer of each node.

In the i-th layer are previously unassigned nodes that are connected to nodes in the (i-1)-th layer.

Preconditions

isCoreNode.getBool(node) defined for all nodes in graph

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the given graph

isCoreNode - IDataProvider

the IDataProvider that contains the nodes from which the BFS starts; core nodes are marked with a true value

Domain	YNode
Values	boolean	`true` if the node is a core node, `false` otherwise

layerIDMap - INodeMap

the INodeMap that will be filled during the BFS execution and holds the zero-based index of the BFS layer to which each node belongs or -1 if the node is not reachable

Domain	YNode
Values	number	the zero-based index of the BFS layer to which each node belongs or `-1` if the node is not reachable

Returns

↪YNodeList[]: an array of YNodeLists each of which contains the nodes of a particular layer

getLayers

(graph: Graph, coreNodes: YNodeList, layerIDMap: INodeMap) : YNodeList

Returns the layers of nodes constructed by a breadth first search.

Remarks

Note: This method works with instances of Graph. To run a breadth-first search on IGraph instances use Bfs instead.

The first of these layers contains all nodes within the given YNodeList. These nodes are the core nodes from which an undirected breadth first search to the other nodes starts. The algorithm fills the provided INodeMap with an integer indicating the layer of each node.

In the i-th layer are previously unassigned nodes that are connected to nodes in the (i-1)-th layer.

Preconditions

isCoreNode.getBool(node) defined for all nodes in graph

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the given graph

coreNodes - YNodeList

the list of core nodes from which the BFS starts

layerIDMap - INodeMap

the INodeMap that will be filled during the BFS execution and holds the zero-based index of the BFS layer to which each node belongs or -1 if the node is not reachable

Domain	YNode
Values	number	the zero-based index of the BFS layer to which each node belongs or `-1` if the node is not reachable

Returns

↪YNodeList[]: an array of YNodeLists each of which contains the nodes of a particular layer

getLayers

(graph: Graph, coreNodes: YNodeList, directed: boolean, layerIDMap: INodeMap, maxLayers?: number) : YNodeList

Returns the layers of nodes constructed by a directed/undirected breadth first search where the maximum number of layers is restricted.

Remarks

Note: This method works with instances of Graph. To run a breadth-first search on IGraph instances use Bfs instead.

The first of these layers contains all nodes within the given YNodeList. These nodes are the core nodes from which either a directed or undirected breadth first search to the other nodes starts. The algorithm fills the provided INodeMap with an integer indicating the layer of each node.

In the i-th layer are previously unassigned nodes that are connected to nodes in the (i-1)-th layer.

Complexity

O(graph.N() + graph.E())

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the given graph

coreNodes - YNodeList

the list of core nodes from which the BFS starts

directed - boolean

true if the graph should be considered directed, false otherwise

layerIDMap - INodeMap

the INodeMap that will be filled during the BFS execution and holds the zero-based index of the BFS layer to which each node belongs or -1 if the node is not reachable

Domain	YNode
Values	number	the zero-based index of the BFS layer to which each node belongs or `-1` if the node is not reachable

maxLayers - number

the number of layers that will be returned or 0 if all layers are required

Returns

↪YNodeList[]: an array of YNodeLists each of which contains the nodes of a particular layer

If the number of layers is restricted, the returned YNodeList may only contain a subset of nodes (i.e., only those with layer <= max layer).

getLayers

(graph: Graph, coreNodes: YNodeList, direction: BfsDirection, layerIDMap: INodeMap, maxLayerCount?: number) : YNodeList

Returns the layers of nodes constructed by a directed/undirected breadth first search where the maximum number of layers is restricted.

Remarks

Note: This method works with instances of Graph. To run a breadth-first search on IGraph instances use Bfs instead.

The first of these layers contains all nodes within the given YNodeList. These nodes are the core nodes from which a breadth first search to the other nodes starts. The algorithm fills the provided INodeMap with an integer indicating the layer index of each node (all core nodes have layer index 0).

In the i-th layer are previously unassigned nodes that are connected to nodes in the (i-1)-th layer.

Complexity

O(graph.N() + graph.E())

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the given graph

coreNodes - YNodeList

the list of core nodes

direction - BfsDirection

one of the predefined direction specifiers

layerIDMap - INodeMap

the INodeMap that will be filled during the BFS execution and holds the zero-based index of the BFS layer to which each node belongs or -1 if the node is not reachable

Domain	YNode
Values	number	the zero-based index of the BFS layer to which each node belongs or `-1` if the node is not reachable

maxLayerCount - number

the maximum number of layers that will be returned or 0 if all layers are required

Returns

↪YNodeList[]: an array of YNodeLists each of which contains the nodes of a particular layer

Throws

Exception({ name: 'ArgumentError' }): if the given direction is not supported

If the number of layers is restricted, the returned YNodeList may only contain a subset of nodes (i.e., only those with layer index < max layer count).