Thursday, 19 September 2013

SMILES Implicit Valence of Aromatic Atoms

The last couple of months I've been reworking the Chemistry Development Kit (CDK) handling of Simplified molecular-input line-entry system (SMILES). In this process there has been a couple of discoveries which may be interesting to share. Something previously not provided by the CDK was correct handling of implicit valence.

Both the Daylight Theory Manual and OpenSMILES Specification explain the concept for the organic subset. The specifications provide a more detailed explanation but as a simple example with the SMILES '[CH2]=[CH][CH3]' we can omit hydrogens counts and just write  'C=CC'. However, with '[CH]=[CH][CH3]' we must include the count on the first atom '[CH]=CC'. We include the labelled count if the implied count does not match.

The OpenSMILES specification explains how we can determine the implied hydrogen count.

"The implicit hydrogen count is determined by summing the bond orders of the bonds connected to the atom. If that sum is equal to a known valence for the element or is greater than any known valence then the implicit hydrogen count is 0. Otherwise the implicit hydrogen count is the difference between that sum and the next highest known valence." - OpenSMILES

This approach is simple and elegant for the aliphatic subset with non-aromatic bonds but what about the aromatic subset? One could speculate we have to assign explicit bond orders (kekulizé) a molecule to obtain the correct counts. Indeed the OpenSMILES specification seems to suggest that.

"...the SMILES software must verify that electrons can be assigned without violating the valence rules..."

Personally, I do not believe this to be the case and having the correct hydrogen count provides an additional validation if we do assign a kekulé structure.

Perhaps how we get the count for the aromatic subset is obvious and doesn't need including in the specification. However as I will show there are a couple approaches used by the different (open source) toolkits.

Disclaimer: I may be completely wrong but given the lack of documented explanation on the issue I believe it's important to at least collect some ideas on how it is currently done and how it could be done.

Parsing in Toolkits

It appears that many toolkits use their own internal valence model rather than one specific to SMILES. It is difficult to know all the intricacies of each toolkit but here's what I see from a high level view. Any maintainers of the respective toolkits please let me know of any mistakes and I'll add a correction.

The CDK uses it's own valence model via a decision tree based atom typer. The atom typer assigns a formal neighbour count which is then used to infer the number of hydrogens. This piece of code is from the end of the current SmilesParser.java:258-276. The decision tree in CDK is a large if else cascade checking possibly exceptions.

Code 1 - CDK atom typing
// CDK org/openscience/cdk/smiles/SmilesParser.java lines 258-276.
 
IAtomType type = matcher.findMatchingAtomType(molecule, atom);
boolean isAromatic = atom.getFlag(CDKConstants.ISAROMATIC);
AtomTypeManipulator.configure(atom, type);
atom.setFlag(CDKConstants.ISAROMATIC, isAromatic);

Open Babel also appears to use it's own valence model. There are actually two parsers - one of them uses the OBAtomTyper to assign implicit valence (smileyformat.cpp:287-288). The OBAtomTyper uses electron counting and SMARTS patterns. I'll come back to how aromatic bonds are treated later.

Code 2 - OpenBabel atom typing
// Open Babel src/formats/smileyformat.cpp lines 278-288
 
OBAtomTyper typer;
typer.AssignImplicitValence(*pmol);

The other parser assigns bond orders to aromatic bonds after parsing. The code snippet below is at the end of the parser (smilesformat.cpp:516-520). With set bond orders the counting is the same as with the aliphatic subset.

Code 3 - OpenBabel atom typing additionals
// Open Babel src/formats/smilesformat.cpp lines 516-520
 
    //set aromatic bond orders
    mol.SetAromaticPerceived();
    FindAromaticBonds(mol);
    FindOrphanAromaticAtoms(mol);// CM 18 Sept 2003
    mol.AssignSpinMultiplicity();
    mol.UnsetAromaticPerceived();

RDKit again uses it's own internal valence model. This model is invoked when parsing SMILES if sanitise is set (SmilesParse.cpp:184-198). Interestingly the RDKit internal model uses a similar approach to Open Babel and my first implementation. Frowns also uses the same approach and we will come back to this later.

Code 4 - RDKit Sanitize
// RDKit Code/GraphMol/SmilesParse/SmilesParse.cpp lines 184-198
 
    if(sanitize && res){
      // we're going to remove explicit Hs from the graph,
      // this triggers a sanitization, so we do not need to
      // worry about doing one here:
      try {
        ROMol *tmp = MolOps::removeHs(*res,false,false);
        delete res;
        res = static_cast<RWMol *>(tmp);
        // figure out stereochemistry:
        MolOps::assignStereochemistry(*res,true);
      } catch (...) {
        delete res;
        throw;
      }
    }
The recent parser written in Scala, chemf, uses a concise decision tree of what aromatic combinations "make sense" (SmilesAtom.scala:38).

Code 5 - Chemf
/* Snippet from chemf chemf.parser.SmilesAtom.scala lines 45 - 62*/
 
    bs count (Aromatic ==) match {
      case 1 ⇒ default (2 + (bs foldMap (_.valence)))
      case 0 ⇒ default (bs foldMap (_.valence))
      case _ ⇒ bs.toList sortBy (_.valence) match {
        case Aromatic::Aromatic::Aromatic::Nil ⇒
          if (e == C || e == N || e == P || e == B) 0.success else fail
        case Aromatic::Aromatic::Single::Nil   ⇒ 
          if (e == C || e == N || e == P || e == B) 0.success else fail
        case Aromatic::Aromatic::Double::Nil   ⇒ 
          if (e == C || e == S) 0.success else fail
        case Aromatic::Aromatic::Nil           ⇒
          if (e == C || e == B) 1.success
          else if (e == N || e == P || e == O || e == S) 0.success
          else fail
        //other combos with 2 or more aromatic bonds don't make sense
        case _ ⇒ fail
      }
    }

OUCH also uses it's own valence model. The primary function used is fillValenceAtIndex. Here is the section which computes the implicit hydrogen count - some comments have been added to explain the variables. Essentially the neighbours are counted and the method is recursively invoked adding hydrogens (and lone pairs) until a default valence is reached.

Code 6 - OUCH
-- snippet from Ouch/Structure/Molecule.hs lines 380-391
 
                     -- n neighbors is larger than the first valence + second
                     -- valence => identity (do nothing)
        outputH    | nb >= ((fst val) + (abs(snd val))) = m     
 
                     -- There is one or more bonds to a radical and the atom 
                     -- is aromatic => recurse with a molecule that has electrons added (mEl)
                   | nbrB && Set.member AromaticAtom (atomMarkerSet a) = fillValenceAtIndex mEL i
 
                     -- Fill empty valences with hydrogen => recurse with a molecule that has 
                     -- an extra hydrogen on this atom index (mH)
                   | nba < fst val                      = fillValenceAtIndex mH i
 
                     -- Then, fill lone-pairs if needed => recruse with a molecule that has an
                     -- extra lone pair on this atom index (mLp)
                   | nb < ((fst val) + (abs(snd val)))  = fillValenceAtIndex mLP i
 
                     -- Pattern completion (default) => identity
                   | otherwise = m

In the above function the bond order sum is used. Interestingly aromatic bonds contribute '2' to the sum (Atom.hs:136-148).

Code 7 - OUCH snippet 2
-- Snippet from Ouch Ouch/Structure/Atom.hs lines 136-148 
 
occupiedValence :: Atom -> Integer
occupiedValence a = output
  where output = Set.fold (\b acc -> acc + bondOrder b) 0 (atomBondSet a)
        bondOrder b = case b of
          Sigma    {}   -> 1
          Pi       {}   -> 2
          PiPi     {}   -> 3
          Aromatic {} -> 2
          Delta    {} -> 4
          Hbond    {} -> 0
          Ionic    {} -> 0
          Antibond {} -> 1
          Any      {} -> 0

PerlMol has a valence model specific to SMILES. The parser doesn't have the aromatic bond token ':' and uses a bond order of '1' for an implicit bond. The hydrogen count is computed as per the aliphatic subset - if the atom is an aromatic carbon or nitrogen the hydrogen count is decreased.

Code 8 - PerlMol
# Snippet from PerlMol Chemistry/File/SMILES.pm lines 412-423
 
# returns the number of hydrogens for an atom, assuming it has
# no charge or radical (because those require an explicit H-count anyway)
sub calc_implicit_hydrogens {
    my ($self, $atom) = @_;
    no warnings 'uninitialized';
    my $h_count = $ORGANIC_ELEMS{$atom->symbol} - $atom->valence;
    if ($atom->attr("smiles/aromatic") and $atom->symbol =~ /^[CN]$/) {
        $h_count--;
    }
    $h_count = 0 if $h_count < 0;
    $h_count;
}

It's clear there are different approaches and it's tempting to speculate there are still some more differences in closed source toolkits.

Generation

Of course the implicit hydrogen count of the aromatic subset also maters when generating SMILES. One well known example is of aromatic nitrogens which contribute a lone pair - for example pyrrole.
1H-pyrrole

The CDK, Open Babel and RDKit handle this as a special exception when generating the SMILES string. The CDK code refers to this as a special nitrogen (SmilesGenerator.java:1652-1657).

Code 9 - CDK's special nitrogen
  // we put in a special check for N.planar3 cases such
            // as for indole and pyrrole, which require an explicit
            // H on the nitrogen. However this only makes sense when
            // the connectivity is not 3 - so for a case such as n1ncn(c1)CC
            // the PLANAR3 N already has 3 bonds, so don't add a H for this case
    boolean isSpecialNitrogen =
    a.getSymbol().equals("N") &&
    a.getHybridization() == IAtomType.Hybridization.PLANAR3 &&
    container.getConnectedAtomsList(a).size() != 3 &&
    (a.getFormalCharge() == null || a.getFormalCharge() == 0);
   brackets = brackets | isSpecialNitrogen;

Similar to CDK, Open Babel has the method CorrectAromaticAmineCharge (smilesformat.cpp:2569-2592)

Code 10 - OpenBabel CorrectAromaticAmineCharge
void OBMol2Cansmi::CorrectAromaticAmineCharge(OBMol &mol)
  {
    OBAtom *atom;
    vector::iterator i;
 
    _aromNH.clear();
    _aromNH.resize(mol.NumAtoms()+1);
 
    for (atom = mol.BeginAtom(i);atom;atom = mol.NextAtom(i))
      if (atom->IsNitrogen() && atom->IsAromatic())
        if (atom->GetHvyValence() == 2)
          {
            if (atom->GetValence() == 3 || atom->GetImplicitValence() == 3)
              _aromNH[atom->GetIdx()] = true;
          }
  }

These hardcoded exceptions work, unless you miss an exception...

1H-phosphole


Neither CDK or the default Open Babel parser will include the required hydrogen. Note - obabel v 2.3.1 (latest on Mac), this might have been fixed in v 2.3.2..

Code 11 - OpenBabel aromatic phosphorus
[intrepid ~]: obabel -:"[nH]1cccc1" -osmi
[nH]1cccc1  
1 molecule converted
[intrepid ~]: obabel -:"[pH]1cccc1" -osmi
P1CCCC1 
1 molecule converted

Adding another conditional (as in RDKit) for aromatic phosphate solves this problem (SmilesWirte.cpp:75-69).

Code 12 - RDKit non-standard handling
// another type of "nonstandard" valence is an aromatic N or P with
// explicit Hs indicated:
if((num==7||num==15) && atom->getIsAromatic() && atom->getNumExplicitHs()){
    nonStandard=true;
}

Although this will handle most (possibly all) cases if there is a way to assign implicit hydrogen counts no special treatment is needed. As with the aliphatic subset if the implicit hydrogen count doesn't match what we have stored we must include the hydrogen counts.

Fractional Bond Orders

As mentioned earlier, my first approach was the same as OpenBabel, RDKit's and Frowns (something I didn't realise until collecting the information for this post). The approach seems obvious - aromatic bonds have bond order '1.5'. This is of course not true but we will see how this model fits examples.

c1ccccc1
Benzene, we find that the bond order sum of each carbon is 3 (1.5 + 1.5). The difference between carbon's next highest valence (4, as per the specification) is 1. So each carbon has 1 implied hydrogen
c1ccc2ccccc2c1
Naphthalene, has two carbons with three aromatic bonds and each with a bond order sum of 4.5 (1.5 + 1.5 + 1.5). This is higher than any specified valence and thus there are no hydrogens.
c1ccc2ocnc2c1
1,3-benzoxazole, has an aromatic nitrogen and oxygen. The nitrogen as two aromatic bonds and thus a bond order sum of 3 (1.5 + 1.5). This is a default valence for nitrogen and so there is no implicit hydrogen. The oxygen also has the bond order sum of 3 which exceeds it's maximum specified valence (2) and again there are no hydrogens.
c1n([H])ccc1
1H-pyrrole, with the labelled hydrogen (c1[nH]ccc1) will work fine - the brackets mean we don't have to look up the implicit valence. However, what happens if we make that an explicit hydrogen? If we apply our rule we hit a problem. The bond order sum of that nitrogen is now 4 (1.5 + 1.5 + 1). The next highest specified valence is 5 and so we have and additional implicit hydrogen (two hydrogens total)? 
c1cn2ccccc2n1
imidazo[1,2-α]pyridine, one nitrogen has 3 aromatic bonds and thus using this model we determine it has a bond order sum of 4.5 (1.5 + 1.5 + 1.5). Depending on whether we choose to round up or down that nitrogen will have either a single hydrogen or none. 


To fix the problematic examples we need an additional rule. Only check the default valence for aromatic atoms. A justification for this could be that elements which have more than one valence cannot go to a higher valence state as the electrons which would bond those hydrogens are contributed to the pi bonding system. We can see this is also the approach used by RDKit - although RDKit doesn't allow 5 valent nitrogen so this particular example won't occur. Also note that the partial bond order sum is rounded up.

Code 12 - RDKit valence calculation
  /* RDKit/Code/GraphMol/Atom.cpp lines 193-232*/

  // check accum is greater than the default valence
  unsigned int dv = PeriodicTable::getTable()->getDefaultValence(d_atomicNum);
  int chr = getFormalCharge();
  if(isEarlyAtom(d_atomicNum)) chr*=-1;  // <- the usual correction for early atoms
  if (accum > (dv + chr) && this->getIsAromatic()){
    // this needs some explanation : if the atom is aromatic and
    // accum > (dv + chr) we assume that no hydrogen can be added
    // to this atom.  We set x = (v + chr) such that x is the
    // closest possible integer to "accum" but less than
    // "accum".
    //
    // "v" here is one of the allowed valences. For example:
    //    sulfur here : O=c1ccs(=O)cc1
    //    nitrogen here : c1cccn1C
    
    int pval = dv + chr;
    const INT_VECT &valens = PeriodicTable::getTable()->getValenceList(d_atomicNum);
    for (INT_VECT_CI vi = valens.begin(); vi != valens.end() && *vi!=-1; ++vi) {
      int val = (*vi) + chr;
      if (val > accum) {
        break;
      } else {
        pval = val;
      }
    }
    accum = pval;
  }
  // despite promising to not to blame it on him - this a trick Greg
  // came up with: if we have a bond order sum of x.5 (i.e. 1.5, 2.5
  // etc) we would like it to round to the higher integer value -- 
  // 2.5 to 3 instead of 2 -- so we will add 0.1 to accum.
  // this plays a role in the number of hydrogen that are implicitly
  // added. This will only happen when the accum is a non-integer
  // value and less than the default valence (otherwise the above if
  // statement should have caught it). An example of where this can
  // happen is the following smiles:
  //    C1ccccC1
  // Daylight accepts this smiles and we should be able to Kekulize
  // correctly.
  accum += 0.1;  


A similar approach is used in Frowns library. The snippet below shows the use of a 1.5 bond order from Atom.py:82-92.

Code 14 - FROWNS sumBondOrders
     def sumBondOrders(self):
         result = 0
         for x in self.bonds:
             if x.bondtype == 4:
                 # XXX FIX ME
                 # this is a hack to fix bad conjugation
                 # this will be fixed soon
                 result += 1.5
             else:
                 result += x.bondorder
         return result

Open Babel also uses a bond order of '1.5'. Although in their case they actually count electrons and then divided by 2 (atom.cpp:1000-1015). This avoids fractional bond orders - at least until the division where the fractional part is truncated (5/2 = 2).

Code 15 - OpenBabel valence
// Open Babel src/atom.cpp lines 1000-1015
 
for (bond = ((OBAtom*)this)->BeginBond(i);bond;bond = ((OBAtom*)this)->NextBond(i))
{
    bo = bond->GetBO();
    bosum += (bo < 5) ? 2*bo : 3;
}
 
bosum /= 2;
return(bosum);

Using this model will work very well and give use correct results. There are however still some questions, in particular the ambiguity and having to round bond order sums is troublesome.

Also we need to know which bonds are aromatic - 'cc' is an aromatic bond and 'CC' is a single bond if we have these as an implicit bond as suggested by SMILES we need to check the atoms in each case to determine if the order is '1' or '1.5'. Additionally I found a couple of examples in ChEMBL where up ('/') and down ('\') bonds are part of an aromatic system (contrived example below). Again we need to check the atoms of those bonds to see if they are aromatic or single. These problems only occur if we have bond labels specifically for handling SMILES but it would be nice to have something more elegant.

C\C=c1/ccc(=C)cn1

Atom-based 

After using the fractional bond order and testing on some datasets I was relatively happy it solved the problem. Using a bond order of 1.5 will certainly work - pragmatic, yes - elegant, no.

Despite this I couldn't shake the feeling that "Dijkstra would not have liked this". I think this is also evident from the comments in the RDKit and Frowns source code (see above).

What I now believe is the correct way, or at least closer to the Daylight way is that instead of modifying the bond orders we modify the starting value of our bond order sum. With aromatic atoms, instead of starting at 0 we start at 1.

The point of the 1.5 bond order is to increase the bond order sum to be higher for aromatic atoms. We can achieve the same thing by simply changing the starting value of the sum. This also fits in that aromaticity in SMILES is primarily defined by atoms and not bonds. There is the ':' aromatic bond but it is not required (and rarely/never used).

In practice this means implicit, single, aromatic, up and down bonds now all contribute 1 to the bond order sum. Of course this is completely bogus but we're not saying that aromatic bond is the same as a single bond - rather just that it contributes a bond order of '1'. This also means that the implicit bond between aliphatic and aromatic atoms 'cc', 'CC' and 'cC' would all contribute the same to the bond order and we can treat them the same.

This is particularly useful for cases like '[Te]1cccc1' (ChemSpider:119908). Using a bond order of 1.5 we would determine the bond order sum of each carbon adjacent to the '[Te]' to be '2.5' or '2' (5/2). Rounding up or down we get '1' (correct) or '2' hydrogens.

It would seem that PerlMol was nearly there - the implicit bond order in PerlMol is '1' and the hydrogen count was decreased for aromatic atoms. This was only done for carbon and nitrogen though and should be applied to all aromatic atoms.

Using this method cleans up the calculation and removes the fractional results. As before we must still only use the default (lowest) valence for multivalent elements. Perhaps there is a more elegant way to avoid that that but it has so far eluded me.

Is it Correct?

I can not say for certain whether this model is correct but it is certainly closer than using a fractional bond order.

The well known Depict service from Daylight displays the structure diagram for a given SMILES string. It will also report problems with SMILES. For example it reports that [C]C has unusual valence 1 (normal 2).

Now what is really interesting is if we give it some aromatic atoms. It turns out that a single aromatic atom [c] also has unusual valence 1 (normal 2). But wait - there aren't any bonds to that atom but it has valence of 1?

Aromatic carbon has no neighbours but has a valence of 1?
Let's add one neighbour [c]c - no warning (2 valent carbon is considered okay). Okay let's try something else, c[c]cc has low valence 3 (normal 4). Again there are only two neighbours but it has a valence of 3. The same is also true for nitrogen, phosphate and the atoms in the aromatic subset.

This also explains why c is '[CH3]'.

Using this approach also allows us to get the correct count for some strange examples. One example could be an acyclic aromatic atom (rejected by some toolkits). This can happen for example with an exocyclic oxygen (oc1ccocc1). Using this approach we reach the correct answer that there are no hydrogens on that sprouting oxygen. This can then be used in the assignment of a correct Kekulé structure. One can see how this SMILES string is interpreted 4 different ways by various toolkits - oc1ccocc1 (Ambit).

With this model it also means that when we generate the SMILES we can now check how many implicit hydrogens aromatic atoms should have. Doing so we would say that for pyrrole the implied hydrogen count would be '0'. This does not match our stored value and so we need to include the bracket atom with the labelled hydrogen count.

Complications

There are of course still some complications - which seem to be when we mix aromatic and aliphatic parts. The fact that the first case here is read as cyclohexane further shows there isn't an aromatic bond order used.

1. C1:C:C:C:C:C1  (daylight reads as cyclohexane)
2. C=1:C=C:C=C:C1 
3. c=1c=cc=cc1    (problematic)
4. c-1c-cc-cc1    

With the described model we can't reach the correct answer for (3.). You're unlikely to encounter such a case in a clean dataset but we can modify our model slightly to get the correct results.

Instead of starting at '1' we add '1' to the bond order sum of aromatic atoms if the bond order sum is the same as the number of explicit neighbours. Indeed this agrees with Depict that 'c[c]cc' has a valance of 3 but '[c]=c' has a valence of 2 (if we started at '1' it would also be '3').

Hopefully this has provided some insight or at least show how the implicit hydrogens can be counted in aromatic SMILES.

Supplementary

Re-reading back through the mailing list it seems this has of course be discussed (at least partially) - no decision was made. As usual the sourceforge mailing archives are a pain to find stuff in but the discussion [1]  is summarised on the OpenSMILES repository [2].

As I see it there are three models which can be used.
  • Use bond order of 1.5 for aromatic bonds.
  • Reduce the hydrogen count for aromatic atoms - also attempts to allow this to specify radicals (C1CCcCC1).  This has many problems but that would need another post.
  • Increase the valence by 1 if there are no double/triple bonds.
Mailing List Links
  1. http://sourceforge.net/mailarchive/forum.php?thread_name=60825b0f0709302037g2d68f2eamdb5ebecf3baea6d1%40mail.gmail.com&forum_name=blueobelisk-smiles
  2. https://github.com/timvdm/OpenSMILES/blob/master/discussion_summary.txt
Other links





Thursday, 27 June 2013

Implementing Hanser's Path Graph Reduction - All Simple Cycles

In the previous post (AllRingsFinder, Sport Edition) I presented runtime results for an algorithm to find all simple cycles. This post explains in detail that implementation - there's a fair bit of code but I tried to keep it short. Hanser's algorithm is remarkably elegant and was a joy to program.

The Algorithm

The set of all cycles can be found in a number of ways. We could trace the cycles by walking every simple path (very inefficient) or perhaps combine all cycles from a cycle basis (requires basis computation first). Hanser et al, 96 describe an alternative approach - it allows us to find all the simple cycles directly.

The process is based on progressive reduction (collapsing) of a path graph. Opposed to edges (bonds) which consist of just the two endpoints, the path graph has edges which describes a walk between the endpoints. To begin all edges are simply their end points, then by removing each vertex the edges are concatenated in to path edges describing a walk. When an edge forms a loop (endpoints are the same vertex) a cycle has been found.

The animation below demonstrates the process of finding the three cycles in a naphthalene like graph. The vertex to be removed is first highlighted - and then the edges that will be combined. It's a little hard to follow when f is reached but there are three edges and three possible ways to combining two edges - from {1,2,3} we can have {1,2}, {2,3} and {1,2}. At the end the three cycles have been found as the paths on the loops.
Removing vertices in a path graph

Implementation

The pseudo code below describes the removal of a vertex x, from the set of vertices V and edges E. First, find all edges which contain x, then for every possible combination (E2), check that the only intersect is x. This avoids creating non-simple paths. If the two edges only intersect at x, then concatenate them to a new reduced edge. Add the new edge to the edges set, E. Once all new edges have been created remove, x and it's old edges from E and V.

REMOVE (x, V, E)
  for each couple of paths (Pxy, Pxz) ∈ E2
      if Pxy ∩ Pxz = {x} then
        Pyz ← Pxy ⊕ Pxz
        E ← E ∪ Pyz
  for each path Pxy ∈ E
    E ← E - {Pxy}
  V ← V - {x}


The exact implementation is not discussed in the paper but notes the requirement of dynamic lists (List) of the edges and binary sets (BitSet) for the labels on the edges.

As expected the AllRingsFinder.remove() uses dynamic lists to store the vertices (atoms). The intersection does not use binary sets and instead takes quadratic time, O(n2) - Path.getIntersectionSize(). An alternate implementation (HanserRingFinder) reduces the number of operations for each removal PathGraph.remove(). The intersection check (PathEdge.isRealPath()), was also improved but is still quadratic.

Observations

So, can we do better and how?

We are actually going to do the opposite from the previous implementations, we will use the binary sets and not use a dynamic lists.

One key realisation is that the path graph is no different from any other graph. We can use different representations of the path graph depending on what operations we need to perform (see. The Right Representation for the Job). As we only reduce edges incident to x we can use an adjacency/incident list to store the path graph. A summary of these and other changes is shown below:
  • Use binary sets - intersection check is now constant time, O(1).
  • Use an incidence list data structure and index edges by their endpoints. With a modification discussed later, we can actually make this constant time.
  • Only check that edges are disjoint except for their endpoints. This is faster than checking if the sets make a singleton of just {x}. As the edges are now indexed by x, all the edges will have x in common. If the other end point is also common then the two edges will form a loop (cycle) when combined. This can be allowed by moving the check for new cycles.
  • Check the degree of a vertex before removal, this provides a fail-fast approach and avoids inconsistencies of a timeout. This is possible as the number of new edges is bounded by the degree of x.
  • Use a recursive data structure and store undirected path edges. This avoids the the reversing and copying of the dynamic lists for each concatenation. The directed path can then be reconstructed when needed - only when a cycle was found. This has minimal influence on speed on small molecules but does makes the implementation more concise.
With these observations in mind, here is what the data structures look like.

ArrayBuilder

To begin, a helper class is needed for the path reconstruction. This class simply allows us to sequentially fill up an int[] array by appending items to the end. It also provides access to the previous element and returns a self-reference on append which will allow us to the chain method calls.
Code 1 - ArrayBuilder
class ArrayBuilder {
    
    int[] xs;
    int   i = 0;
 
    ArrayBuilder(int n) {
        xs = new int[n];
    }
 
    ArrayBuilder append(int x) {
        xs[i++] = x;
        return this;
    }
 
    int prev() {
        return xs[i - 1];
    }
}

PathEdge

There are two types of PathEdge, one is a simple non-reduced edge and one for a reduced edge (a path). We can actually share most of the operations between these and so we first define the API in an abstract superclass.

Unsurprisingly the PathEdge API is very similar to a normal undirected edge in that there is a either() and other(int) for querying the endpoints. Unlike a normal edge, the bits of 'xs' member variable stores which other vertices in the graph lie in the path between the endpoints. We'll come back to order in a bit. Binary set intersection is checked using the '&' operator and for two edges to be disjoint - the intersection should be empty. The path() provides the ordered walk though the edge between the endpoints - we need to start from either end point and then reconstruct the path (see subclasses). It should be noted we use a BitSet for graphs with more than 64 vertices.
Loading ....
The first implementation, the simple edge, is just the two end points. The length is two and there are no reduced vertices. We can therefore always pass an empty set to the superclass. The path through this edge is just the endpoints. The previous vertex in the ArrayBuilder is used to query and append the other endpoint giving a path of length two.
Code 2 - SimpleEdge
final class SimpleEdge extends PathEdge {
    
    // Two endpoints and no reduced vertices (empty set).
    SimpleEdge(int u, int v) {
        super(u, v, 0);
    }
    
    // Given the previous vertex, add the other endpoint.
    ArrayBuilder reconstruct(ArrayBuilder ab) {
        return ab.append(other(ab.prev()));
    }
    
    // we only have the endpoints.
    int len() {
        return 2;
    }
}
The reduced edge is a little more complicated. It is created by concatenating two existing edges which share a common vertex. The new endpoints are the other() endpoint of each edge with respect to x. The set of reduced vertices is the union of the two edges reduced vertices and the new common vertex, x. The length of the path through this edge is the endpoints and number of reduced vertices - stored as bits so the bit count is added. Depending on the end point the path reconstruction proceeds through one edge and then through the other.
Code 3 - ReducedEdge
final class ReducedEdge extends PathEdge {
    
    final PathEdge e, f;
    
    //Two edges with a common endpoint (x). The reduced set 'xs' is the union of
    // the two edge's 'xs' sets and the common endpoint 'x'.
    ReducedEdge(PathEdge e, PathEdge f, int x) {
        super(e.other(x), f.other(x), e.xs | f.xs | 1L << x);
        this.e = e;
        this.f = f;
    }
    
    // Reconstruction delegates to reduced edges.
    ArrayBuilder reconstruct(ArrayBuilder ab) {
        // append the paths of the two edges, order depends on previous vertex 
        return u == ab.prev() ? f.reconstruct(e.reconstruct(ab))
                              : e.reconstruct(f.reconstruct(ab));
    }
    
    // Two endpoints and the number of reduced vertieces.
    int len() {
        return 2 + Long.bitCount(xs); // or: e.len() + f.len() - 1
    }
}

PathGraph

With our path edges defined we now need the graph to store them in. As noted, storing the edges in an incident list allows quick lookup. The add(PathEdge)includes a new edge in the graph and remove(int) removes and returns all edges incident to x. The reduce() method does the combination of the edges which are disjoint. Finally the remove() method, gets the incident edges, reduces them and then either adds them back to the graph or stores the newly discovered cycle. I've have omitted the degree() method for brevity but this is just the size of each list.

Code 4 - PathGraph
class PathGraph {
   
    // edges indexed by thier end points
    List[] g;
    
    PathGraph(int n) {        
        // initalise 'g'       
    }
    
    // adds an edge to the graph.
    void add(PathEdge e) {
        int u = e.either();
        int v = e.other(u);
        g[u].add(e);
        g[v].add(f);
    }
    
    // Remove (and get) all edges incident to 'x'.
    List remove(int x) {
        List es = g[x];
        for (PathEdge e : es)
            g[e.other(x)].remove(e);
        g[x] = Collections.emptyList();
        return es;
    }
    
    // combined all edges 'es' which are disjoint and share the 
    // endpoint 'x'
    List reduce(int x, List es) {
        List reduced = new ArrayList();
        
        for (int i = 0; i < es.size(); i++) {
            for (int j = i + 1; j < es.size(); j++) {
                
                PathEdge e = es.get(i);
                PathEdge f = es.get(j);
                
                if (e.disjoint(f)) 
                    reduced.add(new ReducedPathEdge(e, f, x));
            }
        }
        return reduced;
    }
    
    // Remove 'x' from the graph by reducing all incident edges. Any
    // newly discovered cycles are added to 'cs'.
    void remove(int x, List cs) {
        
        List es      = remove(x);
        List reduced = reduce(x, es);
        
        // for each new edge, either store the cycle or
        // add it back into the graph
        for (PathEdge e : reduced) {
            if(e.loop()) {
                cs.add(e.path());
            } else {
                add(e);
            }
        } 
    }    
}

Although the edge access is more efficient, as the graphs becomes more dense (during reduction) we need to modify more of the incident lists on each removal. We can avoid this by by imposing a predefined order on how vertices are removed. As recommended in the original publication, processing by degree is a good approach. With the ordering predefined, edges need only be indexed by a single endpoint.
Code 5 - Ranked removal
    // indicates the order which vertices will be removed
    int[] rank;
    
    // adds an edge to the graph on the least rank vertex.
    void add(PathEdge e) {
        int u = e.either();
        int v = e.other(u);
        if (rank[u] < rank[v])
            g[u].add(e);
        else 
            g[v].add(f);
    }
    
    // Remove (and get) all edges incident to 'x'.
    List remove(int x) {
        List es = g[x];
        g[x] = Collections.emptyList();
        return es;
    }

All these changes contribute (some more than others) to the performance improvements seen in the previous post (AllRingsFinder, Sport Edition). To run the algorithm we simply build the path graph then successively remove all the vertices.

What's really nice about this implementation is the PathEdge is a persistant data structure and can easily be implemented in a purely functional language. I actually managed to write a version in Scala and Haskell - one issue is that PathGraph also needs to be persistant. There are of course good persistant random access array but they're simply not as fast. Switching back to the edge list representation actually allows you to use cons-lists (singly linked list) but at the cost of performance.

Wednesday, 26 June 2013

AllRingsFinder, Sport Edition

Recently I've been looking at efficient perception of cycles in graphs. The goal is to improve and unify ring perception methods in the Chemistry Development Kit (CDK). Slowly working through, optimising and adding algorithms there was one I was dreading. The AllRingsFinder in CDK provides all simple cycles (every possible ring) in a graph by progressively collapsing edges (Hanser et al, 1996). The AllRingsFinder is used (sometimes incorrectly) throughout the library in many different modules.

To perceive all simple cycles can take a long time and I was pessimistic about making any improvement with it's speed. Fortunately, I was pleasantly surprised.

I'll go through the technical aspects of the implementation in the next post. This post will primarily focus on the performance. It should be noted that the algorithm is exactly the same and only the data structures and operations were modified.

Preliminaries

We will be testing the new implementation named AllCycles against the existing AllRingsFinder and HanserRingFinder. The HanserRingFinder was written by Rich Apodaca (depth-first) and is included in the CDK SMSD module. The AllCycles takes as input an adjacency list graph with the vertices described by integers. This is standard for graph algorithms - the time to convert the CDK molecule (IAtomContainer) is included in all results.

The benchmarks were run with Java 7 (21) on a 2.66 GHz Intel Core i7.

Complete Graphs Benchmark

When each vertex in the graph is adjacent to every other vertex we have the worst case for the algorithm. The number of simple cycles in these graphs grows very rapidly. The graphs are known as complete graphs and are named Kn, n being the number of vertices. The table below summarises the results of each implementation in milliseconds.

AllRingsFinder' is a modified version of AllRingsFinder that does not convert the paths to IRing objects. This conversion is currently inefficient and can impact the performance when there is a large number of cycles. The AllCycles and HanserRingFinder implementations already return the paths as a sequence of integers and atoms respectively.

Edit - I realise now the reason for the difference here is that I accidentally used the default and not silent domain objects. The default objects fire events on updates which can cause massive performance hits - particularly when adding atoms. Using the silent objects (no events) yields similar times to AllRingsFinder' without the IRing conversion. In short - don't use the default objects, ever... you don't need it, trust me. I'll leave the timings as reminded not to do this - the dataset results presented were already using the silent objects.

Graph Number of Cycles Implementation Time (ms)
K3 1 AllCycles 0.00 ms
HanserRingFinder 0.00 ms
AllRingsFinder 0.15 ms
AllRingsFinder' 0.00 ms
K4 7 AllCycles 0.00 ms
HanserRingFinder 0.00 ms
AllRingsFinder 0.95 ms
AllRingsFinder' 0.00 ms
K5 37 AllCycles 0.00 ms
HanserRingFinder 0.15 ms
AllRingsFinder 2.20 ms
AllRingsFinder' 0.75 ms
K6 197 AllCycles 0.10 ms
HanserRingFinder 0.85 ms
AllRingsFinder 7.80 ms
AllRingsFinder' 2.00 ms
K7 1172 AllCycles 0.55 ms
HanserRingFinder 26.10 ms
AllRingsFinder 193.80 ms
AllRingsFinder' 39.80 ms
K8 8018 AllCycles 12.0 ms
HanserRingFinder 817.00 ms
AllRingsFinder 10078.75 ms
AllRingsFinder' 1360.75 ms
K9 62814 AllCycles 994.70 ms
HanserRingFinder 54524.85 ms
AllRingsFinder 389597.00 ms
AllRingsFinder' 81699.53 ms

Performance of each implementation on complete graphs - log scale
It's quite amazing that using the same algorithm and simply changing the data structures (and not firing object events) can produce more than a 300000% improvement in performance (K9).

Dataset Benchmark

Examining the worst case gives us a concise view of how the implementation scales. To judge the real performance several datasets were used; ChEBI, HMDB and a subset of PubChem Compound (CID 0 - 25000).

There are molecules in the datasets with far more cycles than we can reasonably handle. Such molecules are considered impractical and depends on some predefined escape clause. 
  • AllRingsFinder measures the time when the algorithm starts and terminates if a set time limit is exceeded.
  • AllCycles terminates when a preset maximum degree (connections) on a vertex is exceeded.
  • HanserRingFinder does not have a timeout and so was not tested on the datasets.
The table below summarises the results for each dataset. To allow a reasonable number of repeats the timeout for AllRingsFinder was reduced from the default 5000 ms to 50 ms. Running on ChEBI with the default timeout took 389597 ms (29 impractical) and clogged the memory so much the timing was not stable. The maximum degree used for AllCycles was arbitrarily chosen as 500. Additionally the findAllRingsInIsolatedRingSystem() was used instead of findAllRings(). This allowed nearly identical prepossessing for both implementations using the fast RingSearch. Invoking the findAllRings() directly will yield slower results than those listed below. 


Data Molecules Implementation Time (ms) Impractical Cycles
ChEBI 29954 AllCycles 256 ± 56 ms 36 155476
AllRingsFinder 10324 ± 189 ms 86.86 131124.72
HMDB 37495 AllCycles 390 ± 48 ms 2 93148
AllRingsFinder 5410 ± 180 ms 40.83 86230.38
PubChem Compound Subset 22676 AllCycles 195 ± 55 ms 1 61229
AllRingsFinder 1942 ± 173 ms 5.05 60587.58

We can see that for ChEBI we were able to perceive 20000+ more cycles in ~2% of the time. As mentioned the times include the preprocessing and conversion, were molecules loaded direct as adjacency lists the time for PubChem Compound subset (195 ms) would be even faster! The counts for AllRingsFinder are fractional due to the fluctuations between repeats.

Choosing a Maximum Degree Limit

The performance of new implementation depends on choice of the maximum degree. The limit doesn't really have a meaning and may be chosen incorrectly. Set the limit too low and we lose information, too high and we may generate more information than we can handle . 

Running the implementation on all of PubChem Compound (Dec '12) with a limit of 5000 we can retrospectively calculate the limit for a given percentile. In PubChem Compound there were 17842848 ring systems with more than one ring,  987 (0.005%) of which exceeded our hard maximum degree of 5000.

Plotting the cumulated percent (T) against the maximum degree reached indicates that 99% of ring systems can be completed with a limit of just 9. Due to the sheer number of systems, if we did choose that value there would still be 166131 systems which were considered impractical and did not finish. 


To reduced the number of impractical molecules we need to go to fractions of a percent.

Maximum DegreePercent (%)Completed
(ring systems)
Impractical
(ring systems)
7299.95178340138835
8499.96178358766972
12699.97178376925156
21699.98178392933555
68499.99178410651783
88299.991178413421506
106299.992178414291419
144099.993178416021246
307299.994178417891059

This breakdown provides a meaningful insight for an appropriate value. I haven't decided yet where to include a Run Forever option - due to the combinatorial explosion there will always be molecules which we can't compute. I'll leave you with this entertaining video which explains the amazing power of combinatorial explosion.



Results


Wednesday, 17 April 2013

Assert That, Assert This

When writing test assertions with JUnit I tend to favour using assertThat over assertEquals. I've been asked a couple of times now what the benefits and why I use it. I thought it would be nice to write a short post on why I personally use it. The feature has been in available since 2008 so I may skip a couple of details but there are many excellent tutorials.

Correctness

I first used assertThat when I wanted to check for inequality of objects. JUnit provides assertEquals but how does one test that two objects are not equal? There is an assertNotEquals method which you can use but this was only recently added in release 4.11 (Nov 2012).

Previously I may have asserted on a Object.equals predicate.

String a = "a string";
String b = "b string";
 
assertFalse(a.equals(b));

However, if this test fails we'll have no clue what went wrong. You could add an optional failure message but when there is thousands of assertions this get tedious.

Alternatively, you may have been tempted to use assertNotSame which, although it has uses, is probably mostly used incorrectly. This assertion actually does reference inequality. In the example below both assertions pass. Although a and c have the same content, they are different instances.

String a = "a string";
String b = "b string";
 
// assert "a string" and "b string" are not the same 
assertNotSame(a, b); 
 
String c = "a string";
// assert "a string" and "a string" are not the same
assertNotSame(a, c); // whoops! 

Due to string interning and integer caching the assertion could work some of the time. However, to paraphrase Joshua Bloch - any program which depends on string interning for correctness is barely working. A quick look at the Chemistry Development Kit reveals there are at least 121 usages. I wonder how many of these are really meant to be doing reference equality?

We can avoid this confusion by using assertThat. It is now clear when we actually do reference equality.

// assert the content is not equal
assertThat("A", is(not("B"));
 
// assert the two strings are not the same instance
assertThat("A", is(not(sameInstance(new String("A")));

Okay, so our assertions are clearer, but with JUnit 4.11 and assertNotEquals I can avoid this issue. Well, arrays don't override Object.equals, which is why there is assertArrayEquals. Trying to check that two arrays are not equal with assertNotEquals will also fail.

int[] a = new int[]{0, 1, 2};
int[] b = new int[]{0, 1, 2};
 
assertNotEquals(a, b); // nope!

Using assertThat the code is no different from checking non-array objects.

int[] a = new int[]{0, 1, 2};
int[] b = new int[]{0, 1, 2};
 
assertThat(a, is(not(b)));

Expressiveness

I'm also a huge fan of how expressive the assertions can be (check out ScalaTest for really cool readability).  Lets say a value is returned from a method under test which may have multiple equally correct values. With assertThat we can get a much better default failure message if something when wrong.

int x = 6;
 
assertTrue(x < 5);
// no message            
 
assertThat(x, is(lessThan(5)));
// Expected: is a value less than <5>
//      but: <6> was greater than <5>

We can combine matchers logically with not, anyOf and allOf.

int x = 4;
 
assertTrue(x == 5 || x == 6 || x == 7);
// no message
 
assertThat(x, anyOf(is(5), is(6), is(7)));
// Expected: (is <5> or is <6> or is <7>)
//      but: was <4>

We can also check the content of collections without worrying about the implementation. The assertEquals here will only work if xs is a HashSet. If xs is latter changed to a different implementation (TreeSet, ArrayList, etc) the test will now fail, and of course with no failure message. Using assertThat we can check the actual content and get a better failure message if the content does change. I also think it is more readable.

Collection xs = ...
 
// whoops, i forgot the method returns a TreeSet
assertEquals(xs, new HashSet(Arrays.asList(42)));
 
// doesn't depend on implementation
assertThat(xs, hasSize(1));
assertThat(xs, hasItem(42));

Custom Matchers

We can even write custom matchers for common assertions. In the Chemistry Development Kit I may want to check that a returned atom is a carbon. You'd normally do this by checking the symbol is C.

assertThat(atom.getSymbol(), is("C"));

We can write a custom matcher to check an atom is a carbon and provide a default failure message when the assertion fails. The matcher could also handle null and case insensitivity but I've omitted these for clarity.

public class SymbolMatcher extends TypeSafeMatcher<IAtom> {
 
    private final String expected;  
    
    private SymbolMatcher(String expected) {
        this.expected = expected;
    }
 
    @Override protected boolean matchesSafely(IAtom atom) {
        String actual = atom.getSymbol();
        return expected.equals(actual);
    }
 
    @Override public void describeTo(Description description) {
        // symbolToName, map 'C' -> 'carbon'
        description.appendText(symbolToName.get(expected));
    }
 
    public static Matcher<IAtom> carbon() {
        return SymbolMatcher("C");
    }
 
    public static Matcher<IAtom> oxygen() {
        return SymbolMatcher("O");
    }
}

With our matcher written we can import the static method carbon() and use it with assertThat.

Atom atom = new Atom();
atom.setSymbol("O");
        
assertThat(atom, is(carbon()));
 
// Expected: is carbon
//      but: was oxygen

As before the logical matchers can build up a more complex assertion.

assertNotNull(atom);
assertEquals("C", atom.getSymbol());
assertTrue(atom.getFlag(CDKConstants.ISAROMATIC));
assertEquals(IAtomType.Hybridization.SP2, atom.getHybridization());
 
// combining matchers
assertThat(atom, is(allOf(notNullValue(),
                          carbon(),
                          aromatic(),
                          sp2())));

I still think using assertTrue and assertNotNull for isolated assertions is the best way but for many cases assertThat provides better flexibility and correctness.

Wednesday, 30 January 2013

Making the mutable, immutable

There are many advantages to immutability. Immutability makes it impossible to the change of state and establish an invariant in your software. Naturally this lends it's self to parallelisation. Since last year I have been playing around with Scala and the power really started to click. There's a great talk by Rich Hickey on The Value of Values which is also very thought provoking. Even Java, an imperative language, makes extensive use of immutability on it's value classes: String, Integer, Double. Often it is recommended that you minimise the mutability of value classes (Effective Java - Item 15). Unfortunately these are often forgotten when writing higher level data types as they are more easily expressed as mutable. This often leads to defensive copying and over use of cloning. If you can make the data type immutable not only are copies/clones irrelevant but updates can be made more efficient than a full defensive copy followed by an update.


Recently a functional cheminformatics toolkit, ChemF, was published. It demonstrates an impressively light SMILES parser, you can check it out on github. The authors choose to use a coordinate list representation for their molecule which naturally lends it's self to immutability. Now I'm not going to rant too much about why immutability is great but it got me thinking, how could one write an efficient immutable adjacency list representation? There is already an immutable version in the Graph for Scala library but I wanted to have a lightweight implementation for Java. I've been using an adjacency list a lot recently (see previous posts) and writing an immutable graph would definitely be useful. As a reminder here is a graph and it's representation as an adjacency list and matrix.

Graph API

First of, let us define our API.  Wikipedia provides a nice summary of one Graph - Abstract Data Type which we can use. I'm making use of Java 8 - Virtual Extensions here so we only need implement the 'add' and 'neighbors' operations. It should be noted we can't use the primitives for the collections here as we can't make a read only array. As we're not doing arithmetic and thanks to integer caching there is only a tiny performance hit.

Code 1 - Graph API
public interface Graph {
 
    /** neighbors of v */
    public Collection<Integer> neighbors(int v);
    
    /** add a connection between u and v */
    public Graph add(int u, int v);
    
    /** determine whether u and v are adjacent */
    public default boolean adjacent(int u, int v) {
        return neighbors(u).contains(v);
    }
    
    /** degree of vertex v */
    public default int degree(int v) {
        return neighbors(v).size();
    }    
}

Mutable implementation 

To begin, we define a mutable implementation which simply stores a list of lists. We will base our other implementations on this. For conciseness invalid inputs are not handled.

Code 2 - MutableAdjacencyList
public final class MutableAdjacencyList implements Graph {
 
    private final List<List<Integer>> vs;
 
    public MutableAdjacencyList(List<List<Integer>> vs) {
        this.vs = vs;
    }  
 
    public Collection<Integer> neighbors(int v) {
        return vs.get(v);
    }
 
    public MutableAdjacencyList add(int u, int v) {
 
        // ensure capacity
        while (u >= vs.size() || v >= vs.size())
            vs.add(new ArrayList<>(1));
 
        // associate u with v and v with u
        vs.get(u).add(v);
        vs.get(v).add(u);
 
        return vs;        
    } 
}

This will work perfectly well however we have not encapsulated our fields and one could manipulate the internals without going through our defined API. Here we can add a directed edge to an undirected graph.

Code 3 - MutableAdjacencyList usage
Graph g = new MutableAdjacencyList(...).add(0,1)
                                       .add(1,3)
                                       .add(2,3);
// state: {{1},{0,3},{3},{2,1}}
// we can change the internal state without going
// through the API
g.neighbours(0).add(20); 
 
// new state: {{1,20},{0,3},{3},{2,1}}

One obvious fix would be wrap the list when the neighbors are requested. This wrapping provides a read only view of the data.

Code 4 - Encapsulated
public Collection neighbors(int v) {
    return Collections.unmodifiableList(vs.get(v));
}

This successfully stops unmanaged changes to the internal state but adds a penalty (albeit small) for access operations.

Defensive implementation

Generally we're going to want to create our graph once and then perform multiple access operations. Therefore we should avoid creating a new wrapper for each access to a vertices neighbors. Instead of adding the modifiable wrapper on access we can do it just once. As shown below we can make a few simple modifications to the mutable implementation.

Code 5 - DefensiveAdjacencyList
public final class DefensiveAdjacencyList implements Graph {
 
    private final List<List<Integer>> vs;
 
    public DefensiveAdjacencyList(List<List<Integer>> vs) {
        List<List<Integer>> tmp = new ArrayList<>(vs);
        // defensive copy
        for (int v = 0; v < tmp.size(); v++)
            tmp.set(v, Collections.unmodifiableList(new ArrayList<>(tmp.get(v))));
        this.vs = Collections.unmodifiableList(vs);
    }
 
    public Collection<Integer> neighbors(int v) {
        return vs.get(v);
    }
 
    public DefensiveAdjacencyList add(int u, int v) {
 
        List<List<Integer>> tmp = new ArrayList<>(vs);
 
        while (u >= tmp.size() || v >= tmp.size())
            tmp.add(new ArrayList<>(1));
 
        tmp.set(u, new ArrayList<>(tmp.get(u)));
        tmp.set(v, new ArrayList<>(tmp.get(v)));
 
        tmp.get(u).add(v);
        tmp.get(v).add(u);
 
        return new DefensiveAdjacencyList(tmp); 
    } 
}

We have modified the add operation and as we're allowing input in the constructor we perform a defensive copy. Note in the constructor we have to copy each neighbor list as the wrapper only provides a read only view and does not protect against modification to the underlying list. The follow snippet demonstrates that if we are not careful one can still change the unmodifiable list b by changing a.

Code 6 - Read only view
List a = new ArrayList();
a.add("how many items?");
List b = Collections.unmodifiableList(a);
 
System.out.println("there are " + b.size() + " items"); // 1
a.add("are you sure?");
System.out.println("there are now " + b.size() + " items"); // 2

This is a very simple immutable implementation however it is hideously slow to add new neighbors. If we remove the public constructor and force all update operations through our own methods we have complete control of the lists and can do a lot better.

Update only implementation

This next implementation has a private constructor. We now do not need to copy every neighbor list as only we have access to the constructor and can cut down on our copy operations. Granted we could also do this above but the point is we really want to fully encapsulate the operations on our graph.

Code 7 - UpdateOnlyAdjacencyList
public final class UpdateOnlyAdjacencyList implements Graph {
 
    private final List<List<Integer>> vs;
 
    // private constructor - we have complete control over vs
    private UpdateOnlyAdjacencyList(List<List<Integer>> vs) {        
        this.vs = vs;
    }
 
    public Collection<Integer> neighbors(int v) {
        return vs.get(v);
    }
 
    public UpdateOnlyAdjacencyList add(int u, int v) {
        
        List<List<Integer>> tmp = new ArrayList<>(vs);
 
        while (u >= tmp.size() || v >= tmp.size())
            tmp.add(Collections.emptyList());
 
        tmp.set(u, include(tmp.get(u), v));
        tmp.set(v, include(tmp.get(v), u));
 
        return new UpdateOnlyAdjacencyList(tmp);        
    }
  
    // helper method for adding a value to an immutable list
    private static List<Integer> include(List<Integer> list, int x) {
        List<Integer> mutable = new ArrayList<>(list);
        mutable.add(x);
        return Collections.unmodifiableList(mutable);
    } 
}

Performance

To benchmark how each implementation performed I incrementally generated 1000 random graphs with between 10 and 100 vertices. Each vertex had 0.08 probability that it is connected to another vertex. The plot below shows the average time taken by each implementation to generate a each graph (50 repeats).

The update only implementation performs much better than the full defensive copy. Admittedly an extreme case but it demonstrates if we were to open up the implementation to allow mutable input (as we did in the constructor) the cost of doing those copies can be very expensive.

We can extrapolate out the timings and determine roughly how long it would take each implementation to construct 50,000 graphs. If we plot on a continuous scale we really only see a noticeable a difference between the mutable and update after |E| = 100. At an |E| of 200 the defensive copy now takes upwards of 80 seconds whilst the other two both fall below 2.5 seconds.

Although we see closer performance with the update only implementation as the requirements grow we still see divergence. Now, I deliberately started with a poor implementation (DefensiveCopy) just see what we could do wrong. What you really want to do to tune the performance is to combined the update only with a builder. Similar to how the Java library provides a StringBuilder for assembly a large number immutable strings we can define a GraphBuilder for building the immutable graphs. This allows to have a buffer before we fix the state of our graph and in some cases can actually offer a small performance improvement do to fewer resize operations.

Fully Immutable

Finally, it should be noted that the Google Guava library provides truly immutable collections (opposed to the read only wrappers) however there doesn't seem to be one which provides update operations, that is, create a new immutable list with a single item changed. In theory you could get very fast immutability if you only update the part that was actually changing. That is not simple.

Links

[1] - The value of values. http://www.infoq.com/presentations/Value-Values
[2] - Scala Graph https://www.assembla.com/spaces/scala-graph/wiki
[3] - Wikipedia Graph ADT Article - http://en.wikipedia.org/wiki/Graph_(abstract_data_type)
[4] - Guava Immutable Collections - http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained

Appendix

Scala does provide an immutable Vector offering constant time update operations. Here is what our implementation would look like.


Code 8 - Immutable graph in Scala
class AdjacencyList(vs: Vector[List[Int]]) extends Graph {
 
  def adjacent(u: Int, v: Int) = vs(u).contains(v)
 
  def neighbors(v: Int) = vs(v)
 
  def add(u: Int, v: Int) = {    
    // ensure capacity
    val n  = 1 + (u max v) - size()
    val vs = this.vs ++ Vector.fill(n)(List[Int]())
    
    // update u, v neighbor lists
    new AdjacencyList(vs.updated(u, v :: vs(u))
                        .updated(v, u :: vs(v)))
  }
 
}