You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Oliver Kopp <ko...@gmail.com> on 2013/05/28 11:36:31 UTC
[Graph] Missing algorithms
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
[Graph] Missing algorithms
Posted by Oliver Kopp <ko...@gmail.com>.
Dear Bruno,
> He's willing to contribute to commons-graph too. Do you know if there's any algorithm that would be easier to implement and that no one is working on porting to commons-graph ATM, please?
I'm not tracking a list of who is porting which algorithm to
commons-graph. I think, that should be tracked in JIRA at
https://issues.apache.org/jira/browse/SANDBOX-458, possibly as sub
tasks :)
What is not in the list, missing and IMHO easy to implement is "A
Simple, Fast Dominance Algorithm by Cooper, Keith D. and Harvey,
Timothy J. and Kennedy, Ken".
There is an GPL implementation based on JGraphT
(com.jopdesign.wcet.graphutils.Dominators<V, E>), but I'm currently
not finding the source itself. Since Apache does not want to be
infected by GPL code, it might be better to "just" implement the paper
:)
Cheers,
Oliver
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Graph] Missing algorithms
Posted by "Bruno P. Kinoshita" <br...@yahoo.com.br>.
Hi Oliver!
Kudos for the detailed information regarding the missing algorithms in commons-graph. I've a friend who contributes to some OSS projects and is also interested in graphs.
He's willing to contribute to commons-graph too. Do you know if there's any algorithm that would be easier to implement and that no one is working on porting to commons-graph ATM, please?
Thank you!
Bruno P. Kinoshita
http://kinoshita.eti.br
http://tupilabs.com
--- Em ter, 28/5/13, Oliver Kopp <ko...@gmail.com> escreveu:
> De: Oliver Kopp <ko...@gmail.com>
> Assunto: [Graph] Missing algorithms
> Para: dev@commons.apache.org
> Data: Terça-feira, 28 de Maio de 2013, 6:36
> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org