45 typedef int VertexNumber;
46 typedef int EdgeNumber;
47 typedef int ColorNumber;
48 typedef std::pair<VertexNumber,VertexNumber> VertexNumberPair;
61 EdgeInfo(VertexNumber v1, VertexNumber v2)
62 : v0(0), v1(v1), v2(v2), v1final(false), v2final(false),
63 v1final2(false), v2final2(false), allColorsSeen(false),
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 <<
"-";
72 if (o.v2final) os <<
"$";
73 if (o.v2final2) os <<
"-";
74 if (o.allColorsSeen) os <<
"*";
75 if (o.finalEdge) os <<
"$";
80 static VertexNumber
const MAX_VERTICES = USHRT_MAX;
81 static EdgeNumber
const MAX_EDGES = INT_MAX;
82 static ColorNumber
const MAX_COLORS = USHRT_MAX;
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_;
97 ColorNumber numColor_;
101 void addEdge(std::string vertexName1, std::string vertexName2) {
102 edgeNames.push_back(std::make_pair(vertexName1, vertexName2));
105 void setColor(std::string v, std::string color) {
106 name2color[v] = color;
109 void setColor(std::string v,
int color) {
110 name2color[v] = getColor(color);
113 void readEdges(std::string
const& filename) {
114 tdzdd::MessageHandler mh;
117 if (filename.empty()) {
122 mh <<
" \"" << filename <<
"\" ...";
123 std::ifstream fin(filename.c_str(), std::ios::in);
124 if (!fin)
throw std::runtime_error(strerror(errno));
132 void readAdjacencyList(std::string
const& filename) {
133 tdzdd::MessageHandler mh;
136 if (filename.empty()) {
138 readAdjacencyList(std::cin);
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);
151 void readVertexGroups(std::string
const& filename) {
152 tdzdd::MessageHandler mh;
155 if (filename.empty()) {
157 readVertexGroups(std::cin);
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);
171 void readEdges(std::istream& is) {
172 std::string v, v1, v2;
183 else if (v2.empty()) {
188 throw std::runtime_error(
189 "ERROR: More than two tokens in a line");
194 if (!v1.empty() && !v2.empty()) {
195 edgeNames.push_back(std::make_pair(v1, v2));
199 else if (!v1.empty()) {
200 throw std::runtime_error(
201 "ERROR: Only one token in a line");
210 if (!v1.empty() && !v2.empty()) {
211 edgeNames.push_back(std::make_pair(v1, v2));
213 else if (!v1.empty()) {
214 throw std::runtime_error(
"ERROR: Only one token in a line");
218 void readAdjacencyList(std::istream& is) {
228 while (isspace(c = is.get())) {
235 edgeNames.push_back(std::make_pair(to_string(v1), to_string(v2)));
239 void readVertexGroups(std::istream& is) {
240 std::vector<VertexNumber> group;
242 std::string color = getColor(n++);
247 while (isspace(c = is.get())) {
249 color = getColor(n++);
258 name2color[to_string(v)] = color;
262 std::string getColor(
int n) {
263 char const HEX[] =
"0123456789abcdef";
264 std::string color(
"#000000");
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)];
292 for (
size_t i = 0; i < edgeNames.size(); ++i) {
293 std::pair<std::string,std::string>
const& e = edgeNames[i];
295 if (name2edge.count(e) == 0) {
296 edge2name.push_back(e);
298 name2edge[std::make_pair(e.second, e.first)] = -1;
304 std::vector<std::string> stack;
305 stack.reserve(edge2name.size() * 2);
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;
311 if (name2vertex.count(s2) == 0) {
316 if (name2vertex.count(s1) == 0) {
322 vertex2name.push_back(
"");
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));
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;
339 if (name2vertex[s1] > name2vertex[s2]) {
343 VertexNumber v1 = name2vertex[s1];
344 VertexNumber v2 = name2vertex[s2];
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");
351 VertexNumberPair vp(v1, v2);
353 if (edgeIndex.count(vp) == 0) {
354 EdgeNumber a = edgeInfo_.size();
355 edgeInfo_.push_back(EdgeInfo(v1, v2));
357 name2edge[std::make_pair(s1, s2)] = a;
358 name2edge[std::make_pair(s2, s1)] = a;
359 if (vMax < v2) vMax = v2;
362 if (edgeInfo_.size() > size_t(MAX_EDGES))
throw std::runtime_error(
363 "ERROR: Edge number > " + to_string(MAX_EDGES));
367 std::map<std::string,std::set<VertexNumber> > color2vertices;
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);
377 if (color2vertices.size() > size_t(MAX_COLORS)) {
378 throw std::runtime_error(
379 "ERROR: Target paths > " + to_string(MAX_COLORS));
382 virtualMate_.resize(vMax + 1);
383 colorNumber_.resize(vMax + 1);
384 for (VertexNumber v = 1; v <= vMax; ++v) {
389 hasColorPairs_ = !color2vertices.empty();
391 for (std::map<std::string,std::set<VertexNumber> >::iterator t =
392 color2vertices.begin(); t != color2vertices.end(); ++t) {
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;
403 hasColorPairs_ =
false;
406 for (std::set<VertexNumber>::iterator tt = t->second.begin();
407 tt != t->second.end(); ++tt) {
408 VertexNumber v = *tt;
409 colorNumber_[v] = numColor_;
414 std::vector<ColorNumber> colorMap(numColor_ + 1);
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;
426 std::vector<EdgeNumber> lastEdge(vMax + 1);
427 std::vector<EdgeNumber> secondLastEdge(vMax + 1);
428 for (VertexNumber v = 1; v <= vMax; ++v) {
430 secondLastEdge[v] = -1;
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];
440 std::vector<EdgeNumber> finalEdgeToColor(numColor_ + 1);
441 EdgeNumber fitstEdgeToFinalColor = 0;
442 std::vector<bool> touched(numColor_ + 1);
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;
453 fitstEdgeToFinalColor = a;
460 fitstEdgeToFinalColor = a;
469 for (EdgeNumber a = 0; a < edgeSize(); ++a) {
470 EdgeInfo& e = edgeInfo_[a];
471 while (lastEdge[v0] < a) {
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);
486 VertexNumber vertexSize()
const {
490 EdgeNumber edgeSize()
const {
491 return edgeInfo_.size();
495 const& edgeInfo(EdgeNumber a)
const {
496 assert(0 <= a &&
size_t(a) < edgeInfo_.size());
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;
508 std::string vertexName(VertexNumber v)
const {
509 if (v < 1 || vertexSize() < v)
return "?";
510 return vertex2name[v];
513 std::string vertexLabel(VertexNumber v)
const {
514 std::string label = vertexName(v);
516 std::map<std::string,std::string>::const_iterator found =
517 name2label.find(label);
518 if (found != name2label.end()) {
519 label = found->second;
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;
533 EdgeNumber getEdge(std::string
const& name1,
534 std::string
const& name2)
const {
535 return getEdge(std::make_pair(name1, name2));
538 std::pair<std::string,std::string> edgeName(EdgeNumber e)
const {
539 if (e < 0 || edgeSize() <= e)
return std::make_pair(
"?",
"?");
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;
547 std::map<std::string,std::string>::const_iterator found =
548 name2label.find(label);
549 if (found != name2label.end()) {
550 label = found->second;
556 VertexNumber virtualMate(VertexNumber v)
const {
557 return (1 <= v && v <= vMax) ? virtualMate_[v] : 0;
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 =
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;
573 VertexNumber maxFrontierSize()
const {
575 for (EdgeNumber a = 0; a < edgeSize(); ++a) {
576 EdgeInfo
const& e = edgeInfo(a);
577 VertexNumber m = e.v2 - e.v0 + 1;
585 virtualMate_.clear();
586 virtualMate_.resize(vMax + 1);
587 colorNumber_.clear();
588 colorNumber_.resize(vMax + 1);
592 void setDefaultPathColor() {
594 name2color[to_string(1)] =
"#ff7777";
595 name2color[to_string(vMax)] =
"#ff7777";
599 ColorNumber colorNumber(VertexNumber v)
const {
600 return (1 <= v && v <= vMax) ? colorNumber_[v] : 0;
603 ColorNumber numColor()
const {
607 bool hasColorPairs()
const {
608 return hasColorPairs_;
612 std::ostream& dump(std::ostream& os, E
const& edgeDecorator)
const {
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 =
622 if (e != name2label.end()) {
623 os <<
"[label=\"" << e->second <<
"\"]";
625 e = name2color.find(*t);
626 if (e != name2color.end()) {
627 os <<
"[color=\"" << e->second <<
"\",style=filled]";
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 <<
"\"]";
642 t = name2color.find(s1 +
"," + s2);
643 if (t != name2color.end()) {
644 os <<
"[color=\"" << t->second <<
"\",style=bold]";
646 os << edgeDecorator(a);
656 struct NoEdgeDecorator {
657 std::string operator()(EdgeNumber a)
const {
663 std::ostream& dump(std::ostream& os)
const {
664 return dump(os, NoEdgeDecorator());
667 friend std::ostream& operator<<(std::ostream& os, Graph
const& g) {
672 static std::string to_string(
int i) {
673 std::ostringstream oss;