An algorithm for a decomposition of weighted digraphs: with applications to life cycle analysis in ecology

摘要

In the analysis of organism life cycles in ecology, comparisons of life cycles between species or between different types of life cycles within species are frequently conducted. In matrix population models, partitioning of the elasticity matrix is used to quantify the separate contributions of different life cycles to the population growth rate. Such partition is equivalent to a decomposition of the life cycle graph of the population. A graph theoretic spanning tree method to carry out the decomposition was formalized by Wardle [Ecology 79(7), 2539–2549 (1998)]. However there are difficulties in realizing a suitable decomposition for complex life histories using the spanning-tree method. One of the problems is the occurrence of life cycles that contain contradictory directions that defy biological interpretation. We propose an algorithmic approach for decomposing a directed, weighted graph. The graph is to be decomposed into two parts. The first part is a set of simple cycles that contain no contradictory directions and that consist of edges of equal weight. The second part of the decomposition is a subgraph in which no such simple cycles are obtainable. When applied to life cycle analysis in ecology, the proposed method will guarantee a complete decomposition of the life cycle graph into individual life cycles containing no contradictory directions.