1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2010, 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 #ifndef SEQAN_HEADER_GRAPH_IMPL_DIRECTED_H
34 #define SEQAN_HEADER_GRAPH_IMPL_DIRECTED_H
35
36 namespace SEQAN_NAMESPACE_MAIN
37 {
38 //////////////////////////////////////////////////////////////////////////////
39 // Graph - Directed
40 //////////////////////////////////////////////////////////////////////////////
41
42 //////////////////////////////////////////////////////////////////////////////
43
44 /**
45 .Spec.Directed Graph:
46 ..cat:Graph
47 ..general:Class.Graph
48 ..summary:A directed graph that stores the edges in an adjacency list.
49 ..description:
50 ...image:directedGraph|A directed graph.
51 ..signature:Graph<Directed<TCargo, TSpec> >
52 ..param.TCargo:The cargo type that can be attached to the edges.
53 ...metafunction:Metafunction.Cargo
54 ...remarks:Use @Metafunction.Cargo@ to get the cargo type of a directed graph.
55 ...default:$void$
56 ..param.TSpec:The specializing type for the graph.
57 ...metafunction:Metafunction.Spec
58 ...remarks:Use WithoutEdgeId here to omit edge ids.
59 Note: If edges do not store ids external property maps do not work.
60 ...default:$Default$, see @Tag.Default@.
61 ..include:seqan/graph_types.h
62 */
63 template<typename TCargo, typename TSpec>
64 class Graph<Directed<TCargo, TSpec> >
65 {
66 public:
67 typedef typename VertexIdHandler<Graph>::Type TVertexIdManager_;
68 typedef typename EdgeIdHandler<Graph>::Type TEdgeIdManager_;
69 typedef typename EdgeType<Graph>::Type TEdgeStump_;
70 typedef Allocator<SinglePool<sizeof(TEdgeStump_)> > TAllocator_;
71
72 String<TEdgeStump_*> data_vertex; // Pointers to EdgeStump lists
73 TVertexIdManager_ data_id_managerV;
74 TEdgeIdManager_ data_id_managerE;
75 TAllocator_ data_allocator;
76
77 //____________________________________________________________________________
78
79
Graph()80 Graph() {
81 SEQAN_CHECKPOINT
82 }
83
~Graph()84 ~Graph() {
85 SEQAN_CHECKPOINT
86 clear(*this);
87 }
88
Graph(Graph const & _other)89 Graph(Graph const & _other) :
90 data_allocator(_other.data_allocator)
91 {
92 SEQAN_CHECKPOINT
93 _copyGraph(_other, *this);
94 }
95
96 Graph const& operator = (Graph const & _other) {
97 SEQAN_CHECKPOINT
98 if (this == &_other) return *this;
99 clear(*this);
100 data_allocator = _other.data_allocator;
101 _copyGraph(_other, *this);
102 return *this;
103 }
104 };
105
106
107 //////////////////////////////////////////////////////////////////////////////
108 // INTERNAL FUNCTIONS
109 //////////////////////////////////////////////////////////////////////////////
110
111 //////////////////////////////////////////////////////////////////////////////
112
113 template<typename TCargo, typename TSpec>
114 inline String<typename EdgeType<Graph<Directed<TCargo, TSpec> > >::Type*>&
_getVertexString(Graph<Directed<TCargo,TSpec>> const & g)115 _getVertexString(Graph<Directed<TCargo, TSpec> > const& g) {
116 SEQAN_CHECKPOINT
117 typedef Graph<Directed<TCargo, TSpec> > TGraph;
118 typedef typename EdgeType<TGraph>::Type TEdgeStump;
119 return const_cast<String<TEdgeStump*>&>(g.data_vertex);
120 }
121
122 /////////////////////////////////////////////////////////////////////////////
123
124 template<typename TCargo, typename TSpec>
125 inline typename VertexIdHandler<Graph<Directed<TCargo, TSpec> > >::Type&
_getVertexIdManager(Graph<Directed<TCargo,TSpec>> const & g)126 _getVertexIdManager(Graph<Directed<TCargo, TSpec> > const& g) {
127 SEQAN_CHECKPOINT
128 typedef Graph<Directed<TCargo, TSpec> > TGraph;
129 typedef typename VertexIdHandler<TGraph>::Type TVertexIdManager;
130 return const_cast<TVertexIdManager&>(g.data_id_managerV);
131 }
132
133 //////////////////////////////////////////////////////////////////////////////
134
135 template<typename TCargo, typename TSpec>
136 inline typename EdgeIdHandler<Graph<Directed<TCargo, TSpec> > >::Type&
_getEdgeIdManager(Graph<Directed<TCargo,TSpec>> const & g)137 _getEdgeIdManager(Graph<Directed<TCargo, TSpec> > const& g) {
138 SEQAN_CHECKPOINT
139 typedef Graph<Directed<TCargo, TSpec> > TGraph;
140 typedef typename EdgeIdHandler<TGraph>::Type TEdgeIdManager;
141 return const_cast<TEdgeIdManager&>(g.data_id_managerE);
142 }
143
144
145 //////////////////////////////////////////////////////////////////////////////
146
147 template<typename TCargo, typename TSpec>
148 inline void
_copyGraph(Graph<Directed<TCargo,TSpec>> const & source,Graph<Directed<TCargo,TSpec>> & dest,bool transpose)149 _copyGraph(Graph<Directed<TCargo, TSpec> > const& source,
150 Graph<Directed<TCargo, TSpec> >& dest,
151 bool transpose)
152 {
153 SEQAN_CHECKPOINT
154 typedef Graph<Directed<TCargo, TSpec> > TGraph;
155 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
156 typedef typename EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
157 typedef typename EdgeType<TGraph>::Type TEdgeStump;
158 typedef typename Iterator<String<TEdgeStump*> const, Standard>::Type TIterConst;
159 typedef typename Iterator<String<TEdgeStump*>, Standard>::Type TIter;
160 clear(dest);
161 resize(dest.data_vertex, length(_getVertexString(source)));
162 TIter itInit = begin(dest.data_vertex, Standard());
163 TIter itInitEnd = end(dest.data_vertex, Standard());
164 for(;itInit != itInitEnd; ++itInit) *itInit = (TEdgeStump*) 0;
165 TIterConst it = begin(source.data_vertex, Standard());
166 TIterConst itEnd = end(source.data_vertex, Standard());
167 TVertexDescriptor pos = 0;
168 for(;it != itEnd; ++it, ++pos) {
169 TEdgeStump* current = *it;
170 TVertexDescriptor sourceVertex = pos;
171 while(current != (TEdgeStump*) 0) {
172 TVertexDescriptor targetVertex = current->data_target;
173 // Create missing vertices
174 if (sourceVertex>targetVertex) _createVertices(dest,sourceVertex);
175 else _createVertices(dest,targetVertex);
176 // Add edge
177 TEdgeDescriptor e;
178 if (!transpose) e = addEdge(dest, sourceVertex, targetVertex);
179 else e = addEdge(dest, targetVertex, sourceVertex);
180 _assignId(e, _getId(current));
181 assignCargo(e, getCargo(current));
182 current = getNextT(current);
183 }
184 }
185 dest.data_id_managerV = source.data_id_managerV;
186 dest.data_id_managerE = source.data_id_managerE;
187 }
188
189 //////////////////////////////////////////////////////////////////////////////
190
191 template<typename TCargo, typename TSpec>
192 inline void
_copyGraph(Graph<Directed<TCargo,TSpec>> const & source,Graph<Directed<TCargo,TSpec>> & dest)193 _copyGraph(Graph<Directed<TCargo, TSpec> > const& source,
194 Graph<Directed<TCargo, TSpec> >& dest)
195 {
196 _copyGraph(source, dest, false);
197 }
198
199 //////////////////////////////////////////////////////////////////////////////
200 // FUNCTIONS
201 //////////////////////////////////////////////////////////////////////////////
202
203
204 //////////////////////////////////////////////////////////////////////////////
205
206 /**
207 .Function.transpose:
208 ..cat:Graph
209 ..summary:Transposes a graph, either in-place or from source to dest.
210 ..signature:transpose(source [, dest])
211 ..param.source:Source graph.
212 ...type:Class.Graph
213 ..param.dest:Destination graph.
214 ...type:Class.Graph
215 ..returns:void
216 ..include:seqan/graph_types.h
217 */
218
219 template<typename TCargo, typename TSpec>
220 inline void
transpose(Graph<Directed<TCargo,TSpec>> const & source,Graph<Directed<TCargo,TSpec>> & dest)221 transpose(Graph<Directed<TCargo, TSpec> > const& source,
222 Graph<Directed<TCargo, TSpec> >& dest)
223 {
224 SEQAN_CHECKPOINT
225 _copyGraph(source, dest, true);
226 }
227
228 //////////////////////////////////////////////////////////////////////////////
229
230 template<typename TCargo, typename TSpec>
231 inline void
transpose(Graph<Directed<TCargo,TSpec>> & g)232 transpose(Graph<Directed<TCargo, TSpec> >& g)
233 {
234 SEQAN_CHECKPOINT
235 Graph<Directed<TCargo, TSpec> > dest;
236 _copyGraph(g, dest, true);
237 g = dest;
238 }
239
240 //////////////////////////////////////////////////////////////////////////////
241
242 /**
243 .Function.numEdges:
244 ..cat:Graph
245 ..summary:Number of edges in a graph.
246 ..signature:numEdges(g)
247 ..param.g:A graph.
248 ...type:Class.Graph
249 ..returns:Number of edges.
250 ..see:Function.numVertices
251 ..include:seqan/graph_types.h
252 */
253
254 template<typename TCargo, typename TSpec>
255 inline typename Size<Graph<Directed<TCargo, TSpec> > >::Type
numEdges(Graph<Directed<TCargo,TSpec>> const & g)256 numEdges(Graph<Directed<TCargo, TSpec> > const& g)
257 {
258 SEQAN_CHECKPOINT
259 return idCount(g.data_id_managerE);
260 }
261
262 //////////////////////////////////////////////////////////////////////////////
263
264 /**
265 .Function.numVertices:
266 ..cat:Graph
267 ..summary:Number of vertices in a graph.
268 ..signature:numVertices(g)
269 ..param.g:A graph.
270 ...type:Class.Graph
271 ..returns:Number of vertices.
272 ..see:Function.numEdges
273 ..include:seqan/graph_types.h
274 */
275
276 template<typename TCargo, typename TSpec>
277 inline typename Size<Graph<Directed<TCargo, TSpec> > >::Type
numVertices(Graph<Directed<TCargo,TSpec>> const & g)278 numVertices(Graph<Directed<TCargo, TSpec> > const& g)
279 {
280 SEQAN_CHECKPOINT
281 return idCount(g.data_id_managerV);
282 }
283
284 //////////////////////////////////////////////////////////////////////////////
285
286 /**
287 .Function.empty:
288 ..cat:Graph
289 ..param.object.type:Class.Graph
290 ..include:seqan/graph_types.h
291 */
292
293 template<typename TCargo, typename TSpec>
294 inline bool
empty(Graph<Directed<TCargo,TSpec>> const & g)295 empty(Graph<Directed<TCargo, TSpec> > const& g)
296 {
297 SEQAN_CHECKPOINT
298 return (!(idCount(g.data_id_managerV)));
299 }
300
301 //////////////////////////////////////////////////////////////////////////////
302
303 /**
304 .Function.clearEdges:
305 ..cat:Graph
306 ..summary:Removes all edges in a graph.
307 ..signature:clearEdges(g)
308 ..param.g:A graph.
309 ...type:Class.Graph
310 ..returns:void
311 ..see:Function.clearVertices
312 ..see:Function.clear
313 ..include:seqan/graph_types.h
314 */
315
316 template<typename TCargo, typename TSpec>
317 inline void
clearEdges(Graph<Directed<TCargo,TSpec>> & g)318 clearEdges(Graph<Directed<TCargo, TSpec> >& g)
319 {
320 SEQAN_CHECKPOINT
321 typedef Graph<Directed<TCargo, TSpec> > TGraph;
322 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
323 typedef typename EdgeType<TGraph>::Type TEdgeStump;
324 typedef typename Iterator<String<TEdgeStump*>, Standard>::Type TIter;
325 TIter it = begin(g.data_vertex, Standard());
326 TIter itEnd = end(g.data_vertex, Standard());
327 TVertexDescriptor pos = 0;
328 for(;it != itEnd; ++it, ++pos)
329 if (*it != (TEdgeStump*) 0) removeOutEdges(g, pos);
330 }
331
332 //////////////////////////////////////////////////////////////////////////////
333
334 /**
335 .Function.clearVertices:
336 ..cat:Graph
337 ..summary:Removes all vertices in a graph.
338 ..signature:clearVertices(g)
339 ..param.g:A graph.
340 ...type:Class.Graph
341 ..returns:void
342 ..see:Function.clearEdges
343 ..see:Function.clear
344 ..include:seqan/graph_types.h
345 */
346
347 template<typename TCargo, typename TSpec>
348 inline void
clearVertices(Graph<Directed<TCargo,TSpec>> & g)349 clearVertices(Graph<Directed<TCargo, TSpec> >& g)
350 {
351 SEQAN_CHECKPOINT
352 clearEdges(g);
353 releaseAll(g.data_id_managerV);
354 clear(g.data_vertex);
355 }
356
357
358 //////////////////////////////////////////////////////////////////////////////
359
360
361 /**
362 .Function.clear:
363 ..cat:Graph
364 ..param.object.type:Class.Graph
365 ..remarks:If $object$ is a @Class.Graph.graph@, then all vertices and all edges are removed.
366 ..include:seqan/graph_types.h
367 */
368
369 template<typename TCargo, typename TSpec>
370 inline void
clear(Graph<Directed<TCargo,TSpec>> & g)371 clear(Graph<Directed<TCargo, TSpec> >& g)
372 {
373 SEQAN_CHECKPOINT
374 clearVertices(g);
375 }
376
377 //////////////////////////////////////////////////////////////////////////////
378
379 /**
380 .Function.outDegree:
381 ..cat:Graph
382 ..summary:Number of outgoing edges for a given vertex.
383 ..signature:outDegree(g, vertex)
384 ..param.g:A graph.
385 ...type:Class.Graph
386 ..param.g:A vertex descriptor.
387 ...type:Metafunction.VertexDescriptor
388 ..returns:Number of out-edges.
389 ..see:Function.inDegree
390 ..see:Function.degree
391 ..include:seqan/graph_types.h
392 */
393
394 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
395 inline typename Size<Graph<Directed<TCargo, TSpec> > >::Type
outDegree(Graph<Directed<TCargo,TSpec>> const & g,TVertexDescriptor const vertex)396 outDegree(Graph<Directed<TCargo, TSpec> > const& g,
397 TVertexDescriptor const vertex)
398 {
399 SEQAN_CHECKPOINT
400 SEQAN_ASSERT(idInUse(g.data_id_managerV, vertex) == true)
401
402 typedef Graph<Directed<TCargo, TSpec> > TGraph;
403 typedef typename EdgeType<TGraph>::Type TEdgeStump;
404 typedef typename Size<TGraph>::Type TSize;
405 TSize count=0;
406 TEdgeStump* current = getValue(g.data_vertex, vertex);
407 while(current!=0) {
408 current = getNextT(current);
409 ++count;
410 }
411 return count;
412 }
413
414 //////////////////////////////////////////////////////////////////////////////
415
416 /**
417 .Function.inDegree:
418 ..cat:Graph
419 ..summary:Number of incoming edges for a given vertex.
420 ..signature:inDegree(g, vertex)
421 ..param.g:A graph.
422 ...type:Class.Graph
423 ..param.g:A vertex descriptor.
424 ...type:Metafunction.VertexDescriptor
425 ..returns:Number of in-edges.
426 ..see:Function.outDegree
427 ..see:Function.degree
428 ..include:seqan/graph_types.h
429 */
430
431 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
432 inline typename Size<Graph<Directed<TCargo, TSpec> > >::Type
inDegree(Graph<Directed<TCargo,TSpec>> const & g,TVertexDescriptor const vertex)433 inDegree(Graph<Directed<TCargo, TSpec> > const& g,
434 TVertexDescriptor const vertex)
435 {
436 SEQAN_CHECKPOINT
437 SEQAN_ASSERT(idInUse(g.data_id_managerV, vertex) == true)
438
439 typedef Graph<Directed<TCargo, TSpec> > TGraph;
440 typedef typename EdgeType<TGraph>::Type TEdgeStump;
441 typedef typename Size<TGraph>::Type TSize;
442 typedef typename Iterator<String<TEdgeStump*> const, Standard>::Type TIterConst;
443 TIterConst it = begin(g.data_vertex, Standard());
444 TIterConst itEnd = end(g.data_vertex, Standard());
445
446 TSize count=0;
447 for(;it!=itEnd;++it) {
448 TEdgeStump* current = *it;
449 while(current!=0) {
450 if ( (TVertexDescriptor) getTarget(current) == vertex) ++count;
451 current = getNextT(current);
452 }
453 }
454 return count;
455 }
456
457 //////////////////////////////////////////////////////////////////////////////
458
459 /**
460 .Function.degree:
461 ..cat:Graph
462 ..summary:Number of incident edges for a given vertex.
463 ..signature:degree(g, vertex)
464 ..param.g:A graph.
465 ...type:Class.Graph
466 ..param.g:A vertex descriptor.
467 ...type:Metafunction.VertexDescriptor
468 ..returns:Number of incident edges.
469 ..see:Function.outDegree
470 ..see:Function.inDegree
471 ..include:seqan/graph_types.h
472 */
473
474 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
475 inline typename Size<Graph<Directed<TCargo, TSpec> > >::Type
degree(Graph<Directed<TCargo,TSpec>> const & g,TVertexDescriptor const vertex)476 degree(Graph<Directed<TCargo, TSpec> > const& g,
477 TVertexDescriptor const vertex)
478 {
479 SEQAN_CHECKPOINT
480 return (inDegree(g,vertex)+outDegree(g,vertex));
481 }
482
483 //////////////////////////////////////////////////////////////////////////////
484
485 /**
486 .Function.addVertex:
487 ..cat:Graph
488 ..summary:Adds a new vertex to the graph.
489 ..signature:addVertex(g)
490 ..param.g:A graph.
491 ...type:Class.Graph
492 ..returns:A new vertex descriptor.
493 ...type:Metafunction.VertexDescriptor
494 ..see:Function.removeVertex
495 ..include:seqan/graph_types.h
496 */
497
498 template<typename TCargo, typename TSpec>
499 inline typename VertexDescriptor<Graph<Directed<TCargo, TSpec> > >::Type
addVertex(Graph<Directed<TCargo,TSpec>> & g)500 addVertex(Graph<Directed<TCargo, TSpec> >& g)
501 {
502 SEQAN_CHECKPOINT
503 typedef Graph<Directed<TCargo, TSpec> > TGraph;
504 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
505 typedef typename EdgeType<TGraph>::Type TEdgeStump;
506 TVertexDescriptor vd = obtainId(g.data_id_managerV);
507 if (vd == length(g.data_vertex)) appendValue(g.data_vertex, (TEdgeStump*) 0);
508 else g.data_vertex[vd] = (TEdgeStump*) 0;
509 return vd;
510 }
511
512 //////////////////////////////////////////////////////////////////////////////
513
514 /**
515 .Function.removeVertex:
516 ..cat:Graph
517 ..summary:Removes a vertex.
518 ..signature:removeVertex(g, v)
519 ..param.g:A graph.
520 ...type:Class.Graph
521 ..param.v:A vertex descriptor.
522 ...type:Metafunction.VertexDescriptor
523 ..returns:void
524 ..see:Function.addVertex
525 ..include:seqan/graph_types.h
526 */
527
528 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
529 inline void
removeVertex(Graph<Directed<TCargo,TSpec>> & g,TVertexDescriptor const v)530 removeVertex(Graph<Directed<TCargo, TSpec> >& g,
531 TVertexDescriptor const v)
532 {
533 SEQAN_CHECKPOINT
534 SEQAN_ASSERT(idInUse(g.data_id_managerV, v) == true)
535
536 removeOutEdges(g,v); // Remove all outgoing edges
537 removeInEdges(g,v); // Remove all incoming edges
538 releaseId(g.data_id_managerV, v); // Release id
539 }
540
541 //////////////////////////////////////////////////////////////////////////////
542
543 /**
544 .Function.addEdge:
545 ..cat:Graph
546 ..summary:Adds a new edge to the graph, either with or without cargo.
547 ..remarks:For automatons a label is required.
548 ..signature:addEdge(g, source, target [,cargo | ,label])
549 ..signature:addEdge(g, source, target [,label ,cargo])
550 ..param.g:A graph.
551 ...type:Class.Graph
552 ..param.source:A vertex descriptor.
553 ...type:Metafunction.VertexDescriptor
554 ..param.target:A second vertex descriptor.
555 ...type:Metafunction.VertexDescriptor
556 ..param.label:A label for the edge.
557 ...type:Metafunction.Alphabet
558 ...remarks:Can only be used with @Spec.Automaton@.
559 ..param.cargo:A cargo object.
560 ...type:Metafunction.Cargo
561 ..returns:A new edge descriptor.
562 ...type:Metafunction.EdgeDescriptor
563 ..see:Function.removeEdge
564 ..see:Function.addEdges
565 ..include:seqan/graph_types.h
566 */
567
568 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
569 inline typename EdgeDescriptor<Graph<Directed<TCargo, TSpec> > >::Type
addEdge(Graph<Directed<TCargo,TSpec>> & g,TVertexDescriptor const source,TVertexDescriptor const target)570 addEdge(Graph<Directed<TCargo, TSpec> >& g,
571 TVertexDescriptor const source,
572 TVertexDescriptor const target)
573 {
574 SEQAN_CHECKPOINT
575 SEQAN_ASSERT(idInUse(g.data_id_managerV, source) == true)
576 SEQAN_ASSERT(idInUse(g.data_id_managerV, target) == true)
577
578 typedef Graph<Directed<TCargo, TSpec> > TGraph;
579 typedef typename EdgeType<TGraph>::Type TEdgeStump;
580 typedef typename Id<TGraph>::Type TId;
581
582 TEdgeStump* edge_ptr;
583 allocate(g.data_allocator, edge_ptr, 1);
584 valueConstruct(edge_ptr);
585 assignTarget(edge_ptr, target);
586 assignNextT(edge_ptr, (TEdgeStump*) 0);
587 TId id = obtainId(g.data_id_managerE);
588 _assignId(edge_ptr, id);
589 if (g.data_vertex[source]!=0) assignNextT(edge_ptr, getValue(g.data_vertex, source));
590 value(g.data_vertex, source)=edge_ptr;
591 return edge_ptr;
592 }
593
594 //////////////////////////////////////////////////////////////////////////////
595
596 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
597 inline typename EdgeDescriptor<Graph<Directed<TCargo, TSpec> > >::Type
addEdge(Graph<Directed<TCargo,TSpec>> & g,TVertexDescriptor const source,TVertexDescriptor const target,TCargo const cargo)598 addEdge(Graph<Directed<TCargo, TSpec> >& g,
599 TVertexDescriptor const source,
600 TVertexDescriptor const target,
601 TCargo const cargo)
602 {
603 SEQAN_CHECKPOINT
604 typedef Graph<Directed<TCargo, TSpec> > TGraph;
605 typedef typename EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
606 TEdgeDescriptor e = addEdge(g,source,target);
607 assignCargo(e,cargo);
608 return e;
609 }
610
611 //////////////////////////////////////////////////////////////////////////////
612
613 /**
614 .Function.removeEdge:
615 ..cat:Graph
616 ..summary:Removes an edge from the graph. For automatons a label is required.
617 ..signature:removeEdge(g, source, target [, label])
618 ..signature:removeEdge(g, e)
619 ..param.g:A graph.
620 ...type:Class.Graph
621 ..param.source:A vertex descriptor.
622 ...type:Metafunction.VertexDescriptor
623 ..param.target:A second vertex descriptor.
624 ...type:Metafunction.VertexDescriptor
625 ..param.label:A label for the edge.
626 ...type:Metafunction.Alphabet
627 ...remarks:Required to remove an edge in an @Spec.Automaton@.
628 ..param.e:An edge descriptor.
629 ...type:Metafunction.EdgeDescriptor
630 ..returns:void
631 ..see:Function.addEdge
632 ..see:Function.addEdges
633 ..include:seqan/graph_types.h
634 */
635
636 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
637 inline void
removeEdge(Graph<Directed<TCargo,TSpec>> & g,TVertexDescriptor const source,TVertexDescriptor const target)638 removeEdge(Graph<Directed<TCargo, TSpec> >& g,
639 TVertexDescriptor const source,
640 TVertexDescriptor const target)
641 {
642 SEQAN_CHECKPOINT
643 SEQAN_ASSERT(idInUse(g.data_id_managerV, source) == true)
644 SEQAN_ASSERT(idInUse(g.data_id_managerV, target) == true)
645
646 typedef Graph<Directed<TCargo, TSpec> > TGraph;
647 typedef typename EdgeType<TGraph>::Type TEdgeStump;
648
649 // Find edge and predecessor
650 TEdgeStump* pred = 0;
651 TEdgeStump* current = g.data_vertex[source];
652 while(current != (TEdgeStump*) 0) {
653 if ( (TVertexDescriptor) getTarget(current) == target) break;
654 pred = current;
655 current = getNextT(current);
656 }
657
658 // Not found?
659 if (current == (TEdgeStump*) 0) return;
660
661 // Relink the next pointer of predecessor
662 if (pred != (TEdgeStump*) 0) assignNextT(pred, getNextT(current));
663 else g.data_vertex[source] = getNextT(current);
664
665 // Deallocate
666 releaseId(g.data_id_managerE, _getId(current));
667 valueDestruct(current);
668 deallocate(g.data_allocator, current, 1);
669 }
670
671 //////////////////////////////////////////////////////////////////////////////
672
673 template<typename TCargo, typename TSpec, typename TEdgeDescriptor>
674 inline void
removeEdge(Graph<Directed<TCargo,TSpec>> & g,TEdgeDescriptor const edge)675 removeEdge(Graph<Directed<TCargo, TSpec> >& g,
676 TEdgeDescriptor const edge)
677 {
678 SEQAN_CHECKPOINT
679 SEQAN_ASSERT(idInUse(g.data_id_managerV, sourceVertex(g,edge)) == true)
680 SEQAN_ASSERT(idInUse(g.data_id_managerV, targetVertex(g,edge)) == true)
681
682 typedef Graph<Directed<TCargo, TSpec> > TGraph;
683 typedef typename EdgeType<TGraph>::Type TEdgeStump;
684
685 // Find edge and predecessor
686 TEdgeStump* pred = 0;
687 TEdgeStump* current = g.data_vertex[sourceVertex(g,edge)];
688 while(current != (TEdgeStump*) 0) {
689 if (current == edge) break;
690 pred = current;
691 current = getNextT(current);
692 }
693
694 // Not found?
695 if (current == (TEdgeStump*) 0) return;
696
697 // Relink the next pointer of predecessor
698 if (pred != (TEdgeStump*) 0) assignNextT(pred, getNextT(current));
699 else g.data_vertex[sourceVertex(g,edge)] = getNextT(current);
700
701 // Deallocate
702 releaseId(g.data_id_managerE, _getId(current));
703 valueDestruct(current);
704 deallocate(g.data_allocator, current, 1);
705 }
706
707 //////////////////////////////////////////////////////////////////////////////
708
709 /**
710 .Function.removeOutEdges:
711 ..cat:Graph
712 ..summary:Removes the outgoing edges of a given vertex.
713 ..signature:removeOutEdges(g, v)
714 ..param.g:A graph.
715 ...type:Class.Graph
716 ..param.v:A vertex descriptor.
717 ...type:Metafunction.VertexDescriptor
718 ..returns:void
719 ..see:Function.removeInEdges
720 ..include:seqan/graph_types.h
721 */
722
723 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
724 inline void
removeOutEdges(Graph<Directed<TCargo,TSpec>> & g,TVertexDescriptor const v)725 removeOutEdges(Graph<Directed<TCargo, TSpec> >& g,
726 TVertexDescriptor const v)
727 {
728 SEQAN_CHECKPOINT
729 SEQAN_ASSERT(idInUse(g.data_id_managerV, v) == true)
730
731 typedef Graph<Directed<TCargo, TSpec> > TGraph;
732 typedef typename EdgeType<TGraph>::Type TEdgeStump;
733 while(g.data_vertex[v] != (TEdgeStump*) 0) {
734 TVertexDescriptor target = targetVertex(g, g.data_vertex[v]);
735 removeEdge(g,v,target);
736 }
737 }
738
739 //////////////////////////////////////////////////////////////////////////////
740
741 /**
742 .Function.removeInEdges:
743 ..cat:Graph
744 ..summary:Removes the incoming edges of a given vertex.
745 ..signature:removeInEdges(g, v)
746 ..param.g:A graph.
747 ...type:Class.Graph
748 ..param.v:A vertex descriptor.
749 ...type:Metafunction.VertexDescriptor
750 ..returns:void
751 ..see:Function.removeOutEdges
752 ..include:seqan/graph_types.h
753 */
754
755 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
756 inline void
removeInEdges(Graph<Directed<TCargo,TSpec>> & g,TVertexDescriptor const v)757 removeInEdges(Graph<Directed<TCargo, TSpec> >& g,
758 TVertexDescriptor const v)
759 {
760 SEQAN_CHECKPOINT
761 SEQAN_ASSERT(idInUse(g.data_id_managerV, v) == true)
762
763 typedef Graph<Directed<TCargo, TSpec> > TGraph;
764 typedef typename EdgeType<TGraph>::Type TEdgeStump;
765 typedef typename Iterator<String<TEdgeStump*>, Standard>::Type TIter;
766 TIter it = begin(g.data_vertex, Standard());
767 TIter itEnd = end(g.data_vertex, Standard());
768 TVertexDescriptor pos = 0;
769 for(;it!=itEnd;++it, ++pos) {
770 TEdgeStump* current = *it;
771 TVertexDescriptor const sourceVertex = pos;
772 while(current!=0) {
773 if ( (TVertexDescriptor) current->data_target==v) {
774 removeEdge(g, sourceVertex, v);
775 current = g.data_vertex[sourceVertex];
776 } else {
777 current = getNextT(current);
778 }
779 }
780 }
781 }
782
783
784 //////////////////////////////////////////////////////////////////////////////
785
786 /**
787 .Function.targetVertex:
788 ..cat:Graph
789 ..summary:Returns the target vertex of an edge.
790 ..remarks:In a tree the target vertex is always the child.
791 In an undirected graph the larger vertex descriptor of the two endpoints is the target.
792 For an out-edge iterator the target is always the vertex the out-edge iterator has not been initialized with.
793 ..signature:targetVertex(g, e)
794 ..signature:targetVertex(it)
795 ..param.g:A graph.
796 ...type:Class.Graph
797 ..param.e:An edge descriptor.
798 ...type:Metafunction.EdgeDescriptor
799 ..param.it:An edge iterator.
800 ...type:Spec.Out-Edge Iterator
801 ...type:Spec.Edge Iterator
802 ..returns:A vertex descriptor.
803 ...type:Metafunction.VertexDescriptor
804 ..see:Function.sourceVertex
805 ..include:seqan/graph_types.h
806 */
807
808 template<typename TCargo, typename TSpec, typename TEdgeDescriptor>
809 inline typename VertexDescriptor<Graph<Directed<TCargo, TSpec> > >::Type
targetVertex(Graph<Directed<TCargo,TSpec>> const &,TEdgeDescriptor const edge)810 targetVertex(Graph<Directed<TCargo, TSpec> > const&,
811 TEdgeDescriptor const edge)
812 {
813 SEQAN_CHECKPOINT
814 return getTarget(edge);
815 }
816
817 //////////////////////////////////////////////////////////////////////////////
818
819 /**
820 .Function.sourceVertex:
821 ..cat:Graph
822 ..summary:Returns the source vertex of an edge.
823 ..remarks:In a tree the source vertex is always the parent.
824 In an undirected graph the smaller vertex descriptor is the source.
825 Note: If source vertices are not stored in the EdgeStump this operation is expensive.
826 Consider using sourceVertex directly on an edge iterator where this operation is fast!
827 ..signature:sourceVertex(g, e)
828 ..signature:sourceVertex(it)
829 ..param.g:A graph.
830 ...type:Class.Graph
831 ..param.e:An edge descriptor.
832 ...type:Metafunction.EdgeDescriptor
833 ..param.it:An edge iterator.
834 ...type:Spec.Out-Edge Iterator
835 ...type:Spec.Edge Iterator
836 ..returns:A vertex descriptor.
837 ...type:Metafunction.VertexDescriptor
838 ..see:Function.targetVertex
839 ..include:seqan/graph_types.h
840 */
841
842 template<typename TCargo, typename TSpec, typename TEdgeDescriptor>
843 inline typename VertexDescriptor<Graph<Directed<TCargo, TSpec> > >::Type
sourceVertex(Graph<Directed<TCargo,TSpec>> const & g,TEdgeDescriptor const edge)844 sourceVertex(Graph<Directed<TCargo, TSpec> > const& g,
845 TEdgeDescriptor const edge)
846 {
847 SEQAN_CHECKPOINT
848 typedef Graph<Directed<TCargo, TSpec> > TGraph;
849 typedef typename EdgeType<TGraph>::Type TEdgeStump;
850 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
851 typedef typename Iterator<String<TEdgeStump*> const, Standard>::Type TIterConst;
852 TIterConst it = begin(g.data_vertex, Standard());
853 TIterConst itEnd = end(g.data_vertex, Standard());
854 TVertexDescriptor pos = 0;
855 for(;it!=itEnd;++it, ++pos) {
856 TEdgeDescriptor current = *it;
857 while(current!=(TEdgeDescriptor) 0) {
858 if (current == edge) return pos;
859 current=getNextT(current);
860 }
861 }
862 return 0;
863 }
864
865 //////////////////////////////////////////////////////////////////////////////
866
867 /**
868 .Function.getAdjacencyMatrix:
869 ..cat:Graph
870 ..summary:Returns an adjacency matrix representation of the graph.
871 ..signature:getAdjacencyMatrix(g, mat)
872 ..param.g:In-parameter: A graph.
873 ...type:Class.Graph
874 ..param.mat:Out-parameter: A matrix.
875 ...type:Class.Matrix
876 ..returns:void
877 ..include:seqan/graph_types.h
878 */
879
880 template<typename TCargo, typename TSpec, typename TMatrix>
881 inline void
getAdjacencyMatrix(Graph<Directed<TCargo,TSpec>> const & g,TMatrix & mat)882 getAdjacencyMatrix(Graph<Directed<TCargo, TSpec> > const& g,
883 TMatrix& mat)
884 {
885 SEQAN_CHECKPOINT
886
887 typedef Graph<Directed<TCargo, TSpec> > TGraph;
888 typedef typename Size<TGraph>::Type TGraphSize;
889 typedef typename EdgeType<TGraph>::Type TEdgeStump;
890 typedef typename Size<TMatrix>::Type TSize;
891 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
892 typedef typename Iterator<String<TEdgeStump*> const, Standard>::Type TIterConst;
893 typedef typename Value<TMatrix>::Type TMatValue;
894 TSize len = getIdUpperBound(g.data_id_managerV);
895 TIterConst it = begin(g.data_vertex, Standard());
896 TIterConst itEnd = end(g.data_vertex, Standard());
897 clear(mat);
898 resize(mat, len * len, (TMatValue) 0);
899 TVertexDescriptor pos = 0;
900 for(;it!=itEnd; ++it, ++pos) {
901 TEdgeStump* current = *it;
902 TVertexDescriptor const source = pos;
903 while(current != (TEdgeStump*) 0) {
904 TVertexDescriptor target = targetVertex(g,current);
905 mat[source * len + target] = static_cast<TMatValue>(static_cast<TGraphSize>(mat[source * len + target]) + 1);
906 current = getNextT(current);
907 }
908 }
909 }
910
911 //////////////////////////////////////////////////////////////////////////////
912
913
914 /**
915 .Function.findEdge:
916 ..cat:Graph
917 ..summary:Finds an edge.
918 ..remarks:In an automaton an edge is uniquely defined by a vertex and a label.
919 In all other graphs two adjacent vertices uniquely define an edge.
920 If there are multiple edges between two vertices the behaviour is undefined.
921 ..signature:findEdge(g, v, c)
922 ..signature:findEdge(g, v, w)
923 ..param.g:A graph.
924 ...type:Class.Graph
925 ..param.v:A vertex descriptor.
926 ...type:Metafunction.VertexDescriptor
927 ..param.c:An edge label.
928 ...type:Metafunction.Alphabet
929 ..param.w:A vertex descriptor.
930 ...type:Metafunction.VertexDescriptor
931 ..returns:An edge descriptor or 0 if edge is not present.
932 Note: In automatons there is always a valid edge descriptor but the target may be nil.
933 ...type:Metafunction.EdgeDescriptor
934 ..include:seqan/graph_types.h
935 */
936 template<typename TCargo, typename TSpec, typename TVertexDescriptor>
937 inline typename EdgeDescriptor<Graph<Directed<TCargo, TSpec> > >::Type
findEdge(Graph<Directed<TCargo,TSpec>> const & g,TVertexDescriptor const v,TVertexDescriptor const w)938 findEdge(Graph<Directed<TCargo, TSpec> > const& g,
939 TVertexDescriptor const v,
940 TVertexDescriptor const w)
941 {
942 SEQAN_CHECKPOINT
943 SEQAN_ASSERT(idInUse(g.data_id_managerV, v) == true)
944 SEQAN_ASSERT(idInUse(g.data_id_managerV, w) == true)
945
946 typedef Graph<Directed<TCargo, TSpec> > TGraph;
947 typedef typename EdgeType<TGraph>::Type TEdgeStump;
948
949 TEdgeStump* current = g.data_vertex[v];
950 while(current != (TEdgeStump*) 0) {
951 if ( (TVertexDescriptor) getTarget(current) == w) return current;
952 current = getNextT(current);
953 }
954 return 0;
955 }
956
957 //////////////////////////////////////////////////////////////////////////////
958
959 template <typename TFile, typename TCargo, typename TSpec, typename TIDString>
960 inline void
write(TFile & target,Graph<Directed<TCargo,TSpec>> const & g,TIDString const &,Raw)961 write(TFile & target,
962 Graph<Directed<TCargo, TSpec> > const& g,
963 TIDString const &,
964 Raw)
965 {
966 SEQAN_CHECKPOINT
967 typedef Graph<Directed<TCargo, TSpec> > TGraph;
968 typedef typename EdgeType<TGraph>::Type TEdgeStump;
969 typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
970 typedef typename Iterator<String<TEdgeStump*> const, Standard>::Type TIterConst;
971 TIterConst it = begin(g.data_vertex, Standard());
972 TIterConst itEnd = end(g.data_vertex, Standard());
973 TVertexDescriptor pos = 0;
974 _streamWrite(target,"Adjacency list:\n");
975 for(;it!=itEnd;++it, ++pos) {
976 if (!idInUse(_getVertexIdManager(g), pos)) continue;
977 TEdgeStump* current = getValue(it);
978 _streamPutInt(target, pos);
979 _streamWrite(target," -> ");
980 while(current!=0) {
981 _streamPutInt(target, getTarget(current));
982 _streamPut(target, ',');
983 current=getNextT(current);
984 }
985 _streamPut(target, '\n');
986 }
987 it = begin(g.data_vertex, Standard());
988 pos = 0;
989 _streamWrite(target,"Edge list:\n");
990 for(;it!=itEnd;++it, ++pos) {
991 TEdgeStump* current = getValue(it);
992 while(current!=0) {
993 _streamWrite(target,"Source: ");
994 _streamPutInt(target, pos);
995 _streamPut(target, ',');
996 _streamWrite(target,"Target: ");
997 _streamPutInt(target, getTarget(current));
998 _streamPut(target, ' ');
999 _streamWrite(target,"(Id: ");
1000 _streamPutInt(target, _getId(current));
1001 _streamPut(target, ')');
1002 _streamPut(target, '\n');
1003 current=getNextT(current);
1004 }
1005 }
1006 }
1007
1008 }// namespace SEQAN_NAMESPACE_MAIN
1009
1010 #endif //#ifndef SEQAN_HEADER_...
1011