← Back to branch summary

~verifypn-cpn/verifypn/colored

« back to all changes in this revision

Viewing changes to PetriEngine/Structures/DistanceMatrix.cpp

  • Committer: Jonas Finnemann Jensen
  • Date: 2011-09-15 13:30:00 UTC
  • Revision ID: jopsen@gmail.com-20110915133000-wnywm1odf82emiuw
Import of sources from github

Show diffs side-by-side

added added

removed removed

Lines of Context:
PetriEngine/Structures/DistanceMatrix.cpp
 
1
/* PeTe - Petri Engine exTremE
 
2
 * Copyright (C) 2011  Jonas Finnemann Jensen <jopsen@gmail.com>,
 
3
 *                     Thomas Søndersø Nielsen <primogens@gmail.com>,
 
4
 *                     Lars Kærlund Østergaard <larsko@gmail.com>,
 
5
 * 
 
6
 * This program is free software: you can redistribute it and/or modify
 
7
 * it under the terms of the GNU General Public License as published by
 
8
 * the Free Software Foundation, either version 3 of the License, or
 
9
 * (at your option) any later version.
 
10
 * 
 
11
 * This program is distributed in the hope that it will be useful,
 
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
 * GNU General Public License for more details.
 
15
 * 
 
16
 * You should have received a copy of the GNU General Public License
 
17
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
18
 */
 
19
#include "DistanceMatrix.h"
 
20
 
 
21
namespace PetriEngine{
 
22
namespace Structures{
 
23
 
 
24
DistanceMatrix::DistanceMatrix(const PetriNet& net){
 
25
        _dim = net.numberOfPlaces();
 
26
        _matrix = new unsigned int[(_dim * _dim - _dim) + (_dim * _dim)];
 
27
        pm = _matrix + (_dim * _dim - _dim);
 
28
        generate(net);
 
29
}
 
30
 
 
31
DistanceMatrix::~DistanceMatrix(){
 
32
        if(_matrix)
 
33
                delete[] _matrix;
 
34
        _matrix = NULL;
 
35
}
 
36
 
 
37
#define MIN(a,b)        (a < b ? a : b)
 
38
#define MAX(a,b)        (a > b ? a : b)
 
39
 
 
40
void DistanceMatrix::generate(const PetriNet& net){
 
41
        for(size_t i = 0; i < _dim; i++){
 
42
                for(size_t j = 0; j < _dim; j++){
 
43
                        d(j, i) = INFINITE_DISTANCE;
 
44
                }
 
45
        }
 
46
        // Generate the initial connections
 
47
        for(size_t p1 = 0; p1 < _dim; p1++){
 
48
                d(p1, p1) = 0;
 
49
                for(size_t t = 0; t < net.numberOfTransitions(); t++){
 
50
                        if(net.inArc(p1,t) - net.outArc(t, p1) > 0){
 
51
                                for(size_t p2 = 0; p2 < _dim; p2++){
 
52
                                        if(net.outArc(t, p2) - net.inArc(p2, t) > 0){
 
53
                                                d(p1, p2) = 1;
 
54
                                        }
 
55
                                }
 
56
                        }
 
57
                }
 
58
        }
 
59
        // Floyd-Warshall
 
60
        for(size_t k = 0; k < _dim; k++){
 
61
                for(size_t i = 0; i < _dim; i++){
 
62
                        for(size_t j = 0; j < _dim; j++){
 
63
                                unsigned int D = d(i,k) + d(k,j);
 
64
                                if(d(i,k) >= INFINITE_DISTANCE || d(k,j) >= INFINITE_DISTANCE)
 
65
                                        D = INFINITE_DISTANCE;
 
66
                                d(i, j) = MIN(d(i, j), D);
 
67
                        }
 
68
                }
 
69
        }
 
70
        // Generate place order lists
 
71
        for(size_t p1 = 0; p1 < _dim; p1++){
 
72
                for(size_t i = 0; i < _dim; i++){
 
73
                        unsigned int min = INFINITE_DISTANCE;
 
74
                        unsigned int pmin = 0;
 
75
                        for(size_t p2 = 0; p2 < _dim; p2++){
 
76
                                bool taken = false;
 
77
                                for(size_t j = 0; j < i; j++)
 
78
                                        taken |= (pm[p1 * _dim + j] == p2);
 
79
                                if(!taken && d(p2, p1) <= min){
 
80
                                        min = d(p2, p1);
 
81
                                        pmin = p2;
 
82
                                }
 
83
                        }
 
84
                        pm[p1 * _dim + i] = pmin;
 
85
                }
 
86
        }
 
87
}
 
88
 
 
89
 
 
90
 
 
91
} // Structures
 
92
} // PetriEngine