y.algo
Class Bfs

java.lang.Object
  |
  +--y.algo.Bfs

public class Bfs

extends Object

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

Constructor Summary

Bfs()

Method Summary

static NodeList[]	getLayers(Graph graph, DataProvider isCoreNode) Like Bfs.getLayers(Graph,NodeList), but this time the core nodes are identified by a boolean predicate.
static NodeList[]	getLayers(Graph graph, DataProvider isCoreNode, NodeMap layerIDMap) Like Bfs.getLayers(Graph,DataProvider).
static NodeList[]	getLayers(Graph graph, NodeList coreNodes) Returns layers of nodes constructed by a breadth first search.
static NodeList[]	getLayers(Graph graph, NodeList coreNodes, boolean directed, NodeMap layerIDMap) Returns layers of nodes constructed by a breadth first search.
static NodeList[]	getLayers(Graph graph, NodeList coreNodes, NodeMap layerIDMap) Like Bfs.getLayers(Graph,NodeList).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Bfs

public Bfs()

Method Detail

getLayers

public static NodeList[] getLayers(Graph graph,
                                   NodeList coreNodes)

Returns layers of nodes constructed by a breadth first search. The first of these layers contains all nodes within the given NodeList. These nodes are the core nodes from where an undirected breath 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())

getLayers

public static NodeList[] getLayers(Graph graph,
                                   DataProvider isCoreNode)

Like Bfs.getLayers(Graph,NodeList), but this time the core nodes are identified by a boolean predicate.

Precondition:

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

getLayers

public static NodeList[] getLayers(Graph graph,
                                   DataProvider isCoreNode,
                                   NodeMap layerIDMap)

Like Bfs.getLayers(Graph,DataProvider). Additionally the provided node map will be filled with integers that hold the layer number for each node.

getLayers

public static NodeList[] getLayers(Graph graph,
                                   NodeList coreNodes,
                                   NodeMap layerIDMap)

Like Bfs.getLayers(Graph,NodeList). Additionally the provided node map will be filled with integers that hold the layer number for each node.

getLayers

public static NodeList[] getLayers(Graph graph,
                                   NodeList coreNodes,
                                   boolean directed,
                                   NodeMap layerIDMap)

Returns layers of nodes constructed by a breadth first search. The first of these layers contains all nodes within the given NodeList. These nodes are the core nodes from where either a directed or undirected breath first search to the other nodes starts.

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

Complexity:

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