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)

Field Summary

static byte	DIRECTION_BOTH Edge direction specifier for both incoming and outgoing edges.
static byte	DIRECTION_PREDECESSOR Edge direction specifier for incoming edges.
static byte	DIRECTION_SUCCESSOR Edge direction specifier for outgoing edges.

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, byte direction, 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

Field Detail

DIRECTION_PREDECESSOR

public static final byte DIRECTION_PREDECESSOR

Edge direction specifier for incoming edges.

See Also:

getLayers(y.base.Graph, y.base.NodeList, byte, y.base.NodeMap, int), Constant Field Values

DIRECTION_SUCCESSOR

public static final byte DIRECTION_SUCCESSOR

Edge direction specifier for outgoing edges.

See Also:

getLayers(y.base.Graph, y.base.NodeList, byte, y.base.NodeMap, int), Constant Field Values

DIRECTION_BOTH

public static final byte DIRECTION_BOTH

Edge direction specifier for both incoming and outgoing edges.

See Also:

getLayers(y.base.Graph, y.base.NodeList, byte, y.base.NodeMap, int), Constant Field Values

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 information 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())

getLayers

public static NodeList[] getLayers(Graph graph,
                                   NodeList coreNodes,
                                   byte direction,
                                   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

direction - specifies which edges to follow. One of

• DIRECTION_PREDECESSOR,
• DIRECTION_SUCCESSOR, or
• DIRECTION_BOTH

layerIDMap - is used to store the layer depths information 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())