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:
Source code:
main
Belongs to CDK module:
core
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final class 
    Utility for storing IBonds indexed by vertex end points.
  • Method Summary

    Modifier and Type
    Method
    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[][]
    Create an adjacent list representation of the container.
    static int[][]
    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 Details

    • 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: