Say you want to route two (or three, or four…) paths through a network between the same endpoints, and you want to make sure that they don’t overlap, so that if one path fails you can be pretty confident that the other paths are unaffected. The “naive” approach here might be to use Djikstra’s algorithm to find the shortest path through the network, then remove those links from the network and run it again to find the shortest path in the modified network.

This works sometimes but there are a bunch of cases where it can fail, because what you really need to do is find the shortest disjoint pair of paths. In this book, Dr. Ramesh Bhandari of AT&T describes many different techniques to find these paths.  On the flight back from London I thought I’d try implementing his algorithm for shortest edge-disjoint pair routing.  I didn’t quite get it done on one battery charge, but I’ve finished off a first attempt.  The results are on GitHub, here.

Note: the unit test here shows a topology where the naive approach of running Djikstra twice will fail, but Bhandari’s algorithm will find the correct pair of paths.

I’m sure there are a million web pages out there that cover this already but here’s how I do it:

First, grep the interesting URIs out of the access log.  Here I look for everything ending in .png or .jpg – a better regex would filter out all the WordPress stuff, all the thumbnails, all the stuff that didn’t return 200, etc.

cat logs/www_log | awk '{print $7}' | grep -E "\.jpg|\.png$"

Then a quick awk script will indicate the number of times each image has been downloaded.  Because this script keeps all the image URIs in an associative array, it probably won’t scale to millions of images.  (But it will scale to millions of hits on a few images)

awk '{ if ($0 in linecount) linecount[$0]++; else linecount[$0] = 1} END { for (elem in linecount) print elem" "linecount[elem] }' | sort -r -n -k 2 | wc -l

Pipe the two commands together for UNIXy goodness. Produces output like so (with a more aggressive filter regex in step 1):

/wp-content/uploads/2010/01/IMG_7203.jpg 1543
/wp-content/uploads/2010/01/IMG_5761.jpg 1466
/wp-content/uploads/2010/01/IMG_5765.jpg 857
/wp-content/uploads/2010/01/IMG_5764.jpg 732
/wp-content/uploads/2010/01/IMG_5763.jpg 678
/wp-content/uploads/2010/01/IMG_7197.jpg 409
/wp-content/uploads/2010/01/IMG_7198.jpg 406
/wp-content/uploads/2010/01/box-plans-6.jpg 102
/wp-content/uploads/2010/01/box-plans-5.png 87
/wp-content/uploads/2010/01/box-plans-4.png 34
/wp-content/uploads/2010/01/box-plans-2.png 33
/wp-content/uploads/2010/01/box-plans-1.png 26
/wp-content/uploads/2010/01/box-plans-3.png 22

I’ve been fooling around with the Android development platform. It’s quite an adjustment, coming from the iPhone world. I thought I’d post a simple equivalent to the SwingWorker class that works with Android’s Event Dispatch Thread. Here it is:

package ca.razorwire.util;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import android.os.Handler;
import android.os.Looper;
import android.util.Log;

public abstract class UIWorker
{
  private static final ExecutorService __execSvc;
  private static final Handler __edtHandler;

  private static final String TAG = "UIWorker";

  static
  {
    __execSvc = Executors.newSingleThreadExecutor();
    __edtHandler = new Handler( Looper.getMainLooper() );
  }

  public abstract void doInBackground();

  public void done()
  {
    // Log.d(TAG, "done() executing in thread " + Thread.currentThread().getName() );
    // This space intentionally left blank
  }

  public void execute()
  {
    // Log.d(TAG, "execute() executing in thread " + Thread.currentThread().getName() );
    final Runnable doneRunner = new Runnable()
    {
      public void run()
      {
        UIWorker.this.done();
      }
    };

    final Runnable bgRunner = new Runnable()
    {
      public void run()
      {
        // Log.d(TAG, "bgRunner executing in thread " + Thread.currentThread().getName() );
        UIWorker.this.doInBackground();
        __edtHandler.post( doneRunner );
      }
    };
    __execSvc.submit(bgRunner);
  }
}

And here’s a sample usage:

      UIWorker worker = new UIWorker()
      {
        public void doInBackground()
        {
          Log.d( TAG, "Sleeping for a bit." );
          try { Thread.sleep( 10000 ); } catch ( Exception ignore ) {};
        }
      };
      Log.d( TAG, "Executing worker..." );
      worker.execute();
      Log.d( TAG, "Returned from execute()" );

If you uncomment the Log calls in UIWorker, you should see some output like this:

07-08 12:14:11.015: DEBUG/rweeks(1078): Executing worker...
07-08 12:14:11.015: DEBUG/UIWorker(1078): execute() executing in threadmain
07-08 12:14:11.025: DEBUG/UIWorker(1078): bgRunner executing in thread pool-1-thread-1
07-08 12:14:11.035: DEBUG/rweeks(1078): Sleeping for a bit.
07-08 12:14:11.035: DEBUG/rweeks(1078): Returned from execute()
07-08 12:14:21.038: DEBUG/UIWorker(1078): done() executing in thread main

Public domain code, no guarantees, seems to work.