org.openscience.cdk.graph

Class AllPairsShortestPaths

java.lang.Object

org.openscience.cdk.graph.AllPairsShortestPaths

public final class AllPairsShortestPaths
extends Object

Utility to determine the shortest paths between all pairs of atoms in a molecule.

 IAtomContainer        benzene = MoleculeFactory.makeBenzene();
 AllPairsShortestPaths apsp    = new AllPairsShortestPaths(benzene);

 for (int i = 0; i < benzene.getAtomCount(); i++) {

     // only to half the comparisons, we can reverse the
     // path[] to get all j to i
     for (int j = i + 1; j < benzene.getAtomCount(); j++) {

         // reconstruct shortest path from i to j
         int[] path = apsp.from(i).pathTo(j);

         // reconstruct all shortest paths from i to j
         int[][] paths = apsp.from(i).pathsTo(j);

         // reconstruct the atoms in the path from i to j
         IAtom[] atoms = apsp.from(i).atomsTo(j);

         // access the number of paths from i to j
         int nPaths = apsp.from(i).nPathsTo(j);

         // access the distance from i to j
         int distance = apsp.from(i).nPathsTo(j);

     }
 }
 

Author:

John May

See Also:

ShortestPaths

Source code:

master

Belongs to CDK module:

core

Constructor Summary

Constructors

Constructor and Description
AllPairsShortestPaths(IAtomContainer container) Create a new all shortest paths utility for an IAtomContainer.

Method Summary

Methods

Modifier and Type	Method and Description
ShortestPaths	from(IAtom start) Access the shortest paths object for provided start atom.
ShortestPaths	from(int start) Access the shortest paths object for provided start vertex.

Methods inherited from class java.lang.Object

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

Constructor Detail

AllPairsShortestPaths

public AllPairsShortestPaths(IAtomContainer container)

Create a new all shortest paths utility for an IAtomContainer.

Parameters:

container - the molecule of which to find the shortest paths

Method Detail

from

public ShortestPaths from(int start)

Access the shortest paths object for provided start vertex.

 AllPairsShortestPaths apsp = ...;

 // access explicitly
 ShortestPaths sp = asp.from(0);

 // or chain method calls
 int[] path = asp.from(0).pathTo(5);
 

Parameters:

start - the start vertex of the path

Returns:

The shortest paths from the given state vertex

See Also:

ShortestPaths

from

public ShortestPaths from(IAtom start)

Access the shortest paths object for provided start atom.

 AllPairsShortestPaths apsp = ...;
 IAtom start, end = ...;

 // access explicitly
 ShortestPaths sp = asp.from(start);

 // or chain the method calls together

 // first path from start to end atom
 int[] path = asp.from(start).pathTo(end);

 // first atom path from start to end atom
 IAtom[] atoms = asp.from(start).atomTo(end);
 

Parameters:

start - the start atom of the path

Returns:

The shortest paths from the given state vertex

See Also:

ShortestPaths