Tag Archives: possible solution

Computer Algorithms: Graph Best-First Search

Introduction

So far we know how to implement graph depth-first and breadth-first search. These two approaches are crucial in order to understand graph traversal algorithms. However they are just explaining how we can walk through in breadth or depth and sometimes this isn’t enough for an efficient solution of graph traversal.

In the examples so far we had an undirected, unweighted graph and we were using adjacency matrices to represent the graphs. By using adjacency matrices we store 1 in the A[i][j] if there’s an edge between vertex i and vertex j. Otherwise we put a 0. However the value of 1 gives us only the information that we have an edge between two vertices, which is not always enough when designing graphs.

Indeed graphs can be weighted. Sometimes the path between two vertices can have a value. Thinking of a road map we know that distances between cities are represented in miles or kilometers. Thus often representing a road map as a graph, we don’t put just 1 between city A and city B, to say that there is a path between them, but also we put some meaningful information – let’s say the distance in miles between A and B.

Note that this value can be the distance in miles, but it can be something else, like the time in hours we’ve to walk between those two cities. In general this value is a function of A and B. So if we keep the distance between A and B we can say this function is F(A, B) = X, or distance(A, B) = X miles.

Of course in this particular example F(A, B) = F(B, A), but this isn’t always true in practice. We can have a directed graph where F(A, B) != F(B, A).

Here I talk about distance between two cities and it is the edge that brings some additional information. However sometimes we have to store the value of the vertices. Let’s say I’m playing a game (like chess) and each move brings me some additional benefit. So each move (vertex) can be evaluated with some particular value. Thus sometimes we don’t have a function of and edge like F(A, B), but function of the vertices, like F(A) and F(B).

In breadth-first search and depth-first search we just pick up a vertex and we consecutively walk through all its successors that haven’t been visited yet.

Walk Through an Unweithed Graph
In order to walk through an unweithed graph using DFS, we chose consecutively each successor of node i!

So in DFS in particular we started from left to right in the array above. So the first node that has to be explored is vertex “1”.

0: [0, 1, 0, 0, 1, 1]

However sometimes, as I said above, we have weighted graphs, so the question is – is there any problem, regarding to the algorithm speed, if we go consecutively through all successors. The answer in general is yes, so we must modify a bit our code in order to continue not with the first but with the best matching successor. By best-matching we mean that the successor should match some criteria like – minimal or maximal value. Continue reading Computer Algorithms: Graph Best-First Search

A JavaScript Trick You Should Know

JavaScript Strings

You should know that in JavaScript you cannot simply write a multilined code chunk, i.e. something like this:

var str = 'hello
world';

This will result in an error, which can be a problem when you deal with large strings. Imagine a string containing some HTML that should be injected via innerHTML. Now one possible solution is to concatenate two or more strings, by splitting the initial string.

var str = 'hello'
        + 'world';

Howerver this solution result in some additional operations like concatenation. It can be very nice if there was something like the PHP multiline string format.

The PHP Example

In PHP you have the same use case with strings. You can have a string concatenated over multiple lines, but you cannot split lines like so:

// the following line is wrong
$str = 'hello
world'; 
 
// a possible solution to the line above is
$str = 'hello'
     . 'world';
// which is very similar to the js solution in the second example
 
// ... but in PHP there is the so called HEREDOC
$str = <<<EOD
hello
world
EOD;

The heredoc gives us the power to write multiline strings.

The JavaScript Trick

Actually in JavaScript there is something that’s exactly what Heredoc is meant to be for PHP. Take a look at the last example:

var text = <>
this <br />
is
my
multi-line
text
</>.toString();
 
document.body.innerHTML = text;

Thus you can write multiline strings in the JavaScript code.

jQuery.unbind()

Binding Problems

jQuery JavaScript Library
jQuery JavaScript Library

Typically in jQuery when you bind an HTML element with some event this event is fired every time the user (client) triggers it. Thus when you’ve a click event attached on a button you can click it as many times as you want. In some rare cases this can be tricky. Let’s imagine the following scenario.

  1. The user clicks on a “vote” button.
  2. Some AJAX calls are performed.
  3. After a successful AJAX call you setup a cookie to deny further votes from this machine.

This seems to be pretty well known scenario, but as the click event is attached to the button there is enough time to click several times on the “vote” button and to vote several times. In this case before the cookie is set the user can vote more than once. Continue reading jQuery.unbind()

Download Images with PHP

As it seems one possible solution while trying to download images with PHP is to write a “client” to do so. Will it be with cURL, Zend Framework or some other tool – it doesn’t matter.

However one of the most used approaches is simply with file_get_contents and file_put_contents. I’m not sure whether I wrote already about this or not, but this solution simply looks something like this.

 
file_put_contents('/path/to/file', 
                  file_get_contents('http://www.example.com/source.image');

In fact a client will give you more control over the process, to handle errors, etc. So maybe this is a better solution.

More on CSS Optimization

As CSS files are first downloaded to the client and then executed, the main optimization is to make those files smaller. But that doesn’t mean only minifing!

CSS

The Minification Process

While with minification you can strip all the symbols that only take space, but are useless when the browser parses the file, there are some other techniques, which in fact aren’t so simple, to speed up the loading process. By minification you get rid of the white spaces, tabs, new lines, etc., but the file may remain too large.

Useless Rules

Yes, sadly the browser doesn’t need all those white spaces, actually web developers need them. Just because this makes the file more readable, or readable at all. However most of the web applications have one large CSS file, typically named layout.css, main.css or whatever, that contains all the rules for the entire application. In many of the cases one page of a site doesn’t need all the rules for the site, so a possible solution is to remove all of the rules that aren’t used.

There are tools that may help you do the job. Such a tool, that I’m using is the Firefox add-on – Dust-Me Selectors. Of course there are a lot other tools doing the same job, so it’s up to you to pick up one.

After removing all those useless rules you’ll see that the size of the file can be something like 20% of the size of the source file. This is interesting to note, because most of the time the minification cannot give you such performance benefit. In fact this comes with some issues.

One Request or What?

This is the dilemma of the web programming, isn’t it? However thus you can split the main CSS file to few smaller files, but they are named differently so you cannot expect the browser to cache them when the user visits the site for the first time.

The case must be, of course, tested against various situations, so you can decide what suits you. However the typical scenario is to optimize only few of the pages, as they might be the most visited – as for example the homepage. If two of the pages are mainly visited, than you can make custom, small, CSS files for them with only the necessary rules, and let the other pages with the main CSS file. If you’ve a lot of returning visitors, you can be sure the custom files will be cached (if the client cache is turned on) and the second time somebody visits the “homepage” for example the page will load faster.