unbbayes.util.dseparation.impl
Class MSeparationUtility

java.lang.Object
  unbbayes.util.dseparation.impl.MSeparationUtility

All Implemented Interfaces:

IDSeparationUtility

Direct Known Subclasses:

MSeparationUtilityIncludingSeparators

public class MSeparationUtility
extends Object
implements IDSeparationUtility

Author:

Shou Matsumoto Checks d-separation criterion using moral separation (m-separation) criterion, proposed by Lauritzen, Dawid, Larsen and Leimer (1990), which is proven to be equivalent to d-separation criteria. Basic steps (given sets X, Y and the separator S): 1 - generate a graph containing only X, Y, Z and their ancestors. 2 - turn the graph moral (connect/marry nodes having a common child) 3 - eliminate edge orientation 4 - if every single path connecting X to Y is blocked by S, then S d-separates X to Y

Nested Class Summary

class

MSeparationUtility.MSeparationUtilityNodeVisitor Visitor Pattern.

Constructor Summary

protected

MSeparationUtility() Default constructor.

Method Summary

Map<INode,Set<INode>>	buildClosedAdjacentNodeMap(Set<INode> allKeys) Builds a map containing a temporally reference to all adjacent nodes, given a key node.
Set<INode>	getAllAncestors(Set<INode> nodes) Method to get all ancestors of a given set of nodes.
protected Set<INode>	getAllAncestors(Set<INode> nodes, Set<INode> nodesToStop) Method to get all ancestors of a given set of nodes.
Set<INode>	getAllDescendants(Set<INode> nodes) Method to get all descendants of a given set of nodes.
protected Set<INode>	getAllDescendants(Set<INode> nodes, Set<INode> nodesToStop, MSeparationUtility.MSeparationUtilityNodeVisitor visitor) Method to get all descendants of a given set of nodes.
Set<INode>	getAllDSeparatedNodes(Set<INode> consideredNodes, Set<INode> from, Set<INode> separators) Obtains all nodes within graph which is d-separated from the set "from" given the separators.
Set<List<INode>>	getRoutes(INode from, INode to) Obtains a set of path/routes between two nodes, including themselves.
Set<List<INode>>	getRoutes(INode from, INode to, Map<INode,Set<INode>> closedAdjacentNodeMap) Obtains a set of path/routes between two nodes, including themselves.
Set<List<INode>>	getRoutes(INode from, INode to, Map<INode,Set<INode>> closedAdjacentNodeMap, Set<INode> nodesNotToContain, int maxRoutes) Obtains a set of path/routes between two nodes, including themselves.
Set<List<INode>>	getRoutes(INode from, Set<INode> setTo, Map<INode,Set<INode>> closedAdjacentNodeMap, Set<INode> nodesNotToContain, int maxRoutes) Obtains a set of path/routes between two nodes, including themselves.
boolean	isDSeparated(Set<INode> consideredNodes, Set<INode> from, Set<INode> to, Set<INode> separators) Checks if the nodes within "from" are m-separated from nodes from "to", given a set of "separators".
Map<INode,Set<INode>>	makeItMoral(Map<INode,Set<INode>> closedAdjacentNodeMap) If a node has a common child, make them adjacent (marry them - this is something moral).
static MSeparationUtility	newInstance() Default constructor method.

Methods inherited from class java.lang.Object

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

Constructor Detail

MSeparationUtility

protected MSeparationUtility()

Default constructor. It's protected in order to simplify inheritance.

Method Detail

newInstance

public static MSeparationUtility newInstance()

Default constructor method.

Returns:

a new instance of MSeparationutility

buildClosedAdjacentNodeMap

public Map<INode,Set<INode>> buildClosedAdjacentNodeMap(Set<INode> allKeys)

Builds a map containing a temporally reference to all adjacent nodes, given a key node. It is used to represent a undirected graph. Mapping model: node (key) --<>--> set of all adjacent nodes obtained by Node#getAdjacents() It also guarantees that the map is "closed" (destination nodes are also keys). I.E. if "key" is mapped to "node", then "node" must be a key in this map too. It does not go down/up recursively (so that it guarantees only the nodes within the parameter is mapped).

Parameters:

allKeys -

See Also:

Node#getAdjacents()}, Node#makeAdjacents()}

makeItMoral

public Map<INode,Set<INode>> makeItMoral(Map<INode,Set<INode>> closedAdjacentNodeMap)

If a node has a common child, make them adjacent (marry them - this is something moral). It also guarantees that the map is "closed" (destination nodes are also keys). I.E. if "key" is mapped to "node", then "node" must be a key in this map too.

Parameters:

closedAdjacentNodeMap - : OBS. in/out parameter.

Returns:

same as closedAdjacentNodeMap

getRoutes

public Set<List<INode>> getRoutes(INode from,
                                  INode to,
                                  Map<INode,Set<INode>> closedAdjacentNodeMap,
                                  Set<INode> nodesNotToContain,
                                  int maxRoutes)

Obtains a set of path/routes between two nodes, including themselves. Cycles and auto-relationships are not counted as new routes.

Parameters:

from - : a node to start from

to - : a destination node

closedAdjacentNodeMap - : a map indicating all node's adjacency.

nodesNotToContain - : nodes that a returned path should not contain. The algorithm will ignore a path if it contains any node within it. If set to null, this method will start using INode#getChildren() to build a directed path.

maxRoutes - : maximum number of routes to obtain.

Returns:

: a set of all path from "from" to "to". The path is represented as a list containing all nodes included in the path. Since it is a list, it stores the visit order as well.

