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 // Author: Tobias Raussch <rausch@embl.de>
33 // ==========================================================================
34 // Implementation of Kruskal's algorithm.
35 // ==========================================================================
36
37 #ifndef INCLUDE_SEQAN_GRAPH_ALGORITHMS_KRUSKAL_H_
38 #define INCLUDE_SEQAN_GRAPH_ALGORITHMS_KRUSKAL_H_
39
40 namespace seqan {
41
42 // ============================================================================
43 // Forwards
44 // ============================================================================
45
46 // ============================================================================
47 // Tags, Classes, Enums
48 // ============================================================================
49
50 // ============================================================================
51 // Metafunctions
52 // ============================================================================
53
54 // ============================================================================
55 // Functions
56 // ============================================================================
57
58 // ----------------------------------------------------------------------------
59 // Function kruskalsAlgorithm()
60 // ----------------------------------------------------------------------------
61
62 template <typename TWeight, typename TPair>
63 struct LessPairI1_ : public std::unary_function<Pair<TWeight, TPair>, bool>
64 {
operatorLessPairI1_65 bool operator() (Pair<TWeight, TPair> const & a1,
66 Pair<TWeight, TPair> const & a2) const
67 {
68 return (a1.i1 < a2.i1);
69 }
70 };
71
72 /*!
73 * @fn kruskalsAlgorithm
74 * @headerfile <seqan/graph_algorithms.h>
75 * @brief Computes a minimum spanning tree on a graph.
76 *
77 * @signature void kruskalsAlgorithm(edges, g, source, weight);
78 *
79 * @param[out] edges A String of vertex descriptors that represent edges. Each consecutive pair is an edge with the
80 * two end points.
81 * @param[in] g An undirected graph. Types: Undirected Graph
82 * @param[in] source A source vertex. Types: VertexDescriptor
83 * @param[in] weight Edge weights.
84 *
85 * @section Example
86 *
87 * @include demos/graph_algorithms/kruskals_algorithm.cpp
88 *
89 * @include demos/graph_algorithms/kruskals_algorithm.cpp.stdout
90 *
91 * @see primsAlgorithm
92 */
93 template <typename TSpec, typename TVertexDescriptor, typename TWeightMap, typename TEdges>
kruskalsAlgorithm(TEdges & edges,Graph<TSpec> const & g,TVertexDescriptor const,TWeightMap const & weight)94 void kruskalsAlgorithm(TEdges & edges,
95 Graph<TSpec> const & g,
96 TVertexDescriptor const,
97 TWeightMap const & weight)
98 {
99 typedef Graph<TSpec> TGraph;
100 typedef typename Iterator<TGraph, EdgeIterator>::Type TEdgeIterator;
101 typedef typename Value<TWeightMap>::Type TWeight;
102
103 typedef Pair<TVertexDescriptor, TVertexDescriptor> TVertexPair;
104 typedef Pair<TWeight, TVertexPair> TWeightEdgePair;
105 typedef String<TWeightEdgePair> TEdgeList;
106 typedef typename Iterator<TEdgeList>::Type TEdgeListIter;
107 TEdgeList edgeList;
108
109 // Initialization
110 reserve(edges, 2 * (numVertices(g) - 1));
111 UnionFind<TVertexDescriptor> unionFind;
112 resizeVertexMap(unionFind, g);
113
114 // Sort the edges
115 TEdgeIterator itE(g);
116 for(;!atEnd(itE);goNext(itE)) appendValue(edgeList, TWeightEdgePair(getProperty(weight, getValue(itE)), TVertexPair(sourceVertex(itE),targetVertex(itE))));
117 std::sort(begin(edgeList, Standard() ), end(edgeList, Standard() ), LessPairI1_<TWeight, TVertexPair>() );
118
119 // Process each edge
120 TEdgeListIter itEdgeList = begin(edgeList, Standard());
121 TEdgeListIter itEdgeListEnd = end(edgeList, Standard());
122 for (; itEdgeList != itEdgeListEnd; goNext(itEdgeList)) {
123 TVertexDescriptor x = value(itEdgeList).i2.i1;
124 TVertexDescriptor y = value(itEdgeList).i2.i2;
125
126 if (findSet(unionFind, x) == findSet(unionFind, y))
127 continue;
128
129 appendValue(edges, x);
130 appendValue(edges, y);
131 joinSets(unionFind, findSet(unionFind, x), findSet(unionFind, y));
132 }
133 }
134
135 } // namespace seqan
136
137 #endif // #ifndef INCLUDE_SEQAN_GRAPH_ALGORITHMS_KRUSKAL_H_
138