mapss.dif.graph
Class Graphs

java.lang.Object
  mapss.dif.graph.Graphs

public class Graphs
extends java.lang.Object

Miscellaneous utilities for graphs.

Version:

$Id: Graphs.java 409 2007-05-13 19:47:16Z plishker $

Author:

Shuvra S. Bhattacharyya, Ming-Yung Ko

See Also:

mocgraph.Graph.

Method Summary

static java.util.Collection	addFullyConnectedEdges(mocgraph.Graph graph, java.util.Collection nodes) Add edges among the given nodes in the graph such that these nodes are fully connected.
static java.util.Collection	cliqueComponents(mocgraph.Graph graph) Return disjoint components that is clique-decomposed from the graph.
static mocgraph.Graph	complementGraph(mocgraph.Graph graph) Return a complement of the argument graph.
static java.lang.String	displayComponents(mocgraph.Graph graph, java.util.Collection components) Display a collection of node components in text.
static boolean	isConnected(mocgraph.Graph graph) Return true if the given graph is connected.

Methods inherited from class java.lang.Object

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

Method Detail

addFullyConnectedEdges

public static java.util.Collection addFullyConnectedEdges(mocgraph.Graph graph,
                                                          java.util.Collection nodes)

Add edges among the given nodes in the graph such that these nodes are fully connected.

Parameters:

graph - The graph to add the edges.

nodes - The nodes to which edges fully connect.

Returns:

The edges to add.

cliqueComponents

public static java.util.Collection cliqueComponents(mocgraph.Graph graph)

Return disjoint components that is clique-decomposed from the graph.

Parameters:

graph - The graph.

Returns:

The clique components.

complementGraph

public static mocgraph.Graph complementGraph(mocgraph.Graph graph)

Return a complement of the argument graph. A complement graph has all the edges not present in the original graph.

Parameters:

graph - The original graph.

Returns:

The complement graph.

displayComponents

public static java.lang.String displayComponents(mocgraph.Graph graph,
                                                 java.util.Collection components)

Display a collection of node components in text. A node component is a collection of nodes. Node components is displayed per line with the composed nodes' labels.

Parameters:

graph - The graph containing the nodes.

components - The collection of node components.

Returns:

The string to display the node components.

isConnected

public static boolean isConnected(mocgraph.Graph graph)

Return true if the given graph is connected. If the graph contains no nodes return true.

Parameters:

graph - The graph.

Returns:

True if the given graph is connected.