Package org.openscience.cdk.graph

Class 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:
    main
    Belongs to CDK module:
    core

    • 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()