com.tensegrity.graph.model
Class GraphOperations

java.lang.Object
  com.tensegrity.graph.model.GraphOperations

public final class GraphOperations

extends java.lang.Object

Class GraphOperations provides static methods to analyze and modify a graph. Most of the methods depend on the graph algorithm package and represent convenience methods that answer a particular question about a graph. The algorithm package provides more generic algorithms which usually do more than the helper methods in this class.

If you just have a simple question about the graph then you should use this class. If you need to customize a graph algorithm, please look at the underlying algorithms located in package com.tensegrity.graph.algorithm.

Version:

$Id: GraphOperations.java,v 1.15 2005/11/25 11:18:24 KevinCVS Exp $

Author:

S. Rutz

Method Summary

static Node	findRoot(Graph graph) Returns the root node of the given graph if it is a tree and has a single root, otherwise null is returned.
static boolean	hasCycle(Graph graph) Checks whether the given directed graph has a cycle by means of topological searching.
static boolean	isBiconnected(Graph graph) Returns true if the given undirected graph consists of one biconnected component only.
static boolean	isBinaryTree(Graph graph) Checks whether the graph is a binary tree.
static boolean	isConnected(Graph graph) Finds out whether the undirected instance of the given graph is connected.
static boolean	isTree(Graph graph) Performs the full set of conditional checks to determine whether the given Graph is a tree and has at least one root.

Methods inherited from class java.lang.Object

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

Method Detail

isConnected

public static final boolean isConnected(Graph graph)

Finds out whether the undirected instance of the given graph is connected. If it is not connected then the graph has several components. Use the DFS search algorithm to find out the components. This method only gives a yes/no answer.

Parameters:

graph - the graph to investigate

Returns:

true if the undirected instance of the graph is connected.

isBiconnected

public static final boolean isBiconnected(Graph graph)

Returns true if the given undirected graph consists of one biconnected component only. Use the search algorithm implemented in class com.tensegrity.graph.alorithm.BiconnectedDFS to find out the biconnected components.

Parameters:

graph - the graph to investigate

Returns:

true if the undirected instance of the graph is biconnected.

Find more information in the class documentation

hasCycle

public static final boolean hasCycle(Graph graph)

Checks whether the given directed graph has a cycle by means of topological searching.

Parameters:

graph - the directed Graph to investigate.

Returns:

true if the directed instance of the graph has a cycle.

Find more information in the class documentation

isTree

public static final boolean isTree(Graph graph)

Performs the full set of conditional checks to determine whether the given Graph is a tree and has at least one root. A graph is a tree if the following is true:

• The graph is directed.
• The graph is strongly connected (otherwise it would be a forest).
• There is a root node with an incoming edge count of 0.
• All other nodes have an incoming edge count of 1.
• There are no cycles within the graph.

. True is returned if all tests succeed.

Parameters:

graph - the Graph to investigate.

Returns:

true if the graph is a tree.

See Also:

findRoot(Graph)

Find more information in the class documentation

isBinaryTree

public static final boolean isBinaryTree(Graph graph)

Checks whether the graph is a binary tree. The same tree-criteria as in method isTree(Graph) must be met. Additionally all non-leaf nodes of the tree must have a leaving edge degree lesser than 3.

Parameters:

graph - the graph to investigate

Returns:

true if the graph is a tree

See Also:

isTree(Graph)

Find more information in the class documentation

findRoot

public static final Node findRoot(Graph graph)

Returns the root node of the given graph if it is a tree and has a single root, otherwise null is returned. This method can be used to determine whether a graph meets one of the necessary conditions of a tree.

Parameters:

graph - the Graph to investigate

Returns:

the root node of the graph is a tree, otherwise null.

See Also:

isTree(Graph)

Find more information in the class documentation