fn() heaviestIncreasingSubsequenceComputes the heaviest increasing subseqnece.
Computes the heaviest increasing subseqnece.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
void heaviestIncreasingSubsequence(str, weights, pos);
|
Parameters
str
|
An arbitrary ContainerConcept object. |
---|---|
weights
|
A String with a weight for each position in the string. |
pos
|
A String with positions that indicate the members of the heaviest increasing subsequence. |
Detailed Description
Remarks
The last position in pos indicates the first member of the heviest increasing subsequence. Note that only members that contribute a weight are selected, that is, positions with associated 0 weights are ignored.
Example
#include <iostream>
#include <seqan/sequence.h>
#include <seqan/graph_algorithms.h>
using namespace seqan;
int main()
{
// Fill a string and define corresponding weights.
String<char> seq("zeitgeist");
String<unsigned int> weights;
resize(weights, length(seq), 1);
assignProperty(weights, 2, 10);
// Compute heaviest increasing subsequence.
typedef Position<String<unsigned int> >::Type TPosition;
String<TPosition> pos;
unsigned int w = heaviestIncreasingSubsequence(seq, weights, pos);
// Print the results to stdout.
for (int i = 0; i < (int) length(seq); ++i)
std::cout << seq[i] << "(Weight=" << getProperty(weights, i) << "),";
std::cout << "\n"
<< "His: \n";
for (int i = length(pos) - 1; i >= 0; --i)
std::cout << seq[pos[i]] << ',';
std::cout << "(Weight=" << w << ")\n";
return 0;
}
z(Weight=1),e(Weight=1),i(Weight=10),t(Weight=1),g(Weight=1),e(Weight=1),i(Weight=1),s(Weight=1),t(Weight=1), His: e,i,s,t,(Weight=13)
Data Races
Thread safety unknown!