Digraphs are used to model real world systems and therefore the need arises to be able to determine the similarity between two relatively large digraphs. This similarity is in terms of both the structure of the digraphs and the knowledge represented by their vertices and edges.   Two algorithms are presented which derive their basic functionality from the Levenshtein distance algorithm. The Levenshtein algorithm is used in string comparisons to determine similarity. These two algorithms, not only calculate the edit distance between two digraphs, but preserve the operations used to convert one digraph into the other.   The results of the two algorithms are discussed in terms their edit distance cost results and their execution speed. These results are contrasted with one another and with the Levenshtein distance algorithm adapted for representing digraphs. The results indicate that the two proposed algorithms are more accurate in terms of their edit distance calculations than the Levenshtein distance algorithm, but that the Levenshtein algorithm out performs them in terms of execution speed.
['Ilicia Jordaan', 'Linda Marshall']
Edit Distance-based Digraph Similarity