de.ipcon.tools.graph

Class GraphTools

java.lang.Object

de.ipcon.tools.graph.GraphTools

public class GraphTools
extends java.lang.Object

Yet another collection of Graph algorithms.

Method Summary

Modifier and Type	Method and Description
static int	calculateLayer(DirectedGraphNodeI _dgn) Determines the "depth" or layer that the given node is in.
static int	calculateLayer(DirectedGraphNodeI _dgn, java.util.Set _setVisited)
static boolean	canReachMatchingNode(OnlyToDirectedGraphNodeI _dgn, GraphNodeMatcherI _gnm) Checks if any node matching the criteria defined by the given GraphNodeMatcherI can be reached from the given node.
static boolean	containsCycle(OnlyToDirectedGraphNodeI _dgn) Determines if the graph that the given node is part of contains a cycle.
static boolean	containsCycle(OnlyToDirectedGraphNodeI _dgn, java.util.List _listNodePath)
static boolean	containsCycle(OnlyToDirectedGraphNodeI _dgn, java.util.List _listNodePath, java.util.Set _setVisited)
static java.util.List	findLeaves(DirectedGraphNodeI _dgn) Finds and returns all the leaves of the graph the given DirectedGraphNodeI belongs too.
static java.util.List	findLeaves(DirectedGraphNodeI _dgn, java.util.List _listLeaves)
static java.util.List	findLeaves(DirectedGraphNodeI _dgn, java.util.List _listLeaves, java.util.Set _setVisited)
static OnlyToDirectedGraphNodeI	findMatchingNode(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI matcher) Checks if any node matching the criteria defined by the given GraphNodeMatcherI can be reached from the given node and returns the first such node.
static java.util.Collection<GraphPath>	findPathsToMatchingNodes(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI matcher)
static java.util.Collection<GraphPath>	findPathsToMatchingNodes(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI matcher, GraphEdgeFilterI edgeFilter)
static GraphPath	findPathToMatchingNode(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI matcher)
static java.util.List	getPathToRoot(DirectedGraphNodeI _dgn) Get all nodes, including the given node itself, lying on path to the "root" of the graph where the "root" is defined as the first node reached that does not have any incoming edges (no "from" nodes)
static java.util.List	getPathToRoot(DirectedGraphNodeI _dgn, IndexedHashSet _path)

Methods inherited from class java.lang.Object

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

Method Detail

containsCycle

public static boolean containsCycle(OnlyToDirectedGraphNodeI _dgn)

Determines if the graph that the given node is part of contains a cycle.

Parameters:

_dgn - the OnlyToDirectedGraphNodeI from which to start looking for cycles

_listNodePath - a java.util.List that will contain the nodes that form a cycle, if any is found. Can be left null if this info is not required.

_setVisited - Leave this to null, will be set internally in recursive calls to this method.

Returns:

true if the graph containing the given OnlyToDirectedGraphNodeI contains a cycle, false if not.

containsCycle

public static boolean containsCycle(OnlyToDirectedGraphNodeI _dgn,
                                    java.util.List _listNodePath)

containsCycle

public static boolean containsCycle(OnlyToDirectedGraphNodeI _dgn,
                                    java.util.List _listNodePath,
                                    java.util.Set _setVisited)

calculateLayer

public static int calculateLayer(DirectedGraphNodeI _dgn)

Determines the "depth" or layer that the given node is in. Layer is defined as the maximum distance (number of edges) of the given DirectedGraphNodeI from the "root" of the graph where the "root" is defined as the first node reached that does not have any incoming edges (no "from" nodes).

Parameters:

_dgn - the DirectedGraphNodeI for which to calculate its layer

_setVisited - Leave this to null, will be set internally in recursive calls to this method.

Returns:

the layer number of the given node or -1 if the graph containing the given DirectedGraphNodeI contains a cycle.

calculateLayer

public static int calculateLayer(DirectedGraphNodeI _dgn,
                                 java.util.Set _setVisited)

getPathToRoot

public static java.util.List getPathToRoot(DirectedGraphNodeI _dgn)

Get all nodes, including the given node itself, lying on path to the "root" of the graph where the "root" is defined as the first node reached that does not have any incoming edges (no "from" nodes)

Parameters:

_dgn - the node for which the path to the root should be determined

_path - an IndexedHashSet that is filled with the visited nodes; leave to null, a set will be created automatically.

Returns:

a java.util.List containing the nodes from the given node to the root, starting with the given node and having the root node as the last element

Throws:

java.lang.IllegalArgumentException - if a node with more than one parent (from nodes) is reached since the semantics for path from root are not clearly defined for such graphs.

getPathToRoot

public static java.util.List getPathToRoot(DirectedGraphNodeI _dgn,
                                           IndexedHashSet _path)

findLeaves

public static java.util.List findLeaves(DirectedGraphNodeI _dgn)

Finds and returns all the leaves of the graph the given DirectedGraphNodeI belongs too. Leaves are defined as nodes that have no outgoing edges, that is no "to" nodes.

Parameters:

_dgn - the DirectedGraphNodeI from which the search shall start

_listLeaves - a java.util.List in which the found leaves will be collected; leave this as null, a new list will be created automatically then.

_setVisited - Leave this to null, will be set internally in recursive calls to this method.

Returns:

the list of leaves found

findLeaves

public static java.util.List findLeaves(DirectedGraphNodeI _dgn,
                                        java.util.List _listLeaves)

findLeaves

public static java.util.List findLeaves(DirectedGraphNodeI _dgn,
                                        java.util.List _listLeaves,
                                        java.util.Set _setVisited)

canReachMatchingNode

public static boolean canReachMatchingNode(OnlyToDirectedGraphNodeI _dgn,
                                           GraphNodeMatcherI _gnm)

Checks if any node matching the criteria defined by the given GraphNodeMatcherI can be reached from the given node.

Parameters:

_dgn - the OnlyToDirectedGraphNodeI from which to start looking for matching (to) nodes.

_gnm - the GraphNodeMatcherI to use for checking if a node matches.

Returns:

true if at least one matching node can be reached from _dgn; false otherwise.

findMatchingNode

public static OnlyToDirectedGraphNodeI findMatchingNode(OnlyToDirectedGraphNodeI startNode,
                                                        GraphNodeMatcherI matcher)

Checks if any node matching the criteria defined by the given GraphNodeMatcherI can be reached from the given node and returns the first such node.

Parameters:

_dgn - the OnlyToDirectedGraphNodeI from which to start looking for matching (to) nodes.

_gnm - the GraphNodeMatcherI to use for checking if a node matches.

Returns:

the first node found matching the criteria of the given GraphNodeMatcherI or null if no such node could be found in the graph.

findPathToMatchingNode

public static GraphPath findPathToMatchingNode(OnlyToDirectedGraphNodeI startNode,
                                               GraphNodeMatcherI matcher)

findPathsToMatchingNodes

public static java.util.Collection<GraphPath> findPathsToMatchingNodes(OnlyToDirectedGraphNodeI startNode,
                                                                       GraphNodeMatcherI matcher)

findPathsToMatchingNodes

public static java.util.Collection<GraphPath> findPathsToMatchingNodes(OnlyToDirectedGraphNodeI startNode,
                                                                       GraphNodeMatcherI matcher,
                                                                       GraphEdgeFilterI edgeFilter)