de.ipcon.tools.graph

Class GraphTools

java.lang.Object

de.ipcon.tools.graph.GraphTools

public final class GraphTools
extends java.lang.Object

A utility class containing various static graph algorithms. This class is not meant to be instantiated.

Method Summary

Modifier and Type	Method and Description
static int	calculateLayer(DirectedGraphNodeI startNode) Calculates the "layer" or depth of a given node in a graph.
static boolean	canReachMatchingNode(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher) Checks if any node matching the criteria defined by the given matcher can be reached from the start node by traversing outgoing edges.
static boolean	containsCycle(OnlyToDirectedGraphNodeI startNode) Determines if the graph, starting from the given node, contains a cycle.
static boolean	containsCycle(OnlyToDirectedGraphNodeI startNode, java.util.List<OnlyToDirectedGraphNodeI> nodePath) Determines if the graph, starting from the given node, contains a cycle.
static java.util.List<OnlyToDirectedGraphNodeI>	findLeaves(OnlyToDirectedGraphNodeI startNode) Finds all "leaf" nodes in the graph component connected to the given start node.
static OnlyToDirectedGraphNodeI	findMatchingNode(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher) Finds and returns the first reachable node (via outgoing edges) that matches the criteria defined by the given matcher.
static java.util.Collection<GraphPath>	findPathsToMatchingNodes(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher) Finds all paths from the start node to any nodes matching the criteria defined by the given matcher, optionally filtering edges.
static java.util.Collection<GraphPath>	findPathsToMatchingNodes(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher, GraphEdgeFilterI edgeFilter) Finds all paths from the start node to any nodes matching the criteria defined by the given matcher, optionally filtering edges.
static GraphPath	findPathToMatchingNode(OnlyToDirectedGraphNodeI startNode, GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher) Finds the first path from the start node to any node matching the criteria defined by the given matcher, traversing outgoing edges.
static java.util.List<DirectedGraphNodeI>	getPathToRoot(DirectedGraphNodeI startNode) Retrieves the path from the given node up to a "root" node.

Methods inherited from class java.lang.Object

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

Method Detail

containsCycle

public static boolean containsCycle(OnlyToDirectedGraphNodeI startNode)

Determines if the graph, starting from the given node, contains a cycle.

This method performs a depth-first search (DFS) to detect cycles.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which to start looking for cycles. Cannot be null.

Returns:

true if a cycle is detected in the graph reachable from startNode, false otherwise.

Throws:

java.lang.NullPointerException - if startNode is null.

containsCycle

public static boolean containsCycle(OnlyToDirectedGraphNodeI startNode,
                                    java.util.List<OnlyToDirectedGraphNodeI> nodePath)

Determines if the graph, starting from the given node, contains a cycle.

This method performs a depth-first search (DFS) to detect cycles. The nodePath list, if provided, will be populated with the nodes forming the first cycle detected, starting from startNode up to and including the node that closes the cycle.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which to start looking for cycles. Cannot be null.

nodePath - An optional list to store the nodes forming a cycle if one is found. If null, this information is not collected. If provided, it will be modified. The list should be of a type that can accept OnlyToDirectedGraphNodeI instances.

Returns:

true if a cycle is detected in the graph reachable from startNode, false otherwise.

calculateLayer

public static int calculateLayer(DirectedGraphNodeI startNode)

Calculates the "layer" or depth of a given node in a graph.

The layer is defined as the maximum distance (number of edges) from a "root" node. A "root" node is defined as a node with no incoming edges (i.e., getFromNodes() is empty). The layer of a root node is 0.

This method recursively traverses predecessor nodes (obtained via DirectedGraphNodeI.getFromNodes()) to determine the layer. For the recursion to continue upwards from a predecessor, that predecessor node must also be an instance of DirectedGraphNodeI. If a predecessor is not a DirectedGraphNodeI, that path of ancestry cannot be explored further by this method.

Consequently, if all direct predecessors of startNode are not instances of DirectedGraphNodeI (or if startNode has no predecessors), it will be assigned a layer of 0.

Parameters:

startNode - The node (must implement DirectedGraphNodeI) for which to calculate its layer. Cannot be null.

Returns:

The layer number of the given node. Returns 0 if the node is a root or if all its direct predecessors are not instances of DirectedGraphNodeI. Returns -1 if a cycle is detected during the layer calculation.

getPathToRoot

public static java.util.List<DirectedGraphNodeI> getPathToRoot(DirectedGraphNodeI startNode)

Retrieves the path from the given node up to a "root" node. A "root" node is defined as a node with no incoming edges. The path starts with the given node and ends with the root node.

This method assumes a graph structure where paths to a root are unambiguous, specifically, it throws an IllegalArgumentException if a node with more than one predecessor (from-node) is encountered, as the "path to root" becomes ill-defined in such scenarios for this method's logic.

