org.openscience.cdk.graph

Class GraphUtil

java.lang.Object

org.openscience.cdk.graph.GraphUtil

public class GraphUtil
extends Object

Collection of static utilities for manipulating adjacency list representations stored as a int[][]. May well be replaced in future with a Graph data type.

Author:

John May

See Also:

ShortestPaths, RingSearch

Source code:

master

Belongs to CDK module:

core

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	GraphUtil.EdgeToBondMap Utility for storing IBonds indexed by vertex end points.

Method Summary

Modifier and Type	Method and Description
static int[]	cycle(int[][] graph, int[] vertices) Arrange the vertices in a simple cyclic path.
static int[][]	subgraph(int[][] graph, int[] include) Create a subgraph by specifying the vertices from the original graph to include in the subgraph.
static int[][]	toAdjList(IAtomContainer container) Create an adjacent list representation of the container.
static int[][]	toAdjList(IAtomContainer container, GraphUtil.EdgeToBondMap bondMap) Create an adjacent list representation of the container and fill in the bondMap for quick lookup.
static int[][]	toAdjListSubgraph(IAtomContainer container, Set<IBond> include) Create an adjacent list representation of the container that only includes bonds that are in the set provided as an argument.

Methods inherited from class java.lang.Object

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

Method Detail

toAdjList

public static int[][] toAdjList(IAtomContainer container)

Create an adjacent list representation of the container.

Parameters:

container - the molecule

Returns:

adjacency list representation stored as an int[][].

Throws:

NullPointerException - the container was null

IllegalArgumentException - a bond was found which contained atoms not in the molecule

toAdjListSubgraph

public static int[][] toAdjListSubgraph(IAtomContainer container,
                                        Set<IBond> include)

Create an adjacent list representation of the container that only includes bonds that are in the set provided as an argument.

Parameters:

container - the molecule

Returns:

adjacency list representation stored as an int[][].

Throws:

NullPointerException - the container was null

IllegalArgumentException - a bond was found which contained atoms not in the molecule

toAdjList

public static int[][] toAdjList(IAtomContainer container,
                                GraphUtil.EdgeToBondMap bondMap)

Create an adjacent list representation of the container and fill in the bondMap for quick lookup.

Parameters:

container - the molecule

bondMap - a map to index the bonds into

Returns:

adjacency list representation stored as an int[][].

Throws:

NullPointerException - the container was null

IllegalArgumentException - a bond was found which contained atoms not in the molecule

subgraph

public static int[][] subgraph(int[][] graph,
                               int[] include)

Create a subgraph by specifying the vertices from the original graph to include in the subgraph. The provided vertices also provide the mapping between vertices in the subgraph and the original.

 int[][] g  = toAdjList(naphthalene);
 int[]   vs = new int[]{0, 1, 2, 3, 4, 5};

 int[][] h = subgraph(g, vs);
 // for the vertices in h, the provided 'vs' gives the original index
 for(int v = 0; v < h.length; v++) {
     // vs[v] is 'v' in 'g'
 }
 

Parameters:

graph - adjacency list graph

include - the vertices of he graph to include in the subgraph

Returns:

the subgraph

cycle

public static int[] cycle(int[][] graph,
                          int[] vertices)

Arrange the vertices in a simple cyclic path. If the vertices do not form such a path an IllegalArgumentException is thrown.

Parameters:

graph - a graph

vertices - set of vertices

Returns:

vertices in a walk which makes a cycle (first and last are the same)

Throws:

IllegalArgumentException - thrown if the vertices do not form a cycle

See Also:

RingSearch.isolated()