wf_loop_detector.h File Reference

Loop pattern detection in a workflow network. More...

#include <cstddef>
#include <map>
#include <set>
#include <vector>
#include "line/api/wf/wf_link_matrix.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for wf_loop_detector.h:

Go to the source code of this file.

Classes
struct	line::wf::ExpectedIterations< T >
	1/(1-p), with the p >= 1 divergence reported rather than encoded. More...
struct	line::wf::LoopStats< T >
	Mirrors the Java getLoopStats map. More...

Namespaces
namespace	line
namespace	line::wf

Functions
template<class T>
std::vector< int >	line::wf::detect_loops (const Matrix< T > &linkMatrix, const std::vector< int > &serviceNodes, const std::vector< int > &routerNodes, const std::vector< int > &joinNodes=std::vector< int >())
template<class T>
T	line::wf::get_loop_probability (int serviceNode, const Matrix< T > &linkMatrix, const std::vector< int > &routerNodes)
	Probability on the router-to-service edge that closes the loop, 0 when the node is not on a simple loop.
template<class T>
bool	line::wf::validate_loop_pattern (int loopNode, const Matrix< T > &linkMatrix, const std::vector< int > &routerNodes)
	True when the node still has the service -> router -> service structure.
template<class T>
ExpectedIterations< T >	line::wf::get_expected_loop_iterations (const T &loopProbability)
	Mean number of visits of a geometric loop, 1/(1-p).
template<class T>
LoopStats< T >	line::wf::get_loop_stats (const std::vector< int > &loopNodes, const Matrix< T > &linkMatrix, const std::vector< int > &routerNodes)
	Count and moments of the loop probabilities and iteration counts.

Detailed Description

Loop pattern detection in a workflow network.

Templated port of jar/src/main/java/jline/api/wf/Wf_loop_detector.java (no MATLAB counterpart, so the JAR is the reference). Two mechanisms:

• a SIMPLE loop is a service node with an edge to a router that has an edge back to it, the two-hop rework loop that a workflow model builds for a "repeat the activity with probability p" construct;
• a COMPLEX loop is a service node inside a strongly connected component of more than one node that also contains a router or a join, found by Tarjan's algorithm. Only looked for when join nodes are supplied, exactly as in the reference.

The five public methods of the Java class are kept 1:1: detect_loops, get_loop_probability, validate_loop_pattern, get_expected_loop_iterations, get_loop_stats.

Traversal plus, in the statistics, the geometric mean number of iterations 1/(1-p) and averages: sums, one division each. Finite field computation, so this instantiates at exact arithmetic and the expected iteration count of a rational loop probability is an exact rational. No transcendental gate.

The reference returns GlobalConstants.Inf when the loop probability reaches one. An exact rational field has no infinity, so get_expected_loop_iterations returns ExpectedIterations with an explicit infinite flag instead of a sentinel value; get_loop_stats drops the infinite entries, which is what the reference's Double.isFinite filter does.

Definition in file wf_loop_detector.h.