OXT blog
“People say nothing is impossible, but I do nothing every day.” – Whinnie The Pooh

Our aim is to implement hierarchical clustering algorithm with O(N*N*log(N)) complexity using STL.

The idea of hierarchical clustering is merging two nearest clusters on every step starting from N one-element clusters. To find two nearest clusters on step K we need (N-K+1)x(N-K+1) matrix of distances between current clusters. We need, in worst case, N times of updating and finding minimum in sequence of NxN, (N-1)x(N-1), (N-2)x(N-2), …, 1×1 matrix. So, in usual realization of HC algorithm it should cost you O(N*N*N) operations.

To improve algorithm complexity up to O(N*N*log(N)) we can use vector V of similar to priority queues structures. V[i] should consist of sorted by distance points P(i,j) where distance is distance between clusters i and j. Our similar to priority queues data structure should support: ability to extract minimal element with complexity O(1), ability to delete element with complexity O(log(n)), and ability to add and element with complexity O(log(n)).

Standard STL priority_queue allows us to extract minimum and add element with required time, but it has no ability to find quickly an element, so we can’t delete elements with complexity O(log(n)). I propose to use set or multiset STL structure instead. Set and multiset uses “red-black tree” data structure with O(log(n)) complexity of deletion and insertion. Also, in STL sets all elements stored in sorted order and we can easily access to minimum (maximum) element [using standard begin() or end() methods].

In my realization I used following structure to store distances and cluster’s indexes:

struct distances
{
	double dist;
	int index;
};

Also I defined appropriate comparing operator so that elements in my set always sorted in right order.

struct Cmp{
	bool operator()(const distances d1, const distances d2) const
	{
		if(d1.dist == d2.dist)
		{
			return d1.index < d2.index;
		}
		return d1.dist < d2.dist;
	}
};

Then declaration of our vector of sets should look like this one:

std::vector> P;

Here is source codes with sample input file and some comments:

sources.zip

When I tried to use some methods from OpenCV library (for example CvResize()) in my MS Visual Studio 2005 project I encountered with errors in cxtypes.h header file near

#if CV_SSE2
__m128d t = _mm_load_sd( &value );
int i = _mm_cvtsd_si32(t);
return i - _mm_movemask_pd(_mm_cmplt_sd(t,_mm_cvtsi32_sd(t,i)));
#else
....

These errors were related with SSE2. The problem is that my AMD Sempron 2200+ family 6 (x86 family 6 model 8 ) processor do not support SSE2 instructions. SSE – Streaming SIMD Extensions 2 are extends on MMX instructions to operate on special registers to increase computational speed in some cases.

To fix these problems you need to set CV_SSE2 variable to 0 in cxcore’s cxtypes.h (near 65 line).
For example like here:

//  #if defined WIN32 && (!defined WIN64 || defined EM64T) && 
//      (_MSC_VER >= 1400 || defined CV_ICC) 
//      || (defined __SSE2__ && defined __GNUC__ && __GNUC__ >= 4)
//    #include 
//    #define CV_SSE2 1
//  #else
    #define CV_SSE2 0
//  #endif

You may have problems when reading .avi video using MatLab function aviread(). If you have 16-bit color video, aviread() can’t read it correctly. You can receive only grayscaled data using this function in this case. The solution is to use Kelly Kearney’s aviread16bitcol() function, which you can download from here: http://www.mathworks.com/matlabcentral/fileexchange/9314

Do not confuse this printer with LaserJet 1005, it’s different printer (you’ll need drivers from foo2zjs package for 1005).

To make P1005 working you’ll need hplip package. Run hp-setup as root or run hplip from system menu. Unfortunately it is not able to download required plugin (at least in version 2.8.6b). You have to download it manually here http://www.linuxprinting.org/download/printdriver/auxfiles/HP/plugins/hplip-2.8.6b-plugin.run and provide to hp setup tool.

If you have problems printing wide HTML webpage (your text is cropped from the right edge) you can try this solution

I was working on simple symfony website consisting of just one application and one module. Naturally, I wasn’t too creative and choose ‘frontend’ as application name and ‘index’ for module name. When I started to test it on production, it wasn’t working at all except default action. It was giving me 404 error.
After spending some time debugging and logging symfony and mod_rewrite I’ve found out the problem. Rewrite rule was sending me to /index.php/actionname instead of index.php/index/actionname.
The problem was in apache option MultiViews, as soon as I removed it everything started to work as expected. This option tells webserver to search for foo/filename.* if foo/filename wasn’t found.
I had this option enabled in my default virtual host config in my apache distribution and I had never paid any attention to it before.

If you need to display any value or text (for example current point’s value) near different points of your graph in MatLab, you can use text(x,y,’string’) function.

For example:

x = -pi:pi/10:pi;
y = sin(x);
figure('Name', 'Sample graph'), plot(x, y, '--rs');
% Label some points
for i=8:size(x,2)-8
text(x(i), y(i), ['\leftarrow (', num2str(x(i)), ';', num2str(y(i)), ')']);
end

Here is the output:

Output sample

Unfortunately Drupal (as in version 6.5) doesn’t allow easy theming for language selector. However it’s still possible with theme function overriding. Look at the code.

function yourtheme_links($links, $attributes = array('class' => 'links')) {
	list(,$first_link) = each($links);
	if (($first_link['attributes']['class'] == 'language-link')) {
		global $language;
		$new_links = array();
		$num_links = count($links);
		$i = 0;
		foreach ($links as $link) {
			$i ++;
			$link['title'] = '<span class="bg">' . $link['title'] . '</span>';
			$link['html']	= true;
			if ($link['language']->language == $language->language)
				$link['attributes']['class'] = 'selected';
			$new_links[] = $link;
			if ($i < $num_links)
				$new_links[] = array(
					'title'	=> '|',
					'attributes'	=> array('class'	=> 'separator')
				);
		}
		$links = $new_links;
	}
	return theme_links($links, $attributes);
}

It adds ‘selected’ class to the current language (which I think logical) and adds separator element between language links. You can customize them as you wish.

symfony has basic CRUD-like admin generator, which allows you to create controls for filtering list results. Naturally, if you have filtered list and press ‘create’ button it would be nice to have new form with populated from filter form fields.

Here’s basic idea how to do it. In my example I have Work entity which has foreign key to Category entity. I have list of works filterable by category id.
To populate category id on work creation form you need to override generated action:

class worksActions extends autoworksActions
{
  public function executeEdit()
  {
  	parent::executeEdit();
  	if ($this->getRequestParameter('action') == 'create')
  	{
  		$filters = $this->getUser()->getAttributeHolder()->getAll('sf_admin/work/filters');
  		if (isset($filters['category_id']))
  			$this->work->setCategoryId($filters['category_id']);
  	}
  }
}

Look into admin generated actions if you want to more clearly understand why we need such code. It is located at cache/admin/dev/modules/autoWorks/actions/actions.class.php

If you are using classes from Zend Framework Laboratory for PayPal integration (which is somewhat unfinished) you probably will have an error when trying

Zend_Service_Paypal::setExpressCheckout();

The error has strange description ‘Security header is not valid’ and not listed in PayPal documentation.

To fix the error you’ll have to change line in Zend/Service/PayPal.php (in Laboratory tree)

const SERVICE_URI = 'https://api-3t.sandbox.paypal.com/nvp';

to

const SERVICE_URI = 'https://api-3t.paypal.com/nvp';