spn_traps.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_API_SPN_SPN_TRAPS_H
#define LINE_API_SPN_SPN_TRAPS_H
 
/**
 * @file
 * @ingroup api_spn
 * All minimal traps of a stochastic Petri net (Murata 1989, sec. VI-A). A
 * trap Q has Q* contained in *Q: once marked it stays marked. Traps are the
 * siphons of the reverse net, so the enumeration and its worst-case
 * exponential cost are those of spn_siphons with Pre and Post swapped.
 * marked(i) is true when trap i holds a token at m0. The check is
 * structural: inhibitor arcs, priorities and the timed/immediate split are
 * ignored. MATLAB twin: matlab/src/api/spn/spn_traps.m.
 */
 
#include <cstddef>
#include <vector>
 
#include "line/api/spn/spn_net.h"
 
namespace line {
namespace spn {
 
struct SpnTraps {
    std::vector<std::size_t> places;    ///< 1-based node indices, in level order
    std::vector<std::vector<int>> Q;    ///< one minimal trap per row (0/1 over levels)
    std::vector<bool> marked;           ///< trap i holds a token at m0
    std::vector<long long> m0;
};
 
template <class T>
SpnTraps spn_traps(const qn::NetworkStruct<T>& sn,
                   const std::vector<double>& init = std::vector<double>()) {
    const detail::SpnNet net = detail::spn_build_net(sn, "spn_traps");
    SpnTraps out;
    out.places = net.places;
    out.m0 = detail::spn_initmarking(sn, net, init, "spn_traps");
    const std::vector<std::vector<bool>> L = detail::spn_minsiphons(net.post, net.pre);
    out.Q = detail::spn_sets_to_int(L);
    out.marked.assign(L.size(), false);
    for (std::size_t i = 0; i < L.size(); ++i)
        for (std::size_t l = 0; l < net.n; ++l)
            if (L[i][l] && out.m0[l] > 0) out.marked[i] = true;
    return out;
}
 
}  // namespace spn
}  // namespace line
 
#endif  // LINE_API_SPN_SPN_TRAPS_H