TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
Graph.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 <algorithm>
28 #include <cassert>
29 #include <cerrno>
30 #include <cstring>
31 #include <climits>
32 #include <fstream>
33 #include <iostream>
34 #include <map>
35 #include <set>
36 #include <sstream>
37 #include <stdexcept>
38 #include <stdint.h>
39 #include <vector>
40 
41 namespace tdzdd {
42 
43 class Graph {
44 public:
45  typedef int VertexNumber;
46  typedef int EdgeNumber;
47  typedef int ColorNumber;
48  typedef std::pair<VertexNumber,VertexNumber> VertexNumberPair;
49 
50  struct EdgeInfo {
51  VertexNumber v0;
52  VertexNumber v1;
53  VertexNumber v2;
54  bool v1final;
55  bool v2final;
56  bool v1final2;
57  bool v2final2;
58  bool allColorsSeen;
59  bool finalEdge;
60 
61  EdgeInfo(VertexNumber v1, VertexNumber v2)
62  : v0(0), v1(v1), v2(v2), v1final(false), v2final(false),
63  v1final2(false), v2final2(false), allColorsSeen(false),
64  finalEdge(false) {
65  }
66 
67  friend std::ostream& operator<<(std::ostream& os, EdgeInfo const& o) {
68  os << o.v0 << "--" << o.v1;
69  if (o.v1final) os << "$";
70  if (o.v1final2) os << "-";
71  os << "--" << o.v2;
72  if (o.v2final) os << "$";
73  if (o.v2final2) os << "-";
74  if (o.allColorsSeen) os << "*";
75  if (o.finalEdge) os << "$";
76  return os;
77  }
78  };
79 
80  static VertexNumber const MAX_VERTICES = USHRT_MAX;
81  static EdgeNumber const MAX_EDGES = INT_MAX;
82  static ColorNumber const MAX_COLORS = USHRT_MAX;
83 
84 private:
85  std::vector<std::pair<std::string,std::string> > edgeNames;
86  std::map<std::string,std::string> name2label;
87  std::map<std::string,std::string> name2color;
88  std::map<std::string,VertexNumber> name2vertex;
89  std::vector<std::string> vertex2name;
90  std::map<std::pair<std::string,std::string>,EdgeNumber> name2edge;
91  std::vector<std::pair<std::string,std::string> > edge2name;
92  std::vector<EdgeInfo> edgeInfo_;
93  std::map<VertexNumberPair,EdgeNumber> edgeIndex;
94  std::vector<VertexNumber> virtualMate_;
95  std::vector<ColorNumber> colorNumber_;
96  VertexNumber vMax;
97  ColorNumber numColor_;
98  bool hasColorPairs_;
99 
100 public:
101  void addEdge(std::string vertexName1, std::string vertexName2) {
102  edgeNames.push_back(std::make_pair(vertexName1, vertexName2));
103  }
104 
105  void setColor(std::string v, std::string color) {
106  name2color[v] = color;
107  }
108 
109  void setColor(std::string v, int color) {
110  name2color[v] = getColor(color);
111  }
112 
113  void readEdges(std::string const& filename) {
114  tdzdd::MessageHandler mh;
115  mh.begin("reading");
116 
117  if (filename.empty()) {
118  mh << " STDIN ...";
119  readEdges(std::cin);
120  }
121  else {
122  mh << " \"" << filename << "\" ...";
123  std::ifstream fin(filename.c_str(), std::ios::in);
124  if (!fin) throw std::runtime_error(strerror(errno));
125  readEdges(fin);
126  }
127 
128  mh.end();
129  update();
130  }
131 
132  void readAdjacencyList(std::string const& filename) {
133  tdzdd::MessageHandler mh;
134  mh.begin("reading");
135 
136  if (filename.empty()) {
137  mh << " STDIN ...";
138  readAdjacencyList(std::cin);
139  }
140  else {
141  mh << " \"" << filename << "\" ...";
142  std::ifstream fin(filename.c_str(), std::ios::in);
143  if (!fin) throw std::runtime_error(strerror(errno));
144  readAdjacencyList(fin);
145  }
146 
147  mh.end();
148  update();
149  }
150 
151  void readVertexGroups(std::string const& filename) {
152  tdzdd::MessageHandler mh;
153  mh.begin("reading");
154 
155  if (filename.empty()) {
156  mh << " STDIN ...";
157  readVertexGroups(std::cin);
158  }
159  else {
160  mh << " \"" << filename << "\" ...";
161  std::ifstream fin(filename.c_str(), std::ios::in);
162  if (!fin) throw std::runtime_error(strerror(errno));
163  readVertexGroups(fin);
164  }
165 
166  mh.end();
167  update();
168  }
169 
170 private:
171  void readEdges(std::istream& is) {
172  std::string v, v1, v2;
173 
174  while (is) {
175  char c = is.get();
176 
177  if (isspace(c)) {
178  if (!v.empty()) {
179  if (v1.empty()) {
180  v1 = v;
181  v.clear();
182  }
183  else if (v2.empty()) {
184  v2 = v;
185  v.clear();
186  }
187  else {
188  throw std::runtime_error(
189  "ERROR: More than two tokens in a line");
190  }
191  }
192 
193  if (c == '\n') {
194  if (!v1.empty() && !v2.empty()) {
195  edgeNames.push_back(std::make_pair(v1, v2));
196  v1.clear();
197  v2.clear();
198  }
199  else if (!v1.empty()) {
200  throw std::runtime_error(
201  "ERROR: Only one token in a line");
202  }
203  }
204  }
205  else {
206  v += c;
207  }
208  }
209 
210  if (!v1.empty() && !v2.empty()) {
211  edgeNames.push_back(std::make_pair(v1, v2));
212  }
213  else if (!v1.empty()) {
214  throw std::runtime_error("ERROR: Only one token in a line");
215  }
216  }
217 
218  void readAdjacencyList(std::istream& is) {
219  edgeNames.clear();
220  name2label.clear();
221  name2color.clear();
222 
223  VertexNumber v1 = 1;
224  VertexNumber v2;
225 
226  while (is) {
227  char c;
228  while (isspace(c = is.get())) {
229  if (c == '\n') ++v1;
230  }
231  if (!is) break;
232  is.unget();
233  is >> v2;
234 
235  edgeNames.push_back(std::make_pair(to_string(v1), to_string(v2)));
236  }
237  }
238 
239  void readVertexGroups(std::istream& is) {
240  std::vector<VertexNumber> group;
241  int n = 0;
242  std::string color = getColor(n++);
243  name2color.clear();
244 
245  while (is) {
246  char c;
247  while (isspace(c = is.get())) {
248  if (c == '\n') {
249  color = getColor(n++);
250  }
251  }
252  if (!is) break;
253  is.unget();
254 
255  VertexNumber v;
256  is >> v;
257 
258  name2color[to_string(v)] = color;
259  }
260  }
261 
262  std::string getColor(int n) {
263  char const HEX[] = "0123456789abcdef";
264  std::string color("#000000");
265 
266  color[2] = HEX[(n / 256) % 16];
267  color[4] = HEX[(n / 16) % 16];
268  color[6] = HEX[n % 16];
269  color[1] = HEX[15 - ((n * 3) % 11)];
270  color[3] = HEX[(n * 5 + 5) % 11 + 5];
271  color[5] = HEX[15 - ((n * 2 + 7) % 11)];
272  return color;
273  }
274 
275 public:
276  /*
277  * INPUT:
278  * edgeNames
279  * name2label
280  * name2color
281  */
282  void update() {
283  name2vertex.clear();
284  vertex2name.clear();
285  name2edge.clear();
286  edge2name.clear();
287  edgeInfo_.clear();
288  edgeIndex.clear();
289  vMax = 0;
290 
291  // Make unique edge name list
292  for (size_t i = 0; i < edgeNames.size(); ++i) {
293  std::pair<std::string,std::string> const& e = edgeNames[i];
294 
295  if (name2edge.count(e) == 0) {
296  edge2name.push_back(e);
297  name2edge[e] = -1;
298  name2edge[std::make_pair(e.second, e.first)] = -1;
299  }
300  }
301 
302  // Sort vertices by leaving order
303  {
304  std::vector<std::string> stack;
305  stack.reserve(edge2name.size() * 2);
306 
307  for (size_t i = edge2name.size() - 1; i + 1 > 0; --i) {
308  std::string const& s1 = edge2name[i].first;
309  std::string const& s2 = edge2name[i].second;
310 
311  if (name2vertex.count(s2) == 0) {
312  name2vertex[s2] = 0;
313  stack.push_back(s2);
314  }
315 
316  if (name2vertex.count(s1) == 0) {
317  name2vertex[s1] = 0;
318  stack.push_back(s1);
319  }
320  }
321 
322  vertex2name.push_back(""); // begin vertex number with 1
323 
324  while (!stack.empty()) {
325  std::string const& s = stack.back();
326  name2vertex[s] = vertex2name.size();
327  vertex2name.push_back(s);
328  if (vertex2name.size() > size_t(MAX_VERTICES)) throw std::runtime_error(
329  "ERROR: Vertex number > " + to_string(MAX_VERTICES));
330  stack.pop_back();
331  }
332  }
333 
334  for (size_t i = 0; i < edge2name.size(); ++i) {
335  std::pair<std::string,std::string> const& e = edge2name[i];
336  std::string s1 = e.first;
337  std::string s2 = e.second;
338 
339  if (name2vertex[s1] > name2vertex[s2]) {
340  std::swap(s1, s2);
341  }
342 
343  VertexNumber v1 = name2vertex[s1];
344  VertexNumber v2 = name2vertex[s2];
345 
346  if (v1 == 0) throw std::runtime_error(
347  "ERROR: " + s1 + ": No such vertex");
348  if (v2 == 0) throw std::runtime_error(
349  "ERROR: " + s2 + ": No such vertex");
350 
351  VertexNumberPair vp(v1, v2);
352 
353  if (edgeIndex.count(vp) == 0) {
354  EdgeNumber a = edgeInfo_.size();
355  edgeInfo_.push_back(EdgeInfo(v1, v2));
356  edgeIndex[vp] = a;
357  name2edge[std::make_pair(s1, s2)] = a;
358  name2edge[std::make_pair(s2, s1)] = a;
359  if (vMax < v2) vMax = v2;
360  }
361 
362  if (edgeInfo_.size() > size_t(MAX_EDGES)) throw std::runtime_error(
363  "ERROR: Edge number > " + to_string(MAX_EDGES));
364  }
365 
366  {
367  std::map<std::string,std::set<VertexNumber> > color2vertices;
368 
369  for (std::map<std::string,std::string>::iterator t =
370  name2color.begin(); t != name2color.end(); ++t) {
371  VertexNumber v = name2vertex[t->first];
372  if (v == 0) throw std::runtime_error(
373  "ERROR: " + t->first + ": No such vertex");
374  color2vertices[t->second].insert(v); // color => set of vertices
375  }
376 
377  if (color2vertices.size() > size_t(MAX_COLORS)) {
378  throw std::runtime_error(
379  "ERROR: Target paths > " + to_string(MAX_COLORS));
380  }
381 
382  virtualMate_.resize(vMax + 1);
383  colorNumber_.resize(vMax + 1);
384  for (VertexNumber v = 1; v <= vMax; ++v) {
385  virtualMate_[v] = 0;
386  colorNumber_[v] = 0;
387  }
388  numColor_ = 0;
389  hasColorPairs_ = !color2vertices.empty();
390 
391  for (std::map<std::string,std::set<VertexNumber> >::iterator t =
392  color2vertices.begin(); t != color2vertices.end(); ++t) {
393  ++numColor_;
394 
395  if (t->second.size() == 2) {
396  std::set<VertexNumber>::iterator tt = t->second.begin();
397  VertexNumber v1 = *tt++;
398  VertexNumber v2 = *tt;
399  virtualMate_[v1] = v2;
400  virtualMate_[v2] = v1;
401  }
402  else {
403  hasColorPairs_ = false;
404  }
405 
406  for (std::set<VertexNumber>::iterator tt = t->second.begin();
407  tt != t->second.end(); ++tt) {
408  VertexNumber v = *tt;
409  colorNumber_[v] = numColor_;
410  }
411  }
412 
413  // sort colorNumber
414  std::vector<ColorNumber> colorMap(numColor_ + 1);
415  ColorNumber cn = 0;
416  for (VertexNumber v = 1; v <= vMax; ++v) {
417  ColorNumber c = colorNumber_[v];
418  if (c == 0) continue;
419  ColorNumber& cc = colorMap[c];
420  if (cc == 0) cc = ++cn;
421  colorNumber_[v] = cc;
422  }
423  }
424 
425  {
426  std::vector<EdgeNumber> lastEdge(vMax + 1);
427  std::vector<EdgeNumber> secondLastEdge(vMax + 1);
428  for (VertexNumber v = 1; v <= vMax; ++v) {
429  lastEdge[v] = -1;
430  secondLastEdge[v] = -1;
431  }
432  for (EdgeNumber a = 0; a < edgeSize(); ++a) {
433  EdgeInfo& e = edgeInfo_[a];
434  secondLastEdge[e.v1] = lastEdge[e.v1];
435  secondLastEdge[e.v2] = lastEdge[e.v2];
436  lastEdge[e.v1] = a;
437  lastEdge[e.v2] = a;
438  }
439 
440  std::vector<EdgeNumber> finalEdgeToColor(numColor_ + 1);
441  EdgeNumber fitstEdgeToFinalColor = 0;
442  std::vector<bool> touched(numColor_ + 1);
443  touched[0] = true;
444  ColorNumber k = numColor_;
445  for (EdgeNumber a = 0; a < edgeSize(); ++a) {
446  EdgeInfo const& e = edgeInfo(a);
447  ColorNumber n1 = colorNumber(e.v1);
448  ColorNumber n2 = colorNumber(e.v2);
449  finalEdgeToColor[n1] = a;
450  finalEdgeToColor[n2] = a;
451  if (!touched[n1]) {
452  if (--k == 0) {
453  fitstEdgeToFinalColor = a;
454  break;
455  }
456  touched[n1] = true;
457  }
458  if (!touched[n2]) {
459  if (--k == 0) {
460  fitstEdgeToFinalColor = a;
461  break;
462  }
463  touched[n2] = true;
464  }
465  }
466 
467  VertexNumber v0 = 1;
468 
469  for (EdgeNumber a = 0; a < edgeSize(); ++a) {
470  EdgeInfo& e = edgeInfo_[a];
471  while (lastEdge[v0] < a) {
472  ++v0;
473  assert(v0 <= vMax);
474  }
475  e.v0 = v0;
476  e.v1final = (a == lastEdge[e.v1]);
477  e.v2final = (a == lastEdge[e.v2]);
478  e.v1final2 = (a == secondLastEdge[e.v1]);
479  e.v2final2 = (a == secondLastEdge[e.v2]);
480  e.allColorsSeen = (a >= fitstEdgeToFinalColor);
481  e.finalEdge = (a == edgeSize() - 1);
482  }
483  }
484  }
485 
486  VertexNumber vertexSize() const {
487  return vMax;
488  }
489 
490  EdgeNumber edgeSize() const {
491  return edgeInfo_.size();
492  }
493 
494  EdgeInfo
495  const& edgeInfo(EdgeNumber a) const {
496  assert(0 <= a && size_t(a) < edgeInfo_.size());
497  return edgeInfo_[a];
498  }
499 
500  VertexNumber getVertex(std::string const& name) const {
501  std::map<std::string,VertexNumber>::const_iterator found =
502  name2vertex.find(name);
503  if (found == name2vertex.end()) throw std::runtime_error(
504  "ERROR: " + name + ": No such vertex");
505  return found->second;
506  }
507 
508  std::string vertexName(VertexNumber v) const {
509  if (v < 1 || vertexSize() < v) return "?";
510  return vertex2name[v];
511  }
512 
513  std::string vertexLabel(VertexNumber v) const {
514  std::string label = vertexName(v);
515 
516  std::map<std::string,std::string>::const_iterator found =
517  name2label.find(label);
518  if (found != name2label.end()) {
519  label = found->second;
520  }
521 
522  return label;
523  }
524 
525  EdgeNumber getEdge(std::pair<std::string,std::string> const& name) const {
526  std::map<std::pair<std::string,std::string>,EdgeNumber>::const_iterator found =
527  name2edge.find(name);
528  if (found == name2edge.end()) throw std::runtime_error(
529  "ERROR: " + name.first + "," + name.second + ": No such edge");
530  return found->second;
531  }
532 
533  EdgeNumber getEdge(std::string const& name1,
534  std::string const& name2) const {
535  return getEdge(std::make_pair(name1, name2));
536  }
537 
538  std::pair<std::string,std::string> edgeName(EdgeNumber e) const {
539  if (e < 0 || edgeSize() <= e) return std::make_pair("?", "?");
540  return edge2name[e];
541  }
542 
543  std::string edgeLabel(EdgeNumber e) const {
544  std::pair<std::string,std::string> name = edgeName(e);
545  std::string label = name.first + "," + name.second;
546 
547  std::map<std::string,std::string>::const_iterator found =
548  name2label.find(label);
549  if (found != name2label.end()) {
550  label = found->second;
551  }
552 
553  return label;
554  }
555 
556  VertexNumber virtualMate(VertexNumber v) const {
557  return (1 <= v && v <= vMax) ? virtualMate_[v] : 0;
558  }
559 
560  EdgeNumber getEdge(VertexNumber v1, VertexNumber v2) const {
561  assert(1 <= v1 && v1 <= vMax);
562  assert(1 <= v2 && v2 <= vMax);
563  if (v1 > v2) std::swap(v1, v2);
564  VertexNumberPair vp(v1, v2);
565  std::map<VertexNumberPair,EdgeNumber>::const_iterator found =
566  edgeIndex.find(vp);
567  if (found == edgeIndex.end()) throw std::runtime_error(
568  "ERROR: (" + to_string(v1) + "," + to_string(v2)
569  + "): No such edge");
570  return found->second;
571  }
572 
573  VertexNumber maxFrontierSize() const {
574  VertexNumber n = 0;
575  for (EdgeNumber a = 0; a < edgeSize(); ++a) {
576  EdgeInfo const& e = edgeInfo(a);
577  VertexNumber m = e.v2 - e.v0 + 1;
578  if (n < m) n = m;
579  }
580  return n;
581  }
582 
583  void clearColors() {
584  name2color.clear();
585  virtualMate_.clear();
586  virtualMate_.resize(vMax + 1);
587  colorNumber_.clear();
588  colorNumber_.resize(vMax + 1);
589  numColor_ = 0;
590  }
591 
592  void setDefaultPathColor() {
593  name2color.clear();
594  name2color[to_string(1)] = "#ff7777";
595  name2color[to_string(vMax)] = "#ff7777";
596  update();
597  }
598 
599  ColorNumber colorNumber(VertexNumber v) const {
600  return (1 <= v && v <= vMax) ? colorNumber_[v] : 0;
601  }
602 
603  ColorNumber numColor() const {
604  return numColor_;
605  }
606 
607  bool hasColorPairs() const {
608  return hasColorPairs_;
609  }
610 
611  template<typename E>
612  std::ostream& dump(std::ostream& os, E const& edgeDecorator) const {
613  os << "graph {\n";
614  //os << " layout=neato;\n";
615 
616  for (std::vector<std::string>::const_iterator t = vertex2name.begin();
617  t != vertex2name.end(); ++t) {
618  if (t->empty()) continue;
619  os << " \"" << *t << "\"";
620  std::map<std::string,std::string>::const_iterator e =
621  name2label.find(*t);
622  if (e != name2label.end()) {
623  os << "[label=\"" << e->second << "\"]";
624  }
625  e = name2color.find(*t);
626  if (e != name2color.end()) {
627  os << "[color=\"" << e->second << "\",style=filled]";
628  }
629  os << ";\n";
630  }
631 
632  for (EdgeNumber a = 0; a < edgeSize(); ++a) {
633  EdgeInfo const& e = edgeInfo(a);
634  std::string s1 = vertex2name[e.v1];
635  std::string s2 = vertex2name[e.v2];
636  os << " \"" << s1 << "\"--\"" << s2 << "\"";
637  std::map<std::string,std::string>::const_iterator t =
638  name2label.find(s1 + "," + s2);
639  if (t != name2label.end()) {
640  os << "[label=\"" << t->second << "\"]";
641  }
642  t = name2color.find(s1 + "," + s2);
643  if (t != name2color.end()) {
644  os << "[color=\"" << t->second << "\",style=bold]";
645  }
646  os << edgeDecorator(a);
647  os << ";\n";
648  }
649 
650  os << "}\n";
651  os.flush();
652  return os;
653  }
654 
655 private:
656  struct NoEdgeDecorator {
657  std::string operator()(EdgeNumber a) const {
658  return "";
659  }
660  };
661 
662 public:
663  std::ostream& dump(std::ostream& os) const {
664  return dump(os, NoEdgeDecorator());
665  }
666 
667  friend std::ostream& operator<<(std::ostream& os, Graph const& g) {
668  return g.dump(os);
669  }
670 
671 private:
672  static std::string to_string(int i) {
673  std::ostringstream oss;
674  oss << i;
675  return oss.str();
676  }
677 };
678 
679 } // namespace tdzdd