Detecting Meta-Patterns from Frameworks Using Hybrid Genetic Algorithm

  • Authors

    • Tapan Kant
    • Manjari Gupta
    • Anil Kumar Tripathi
    • Meeta Prakash
    2018-04-18
    https://doi.org/10.14419/ijet.v7i2.20.16732
  • Genetic Algorithm, meta-patterns, Object-oriented framework, Sub-graph.

  • Meta-patterns are a sort of basic object-oriented constructs that have been used to design an object-oriented framework. It has been used to precisely describe possible design pattern of a framework at meta-level to manifest framework hot-spots and its corresponding adaptability. The present study is an attempt to develop a genetic algorithm approach for detecting the types and numbers of meta-patterns. For this purpose we have converted the UML class diagram of object-oriented framework and meta-patterns into directed graph and applied hybrid genetic algorithm. The obtained results from the proposed algorithm are further validated manually with the recall and precision percentage of 86.20 and 80.64 respectively. Overall the study demonstrates the utility of the uniquely proposed algorithm for the near accurate identification of meta-patterns for high reusability. This can be applied on frameworks for assessing the evolution process, documentation of hot-spots and reducing the customization effort.

     

  • References

    1. [1] W. Pree, “Hot-spot-driven framework development,†in Summer School on Reusable Architectures in Object-Oriented software Development, pp. 123-127, ACM, 1995.

      [2] W. Pree, “Meta patterns - a means for capturing the essentials of reusable object-oriented design,†in Object-Oriented Programming (M. Tokoro and R. Pareschi, eds.), vol. 821 of Lecture Notes in Computer Science, pp. 150-162, Springer Berlin Heidelberg, 1994.

      [3] R. Schauer, S. Robitaille, F. Martel, and R. Keller, “Hot spot recovery in object-oriented software with inheritance and composition template methods,†in Software Maintenance, 1999. (ICSM ’99) Proceedings. IEEE International Conference on, pp. 220-229, 1999.

      [4] S. Thummalapenta and T. Xie, “Spotweb: Detecting framework hotspots and coldspots via mining open source code on the web,†in Automated Software Engineering, 2008. ASE 2008. 23rd IEEE/ACM International Conference on, pp. 327{336, Sept 2008.

      [5] J. de Lara, R. Bardohl, H. Ehrig, K. Ehrig, U. Prange, and G. Taentzer, “Attributed graph transformation with node type inheritance,†Theoretical Computer Science, vol. 376, no. 3, pp. 139 -163, 2007. Fundamental Aspects of Software Engineering.

      [6] R. Bardohl, H. Ehrig, J. de Lara, and G. Taentzer, “Integrating meta-modelling aspects with graph transformation for efficient visual language definition and model manipulation,†in Fundamental Approaches to Software Engineering (M. Wermelinger and T. Margaria-Steffen, eds.), vol. 2984 of Lecture Notes in Computer Science, pp. 214{228, Springer Berlin Heidelberg, 2004.

      [7] S. Kuske, M. Gogolla, R. Kollmann, and H.-J. Kreowski, “An integrated semantics for uml class, object and state diagrams based on graph transformation,†in Integrated Formal Methods (M. Butler, L. Petre, and K. Sere, eds.), vol. 2335 of Lecture Notes in Computer Science, pp. 11-28, Springer Berlin Heidelberg, 2002.

      [8] A. Maraee and M. Balaban, “Efficient reasoning about finite satisfiability of uml class diagrams with constrained generalization sets,†in Model Driven Architecture- Foundations and Applications (D. Akehurst, R. Vogel, and R. Paige, eds.), vol. 4530 of Lecture Notes in Computer Science, pp. 17-31, Springer Berlin Heidelberg, 2007.

      [9] J. R. Ullmann, “An algorithm for subgraph isomorphism,†J. ACM, vol. 23, pp. 31-42, Jan. 1976.

      [10] P. J. Durand, R. Pasari, J. W. Baker, and C.-c. Tsai, “An efficient algorithm for similarity analysis of molecules,†Internet Journal of Chemistry, vol. 2, no. 17, pp. 1-16, 1999.

      [11] J. J. McGregor, “Backtrack search algorithms and the maximal common subgraph problem,†Software: Practice and Experience, vol. 12, no. 1, pp. 23-34, 1982.

      [12] F. P. Conte Donatello and V. Mario, “Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs.,†Journal of Graph Algorithms and Applications, vol. 11, no. 1, pp. 99-143, 2007.

      [13] H. Bunke, P. Foggia, C. Guidobaldi, C. Sansone, and M. Vento, “A comparison of algorithms for maximum common subgraph on randomly connected graphs,†in Structural, Syntactic, and Statistical Pattern Recognition (T. Caelli, A. Amin, R. Duin, D. de Ridder, and M. Kamel, eds.), vol. 2396 of Lecture Notes in Computer Science, pp. 123-132, Springer Berlin Heidelberg, 2002.

      [14] K. Kim and B.-R. Moon, “Malware detection based on dependency graph using hybrid genetic algorithm,†in Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO ’10, (New York, NY, USA), pp. 1211{1218, ACM, 2010.

      [15] A. Pande, M. Gupta, and A. Tripathi, “A new approach for detecting design patterns by graph decomposition and graph isomorphism,†in Contemporary Computing (S. Ranka, A. Banerjee, K. Biswas, S. Dua, P. Mishra, R. Moona, S.-H. Poon, and C.-L. Wang, eds.), vol. 95 of Communications in Computer and Information Science, pp. 108-119, Springer Berlin Heidelberg, 2010.

      [16] W. Pree, “Hot-spot-driven framework development,†in Summer School on Reusable Architectures in Object-Oriented software Development, pp. 123-127, ACM, 1995.

      [17] J. Choi, Y. Yoon, and B.-R. Moon, “An efficient genetic algorithm for subgraph isomorphism,†in Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12, (New York, NY, USA), pp. 361-368, ACM, 2012.

      [18] M. Mattsson and J. Bosch, “Observations on the evolution of an industrial oo framework,†in Software Maintenance, 1999. (ICSM ’99) Proceedings. IEEE International Conference on, pp. 139-145, 1999.

      [19] M. Mattsson and J. Bosch, “Characterizing stability in evolving frameworks,†in Technology of Object-Oriented Languages and Systems, 1999. Proceedings of, pp. 118-130, Jul 1999.

      [20] E. Gamma, R. Helm, R. Johnson, and J. Vlissides, “Design patterns: elements of reusable object-oriented softwareâ€. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1995.

      [21] R. E. Johnson, “Documenting frameworks using patterns,†in OOPSLA ’92: conference proceedings on Object-oriented programming systems, languages, and applications, (New York, NY, USA), pp. 63-76, ACM, 1992.

      [22] R. Campbell and N. Islam, “A technique for documenting the framework of an object-oriented system,†in Object Orientation in Operating Systems, 1992., Proceedings of the Second International Workshop on, pp. 288-300, Sep 1992.

      [23] K. Beck and R. E. Johnson, “Patterns generate architectures,†in Proceedings of the 8th European Conference on Object-Oriented Programming, ECOOP ’94, (London, UK, UK), pp. 139-149, Springer-Verlag, 1994.

      [24] D. B. Lange and Y. Nakamura, “Interactive visualization of design patterns can help in framework understanding,†in Proceedings of the Tenth Annual Conference on Object-oriented Programming Systems, Languages, and Applications, OOPSLA ’95, (New York, NY, USA), pp. 342-357, ACM, 1995.

      [25] G. E. Krasner and S. T. Pope, “A cookbook for using the model-view controller user interface paradigm in smalltalk-80,†J. Object Oriented Program., vol. 1, pp. 26-49, Aug. 1988.

      [26] I. ParcPlace-Digitalk, VisualWorks: Cookbook. ParcPlace-Digitalk, Incorporated, 1995.

      [27] G. Froehlich, H. J. Hoover, L. Liu, and P. Sorenson, “Hooking into object-oriented application frameworks,†in ICSE ’97: Proceedings of the 19th international conference on Software engineering, (New York, NY, USA), pp. 491-501, ACM, 1997.

      [28] S. Thummalapenta and T. Xie, “Parseweb: A programmer assistant for reusing open source code on the web,†in Proceedings of the Twenty-second IEEE/ACM International Conference on Automated Software Engineering, ASE ’07, (New York, NY, USA), pp. 204-213, ACM, 2007.

      [29] M. E. Fayad, D. C. Schmidt, and R. E. Johnson, “Implementing application frameworks: objectoriented frameworks at work.†New York, NY, USA: John Wiley & Sons, Inc., 1999.

      [30] R. D. Brown, G. Jones, P. Willett, and R. C. Glen, “Matching two-dimensional chemical graphs using genetic algorithms,†Journal of Chemical Information and Computer Sciences, vol. 34, no. 1, pp. 63-70, 1994.

      [31] M. Wagener and J. Gasteiger, “The determination of maximum common substructures by a genetic algorithm: Application in synthesis design and for the structural analysis of biological activity,†Angewandte Chemie International Edition in English, vol. 33, no. 11, pp. 1189-1192, 1994.

      [32] M. Bernardi, M. Cimitile, and G. Di Lucca, “A model-driven graph-matching approach for design pattern detection,†in Reverse Engineering (WCRE), 2013 20th Working Conference on, pp. 172-181, Oct 2013.

      [33] N. Tsantalis, A. Chatzigeorgiou, G. Stephanides, and S. Halkidis, “Design pattern detection using similarity scoring,†Software Engineering, IEEE Transactions on, vol. 32, pp. 896-909, Nov 2006.

      [34] L. Qing-hua, Z. Zhi-xiang, and B. Ke-rong, “Design pattern mining using graph matching,†Wuhan University Journal of Natural Sciences, vol. 9, no. 4, pp. 444-448, 2004.

      [35] R. Ferenc, A. Beszedes, L. Fulop, and J. Lele, “Design pattern mining enhanced by machine learning,†in Software Maintenance, 2005. ICSM’05. Proceedings of the 21st IEEE International Conference on, pp. 295-304, Sept 2005.

      [36] M. Zanoni, F. A. Fontana, and F. Stella, “On applying machine learning techniques for design pattern detection,†Journal of Systems and Software, vol. 103, pp. 102 -117, 2015.

      [37] J. Viljamaa, “Reverse engineering framework reuse interfaces,†in Proceedings of the 9th European Software Engineering Conference Held Jointly with 11th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE-11, (New York, NY, USA), pp. 217-226, ACM, 2003.

      [38] M. Bruch, T. Sch¨afer, and M. Mezini, “Fruit: Ide support for framework understanding,†in Proceedings of the 2006 OOPSLA Workshop on Eclipse Technology eXchange, eclipse ’06, (New York, NY, USA), pp. 55-59, ACM, 2006.

      [39] T. Tourwe and T. Mens, “Automated support for framework-based software,†in Software Maintenance, 2003. ICSM 2003. Proceedings. International Conference on, pp. 148-157, Sept 2003.

      [40] G. Kiczales and J. Lamping, “Issues in the design and specification of class libraries,†in Conference Proceedings on Object-oriented Programming Systems, Languages, and Applications, OOPSLA ’92, (New York, NY, USA), pp. 435-451, ACM, 1992.

      [41] J. Lamping, “Typing the specialization interface,†in Proceedings of the Eighth Annual Conference on Object-oriented Programming Systems, Languages, and Applications, OOPSLA ’93, (New York, NY, USA), pp. 201-214, ACM, 1993.

      [42] M. Mezini, “Maintaining the consistency of class libraries during their evolution,†SIGPLAN Not., vol. 32, pp. 1-21, Oct. 1997.

      [43] P. Steyaert, C. Lucas, K. Mens, and T. D’Hondt, “Reuse contracts: Managing the evolution of reusable assets,†in Proceedings of the 11th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’96, (New York, NY, USA), pp. 268-285, ACM, 1996.

  • Downloads

  • How to Cite

    Kant, T., Gupta, M., Kumar Tripathi, A., & Prakash, M. (2018). Detecting Meta-Patterns from Frameworks Using Hybrid Genetic Algorithm. International Journal of Engineering & Technology, 7(2.20), 350-356. https://doi.org/10.14419/ijet.v7i2.20.16732