Hi, In a discussion with Simone, we thought it would be a good idea of having a list of missing algorithms in Apache Commons Graph. I compiled a first shot for such a list in https://issues.apache.org/jira/browse/SANDBOX-458.
Although there are BSD-licensed graph-libraries, jBPT is the only library offering algorithms which are useful in the context of business process management (BPM), especially analysis of business processes [1]. Unfortunately, jBPT is licensed under LGPL. In the context of BPM, a transformation of different languages comes important. For instance, it is desired to transform BPMN to BPEL to enable the usage of Workflow Engines such as Apache ODE with BPMN as input model. I'm in the middle of such a transformation. I've based it on jBPT since I wasn't aware up then that LGPL causes problems. I read a BPMN file into a graph and parse it with jBPT into an RPST [2], which is then interpreted an transformed to BPEL. The RPST itself relies on an SPQR tree [3]. There is an implementation for RPST based on [2], but this implementation uses a C library being GPL-licensed. There is an improvement of the algorithm presented in [4], but the only implementation is jBPT. If someone supported me in getting an Apache-based SPQR and RPST implementation, I'd be very happy. Cheers, Oliver [1] Artem Polyvyanyy and Matthias Weidlich. Towards a Compendium of Process Technologies: The jBPT Library for Process Model Analysis. Proceedings of the Forum of the 25th International Conference on Advanced Information Systems Engineering (CAiSE Forum'13), Valencia, Spain, 2013. To appear. [2] Vanhatalo, J.; Völzer, H. & Koehler, J. Dumas, M. The Refined Process Structure Tree BPM'08: Business Process Management, 6th International Conference, BPM 2008, Springer, 2008, 5240, 100-115 [3] Gutwenger, C. & Mutzel, P. A Linear Time Implementation of SPQR-Trees Graph Drawing, Springer Berlin Heidelberg, 2001, 1984, 77-90 [4] Polyvyanyy, A.; Vanhatalo, J. & Völzer, H. Simplified Computation and Generalization of the Refined Process Structure Tree Web Services and Formal Methods, Springer Berlin Heidelberg, 2011, 6551, 25-41
