March 26, 2012, 9:35 pm
Another rough and ready algorithm. Finding the greatest subtree in a binary tree…
Things to remember, values in the tree can be negative so it’s not just the root (sigh).
This implementation is very inefficient. Caching sum in the node makes the efficiency reasonable I believe. But the problem is essentially recursive? Should do some googling to see if there is a better solution.
#include <iostream>
using namespace std;
class Node {
public:
Node () : left(NULL), right(NULL) {}
int value;
int sum;
Node *left;
Node *right;
int getsum() {
sum = 0;
if((left == NULL) && (right == NULL)) return value;
if(left != NULL) sum += left->getsum();
if(right != NULL) sum += right->getsum();
sum += value;
return sum;
}
};
Node *greatestsubtree(Node *current,Node *max) {
if(current == NULL) return max;
int mval = current->getsum();
if(mval > max->getsum()) max = current;
Node *l = greatestsubtree(current->left,max);
Node *r = greatestsubtree(current->right,max);
if(l->getsum() > max->getsum()) max = l;
if(r->getsum() > max->getsum()) max = r;
return max;
}
int main() {
Node *root = new Node();
root->left = new Node();
root->right = new Node();
root->value = 10;
root->left->value = -10;
root->right->value = 5;
root->left->left = new Node();
root->left->left->value = 100;
root->left->right = new Node();
root->left->right->value = 0;
root->right->left = new Node();
root->right->left->value = -8;
cout << root << endl;
cout << greatestsubtree(root,root)->getsum();
}
Version with caching…
#include <iostream>
using namespace std;
class Node {
public:
Node () : left(NULL), right(NULL),sumcache(false) {}
int value;
int sum;
bool sumcache;
Node *left;
Node *right;
int getsum() {
if(sumcache) return sum;
sum = 0;
if((left == NULL) && (right == NULL)) return value;
if(left != NULL) sum += left->getsum();
if(right != NULL) sum += right->getsum();
sum += value;
sumcache = true;
return sum;
}
};
Node *greatestsubtree(Node *current,Node *max) {
if(current == NULL) return max;
int mval = current->getsum();
if(mval > max->getsum()) max = current;
Node *l = greatestsubtree(current->left,max);
Node *r = greatestsubtree(current->right,max);
if(l->getsum() > max->getsum()) max = l;
if(r->getsum() > max->getsum()) max = r;
return max;
}
int main() {
Node *root = new Node();
root->left = new Node();
root->right = new Node();
root->value = 10;
root->left->value = -10;
root->right->value = 5;
root->left->left = new Node();
root->left->left->value = 100;
root->left->right = new Node();
root->left->right->value = 0;
root->right->left = new Node();
root->right->left->value = -8;
cout << root << endl;
cout << greatestsubtree(root,root)->getsum();
}
March 23, 2012, 11:24 pm
Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;
class Node {
public:
Node() {
}
vector<Node *> children;
Node *parent;
};
Node *make_random_tree(size_t size,Node *root=NULL) {
if(root == NULL) {
root = new Node();
}
Node *current = root;
size_t children=rand()%size;
for(size_t i=0;i<children;i++) {
Node *nd = new Node();
nd->parent = current;
current->children.push_back(nd);
}
for(size_t n=0;n<current->children.size();n++) {
make_random_tree(size-children,current->children[n]);
}
return root;
}
Node *get_random(Node *root,size_t avg_size) {
Node *current = root;
for(;rand()%(avg_size*2) != 0;) {
if(current->children.size() == 0) return current;
current = current->children[rand()%current->children.size()];
}
return current;
}
Node * get_next_child(Node *node,Node *child) {
bool next=false;
for(size_t n=0;n<node->children.size();n++) {
if(next==true) {
return node->children[n];
}
if(node->children[n] == child) next=true;
}
return NULL;
}
vector<Node *> get_path(Node *root,Node *n) {
vector<Node *> current_path;
current_path.push_back(root);
if(n==root) return current_path;
Node *current_child = root->children[0];
for(;;) {
current_path.push_back(current_child);
if(current_child == n) return current_path;
if(current_child->children.size() != 0) {
current_path.push_back(current_child->children[0]);
current_child = current_child->children[0];
} else {
current_child = NULL;
for(;current_child == NULL;) {
Node *old_child = current_path[current_path.size()-1];
current_path.erase(current_path.begin()+current_path.size()-1,current_path.end());
current_child = get_next_child(current_path[current_path.size()-1],old_child);
if(old_child==root) { return vector<Node *>(); }
}
}
}
// Should never get here
return vector<Node *>();
}
vector<Node *> get_path_parent(Node *root,Node *n) {
vector<Node *> v;
for(Node *current = n;current != root;current = current->parent) {
v.push_back(current);
}
v.push_back(root);
reverse(v.begin(),v.end());
return v;
}
Node *find_lca_parent(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path_parent(root,n1);
vector<Node *> path2 = get_path_parent(root,n2);
for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl;
for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl;
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
Node *find_lca(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path(root,n1);
vector<Node *> path2 = get_path(root,n2);
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
int main() {
Node *root = make_random_tree(100);
Node *n1 = get_random(root,20);
Node *n2 = get_random(root,20);
Node *lca1a = find_lca_parent(root,n1,n2);
Node *lca1b = find_lca (root,n1,n2);
cout << "LCA1-a: " << lca1a << endl;
cout << "LCA1-b: " << lca1a << endl;
Node *n3 = root->children[0]->children[0]->children[0];
Node *n4 = root->children[0]->children[0]->children[1];
Node *lca2a = find_lca_parent(root,n3,n4);
Node *lca2b = find_lca (root,n3,n4);
cout << "LCA2-a: " << lca2a << endl;
cout << "LCA2-b: " << lca2b << endl;
}
March 20, 2012, 4:42 pm
This is a simple, inefficient implementation of the Burrows-Wheeler transform in C++. I wrote it just to play around with the algorithm, not for any practical application. It takes a single text file as the input, then performs the transform and reverses it:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void bwt(string input,string &bwt_str,int &primaryidx) {
vector<string> rotations;
// 1. generate rotations of input
cout << "rotations:" << endl;
for(int n=0;n<input.size();n++) {
string s;
s += input[n];
for(int i=n+1;i!=n;i++) {
if(i==input.size()) i=0;
s += input[i];
if(i==input.size()-1) i=-1;
}
rotations.push_back(s);
cout << s << endl;
}
// 2. sort
cout << "sorted:" << endl;
sort(rotations.begin(),rotations.end());
for(size_t n=0;n<rotations.size();n++) {
cout << rotations[n] << endl;
}
bwt_str.clear();
for(size_t n=0;n<rotations.size();n++) {
bwt_str += rotations[n].substr(rotations[n].size()-1,1);
if(rotations[n] == input) {primaryidx = n;}
}
cout << "bwt string: " << bwt_str << endl;
cout << "primaryidx: " << primaryidx << endl;
}
string rbwt(string bwt_str,int primaryidx) {
vector<string> cur_str;
for(size_t n=0;n<bwt_str.size();n++) {
string s;
s = bwt_str.substr(n,1);
cur_str.push_back(s);
}
for(;cur_str[0].size() < bwt_str.size();) {
vector<string> new_str = cur_str;
sort(new_str.begin(),new_str.end());
for(size_t n=0;n<cur_str.size();n++) {
cur_str[n] = cur_str[n] + new_str[n].substr(new_str[n].size()-1,1);
}
}
cout << "reversed transform:" << endl;
for(size_t n=0;n<cur_str.size();n++) {
cout << cur_str[n] << endl;
}
sort(cur_str.begin(),cur_str.end());
cout << "Original String: " << cur_str[primaryidx] << endl;
return cur_str[primaryidx];
}
int main(int argc,char **argv) {
string s;
ifstream infile(argv[1]);
for(;!infile.eof();) {
char c = (char)infile.get();
if(!infile.eof()) s += string(1,c);
}
cout << "input: " << s << "END" << endl;
string bwt_str;
int primaryidx;
bwt(s,bwt_str,primaryidx);
rbwt(bwt_str,primaryidx);
}
March 20, 2012, 10:24 am
Some quick Javascript which plots random walks from a point…
View it here.
<html>
<head>
<script type="text/javascript">
var ittr=8;
var delta=-0.005;
function draw_frame() {
var canvas = document.getElementById("m_canvas");
if(canvas.getContext) {
var ctx = canvas.getContext("2d");
ctx.lineWidth = 0;
ctx.fillStyle = "rgb(0,0,0)";
var x=250;
var y=250;
for(var n=0;n<200;n++) {
var r=Math.floor(Math.random()*4);
if(r==0) { x+=1; y+=0; }
if(r==1) { x+=0; y+=1; }
if(r==2) { x-=1; y+=0; }
if(r==3) { x-=0; y-=1; }
ctx.fillRect(x*1,y*1,1,1);
}
ctx.fillStyle = "rgb(0,200,200)";
ctx.fillRect(250,250,3,3);
}
}
</script>
</head>
<body onload="setInterval(draw_frame,10);" >
<canvas id="m_canvas" width="500" height="500">You need a Javascipt</canvas>
</body>
</html>
RSS