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 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 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, boolean directed, NodeMap layerIDMap, int maxLayers) Returns layers of nodes constructed by a breadth first search.
static NodeList[]	getLayers(Graph graph, NodeList coreNodes, NodeMap layerIDMap) Like 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 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 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 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())

getLayers

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

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.

Parameters:

graph - the graph the bfs is running on

coreNodes - contains the nodes the bfs run starts from

directed - true: only outgoing edges are attended, false: all edges

layerIDMap - is used to store the layer depths informations in

maxLayers - number of layers that will be returned. "0" for all layers

Returns:

an array of NodeLists representing the layers

Complexity:

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