TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
PathZddByStdMap.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <cassert>
28 #include <map>
29 
30 #include "../DdSpec.hpp"
31 #include "../util/Graph.hpp"
32 
33 namespace tdzdd {
34 
35 struct PathZddByStdMap: public tdzdd::DdSpec<PathZddByStdMap,
36  std::map<int16_t,int16_t>,2> {
37 
38  Graph const& graph;
39  int const n;
40 
41 public:
42  PathZddByStdMap(Graph const& graph)
43  : graph(graph), n(graph.edgeSize()) {
44  }
45 
46  int getRoot(State& mate) const {
47  for (Graph::VertexNumber v = 1; v <= graph.vertexSize(); ++v) {
48  Graph::VertexNumber w = graph.virtualMate(v);
49  if (w >= 1) mate[v] = w;
50  }
51  return n;
52  }
53 
54  int getChild(State& mate, int level, int take) const {
55  Graph::EdgeInfo const& e = graph.edgeInfo(n - level);
56  int const v1 = e.v1;
57  int const v2 = e.v2;
58  State::iterator t1 = mate.find(v1);
59  State::iterator t2 = mate.find(v2);
60  bool const u1 = (t1 == mate.end());
61  bool const u2 = (t2 == mate.end());
62  int const w1 = u1 ? v1 : t1->second;
63  int const w2 = u2 ? v2 : t2->second;
64 
65  if (take) {
66  if (w1 == 0 || w2 == 0) return 0;
67  if (e.v1final && u1) return 0;
68  if (e.v2final && u2) return 0;
69 
70  if (w1 == v2) {
71  assert(w2 == v1);
72  for (State::const_iterator t = mate.begin(); t != mate.end();
73  ++t) {
74  if (t->first != v1 && t->first != v2 && t->second > 0) return 0;
75  }
76  return -1;
77  }
78 
79  mate[v1] = mate[v2] = 0;
80  mate[w1] = w2, mate[w2] = w1;
81  }
82 
83  if (e.v1final && !u1) {
84  if (mate[v1] != 0) return 0;
85  mate.erase(v1);
86  }
87 
88  if (e.v2final && !u2) {
89  if (mate[v2] != 0) return 0;
90  mate.erase(v2);
91  }
92 
93  return level - 1;
94  }
95 
96  size_t hashCode(State const& mate) const {
97  size_t h = 0;
98  for (State::const_iterator t = mate.begin(); t != mate.end(); ++t) {
99  h += t->first;
100  h *= 314159257;
101  h += t->second;
102  h *= 271828171;
103  }
104  return h;
105  }
106 };
107 
108 } // namespace tdzdd
Abstract class of DD specifications using scalar states.
Definition: DdSpec.hpp:257