getRoutes

public Set<List<INode>> getRoutes(INode from,
                                  Set<INode> setTo,
                                  Map<INode,Set<INode>> closedAdjacentNodeMap,
                                  Set<INode> nodesNotToContain,
                                  int maxRoutes)

Obtains a set of path/routes between two nodes, including themselves. Cycles are not counted as new routes.

Parameters:

from - : a node to start from

setTo - : a set of possible destination node. A returning path will contain (only) one node within setTo at the end of path.

closedAdjacentNodeMap - : a map indicating all node's adjacency. If set to null, this method will start using INode#getChildren() to build a directed path.

nodesNotToContain - : nodes that a returned path should not contain. The algorithm will ignore a path if it contains any node within it.

maxRoutes - : maximum number of routes to obtain.

Returns:

: a set of all path from "from" to "to". The path is represented as a list containing all nodes included in the path. Since it is a list, it stores the visit order as well.

getRoutes

public Set<List<INode>> getRoutes(INode from,
                                  INode to,
                                  Map<INode,Set<INode>> closedAdjacentNodeMap)

Obtains a set of path/routes between two nodes, including themselves. Cycles are not counted as new routes. This is equals to #getRoutesRec(INode, INode, Map, List, null)

Parameters:

from - : a node to start from

to - : a destination node

closedAdjacentNodeMap - : a map indicating all node's adjacency. a path if it contains any node within it. If set to null, this method will start using INode#getChildren() to build a directed path.

Returns:

: a set of all path from "from" to "to". The path is represented as a list containing all nodes included in the path. Since it is a list, it stores the visit order as well.

getRoutes

public Set<List<INode>> getRoutes(INode from,
                                  INode to)

Obtains a set of path/routes between two nodes, including themselves. This is the same as calling getRoutes(INode, INode, Map) setting the Map as null. Cycles are not counted as new routes.

Parameters:

from - : a node to start from

to - : a destination node If set to null, this method will start using INode#getChildren() to build a directed path.

Returns:

: a set of all path from "from" to "to". The path is represented as a list containing all nodes included in the path. Since it is a list, it stores the visit order as well.

See Also:

getRoutes(INode, INode, Map)

getAllAncestors

public Set<INode> getAllAncestors(Set<INode> nodes)

Method to get all ancestors of a given set of nodes. It is equivalent to #getAllAncestors(Set, null)

Parameters:

nodes - : nodes to be analyzed.

Returns:

: a set of nodes

See Also:

getAllAncestors(Set, Set)

getAllAncestors

protected Set<INode> getAllAncestors(Set<INode> nodes,
                                     Set<INode> nodesToStop)

Method to get all ancestors of a given set of nodes.

Parameters:

nodes - : nodes to be analyzed.

nodesToStop - : the recursive search for further ancestors will stop if any of those nodes are detected as direct ancestor. Only the current recursion will stop, so, only the nodes which are exclusively ancestors of nodesToStop will be ignored.

Returns:

: a set of nodes not including nodesToStop and their unique ancestors (nodes which are ancestors of only nodesToStop)

getAllDescendants

public Set<INode> getAllDescendants(Set<INode> nodes)

Method to get all descendants of a given set of nodes.

Parameters:

nodes - : nodes to be analyzed.

Returns:

: a set of nodes not including nodesToStop and their unique descendants (nodes which are descendants of only nodesToStop)

getAllDescendants

protected Set<INode> getAllDescendants(Set<INode> nodes,
                                       Set<INode> nodesToStop,
                                       MSeparationUtility.MSeparationUtilityNodeVisitor visitor)

Method to get all descendants of a given set of nodes.

Parameters:

nodes - : nodes to be analyzed.

nodesToStop - : the recursive search for further descendants will stop if any of those nodes are detected. Only the current recursion will stop, so, only the nodes which are exclusively descendants of nodesToStop will be ignored. Using null to this param will make this method to find all descendants

visitor - : visitor to be executed when any of nodesToStop is detected. A node inside nodesToStop will be passed as argument and its return will be added to return. Set it to null if nothing must be done.

Returns:

: a set of nodes not including nodesToStop and their unique descendants (nodes which are descendants of only nodesToStop)

isDSeparated

public boolean isDSeparated(Set<INode> consideredNodes,
                            Set<INode> from,
                            Set<INode> to,
                            Set<INode> separators)

Checks if the nodes within "from" are m-separated from nodes from "to", given a set of "separators". Lauritzen, Dawid, Larsen and Leimer (1990), says that m-separation is equivalent to d-separation.

Specified by:

isDSeparated in interface IDSeparationUtility

Parameters:

graph - : NOT USED BY THIS IMPLEMENTATION (since it uses only the parents/children of the nodes)

from - : set 1 of nodes which m-separation is going to be tested

to - : set 2 of nodes which m-separation is going to be tested

separators - : set of separators.

Returns:

: true if "from" is m-separated with "to" given "separators". False otherwise.

getAllDSeparatedNodes

public Set<INode> getAllDSeparatedNodes(Set<INode> consideredNodes,
                                        Set<INode> from,
                                        Set<INode> separators)

Description copied from interface: IDSeparationUtility

Obtains all nodes within graph which is d-separated from the set "from" given the separators.

Specified by:

getAllDSeparatedNodes in interface IDSeparationUtility

Parameters:

consideredNodes - : nodes to be tested. They must reside in the same network containing the nodes within from, and separators sets.

from - set of nodes which d-separation is going to be tested

separators - : set of separators.

Returns:

set of all d-separated nodes within graph