Identificación eficiente de componentes fuertemente conexas en la causalización de grandes modelos orientados a objetos

Abstract

Este artículo describe un algoritmo para encontrar componentes fuertemente conexas (CFC) de grafos dirigidos que presentan patrones repetitivos en su estructura. Dichos grafos pueden ser definidos de manera compacta utilizando Set-Based Graphs (SBG). Aprovechando esta representación, el costo computacional del algoritmo propuesto no varia al incrementar la cantidad de vértices y aristas presentes en el mismo patrón.Su principal aplicación es la detección de lazos algebraicos durante la causalización de modelos orientados a objetos que cuentan con arreglos de variables y ecuaciones. De este modo el algoritmo propuesto preserva y retorna un resultado compacto, lo cual es útil para generar código de simulación eficiente.Además de presentar el algoritmo en cuestión, el artículo incluye resultados teóricos relativos a su complejidad computacional. Por último se analiza el rendimiento real del algoritmo en dos modelos con distintos tipos de lazos algebraicos.

This article describes an algorithm that finds strongly connected components (SCC) in directed graphs with repetitive patterns in its structure. These graphs can be compactly defined using the Set-Based Graphs (SBG) representation. This way, the computational cost of the proposed algorithm is independent of the number of verticesand edges present in the same pattern.The main application is the detection of algebraic loops during the causalization of object oriented models defined using arrays of variables and equations. This way the algorithm preserves and returns a compact result, which is convenient to generate efficient simulation code.Besides the description of the proposed procedure, the article includes theoretical results regarding its time complexity. Finally, two examples of two models with different types of algebraic loops are presented at the end of this work.