main.cpp

#ifdef _MSC_VER
#pragma warning(disable : 4503)
#endif

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
#include <sstream>

class Transition
{
public:
    Transition(const std::string& label, const std::set<std::string>& ins, const std::set<std::string>& outs):
        label(label), ins(ins), outs(outs)
    {
    }

    std::string label;
    std::set<std::string> ins;
    std::set<std::string> outs;

};

typedef std::set<std::string> Marking;

Marking intersection(const Marking& a, const Marking& b)
{
    Marking ret;
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(ret, ret.begin()));
    return ret;
}

Marking difference(const Marking& a, const Marking& b)
{
    Marking ret;
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(ret, ret.begin()));
    return ret;
}

Marking sum(const Marking& a, const Marking& b)
{
    Marking ret;
    std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(ret, ret.begin()));
    return ret;
}

typedef std::map<Marking, std::map<std::string, Marking>> VisitMap;

std::vector<Transition> filter(const std::vector<Transition>& transitions, const Marking& m, const VisitMap& vmap)
{
    std::vector<Transition> ret;
    const auto it = vmap.find(m);
    std::map<std::string, Marking> labels;
    if(it != vmap.end())
        labels = it->second;

    for(const Transition& t : transitions)
        if(intersection(m, t.ins) == t.ins && labels.find(t.label) == labels.end())
            ret.push_back(t);

    return ret;
}

std::string str(const Marking& a)
{
    std::ostringstream ss;
    ss << "(";
    bool first = true;
    for(const std::string& p : a)
    {
        if(!first)
            ss << ", ";

        ss << p;
        first = false;
    }

    ss << ")";
    return ss.str();
}

int main()
{
    std::vector<Transition> transitions;
    transitions.push_back(Transition("1", { "a", "b" }, { "c", "d" }));
    transitions.push_back(Transition("2", { "c" }, { "a" }));
    transitions.push_back(Transition("3", { "d" }, { "b" }));
    transitions.push_back(Transition("4", { "d" }, { "e" }));

    Marking marking = {"a", "b"};
    VisitMap visited;
    std::set<Marking> unfinished_markings = { marking };
    while(true)
    {
        const std::vector<Transition> enabled = filter(transitions, marking, visited);
        if(enabled.size() > 0)
        {
            const Transition e = enabled.front();
            const Marking new_marking = sum(difference(marking, e.ins), e.outs);
            visited[marking][e.label] = new_marking;
            marking = new_marking;
            unfinished_markings.insert(marking);
        }
        else
        {
            unfinished_markings.erase(marking);
            if(unfinished_markings.empty())
                break;
            else
                marking = *unfinished_markings.begin();
        }
    }//while true

    for(const auto& v : visited)
        for(const auto& v2 : v.second)
            std::cout << str(v.first) << " ---" << v2.first << "--> " << str(v2.second) << std::endl;
}