wf_branch_detector.h File Reference

Branch (probabilistic choice) pattern detection in a workflow network. More...

#include <algorithm>
#include <cmath>
#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_branch_detector.h:

Go to the source code of this file.

Classes
struct	line::wf::BranchPattern< T >
	Mirrors the Java BranchPattern. More...
struct	line::wf::BranchDiversity< T >
	Mirrors the Java calculateBranchDiversity map. More...
struct	line::wf::BranchStats< T >
	Mirrors the Java getBranchStats map. More...
struct	line::wf::BranchAlternative< T >
	One alternative of a branch: the node and its probability. More...

Namespaces
namespace	line
namespace	line::wf

Functions
template<class T>
std::vector< BranchPattern< T > >	line::wf::detect_branches (const Matrix< T > &linkMatrix, const std::vector< int > &serviceNodes, const std::vector< int > &joinNodes)
template<class T>
bool	line::wf::validate_branch_pattern (const BranchPattern< T > &pattern, const Matrix< T > &linkMatrix)
	Probabilities sum to one within 1e-2 and every alternative is a fork successor.
template<class T>
BranchDiversity< T >	line::wf::calculate_branch_diversity (const BranchPattern< T > &pattern)
	Shannon entropy of the branch probabilities, the same entropy normalized by log(n), the Gini coefficient of the probability vector, and the reciprocal of the largest probability.
template<class T>
BranchStats< T >	line::wf::get_branch_stats (const std::vector< BranchPattern< T > > &patterns)
	Count, total, mean/max/min alternatives, and the mean entropy and balance.
template<class T>
BranchAlternative< T >	line::wf::find_most_probable_branch (const BranchPattern< T > &pattern)
	The alternative with the largest probability.
template<class T>
BranchAlternative< T >	line::wf::find_least_probable_branch (const BranchPattern< T > &pattern)
	The alternative with the smallest probability.

Detailed Description

Branch (probabilistic choice) pattern detection in a workflow network.

Templated port of jar/src/main/java/jline/api/wf/Wf_branch_detector.java (no MATLAB counterpart, so the JAR is the reference). A branch point is a node with more than one outgoing edge of which at least two lead to a service node; the branch is accepted when the probabilities of those service edges sum to one within 1e-2, and it is annotated with the first join node reachable from every branch alternative.

The six public methods of the Java class are kept 1:1: detect_branches, validate_branch_pattern, calculate_branch_diversity, get_branch_stats, find_most_probable_branch, find_least_probable_branch.

ARITHMETIC. detect_branches, validate_branch_pattern and the two extremal queries only add and compare probabilities, so they are finite field computations and instantiate at exact arithmetic; the 1e-2 slack on the branch probability sum is a structural admission threshold inherited from the reference, not a rounding allowance, so it is kept in every instantiation. calculate_branch_diversity and get_branch_stats compute the Shannon entropy of the branch probabilities and therefore need log; both carry the transcendental gate.

REFERENCE DEFECT (JAR): calculateBranchDiversity divides the Gini sum by (n-1), so a one-alternative pattern yields a division by zero (NaN in Java). The port rejects n < 2 with an InputError instead of returning a NaN; detect_branches never emits such a pattern, so no detected pattern is affected.

Definition in file wf_branch_detector.h.