Parameters:

startNode - The node (must implement DirectedGraphNodeI) from which to find the path to a root. Cannot be null.

Returns:

A List of DirectedGraphNodeI nodes representing the path. The first element is startNode, and the last is a root node.

Throws:

java.lang.IllegalArgumentException - If a node with multiple predecessors is encountered, or if a cycle is detected, or if an ancestor node is not a DirectedGraphNodeI.

findLeaves

public static java.util.List<OnlyToDirectedGraphNodeI> findLeaves(OnlyToDirectedGraphNodeI startNode)

Finds all "leaf" nodes in the graph component connected to the given start node. A leaf node is defined as a node with no outgoing edges (i.e., getToNodes() is empty).

The search explores the connected component of the startNode. For the purpose of identifying all nodes within this component, edges are conceptually treated as undirected (i.e., traversal can occur via both outgoing getToNodes() and incoming getFromNodes() if the node is an instance of DirectedGraphNodeI). However, the definition of a "leaf" strictly depends on the absence of outgoing edges.

Traversal proceeds as follows:

• Forward traversal (via OnlyToDirectedGraphNodeI.getToNodes()) is always performed.
• Backward traversal (via DirectedGraphNodeI.getFromNodes()) is performed only if a visited node is an instance of DirectedGraphNodeI, allowing the exploration to move "up" the graph structure where possible.

Note: The original NetRexx implementation comment stated, "Implementation might not be optimal, but seems to work." The inclusion of backward traversal (where possible) means this method identifies leaves within the entire reachable component, not just descendants of the startNode.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which the search for leaves begins. This node serves as the entry point to the graph component to be explored. Cannot be null.

Returns:

A List of OnlyToDirectedGraphNodeI nodes that are identified as leaves within the connected component of startNode. The list will be empty if no leaves are found or if the start node itself is null (though a NullPointerException would be thrown by NullCheckTools in that case).

canReachMatchingNode

public static boolean canReachMatchingNode(OnlyToDirectedGraphNodeI startNode,
                                           GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher)

Checks if any node matching the criteria defined by the given matcher can be reached from the start node by traversing outgoing edges.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which to start searching. Cannot be null.

matcher - The GraphNodeMatcherI to use for checking if a node matches. The matcher will be applied to OnlyToDirectedGraphNodeI instances. Cannot be null.

Returns:

true if at least one matching node can be reached, false otherwise.

findMatchingNode

public static OnlyToDirectedGraphNodeI findMatchingNode(OnlyToDirectedGraphNodeI startNode,
                                                        GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher)

Finds and returns the first reachable node (via outgoing edges) that matches the criteria defined by the given matcher. The search is typically depth-first.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which to start searching. Cannot be null.

matcher - The GraphNodeMatcherI to use for checking if a node matches. The matcher will be applied to OnlyToDirectedGraphNodeI instances. Cannot be null.

Returns:

The first matching OnlyToDirectedGraphNodeI found, or null if no such node is reached.

findPathToMatchingNode

public static GraphPath findPathToMatchingNode(OnlyToDirectedGraphNodeI startNode,
                                               GraphNodeMatcherI<? super OnlyToDirectedGraphNodeI> matcher)

Finds the first path from the start node to any node matching the criteria defined by the given matcher, traversing outgoing edges.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which to start searching. Cannot be null.

matcher - The GraphNodeMatcherI to use for checking if a node matches. The matcher will be applied to OnlyToDirectedGraphNodeI instances. Cannot be null.

Returns:

A GraphPath to the first matching node found, or null if no such path exists.

findPathsToMatchingNodes

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

Finds all paths from the start node to any nodes matching the criteria defined by the given matcher, optionally filtering edges.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which to start searching. Cannot be null.

matcher - The GraphNodeMatcherI to use for checking if a node matches. The matcher will be applied to OnlyToDirectedGraphNodeI instances. Cannot be null.

Returns:

A Collection of GraphPath objects, each leading to a matching node. Returns an empty collection if no matching nodes are found.

findPathsToMatchingNodes

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

Finds all paths from the start node to any nodes matching the criteria defined by the given matcher, optionally filtering edges.

Parameters:

startNode - The node (must implement OnlyToDirectedGraphNodeI) from which to start searching. Cannot be null.

matcher - The GraphNodeMatcherI to use for checking if a node matches. The matcher will be applied to OnlyToDirectedGraphNodeI instances. Cannot be null.

edgeFilter - An optional GraphEdgeFilterI to exclude certain edges from traversal. If an edge "fits" the filter, it is excluded. Can be null if no edge filtering is needed.

Returns:

A Collection of GraphPath objects, each leading to a matching node. Returns an empty collection if no matching nodes are found.