MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison. Kpodjedo, S., Ricca, F., Galinier, P., Antoniol, G., & Guéhéneuc, Y. Transactions on Software Engineering (TSE), 39(8):1090–1111, IEEE CS Press, Feburary, 2013. 23 pages.
MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison [pdf]Paper  abstract   bibtex   
Matching algorithms play a fundamental role in many important but difficult software engineering activities, especially design evolution analysis and model comparison. We present MADMatch, a fast and scalable Many-to-many Approximate Diagram Matching approach based on an Error-Tolerant Graph matching (ETGM) formulation. Diagrams are represented as graphs, costs are assigned to possible differences between two given graphs, and the goal is to retrieve the cheapest matching. We address the resulting optimisation problem with a tabu search enhanced by the novel use of lexical and structural information. Through several case studies with different types of diagrams and tasks, we show that our generic approach obtains better results than dedicated state-of-the-art algorithms, such as AURA, PLTSDiff or UMLDiff, on the exact same datasets used to introduce (and evaluate) these algorithms.

Downloads: 0