Weighted directed graph clustering

I had a really huge sets of molecules and it's I'd like to compare according to various factors. So I created a similarity measure which was very informative and fitted for comparing different types of molecules. After I introduced comparing between two elements I'd like to go further and try to cluster them, however I've got a problem, my similarity measure is not reflexive, i.e. $dist(A,B)!=dist(B,A)$ (though it satisfies triangle inequality). And I have no problem about it since it represents the problem of my interest perfectly. I generated the distance matrix ( or dissimilarity, my measure is bounded $[0,1]$ so it could be converted to similarity as well ).

I thought that clustering with asymmetric distances isn't common thing, so there is not much algorithms implemented (only ones that I know are OPTICS and DBSCAN, but as I tried they are no good), so I decided maybe I should change this problem to the problem of clustering strongly connected directed graph with weights. Maybe someone is aware of such issue and knows some usable implementation of it?

I found Tarjan's article, so maybe someone is familiar with the approach described there and knows possible implementation.

This question is also methodological. Maybe I should check another clustering algorithms, however I don't want to change my measure formula.

-
Checking if a distance function satisfies triangle inequality may be useful too... –  Daved May 13 '13 at 22:02
Thank you, I forgot to mention. My distance function satisfies triangle inequality. –  user974514 May 13 '13 at 22:24
I'm interested in a solution to this. Have you figured out something yet. –  yati sagade Sep 29 '14 at 10:05