org.biopax.paxtools.query.algorithm

Class BFS

java.lang.Object

org.biopax.paxtools.query.algorithm.BFS

Direct Known Subclasses:

CycleBreaker

public class BFS
extends Object

Implements breadth-first search. Takes a set of source nodes, distance limit and labels nodes towards one direction, with their breadth distances.

Author:

Ozgun Babur, Merve Cakir

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	BACKWARD Backward traversal direction.
static int	BLACK Color black indicates that the node was processed.
protected Map<GraphObject,Integer>	colors Color labels.
protected Direction	direction Whether the direction is FORWARD, it is REVERSE otherwise.
protected Map<GraphObject,Integer>	dist Distance labels.
static boolean	DOWNWARD Backward traversal direction.
static boolean	FORWARD Forward traversal direction.
static int	GRAY Color gray indicates that the node is in queue waiting to be procecessed.
protected int	limit Stop distance.
protected LinkedList<Node>	queue BFS queue.
protected Set<Node>	sourceSet BFS starts from source nodes.
protected Set<Node>	stopSet BFS will not further traverse neighbors of any node in the stopSet.
static boolean	UPWARD Forward traversal direction.
static int	WHITE Color white indicates the node is not processed.

Constructor Summary

Constructors

Constructor and Description
BFS() Empty constructor for other possible uses.
BFS(Set<Node> sourceSet, Set<Node> stopSet, Direction direction, int limit) Constructor with all parameters.

Method Summary

Modifier and Type	Method and Description
protected int	getColor(Node node) Gets color tag of the node
int	getLabel(GraphObject go) Gets the distance label of the object.
protected void	initMaps() Initializes maps used during query.
protected boolean	isEquivalentInTheSet(Node node, boolean direction, Set<Node> set) Checks if an equivalent of the given node is in the set.
protected boolean	isEquivalentInTheSet(Node node, Set<Node> set) Checks if an equivalent of the given node is in the set.
protected void	labelEquivRecursive(Node node, boolean up, int dist, boolean enqueue, boolean head) Labels equivalent nodes recursively.
protected void	processNode(Node current) Processes a node.
Map<GraphObject,Integer>	run() Executes the algorithm.
protected void	setColor(Node node, int color) Sets color tag
protected void	setLabel(GraphObject go, int label) Sets the distance label.

Methods inherited from class java.lang.Object

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

Field Detail

dist

protected Map<GraphObject,Integer> dist

Distance labels. Missing label interpreted as infinitive.

colors

protected Map<GraphObject,Integer> colors

Color labels. Missing color interpreted as white.

sourceSet

protected Set<Node> sourceSet

BFS starts from source nodes. They get the label 0.

stopSet

protected Set<Node> stopSet

BFS will not further traverse neighbors of any node in the stopSet.

direction

protected Direction direction

Whether the direction is FORWARD, it is REVERSE otherwise.

limit

protected int limit

Stop distance.

queue

protected LinkedList<Node> queue

BFS queue.

FORWARD

public static final boolean FORWARD

Forward traversal direction.

See Also:

Constant Field Values

BACKWARD

public static final boolean BACKWARD

Backward traversal direction.

See Also:

Constant Field Values

UPWARD

public static final boolean UPWARD

Forward traversal direction.

See Also:

Constant Field Values

DOWNWARD

public static final boolean DOWNWARD

Backward traversal direction.

See Also:

Constant Field Values

WHITE

public static final int WHITE

Color white indicates the node is not processed.

See Also:

Constant Field Values

GRAY

public static final int GRAY

Color gray indicates that the node is in queue waiting to be procecessed.

See Also:

Constant Field Values

BLACK

public static final int BLACK

Color black indicates that the node was processed.

See Also:

Constant Field Values

Constructor Detail

BFS

public BFS(Set<Node> sourceSet,
           Set<Node> stopSet,
           Direction direction,
           int limit)

Constructor with all parameters.

Parameters:

sourceSet - Seed of BFS

stopSet - Nodes that won't be traversed

direction - Direction of the traversal

limit - Distance limit

BFS

public BFS()

Empty constructor for other possible uses.

Method Detail

run

public Map<GraphObject,Integer> run()

Executes the algorithm.

Returns:

BFS tree

initMaps

protected void initMaps()

Initializes maps used during query.

processNode

protected void processNode(Node current)

Processes a node.

Parameters:

current - The current node

labelEquivRecursive

protected void labelEquivRecursive(Node node,
                                   boolean up,
                                   int dist,
                                   boolean enqueue,
                                   boolean head)

Labels equivalent nodes recursively.

Parameters:

node - Node to label equivalents

up - Traversing direction. Up means towards parents, if false then towards children

dist - The label

enqueue - Whether to enqueue equivalents

head - Where to enqueue. Head or tail.

isEquivalentInTheSet

protected boolean isEquivalentInTheSet(Node node,
                                       Set<Node> set)

Checks if an equivalent of the given node is in the set.

Parameters:

node - Node to check equivalents

set - Node set

Returns:

true if an equivalent is in the set

isEquivalentInTheSet

protected boolean isEquivalentInTheSet(Node node,
                                       boolean direction,
                                       Set<Node> set)

Checks if an equivalent of the given node is in the set.

Parameters:

node - Node to check equivalents

direction - Direction to go to get equivalents

set - Node set

Returns:

true if an equivalent is in the set

getColor

protected int getColor(Node node)

Gets color tag of the node

Parameters:

node - Node to get color tag

Returns:

color tag

setColor

protected void setColor(Node node,
                        int color)

Sets color tag

Parameters:

node - node to set color tag

color - the color tag

getLabel

public int getLabel(GraphObject go)

Gets the distance label of the object.

Parameters:

go - object to get the distance

Returns:

the distance label

setLabel

protected void setLabel(GraphObject go,
                        int label)

Sets the distance label.

Parameters:

go - object to set the distance label

label - the distance label