← Back to branch summary

~tapaal-ltl/verifypn/scc-optimise

« back to all changes in this revision

Viewing changes to include/PetriEngine/TAR/AntiChain.h

  • Committer: srba.jiri at gmail
  • Date: 2020-09-11 14:23:39 UTC
  • mfrom: (213.1.151 interval_tar)
  • Revision ID: srba.jiri@gmail.com-20200911142339-bq9328s1gppw24uj
merged in lp:~verifypn-maintainers/verifypn/interval_tar doing 
- Implements TAR w/o z3, but using a simple integer inference engine for Hoare logic.
 - Replaces LP-Solve with GLPK, reduces computation-time and memory overhead
 - Implements new global properties, translated into CTL formulae.

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/PetriEngine/TAR/AntiChain.h
 
1
// -*- mode: C++; c-file-style: "stroustrup"; c-basic-offset: 4; indent-tabs-mode: nil; -*-
 
2
///////////////////////////////////////////////////////////////////////////////
 
3
//
 
4
// This file is a part of UPPAAL.
 
5
// Copyright (c) 1995 - 2006, Uppsala University and Aalborg University.
 
6
// All right reserved.
 
7
//
 
8
///////////////////////////////////////////////////////////////////////////////
 
9
 
 
10
#ifndef ANTICHAIN_H
 
11
#define ANTICHAIN_H
 
12
 
 
13
#include <vector>
 
14
#include <map>
 
15
#include <unordered_map>
 
16
#include <stack>
 
17
#include <algorithm>
 
18
 
 
19
 
 
20
 
 
21
template<typename T, typename U>
 
22
class AntiChain 
 
23
{
 
24
    using set_t     = std::set<U>;
 
25
    using sset_t    = std::vector<U>;
 
26
    using smap_t    = std::vector<std::vector<sset_t>>;
 
27
    
 
28
    smap_t map;
 
29
    
 
30
    struct node_t {
 
31
        U key;
 
32
        std::vector<node_t*> children;
 
33
    };
 
34
    
 
35
    public:
 
36
        AntiChain(){};
 
37
        
 
38
        void clear()
 
39
        {
 
40
            map.clear();
 
41
        }
 
42
 
 
43
        template<typename S>
 
44
        bool subsumed(T& el, const S& set)
 
45
        {
 
46
            bool exists = false;
 
47
            if(map.size() > (size_t)el)
 
48
            {
 
49
                for(auto& s : map[el])
 
50
                {
 
51
                    if(std::includes(set.begin(), set.end(), s.begin(), s.end()))
 
52
                    {
 
53
                        /*std::cout << "SUBSUMBED BY ";
 
54
                        for(auto& e : s) std::cout << e << ",";
 
55
                        std::cout << std::endl;*/
 
56
                        exists = true;
 
57
                        break;
 
58
                    }
 
59
                }
 
60
            }
 
61
            return exists;
 
62
        }
 
63
        
 
64
        template<typename S>
 
65
        bool insert(T& el, const S& set)
 
66
        {
 
67
            bool inserted = false;
 
68
            if(map.size() <= (size_t)el) map.resize(el + 1);
 
69
/*            std::cout << "ANTI (" << (size_t)el << ") -> ";
 
70
            for(auto& e : set) std::cout << e << ",";
 
71
            std::cout << std::endl;*/
 
72
            if(!subsumed(el, set))
 
73
            {
 
74
                auto& chains = map[el];
 
75
                for(int i = chains.size() - 1; i >= 0; --i)
 
76
                {
 
77
                    if(std::includes(chains[i].begin(), chains[i].end(), set.begin(), set.end()))
 
78
                    {
 
79
                        chains.erase(chains.begin() + i);
 
80
                    }
 
81
                }
 
82
                chains.emplace_back(sset_t{set.begin(), set.end()});                
 
83
                inserted = true;
 
84
            }
 
85
            else
 
86
            {
 
87
                inserted = false;
 
88
            }
 
89
            
 
90
            return inserted;
 
91
        }  
 
92
};
 
93
 
 
94
 
 
95
#endif /* ANTICHAIN_H */