← Back to branch summary

~tapaal-ltl/verifypn/scc-optimise

« back to all changes in this revision

Viewing changes to 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:
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
 
#ifdef ENABLE_TAR
11
 
#ifndef ANTICHAIN_H
12
 
#define ANTICHAIN_H
13
 
 
14
 
#include <vector>
15
 
#include <map>
16
 
#include <unordered_map>
17
 
#include <stack>
18
 
#include <algorithm>
19
 
 
20
 
 
21
 
 
22
 
template<typename T, typename U>
23
 
class AntiChain 
24
 
{
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
 
        bool subsumed(T& el, sset_t& set)
44
 
        {
45
 
            bool exists = false;
46
 
            if(map.size() > (size_t)el)
47
 
            {
48
 
                for(auto& s : map[el])
49
 
                {
50
 
                    if(std::includes(set.begin(), set.end(), s.begin(), s.end()))
51
 
                    {
52
 
                        /*std::cout << "SUBSUMBED BY ";
53
 
                        for(auto& e : s) std::cout << e << ",";
54
 
                        std::cout << std::endl;*/
55
 
                        exists = true;
56
 
                        break;
57
 
                    }
58
 
                }
59
 
            }
60
 
            return exists;
61
 
        }
62
 
        
63
 
        bool insert(T& el, sset_t& set)
64
 
        {
65
 
            bool inserted = false;
66
 
            if(map.size() <= (size_t)el) map.resize(el + 1);
67
 
/*            std::cout << "ANTI (" << (size_t)el << ") -> ";
68
 
            for(auto& e : set) std::cout << e << ",";
69
 
            std::cout << std::endl;*/
70
 
            if(!subsumed(el, set))
71
 
            {
72
 
                auto& chains = map[el];
73
 
                for(int i = chains.size() - 1; i >= 0; --i)
74
 
                {
75
 
                    if(std::includes(chains[i].begin(), chains[i].end(), set.begin(), set.end()))
76
 
                    {
77
 
                        chains.erase(chains.begin() + i);
78
 
                    }
79
 
                }
80
 
                chains.push_back(set);                
81
 
                inserted = true;
82
 
            }
83
 
            else
84
 
            {
85
 
                inserted = false;
86
 
            }
87
 
            
88
 
            return inserted;
89
 
        }  
90
 
};
91
 
 
92
 
 
93
 
#endif /* ANTICHAIN_H */
94
 
 
95
 
#endif
 
 
b'\\ No newline at end of file'