1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 // its contributors may be used to endorse or promote products derived
17 // from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32
33
34 #ifndef SEQAN_HEADER_GRAPH_DRAWING_H
35 #define SEQAN_HEADER_GRAPH_DRAWING_H
36
37 namespace SEQAN_NAMESPACE_MAIN
38 {
39
40 //////////////////////////////////////////////////////////////////////////////
41 // Graph - Drawing
42 //////////////////////////////////////////////////////////////////////////////
43
44 //////////////////////////////////////////////////////////////////////////////
45
46
47 //////////////////////////////////////////////////////////////////////////////
48 // WRITING
49 //////////////////////////////////////////////////////////////////////////////
50
51
52
53 //////////////////////////////////////////////////////////////////////////////
54 // INTERNAL FUNCTIONS
55 //////////////////////////////////////////////////////////////////////////////
56
57 //////////////////////////////////////////////////////////////////////////////
58
59
60 //////////////////////////////////////////////////////////////////////////////
61
62 template <typename TAlphabet, typename TCargo, typename TSpec, typename TVertexDescriptor, typename TAttributes>
63 inline void
_markRootVertex(Graph<Automaton<TAlphabet,TCargo,TSpec>> const & g,TVertexDescriptor const & v,TAttributes & str)64 _markRootVertex(Graph<Automaton<TAlphabet, TCargo, TSpec> > const& g,
65 TVertexDescriptor const& v,
66 TAttributes& str)
67 {
68 SEQAN_CHECKPOINT
69 if (isRoot(g,v)) {
70 append(str, ", shape = doublecircle");
71 }
72 }
73
74 //////////////////////////////////////////////////////////////////////////////
75
76 template <typename TCargo, typename TSpec, typename TVertexDescriptor, typename TAttributes>
77 inline void
_markRootVertex(Graph<Directed<TCargo,TSpec>> const &,TVertexDescriptor const &,TAttributes &)78 _markRootVertex(Graph<Directed<TCargo, TSpec> > const&,
79 TVertexDescriptor const&,
80 TAttributes&)
81 {
82 SEQAN_CHECKPOINT
83 }
84
85 //////////////////////////////////////////////////////////////////////////////
86
87 template <typename TCargo, typename TSpec, typename TVertexDescriptor, typename TAttributes>
88 inline void
_markRootVertex(Graph<Undirected<TCargo,TSpec>> const &,TVertexDescriptor const &,TAttributes &)89 _markRootVertex(Graph<Undirected<TCargo, TSpec> > const&,
90 TVertexDescriptor const&,
91 TAttributes&)
92 {
93 SEQAN_CHECKPOINT
94 }
95
96
97 //////////////////////////////////////////////////////////////////////////////
98
99 template <typename TCargo, typename TSpec, typename TVertexDescriptor, typename TAttributes>
100 inline void
_markRootVertex(Graph<Tree<TCargo,TSpec>> const & g,TVertexDescriptor const & v,TAttributes & str)101 _markRootVertex(Graph<Tree<TCargo, TSpec> > const& g,
102 TVertexDescriptor const& v,
103 TAttributes& str)
104 {
105 SEQAN_CHECKPOINT
106 if (isRoot(g,v)) {
107 append(str, ", shape = doublecircle");
108 }
109 }
110
111 //////////////////////////////////////////////////////////////////////////////
112
113 template<typename TAlphabet, typename TCargo, typename TSpec, typename TPosition, typename TNodeMap>
114 inline void
_createTrieNodeAttributes(Graph<Automaton<TAlphabet,TCargo,TSpec>> const & g,String<String<TPosition>> pos,TNodeMap & nodeMap)115 _createTrieNodeAttributes(Graph<Automaton<TAlphabet, TCargo, TSpec> > const& g,
116 String<String<TPosition> > pos,
117 TNodeMap& nodeMap)
118 {
119 SEQAN_CHECKPOINT
120 typedef Graph<Automaton<TAlphabet, TCargo, TSpec> > TGraph;
121 resizeVertexMap(nodeMap, g);
122 typedef typename Iterator<TGraph, VertexIterator>::Type TConstIter;
123 TConstIter it(g);
124 for(;!atEnd(it);++it) {
125 String<char> tmp;
126 std::stringstream s;
127 s << *it;
128 String<TPosition> endPositions = getProperty(pos,*it);
129 if (!empty(endPositions)) {
130 s << " {";
131 append(tmp, "shape = box, ");
132 typename Iterator<String<TPosition>, Rooted>::Type itP = begin(endPositions);
133 typename Iterator<String<TPosition>, Rooted>::Type beginP = itP;
134 for(;!atEnd(itP);goNext(itP)) {
135 if (beginP != itP) s << ", ";
136 s << *itP;
137 }
138 s << "}";
139 }
140
141 append(tmp, "label = \"");
142 append(tmp, s.str().c_str());
143 append(tmp, "\"");
144 _markRootVertex(g, *it, tmp);
145 assignProperty(nodeMap, *it, tmp);
146 }
147 }
148
149 //////////////////////////////////////////////////////////////////////////////
150
151 template<typename TSpec, typename TNodeAttributes>
152 inline void
_createNodeAttributes(Graph<TSpec> const & g,TNodeAttributes & nodeMap)153 _createNodeAttributes(Graph<TSpec> const& g,
154 TNodeAttributes& nodeMap)
155 {
156 typedef Graph<TSpec> TGraph;
157 resizeVertexMap(nodeMap, g);
158
159 typedef typename Iterator<TGraph, VertexIterator>::Type TConstIter;
160 TConstIter it(g);
161 for(;!atEnd(it);++it) {
162 std::ostringstream outs;
163 outs << "label = \"";
164 outs << *it;
165 outs << "\"";
166 String<char> tmp;
167 append(tmp, outs.str().c_str());
168 _markRootVertex(g, *it, tmp);
169 assignProperty(nodeMap, *it, tmp);
170 }
171 }
172
173 //////////////////////////////////////////////////////////////////////////////
174
175 template<typename TSpec, typename TNodeAttributes, typename TNameMap>
176 inline void
_createNodeAttributes(Graph<TSpec> const & g,TNodeAttributes & nodeMap,TNameMap const & nameMap)177 _createNodeAttributes(Graph<TSpec> const& g,
178 TNodeAttributes& nodeMap,
179 TNameMap const& nameMap)
180 {
181 typedef Graph<TSpec> TGraph;
182 resizeVertexMap(nodeMap, g);
183
184 typedef typename Iterator<TGraph, VertexIterator>::Type TConstIter;
185 TConstIter it(g);
186 for(;!atEnd(it);++it) {
187 std::ostringstream outs;
188 outs << "label = \"";
189 outs << getProperty(nameMap,*it);
190 outs << "\"";
191 String<char> tmp;
192 append(tmp, outs.str().c_str());
193 _markRootVertex(g, *it, tmp);
194 assignProperty(nodeMap, *it, tmp);
195 }
196 }
197
198 //////////////////////////////////////////////////////////////////////////////
199 template<typename TSpec, typename TEdgeAttributes>
200 inline void
_createEmptyEdgeAttributes(Graph<TSpec> const & g,TEdgeAttributes & edgeMap)201 _createEmptyEdgeAttributes(Graph<TSpec> const& g,
202 TEdgeAttributes& edgeMap)
203 {
204 typedef Graph<TSpec> TGraph;
205 resizeEdgeMap(edgeMap, g);
206
207 typedef typename Iterator<TGraph, EdgeIterator>::Type TConstEdIter;
208 TConstEdIter itEd(g);
209 for(;!atEnd(itEd);++itEd) {
210 assignProperty(edgeMap, *itEd, String<char>(""));
211 }
212 }
213
214 //////////////////////////////////////////////////////////////////////////////
215
216 template <typename TCargo, typename TSpec, typename TEdgeAttributes>
217 inline void
_createEdgeAttributes(Graph<Directed<TCargo,TSpec>> const & g,TEdgeAttributes & edgeMap)218 _createEdgeAttributes(Graph<Directed<TCargo, TSpec> > const& g,
219 TEdgeAttributes& edgeMap)
220 {
221 _createEmptyEdgeAttributes(g,edgeMap);
222 }
223
224 //////////////////////////////////////////////////////////////////////////////
225
226 template <typename TCargo, typename TSpec, typename TEdgeAttributes>
227 inline void
_createEdgeAttributes(Graph<Undirected<TCargo,TSpec>> const & g,TEdgeAttributes & edgeMap)228 _createEdgeAttributes(Graph<Undirected<TCargo, TSpec> > const& g,
229 TEdgeAttributes& edgeMap)
230 {
231 SEQAN_CHECKPOINT
232 _createEmptyEdgeAttributes(g,edgeMap);
233 }
234
235 //////////////////////////////////////////////////////////////////////////////
236
237 template <typename TSpec, typename TEdgeAttributes>
238 inline void
_createEdgeAttributes(Graph<Tree<void,TSpec>> const & g,TEdgeAttributes & edgeMap)239 _createEdgeAttributes(Graph<Tree<void, TSpec> > const& g,
240 TEdgeAttributes& edgeMap)
241 {
242 SEQAN_CHECKPOINT
243 _createEmptyEdgeAttributes(g,edgeMap);
244 }
245
246 //////////////////////////////////////////////////////////////////////////////
247
248 template <typename TCargo, typename TSpec, typename TEdgeAttributes>
249 inline void
_createEdgeAttributes(Graph<Tree<TCargo,TSpec>> const & g,TEdgeAttributes & edgeMap)250 _createEdgeAttributes(Graph<Tree<TCargo, TSpec> > const& g,
251 TEdgeAttributes& edgeMap)
252 {
253 typedef Graph<Tree<TCargo, TSpec> > TGraph;
254 resizeEdgeMap(edgeMap, g);
255
256 typedef typename Iterator<TGraph, EdgeIterator>::Type TConstEdIter;
257 TConstEdIter itEd(g);
258 for(;!atEnd(itEd);++itEd) {
259 std::ostringstream outs;
260 outs << "label = \"";
261 outs << (TCargo) getCargo(*itEd);
262 outs << "\"";
263 append(property(edgeMap, *itEd), outs.str().c_str());
264 }
265 }
266
267 //////////////////////////////////////////////////////////////////////////////
268
269 template <typename TAlphabet, typename TCargo, typename TSpec, typename TEdgeAttributes>
270 inline void
_createEdgeAttributes(Graph<Automaton<TAlphabet,TCargo,TSpec>> const & g,TEdgeAttributes & edgeMap)271 _createEdgeAttributes(Graph<Automaton<TAlphabet, TCargo, TSpec> > const& g,
272 TEdgeAttributes& edgeMap)
273 {
274 SEQAN_CHECKPOINT
275 typedef Graph<Automaton<TAlphabet, TCargo, TSpec> > TGraph;
276 resizeEdgeMap(edgeMap, g);
277
278 typedef typename Iterator<TGraph, EdgeIterator>::Type TConstEdIter;
279 TConstEdIter itEd(g);
280 for(;!atEnd(itEd);++itEd) {
281 String<char> tmp("label = \"");
282 append(tmp, label(itEd));
283 append(tmp, "\"");
284 assignProperty(edgeMap, *itEd, tmp);
285 }
286 }
287
288
289 //////////////////////////////////////////////////////////////////////////////
290
291 template <typename TAlphabet, typename TCargo, typename TSpec, typename TEdgeAttributes>
292 inline void
_createEdgeAttributes(Graph<Automaton<TAlphabet,TCargo,WordGraph<TSpec>>> const & g,TEdgeAttributes & edgeMap)293 _createEdgeAttributes(Graph<Automaton<TAlphabet, TCargo, WordGraph<TSpec> > > const& g,
294 TEdgeAttributes& edgeMap)
295 {
296 SEQAN_CHECKPOINT
297 typedef Graph<Automaton<TAlphabet, TCargo, WordGraph<TSpec> > > TGraph;
298 resizeEdgeMap(edgeMap, g);
299
300 typedef typename Iterator<TGraph, EdgeIterator>::Type TConstEdIter;
301 TConstEdIter itEd(g);
302 for(;!atEnd(itEd);++itEd) {
303 String<TAlphabet> labelTmp = getCargo(*itEd);
304 String<char> str;
305 resize(str,length(labelTmp)+1);
306 value(str,0) = label(itEd);
307 typename Iterator<String<TAlphabet>, Rooted>::Type it = begin(labelTmp);
308 for(;!atEnd(it);++it) {
309 char c = convert<char>(getValue(it));
310 value(str,position(it) + 1) = c;
311 }
312 String<char> tmp("label = \"");
313 append(tmp, str);
314 append(tmp, "\"");
315 assignProperty(edgeMap, *itEd, tmp);
316 }
317 }
318
319 //////////////////////////////////////////////////////////////////////////////
320
321 template <typename TFile, typename TCargo, typename TSpec>
322 inline void
_writeGraphFooter(TFile &,Graph<Directed<TCargo,TSpec>> const &,DotDrawing)323 _writeGraphFooter(TFile &,
324 Graph<Directed<TCargo, TSpec> > const&,
325 DotDrawing)
326 {
327 //IOREV
328 SEQAN_CHECKPOINT
329 }
330
331 //////////////////////////////////////////////////////////////////////////////
332
333 template <typename TFile, typename TCargo, typename TSpec>
334 inline void
_writeGraphFooter(TFile &,Graph<Undirected<TCargo,TSpec>> const &,DotDrawing)335 _writeGraphFooter(TFile &,
336 Graph<Undirected<TCargo, TSpec> > const&,
337 DotDrawing)
338 {
339 //IOREV
340 SEQAN_CHECKPOINT
341 }
342
343 //////////////////////////////////////////////////////////////////////////////
344
345 template <typename TFile, typename TCargo, typename TSpec>
346 inline void
_writeGraphFooter(TFile &,Graph<Tree<TCargo,TSpec>> const &,DotDrawing)347 _writeGraphFooter(TFile &,
348 Graph<Tree<TCargo, TSpec> > const&,
349 DotDrawing)
350 {
351 //IOREV
352 SEQAN_CHECKPOINT
353 }
354
355
356 //////////////////////////////////////////////////////////////////////////////
357
358 template <typename TFile, typename TAlphabet, typename TCargo, typename TSpec>
359 inline void
_writeGraphFooter(TFile &,Graph<Automaton<TAlphabet,TCargo,TSpec>> const &,DotDrawing)360 _writeGraphFooter(TFile &,
361 Graph<Automaton<TAlphabet, TCargo, TSpec> > const&,
362 DotDrawing)
363 {
364 //IOREV
365 SEQAN_CHECKPOINT
366 }
367
368 //////////////////////////////////////////////////////////////////////////////
369
370 template <typename TFile, typename TAlphabet, typename TCargo, typename TSpec>
371 inline void
_writeGraphType(TFile & file,Graph<Automaton<TAlphabet,TCargo,TSpec>> const &,DotDrawing)372 _writeGraphType(TFile & file,
373 Graph<Automaton<TAlphabet, TCargo, TSpec> > const&,
374 DotDrawing)
375 {
376 //IOREV
377 write(file, "digraph");
378 }
379
380 //////////////////////////////////////////////////////////////////////////////
381
382 template <typename TFile, typename TCargo, typename TSpec>
383 inline void
_writeGraphType(TFile & file,Graph<Directed<TCargo,TSpec>> const &,DotDrawing)384 _writeGraphType(TFile & file,
385 Graph<Directed<TCargo, TSpec> > const&,
386 DotDrawing)
387 {
388 //IOREV
389 write(file, "digraph");
390 }
391
392 //////////////////////////////////////////////////////////////////////////////
393
394 template <typename TFile, typename TCargo, typename TSpec>
395 inline void
_writeGraphType(TFile & file,Graph<Undirected<TCargo,TSpec>> const &,DotDrawing)396 _writeGraphType(TFile & file,
397 Graph<Undirected<TCargo, TSpec> > const&,
398 DotDrawing)
399 {
400 //IOREV
401 write(file, "graph");
402 }
403
404 //////////////////////////////////////////////////////////////////////////////
405
406 template <typename TFile, typename TCargo, typename TSpec>
407 inline void
_writeGraphType(TFile & file,Graph<Tree<TCargo,TSpec>> const &,DotDrawing)408 _writeGraphType(TFile & file,
409 Graph<Tree<TCargo, TSpec> > const&,
410 DotDrawing)
411 {
412 //IOREV
413 write(file, "digraph");
414 }
415
416 //////////////////////////////////////////////////////////////////////////////
417
418 template <typename TFile, typename TAlphabet, typename TCargo, typename TSpec>
419 inline void
_writeEdgeType(TFile & file,Graph<Automaton<TAlphabet,TCargo,TSpec>> const &,DotDrawing)420 _writeEdgeType(TFile & file,
421 Graph<Automaton<TAlphabet, TCargo, TSpec> > const&,
422 DotDrawing)
423 {
424 //IOREV
425 write(file, " -> ");
426 }
427
428 //////////////////////////////////////////////////////////////////////////////
429
430 template <typename TFile, typename TCargo, typename TSpec>
431 inline void
_writeEdgeType(TFile & file,Graph<Directed<TCargo,TSpec>> const &,DotDrawing)432 _writeEdgeType(TFile & file,
433 Graph<Directed<TCargo, TSpec> > const&,
434 DotDrawing)
435 {
436 //IOREV
437 write(file, " -> ");
438 }
439
440 //////////////////////////////////////////////////////////////////////////////
441
442 template <typename TFile, typename TCargo, typename TSpec>
443 inline void
_writeEdgeType(TFile & file,Graph<Undirected<TCargo,TSpec>> const &,DotDrawing)444 _writeEdgeType(TFile & file,
445 Graph<Undirected<TCargo, TSpec> > const&,
446 DotDrawing)
447 {
448 //IOREV
449 write(file, " -- ");
450 }
451
452 //////////////////////////////////////////////////////////////////////////////
453
454 template <typename TFile, typename TCargo, typename TSpec>
455 inline void
_writeEdgeType(TFile & file,Graph<Tree<TCargo,TSpec>> const &,DotDrawing)456 _writeEdgeType(TFile & file,
457 Graph<Tree<TCargo, TSpec> > const&,
458 DotDrawing)
459 {
460 //IOREV
461 write(file, " -> ");
462 }
463
464 //////////////////////////////////////////////////////////////////////////////
465 // FUNCTIONS
466 //////////////////////////////////////////////////////////////////////////////
467
468
469 //////////////////////////////////////////////////////////////////////////////
470
471 /*!
472 * @fn Graph#write
473 * @brief The graph to write out.
474 *
475 * @signature void write(file, graph[, nodeMap[, edgeMap]], tag);
476 *
477 * @param[in,out] file The @link StreamConcept @endlink to write to.
478 * @param[in] graph The @link Graph @endlink to write out.
479 * @param[in] nodeMap Vertex labels for each vertex; optional.
480 * @param[in] edgeMap Edge label for each edge; optional.
481 * @param[in] tag Format tag to use for writing. Types: DotDrawing.
482 */
483
484 template <typename TTarget, typename TSpec, typename TNodeAttributes, typename TEdgeAttributes>
485 void
writeRecords(TTarget & target,Graph<TSpec> const & g,TNodeAttributes const & nodeMap,TEdgeAttributes const & edgeMap,DotDrawing)486 writeRecords(
487 TTarget & target,
488 Graph<TSpec> const& g,
489 TNodeAttributes const& nodeMap,
490 TEdgeAttributes const& edgeMap,
491 DotDrawing)
492 {
493 typedef Graph<TSpec> TGraph;
494 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
495 typename DirectionIterator<TTarget, Output>::Type iter = directionIterator(target, Output());
496
497 _writeGraphType(iter,g,DotDrawing());
498 write(iter, " G {\n");
499 writeValue(iter, '\n');
500 write(iter, "/* Graph Attributes */\n");
501 write(iter, "graph [rankdir = LR];\n");
502 writeValue(iter, '\n');
503 write(iter, "/* Node Attributes */\n");
504 write(iter, "node [shape = rectangle, fillcolor = white, style = filled, fontname = \"Times-Italic\"];\n");
505 writeValue(iter, '\n');
506 write(iter, "/* Edge Attributes */\n");
507 write(iter, "edge [fontname = \"Times-Italic\", arrowsize = 0.75, fontsize = 16];\n");
508 writeValue(iter, '\n');
509
510 write(iter, "/* Nodes */\n");
511 typedef typename Iterator<TGraph, VertexIterator>::Type TConstIter;
512 TConstIter it(g);
513 for(;!atEnd(it);++it) {
514 appendNumber(iter, (int)*it);
515 write(iter, " [");
516 write(iter, getProperty(nodeMap, *it));
517 write(iter, "];\n");
518 }
519 writeValue(iter, '\n');
520
521 write(iter, "/* Edges */\n");
522 typedef typename Iterator<TGraph, EdgeIterator>::Type TConstEdIter;
523 TConstEdIter itEd(g);
524 for(;!atEnd(itEd);++itEd) {
525 TVertexDescriptor sc = sourceVertex(itEd);
526 TVertexDescriptor tr = targetVertex(itEd);
527 appendNumber(iter, sc);
528 _writeEdgeType(iter, g, DotDrawing());
529 appendNumber(iter, tr);
530 write(iter, " [");
531 write(iter, getProperty(edgeMap, *itEd));
532 write(iter, "];\n");
533 }
534 writeValue(iter, '\n');
535
536 _writeGraphFooter(iter,g,DotDrawing());
537
538 write(iter, "}\n");
539 }
540
541 //////////////////////////////////////////////////////////////////////////////
542
543 template <typename TFile, typename TSpec, typename TNodeAttributes>
544 inline void
writeRecords(TFile & file,Graph<TSpec> const & g,TNodeAttributes const & nodeMap,DotDrawing)545 writeRecords(
546 TFile & file,
547 Graph<TSpec> const& g,
548 TNodeAttributes const& nodeMap,
549 DotDrawing)
550 {
551 //IOREV _doc_ _batchreading_
552 String<String<char> > edgeMap;
553 _createEdgeAttributes(g,edgeMap);
554 writeRecords(file,g,nodeMap,edgeMap,DotDrawing());
555 }
556
557
558 //////////////////////////////////////////////////////////////////////////////
559
560 template <typename TFile, typename TSpec>
561 inline void
writeRecords(TFile & file,Graph<TSpec> const & g,DotDrawing)562 writeRecords(
563 TFile & file,
564 Graph<TSpec> const& g,
565 DotDrawing)
566 {
567 //IOREV _doc_ _batchreading_
568 String<String<char> > nodeMap;
569 _createNodeAttributes(g,nodeMap);
570 String<String<char> > edgeMap;
571 _createEdgeAttributes(g,edgeMap);
572 writeRecords(file,g,nodeMap,edgeMap,DotDrawing());
573 }
574
575
576
577
578
579 //////////////////////////////////////////////////////////////////////////////
580 // READING
581 //////////////////////////////////////////////////////////////////////////////
582
583 //////////////////////////////////////////////////////////////////////////////
584
585 template<typename TSpec, typename TStatement, typename TNodeAttributes, typename TEdgeAttributes, typename TNodeIdMap>
586 inline void
_addNode(Graph<TSpec> & g,TStatement & node_id,TStatement & attr_list,TNodeAttributes & nodeMap,TEdgeAttributes &,TNodeIdMap & nodeIdMap)587 _addNode(Graph<TSpec>& g,
588 TStatement& node_id,
589 TStatement& attr_list,
590 TNodeAttributes& nodeMap,
591 TEdgeAttributes&,
592 TNodeIdMap& nodeIdMap)
593 {
594 typedef Graph<TSpec> TGraph;
595 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
596
597 if (nodeIdMap.find(node_id) == nodeIdMap.end()) {
598 TVertexDescriptor _id = addVertex(g);
599 nodeIdMap.insert(std::make_pair(node_id, _id));
600 resizeVertexMap(nodeMap, g);
601 assignProperty(nodeMap, _id, attr_list);
602 }
603 }
604
605 //////////////////////////////////////////////////////////////////////////////
606
607 template<typename TCargo, typename TSpec, typename TVertexDescriptor, typename TNodeAttributes, typename TEdgeAttributes, typename TStatement>
608 inline void
_addEdge(Graph<Directed<TCargo,TSpec>> & g,TVertexDescriptor sourceV,TVertexDescriptor targetV,TNodeAttributes &,TEdgeAttributes & edgeMap,TStatement & attr_list)609 _addEdge(Graph<Directed<TCargo, TSpec> >& g,
610 TVertexDescriptor sourceV,
611 TVertexDescriptor targetV,
612 TNodeAttributes&,
613 TEdgeAttributes& edgeMap,
614 TStatement& attr_list)
615 {
616 typedef Graph<Directed<TCargo, TSpec> > TGraph;
617 typedef typename EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
618 TEdgeDescriptor e = addEdge(g, sourceV, targetV);
619 resizeEdgeMap(edgeMap, g);
620 assignProperty(edgeMap, e, attr_list);
621 }
622
623 //////////////////////////////////////////////////////////////////////////////
624
625 template<typename TCargo, typename TSpec, typename TVertexDescriptor, typename TNodeAttributes, typename TEdgeAttributes, typename TStatement>
626 inline void
_addEdge(Graph<Undirected<TCargo,TSpec>> & g,TVertexDescriptor sourceV,TVertexDescriptor targetV,TNodeAttributes &,TEdgeAttributes & edgeMap,TStatement & attr_list)627 _addEdge(Graph<Undirected<TCargo, TSpec> >& g,
628 TVertexDescriptor sourceV,
629 TVertexDescriptor targetV,
630 TNodeAttributes&,
631 TEdgeAttributes& edgeMap,
632 TStatement& attr_list)
633 {
634 typedef Graph<Undirected<TCargo, TSpec> > TGraph;
635 typedef typename EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
636 TEdgeDescriptor e = addEdge(g, sourceV, targetV);
637 resizeEdgeMap(edgeMap, g);
638 assignProperty(edgeMap, e, attr_list);
639 }
640
641 //////////////////////////////////////////////////////////////////////////////
642
643 template<typename TCargo, typename TSpec, typename TVertexDescriptor, typename TNodeAttributes, typename TEdgeAttributes, typename TStatement>
644 inline void
_addEdge(Graph<Tree<TCargo,TSpec>> & g,TVertexDescriptor sourceV,TVertexDescriptor targetV,TNodeAttributes &,TEdgeAttributes & edgeMap,TStatement & attr_list)645 _addEdge(Graph<Tree<TCargo, TSpec> >& g,
646 TVertexDescriptor sourceV,
647 TVertexDescriptor targetV,
648 TNodeAttributes&,
649 TEdgeAttributes& edgeMap,
650 TStatement& attr_list)
651 {
652 typedef Graph<Tree<TCargo, TSpec> > TGraph;
653 typedef typename EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
654 TEdgeDescriptor e = addEdge(g, sourceV, targetV);
655 resizeEdgeMap(edgeMap, g);
656 assignProperty(edgeMap, e, attr_list);
657 }
658
659 //////////////////////////////////////////////////////////////////////////////
660
661 template<typename TAlphabet, typename TCargo, typename TSpec, typename TString>
662 inline typename Alphabet<Graph<Automaton<TAlphabet, TCargo, TSpec> > >::Type
_getInternalLabel(Graph<Automaton<TAlphabet,TCargo,TSpec>> &,TString & str)663 _getInternalLabel(Graph<Automaton<TAlphabet, TCargo, TSpec> >&,
664 TString& str)
665 {
666 return str[0];
667 }
668
669 //////////////////////////////////////////////////////////////////////////////
670
671 template<typename TAlphabet, typename TCargo, typename TSpec, typename TString>
672 inline String<TAlphabet>
_getInternalLabel(Graph<Automaton<TAlphabet,TCargo,WordGraph<TSpec>>> &,TString & str)673 _getInternalLabel(Graph<Automaton<TAlphabet, TCargo, WordGraph<TSpec> > >&,
674 TString& str)
675 {
676 return str;
677 }
678
679 //////////////////////////////////////////////////////////////////////////////
680
681 template<typename TAlphabet, typename TCargo, typename TSpec, typename TVertexDescriptor, typename TNodeAttributes, typename TEdgeAttributes, typename TStatement>
682 inline void
_addEdge(Graph<Automaton<TAlphabet,TCargo,TSpec>> & g,TVertexDescriptor sourceV,TVertexDescriptor targetV,TNodeAttributes &,TEdgeAttributes & edgeMap,TStatement & attr_list)683 _addEdge(Graph<Automaton<TAlphabet, TCargo, TSpec> >& g,
684 TVertexDescriptor sourceV,
685 TVertexDescriptor targetV,
686 TNodeAttributes&,
687 TEdgeAttributes& edgeMap,
688 TStatement& attr_list)
689 {
690 typedef Graph<Automaton<TAlphabet, TCargo, TSpec> > TGraph;
691 typedef typename EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
692
693 // We need the label
694 typedef typename Value<TStatement>::Type TValue;
695 typedef typename Iterator<TStatement>::Type TIter;
696 typedef typename Position<TIter>::Type TPos;
697
698 String<TValue> label;
699 TIter it = begin(attr_list);
700 bool found = false;
701 for(;!atEnd(it);goNext(it)) {
702 TPos pos = position(it);
703 if (*it == ',') {
704 found = false;
705 } else if (found) {
706 append(label, *it);
707 } else if ((pos + 5 < length(attr_list)) &&
708 (infix(attr_list, it, it + 5) == "label"))
709 {
710 found = true;
711 it += 5;
712 }
713 }
714 TEdgeDescriptor e = addEdge(g, sourceV, targetV, _getInternalLabel(g, label));
715 resizeEdgeMap(edgeMap, g);
716 assignProperty(edgeMap, e, attr_list);
717 }
718
719
720 //////////////////////////////////////////////////////////////////////////////
721
722 template<typename TSpec, typename TStatement, typename TNodeAttributes, typename TEdgeAttributes, typename TNodeIdMap>
723 inline void
_addEdge(Graph<TSpec> & g,TStatement & left_node_id,TStatement & right_node_id,TStatement & attr_list,TNodeAttributes & nodeMap,TEdgeAttributes & edgeMap,TNodeIdMap & nodeIdMap)724 _addEdge(Graph<TSpec>& g,
725 TStatement& left_node_id,
726 TStatement& right_node_id,
727 TStatement& attr_list,
728 TNodeAttributes& nodeMap,
729 TEdgeAttributes& edgeMap,
730 TNodeIdMap& nodeIdMap)
731 {
732 typedef Graph<TSpec> TGraph;
733 typedef typename Value<TStatement>::Type TValue;
734 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
735 typedef std::map<String<TValue>, TVertexDescriptor> TMap;
736
737 TVertexDescriptor sourceV;
738 TVertexDescriptor targetV;
739
740 typename TMap::iterator pos;
741 pos = nodeIdMap.find(left_node_id);
742 if (pos == nodeIdMap.end()) return;
743 else sourceV = pos->second;
744
745 pos = nodeIdMap.find(right_node_id);
746 if (pos == nodeIdMap.end()) return;
747 else targetV = pos->second;
748
749 _addEdge(g, sourceV, targetV, nodeMap, edgeMap, attr_list);
750 }
751
752 //////////////////////////////////////////////////////////////////////////////
753
754 template<typename TSpec, typename TStatement, typename TNodeAttributes, typename TEdgeAttributes, typename TNodeIdMap>
755 inline void
_processNodeStatement(Graph<TSpec> & g,TStatement & stmt,TNodeAttributes & nodeMap,TEdgeAttributes & edgeMap,TNodeIdMap & nodeIdMap)756 _processNodeStatement(Graph<TSpec>& g,
757 TStatement& stmt,
758 TNodeAttributes& nodeMap,
759 TEdgeAttributes& edgeMap,
760 TNodeIdMap& nodeIdMap)
761 {
762 typedef typename Value<TStatement>::Type TValue;
763 typedef typename Iterator<TStatement>::Type TIter;
764
765 String<TValue> node_id;
766 String<TValue> attr_list; // Multiple attribute lists are ignored
767 bool inAttr = false;
768 TIter it = begin(stmt);
769 for(;!atEnd(it);goNext(it)) {
770 if (*it == '[') {
771 inAttr = true;
772 continue;
773 } else if (*it == ']') {
774 // Finished
775 break;
776 } else if ((*it == ' ') ||
777 (*it == '"')) {
778 continue;
779 }
780 if (inAttr) {
781 append(attr_list, *it);
782 } else {
783 append(node_id, *it);
784 }
785 }
786 _addNode(g, node_id, attr_list, nodeMap, edgeMap, nodeIdMap);
787 }
788
789
790 //////////////////////////////////////////////////////////////////////////////
791
792 template<typename TSpec, typename TStatement, typename TNodeAttributes, typename TEdgeAttributes, typename TPosition, typename TNodeIdMap>
793 inline void
_processEdgeStatement(Graph<TSpec> & g,TStatement & stmt,TNodeAttributes & nodeMap,TEdgeAttributes & edgeMap,TPosition pos,TNodeIdMap & nodeIdMap)794 _processEdgeStatement(Graph<TSpec>& g,
795 TStatement& stmt,
796 TNodeAttributes& nodeMap,
797 TEdgeAttributes& edgeMap,
798 TPosition pos,
799 TNodeIdMap& nodeIdMap)
800 {
801 typedef typename Value<TStatement>::Type TValue;
802 typedef typename Iterator<TStatement>::Type TIter;
803
804 String<TValue> left_node_id;
805 String<TValue> right_node_id;
806 String<TValue> attr_list; // Multiple attribute lists are ignored
807 bool inAttr = false;
808 TIter it = begin(stmt);
809 unsigned int localPos = 0;
810 for(;!atEnd(it);goNext(it), ++localPos) {
811 if (*it == '[') {
812 inAttr = true;
813 continue;
814 } else if (*it == ']') {
815 // Finished
816 break;
817 } else if ((*it == ' ') ||
818 (*it == '"')) {
819 continue;
820 }
821 if (inAttr) {
822 append(attr_list, *it);
823 } else if (localPos < pos) {
824 append(left_node_id, *it);
825 } else if (localPos > pos+1) {
826 append(right_node_id, *it);
827 }
828 }
829 //std::cout << left_node_id << "," << right_node_id << "," << std::endl;
830 _addEdge(g, left_node_id, right_node_id, attr_list, nodeMap, edgeMap, nodeIdMap);
831 }
832
833 //////////////////////////////////////////////////////////////////////////////
834
835 template<typename TSpec, typename TStatement, typename TNodeAttributes, typename TEdgeAttributes, typename TNodeIdMap>
836 inline void
_processStatement(Graph<TSpec> & g,TStatement & stmt,TNodeAttributes & nodeMap,TEdgeAttributes & edgeMap,TNodeIdMap & nodeIdMap)837 _processStatement(Graph<TSpec>& g,
838 TStatement& stmt,
839 TNodeAttributes& nodeMap,
840 TEdgeAttributes& edgeMap,
841 TNodeIdMap& nodeIdMap)
842 {
843 // Clear everything up to the last line
844 typedef typename Value<TStatement>::Type TValue;
845 typedef typename Iterator<TStatement>::Type TIter;
846
847 // Exclude header and empty lines
848 TIter it = begin(stmt);
849 String<TValue> _id;
850 for(;!atEnd(it);goNext(it)) {
851 if ((*it != '\t') && (*it != ' ') && (*it != '\n') && (*it != '\r')) {
852 append(_id, *it);
853 } else {
854 // Exclude any graph, subgraph, node and edge processing attributes
855 if ((_id == "graph") || (_id == "node") || (_id == "edge") || (_id == "subgraph") || (length(_id)<1)) {
856 clear(stmt);
857 return;
858 } else break;
859 }
860 }
861
862 // Process Edges
863 it = begin(stmt);
864 clear(_id);
865 _id = "00";
866 unsigned int pos = 0;
867 for(;!atEnd(it);goNext(it), ++pos) {
868 _id[pos % 2] = *it;
869 if ((_id == "--") || (_id == "->")) {
870 //std::cout << stmt << std::endl;
871 _processEdgeStatement(g, stmt, nodeMap, edgeMap, pos - 1, nodeIdMap);
872 clear(stmt);
873 return;
874 }
875 }
876
877 // Process nodes
878 //std::cout << stmt << std::endl;
879 _processNodeStatement(g, stmt, nodeMap, edgeMap, nodeIdMap);
880 clear(stmt);
881 }
882
883
884 //////////////////////////////////////////////////////////////////////////////
885
886 template <typename TSpec, typename TNodeAttributes, typename TEdgeAttributes, typename TInStream>
readRecords(Graph<TSpec> & g,TNodeAttributes & nodeMap,TEdgeAttributes & edgeMap,TInStream & stream,DotDrawing)887 void readRecords(
888 Graph<TSpec>& g,
889 TNodeAttributes& nodeMap,
890 TEdgeAttributes& edgeMap,
891 TInStream & stream,
892 DotDrawing)
893 {
894 typename DirectionIterator<TInStream, Input>::Type reader = directionIterator(stream, Input());
895
896 typedef Graph<TSpec> TGraph;
897 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
898 typedef std::map<CharString, TVertexDescriptor> TMap;
899 TMap nodeIdMap;
900
901 CharString stmt;
902 while (!atEnd(reader))
903 {
904 clear(stmt);
905 readUntil(stmt, reader, EqualsChar<';'>());
906 _processStatement(g, stmt, nodeMap, edgeMap, nodeIdMap);
907 skipLine(reader);
908 }
909 }
910
911 //////////////////////////////////////////////////////////////////////////////
912
913 template <typename TSpec, typename TInStream>
readRecords(Graph<TSpec> & g,TInStream & stream,DotDrawing)914 void readRecords(
915 Graph<TSpec>& g,
916 TInStream & stream,
917 DotDrawing)
918 {
919 String<CharString> nodeMap;
920 String<CharString> edgeMap;
921 readRecords(g, nodeMap, edgeMap, stream, DotDrawing());
922 }
923
924
925 }// namespace SEQAN_NAMESPACE_MAIN
926
927 #endif //#ifndef SEQAN_HEADER_...
928