
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.Bfs
public class Bfs
This class provides services that center around breadth first search (BFS).
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
NodeList
or with a DataProvider
that returns true
for core nodes and false
for all other nodes.
The output is given as an array of NodeList
s each of which contains the nodes of a particular layer.
Field Summary  

static byte 
DIRECTION_BOTH
An edge direction specifier for both incoming and outgoing edges. 
static byte 
DIRECTION_PREDECESSOR
An edge direction specifier for incoming edges. 
static byte 
DIRECTION_SUCCESSOR
An edge direction specifier for outgoing edges. 
Method Summary  

static NodeList[] 
getLayers(Graph graph,
DataProvider isCoreNode)
Returns the layers of nodes constructed by a breadth first search. 
static NodeList[] 
getLayers(Graph graph,
DataProvider isCoreNode,
NodeMap layerIDMap)
Returns the layers of nodes constructed by a breadth first search. 
static NodeList[] 
getLayers(Graph graph,
NodeList coreNodes)
Returns the layers of nodes calculated by a breadth first search. 
static NodeList[] 
getLayers(Graph graph,
NodeList coreNodes,
boolean directed,
NodeMap layerIDMap)
Returns the layers of nodes constructed by either a directed or undirected breadth first search. 
static NodeList[] 
getLayers(Graph graph,
NodeList coreNodes,
boolean directed,
NodeMap layerIDMap,
int maxLayers)
Returns the layers of nodes constructed by a directed/undirected breadth first search where the maximum number of layers is restricted. 
static NodeList[] 
getLayers(Graph graph,
NodeList coreNodes,
byte direction,
NodeMap layerIDMap,
int maxLayerCount)
Returns the layers of nodes constructed by a directed/undirected breadth first search where the maximum number of layers is restricted. 
static NodeList[] 
getLayers(Graph graph,
NodeList coreNodes,
NodeMap layerIDMap)
Returns the layers of nodes constructed by a breadth first search. 
Methods inherited from class java.lang.Object 

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

public static final byte DIRECTION_PREDECESSOR
getLayers(y.base.Graph, y.base.NodeList, byte, y.base.NodeMap, int)
,
Constant Field Valuespublic static final byte DIRECTION_SUCCESSOR
getLayers(y.base.Graph, y.base.NodeList, byte, y.base.NodeMap, int)
,
Constant Field Valuespublic static final byte DIRECTION_BOTH
getLayers(y.base.Graph, y.base.NodeList, byte, y.base.NodeMap, int)
,
Constant Field ValuesMethod Detail 

public static NodeList[] getLayers(Graph graph, NodeList coreNodes)
The first of these layers contains all nodes within the given NodeList
.
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
(i1)
th layer.
O(graph.N() + graph.E())
graph
 the given graphcoreNodes
 the list of core nodes from which the BFS starts
NodeList
s each of which contains the nodes of a particular layerpublic static NodeList[] getLayers(Graph graph, DataProvider isCoreNode)
The first of these layers contains all nodes for which the given DataProvider
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
(i1)
th layer.
isCoreNode.getBool(node)
defined for all nodes in graphgraph
 the given graphisCoreNode
 the DataProvider
that contains the nodes from which the BFS starts;
core nodes are marked with a true
value
NodeList
s each of which contains the nodes of a particular layerpublic static NodeList[] getLayers(Graph graph, DataProvider isCoreNode, NodeMap layerIDMap)
The first of these layers contains all nodes for which the given DataProvider
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 NodeMap
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
(i1)
th layer.
isCoreNode.getBool(node)
defined for all nodes in graphgraph
 the given graphisCoreNode
 the DataProvider
that contains the nodes from which the BFS starts;
core nodes are marked with a true
valuelayerIDMap
 the NodeMap
that will be filled during the BFS execution and holds the zerobased index of
the BFS layer to which each node belongs or 1
if the node is not reachable
NodeList
s each of which contains the nodes of a particular layerpublic static NodeList[] getLayers(Graph graph, NodeList coreNodes, NodeMap layerIDMap)
The first of these layers contains all nodes within the given NodeList
.
These nodes are the core nodes from which an undirected breadth first search to the other nodes starts.
The algorithm fills the provided NodeMap
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
(i1)
th layer.
isCoreNode.getBool(node)
defined for all nodes in graphgraph
 the given graphcoreNodes
 the list of core nodes from which the BFS startslayerIDMap
 the NodeMap
that will be filled during the BFS execution and holds the zerobased index of
the BFS layer to which each node belongs or 1
if the node is not reachable
NodeList
s each of which contains the nodes of a particular layerpublic static NodeList[] getLayers(Graph graph, NodeList coreNodes, boolean directed, NodeMap layerIDMap)
The first of these layers contains all nodes within the given NodeList
.
These nodes are the core nodes from which a directed/undirected breadth first search to the other
nodes starts.
The algorithm fills the provided NodeMap
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
(i1)
th layer.
O(graph.N() + graph.E())
graph
 the given graphcoreNodes
 the list of core nodes from which the BFS startsdirected
 true
if the graph should be considered directed, false
otherwiselayerIDMap
 the NodeMap
that will be filled during the BFS execution and holds the zerobased index of
the BFS layer to which each node belongs or 1
if the node is not reachable
NodeList
s each of which contains the nodes of a particular layerpublic static NodeList[] getLayers(Graph graph, NodeList coreNodes, boolean directed, NodeMap layerIDMap, int maxLayers)
The first of these layers contains all nodes within the given NodeList
.
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 NodeMap
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
(i1)
th layer.
NodeList
may only contain a subset of nodes
(i.e., only those with layer <= max layer).O(graph.N() + graph.E())
graph
 the given graphcoreNodes
 the list of core nodes from which the BFS startsdirected
 true
if the graph should be considered directed, false
otherwiselayerIDMap
 the NodeMap
that will be filled during the BFS execution and holds the zerobased index of
the BFS layer to which each node belongs or 1
if the node is not reachablemaxLayers
 the number of layers that will be returned or 0
if all layers are required
NodeList
s each of which contains the nodes of a particular layerpublic static NodeList[] getLayers(Graph graph, NodeList coreNodes, byte direction, NodeMap layerIDMap, int maxLayerCount)
The first of these layers contains all nodes within the given NodeList
.
These nodes are the core nodes from which a breadth first search to the other nodes starts.
The algorithm fills the provided NodeMap
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
(i1)
th layer.
NodeList
may only contain a subset of nodes
(i.e., only those with layer index < max layer count).O(graph.N() + graph.E())
graph
 the given graphcoreNodes
 the list of core nodesdirection
 one of the predefined direction specifierslayerIDMap
 the NodeMap
that will be filled during the BFS execution and holds the zerobased index of
the BFS layer to which each node belongs or 1
if the node is not reachablemaxLayerCount
 the maximum number of layers that will be returned or 0
if all layers are required
NodeList
s each of which contains the nodes of a particular layer
java.lang.IllegalArgumentException
 if the given direction is not supported

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 