Thursday 31 January 2008

We'll show you how to implement Huffman encoding, which is useful when dealing with small sets of items, such as character strings, in Python. Read more »

Tags: compression, huffman encoding, python

Less painful getters and setters using properties in Python

It's a popular design guideline to require class attributes to be managed by methods, usually referred to as getter and setter methods. These methods increase the safety of your attributes, but come at a cost of simplicity and verbosity. With Python properties, you can have it both ways. Read more »

Tags: access, class, field, method, property, python

Extending Vim with Python

If you're a user of the text editor Vim, chances are you are already impressed with the number and power of its inbuilt features. If you've ever tried to add your own functionality to the editor but been turned off by its arcane Vimscript language, then you'll be pleased to know that Vim now supports internal Python scripting. Read more »

Writing and appending to zip archives in Python

Following up from last week's article on reading zip archives, we show you how you can create your own archives using Python. Read more »

Tags: append, archives, python, write, zip

Reading zip archives in Python

Zip is the name of a popular file compression algorithm, which lets you both combine multiple files into a single archive and store them on disk using less space. We'll show you how you can open and read zip files in your Python scripts. Read more »

Tags: archive, compression, python, zip

Tkinter canvas: freeform GUIs in Python

The Tkinter framework provides some standard GUI widgets for use in building Graphical User Interfaces in Python. If you need more freedom you can use the Canvas widget included in Tkinter, which gives you an area where you can draw custom shapes. Read more »

Tags: canvas, drawing, gui, python, shape, tk

Partial function application in Python

Python is not an inherently functional language, but with the help of the functools library you can write some programs in a functional style. One of the key tools do to writing functional code is partial function application, which is available through the functools module. Read more »

Tags: application, curry, function, partial, python

Build a basic Web scraper in Python

There are times when your programs need to access the Web without worrying about the details of the mark-up. In this example we write a HTML scraper using the Python parsing library BeautifulSoup. Read more »

Tags: html, parsing, python, scraper, sgml, xml

Generating functions rather than lists in Python

There are situations where list comprehensions are useful, but also situations where you're better served by using some other form. In this article we'll take an example of where a function factory is the better choice. Read more »

Tags: comprehension, design, factory, function, generator, list, pattern, python

Python priority queues - the heapq module

The heap is an integral component in many algorithms -- a data structure that keeps elements organised so that it is always easy to find the smallest value. We'll show you how you can use the heapq module to implement heaps in Python in just a few lines of code. Read more »

Tags: heap, priority, python, queue

RDF, semantic web

http://esw.w3.org/topic/SweoIG/TaskForces/CommunityProjects/LinkingOpenData

http://dbpedia.org/

The Open Data Movement aims at making data freely available to everyone. There are already various interesting open data sets availiable on the Web. Examples include Wikipedia, Wikibooks , Geonames, MusicBrainz, WordNet, the DBLP bibliography and many more which are published under Creative Commons or Talis licenses.

The goal of the W3C SWEO Linking Open Data community project is to extend the Web with a data commons by publishing various open datasets as RDF on the Web and by setting RDF links between data items from different data sources.

RDF links enable you to navigate from a data item within one data source to related data items within other sources using a Semantic Web browser. RDF links can also be followed by the crawlers of Semantic Web search engines, which may provide sophisticated search and query capabilities over crawled data. As query results are structured data and not just links to HTML pages, they can be used within other applications.

The figure below shows the datasets that have been published and interlinked by the project so far. Collectively, the datasets consist of over two billion RDF triples, which are interlinked by around 3 million RDF links (October 2007).

DBpedia is a community effort to extract structured information from Wikipedia and to make this information available on the Web. DBpedia allows you to ask sophisticated queries against Wikipedia and to link other datasets on the Web to Wikipedia data.

C++ container benchmark

http://www.stepanovpapers.com/container_benchmark.cpp

g++ -Wall -o benchmark benchmark.cc
g++ -Wall -O2 -o benchmark benchmark.cc
g++ -Wall -O3 -o benchmark  benchmark.cc


/* Standard Container Benchmark 


   Version 0.9, May 23, 2003 


The primary purpose of this benchmark is to show how different standard 
containers are in terms of performance. We have observed that programmers  
often use sets, multisets, deques in the situations where sorted vectors 
are the optimal solutions. Similarly, programmers often choose lists simply 
because they do a few insertions and deletions without knowing that vectors  
are more efficient at that for small containers. 


Frequently, of course, performance does not matter, 
but it is important that programmers are aware of the consequences of their 
choices. We are not saying that only vectors should be used, there are  
cases when one really needs a more complicated data structure, but one needs to 
understand the price for additional functionality. 


The secondary purpose of the benchmark is to encourage compiler and library vendors to  
keep improving performance. For example, it is not acceptable that some compilers give 
you a sizable penalty for using vector iterators instead of pointer. It is also quite 
clear that  performance of other standard containers could be improved.  


The benchmark is doing the same task 7 times using different data structures: 
array, vector (using a pointer as iterator), vector (using the defailt cector iterator), 
list, deque, set and multiset. The task is to remove duplicates from a sequence of doubles.  
This is a simple test, but it illustrates the performance of containers. 


It is clear that the benchmark needs to be eventually extended 
to slists and even to hash-sets and hash-maps, but we decided that at present it  
should work only with the standard containers. As the standard grows, so can 
the benchmark. The additional benefit of not including hash based containers is 
that now all the test have identical asymptotic complexity and, even more  
importantly, do almost the same number of comparisons. The difference is only 
in data structure overhead and cache behavior. 


The number of times that a given test is run inversly proportional to NlogN where N is the  
size of the sequence.  This allows one to see how containers of different size behave. 
The instructive values used for the benchmark are: 10, 100, 1000, 10000, 100000, 1000000. 


The time taken for a run of the benchmark depends on the machine used, the compiler used,  
the compiler and optimizer settings used, as well as the standard library. Please note that 
the time taken could be several minutes - and much more if you use a slow debug mode. 


The output is a table where columns are separated by tabs and rows by newlines. This is  
barely ok for a human reader, but ideal for feeding into a program, such as a spreadsheet 
for display or analysis. 


If you want to add your own test of a container, add the name of your container to 
 the "header string, write a test function like the existing ones, e.g. vector_test, 
and add a call of "run" for your test in "run_tests". 


Alex Stepanov 
 stepa...@adobe.com 


Bjarne Stroustrup 
b...@cs.tamu.edu 


*/ 


#include <stddef.h>       // some older implementations lack <cstddef>  
#include <time.h> 
#include <math.h> 
#include <stdlib.h> 


#include <vector> 
#include <algorithm> 
#include <list> 
#include <deque> 
#include <set>  


#include <iostream> 
#include <iomanip> 


typedef double element_t; 


using namespace std; 


vector<double> result_times; // results are puched into this vector  


const char header[] = 
                "\tarray" 
                "\tvector with pointers" 
                "\tvector with iterators" 
                "\tdeque"  
                "\tlist" 
                "\tset" 
                "\tmultiset"; 


void do_head() 
{ 
        cout << "size" << header << '\n';  



} 


int do_tail() 
{ 
        // in case you want to stop for confirmation in a windows console application 
        //char c; 
        //cin >> c; 
        return 0; 

 
} 


void do_row(int size) 
{ 
        cout << size; 
        cout << fixed << setprecision(2); 
        for (size_t i = 0; i < result_times.size(); ++i) 
                cout << '\t' << result_times[i];  
        cout << '\n'; 


} 


clock_t start_time; 

inline void start_timer() { start_time = clock(); } 


inline double timer() 
{ 
  clock_t end_time = clock(); 
   return (end_time - start_time)/double(CLOCKS_PER_SEC); 



} 


typedef void(*Test)(element_t*, element_t*, int); 
void run(Test f, element_t* first, element_t* last, int number_of_times) 
{ 
         start_timer(); 
        while (number_of_times-- > 0) f(first,last,number_of_times); 
        result_times.push_back(timer()); 


} 


void array_test(element_t* first, element_t* last, int number_of_times)  
{ 
       element_t* array = new element_t[last - first]; 
       copy(first, last, array); 
       sort(array, array + (last - first)); 
       unique(array, array + (last - first)); 
       delete [] array;    


} 


void vector_pointer_test(element_t* first, element_t* last, int number_of_times) 
{ 
       vector<element_t> container(first, last); 
           // &*container.begin() gets us a pointer to the first element  
       sort(&*container.begin(), &*container.end()); 
       unique(&*container.begin(), &*container.end()); 


} 


void vector_iterator_test(element_t* first, element_t* last, int number_of_times)  
{ 
       vector<element_t> container(first, last); 
       sort(container.begin(), container.end()); 
       unique(container.begin(), container.end()); 


} 


void deque_test(element_t* first, element_t* last, int number_of_times)  
{   
//       deque<element_t> container(first, last); CANNOT BE USED BECAUSE OF MVC++ 6 
        deque<element_t> container(size_t(last - first), 0.0); 
        copy(first, last, container.begin());  
        sort(container.begin(), container.end()); 
        unique(container.begin(), container.end()); 


} 


void list_test(element_t* first, element_t* last, int number_of_times) 
{ 
       list<element_t> container(first, last);  
       container.sort(); 
           container.unique(); 


} 


void set_test(element_t* first, element_t* last, int number_of_times) 
{ 
       set<element_t> container(first, last);  


} 


void multiset_test(element_t* first, element_t* last, int number_of_times) 
{ 
       multiset<element_t> container(first, last); 
       typedef multiset<element_t>::iterator iterator;  
           { 
                        iterator first = container.begin(); 
                        iterator last = container.end(); 

                        while (first != last) { 
                                iterator next = first;  
                                if (++next == last) break; 
                                if (*first == *next) 
                                        container.erase(next); 
                                else  
                                        ++first; 
                        } 
           } 



} 


void initialize(element_t* first, element_t* last) 
{ 
  element_t value = 0.0; 
  while (first != last) {  
         *first++ = value; 
         value += 1.; 
  } 


} 


double logtwo(double x) 
{ 
  return log(x)/log((double) 2.0); 


} 


const int largest_size = 1000000; 
 
int number_of_tests(int size) { 
        double n = size; 
        double largest_n = largest_size; 
        return int(floor((largest_n * logtwo(largest_n)) / (n * logtwo(n)))); 



} 


 void run_tests(int size) 
{ 
        const int n = number_of_tests(size); 
        const size_t length = 2*size; 
        result_times.clear(); 

// make a random test set of the chosen size: 
  vector<element_t> buf(length);  
  element_t* buffer = &buf[0]; 
  element_t* buffer_end = &buf[length]; 
  initialize(buffer, buffer + size);            // elements 
  initialize(buffer + size, buffer_end);        // duplicate elements  
  random_shuffle(buffer, buffer_end); 


// test the containers: 
  run(array_test, buffer, buffer_end, n); 
  run(vector_pointer_test, buffer, buffer_end, n); 
  run(vector_iterator_test, buffer, buffer_end, n);  
  run(deque_test, buffer, buffer_end, n); 
  run(list_test, buffer, buffer_end, n); 
  run(set_test, buffer, buffer_end, n); 
  run(multiset_test, buffer, buffer_end, n); 
  do_row(size); 



}  


int main() 
{ 
  do_head(); 
  const int sizes [] = {10, 100, 1000, 10000, 100000, 1000000}; 
  const int n = sizeof(sizes)/sizeof(int); 
  for (int i = 0; i < n; ++i) run_tests(sizes[i]); 
   return do_tail(); 


}

Boost Graph Library

http://www.informit.com/articles/printerfriendly.aspx?p=673259
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html

Manipulating C++ Graph Data Structures with the Boost Graph Library

By Jeff Cogswell

Date: Dec 1, 2006

Return to the article

Quickly becoming a de facto standard C++ library, the Boost library includes a powerful graph data structure that's also easy to use. Jeff Cogswell discusses some interesting theory behind graphs, and explains the Boost library's graph structures.

In advanced mathematics, a graph is a special data structure made up of lines (called edges) connected together at endpoints (called vertices or nodes). This definition of the term graph is in contrast to a popular definition used in early math classes, where a graph is simply a plot of a function.

Many computer science and mathematical algorithms make use of graphs. Because graphs are so important in many algorithms, a data structure for a graph is equally important. Most languages don't have graph data structures built in; indeed, C++ doesn't. Therefore, when you need a graph data structure, you either have to code one yourself or make use of a third-party library offering a graph data structure.

The Boost library is quickly becoming a de facto standard C++ library, and it includes a graph data structure that's easy to use yet powerful. In this article, I discuss the theory behind graphs, and then we explore the Boost library's graph structures.

Grasping Graph Theory

As I already mentioned, a graph is simply a set of vertices (the points) connected by edges (the lines). When two vertices are connected by an edge, those two vertices are said to be adjacent. If you enjoy mathematics, you might like to know that this definition can be described a bit more technically by stating that a graph consists of a finite set of vertices along with a finite set of unordered pairs of distinct vertices; you can see that the pairs of vertices represent the edges of the graph.

Graphs provide a visual way of displaying underlying information. For example, a large airline serves many cities. The airline's web site might provide a map showing cities as dots, and lines connecting the cities representing flights between those cities. This map could be considered a graph. Similar graphs might include those showing a trucking company's delivery routes between cities, or bus routes between cities.

Although, technically speaking, a graph consists simply of vertices connected by edges, this limited definition isn't particularly useful. Often, graphs are more useful when they have more associated information. For example, a flight map might also show the flight numbers associated with each flight. In this representation, a graph consists of vertices, edges, and numbers associated with the edges. When numbers are associated with edges, such graphs are called weighted graphs.

Certainly, some graphs might need more than one piece of data associated with each edge. For example, in addition to the flight numbers, the airline map might show the length of each flight. In terms of computer science, however, such information would still be considered individual pieces of data in the form of individual structures or objects associated with each edge, with each structure containing a flight number and a flight time

Similarly, a graph might need to have information attached to the vertices, such as city names in the case of the airline map. In mathematics, you can attach numbers to vertices and use such numbers in calculations.

Another somewhat limiting aspect of a traditional definition of a graph is that the edges connecting the vertices don't have directions. In real life, a system that can be modeled by a graph will likely have directions. For example, if you travel by train somewhere, you definitely want to feel comfortable that the tracks you're riding on from one city to the next are carrying the train in a single direction! When you add directions to graphs, you have what mathematicians call a directed graph, or digraph for short.

Important to graph theory is another type of graph, limited by the restriction that the graph can be drawn on a sheet of paper without any edges crossing. Such a graph is called a planar graph. The term planar is used because the graph can be drawn on a single plane. Of course, this plane might not always be flat in the geometrical sense; the plane could exist on a curved surface such as the surface of the Earth, in which case it still maps to two dimensions. That's getting into another interesting area of mathematics called topology, however, which we won't cover here.

Old and Famous Problems

Graphs aren't just for representing data. They're often used in problem solving, and, as such, play a central role in many algorithms. Over the years, mathematicians have used graphs to solve many famous problems. One of the most famous is calculating how many colors are needed to color each country on a world map, such that no two adjacent countries share the same color. (If two countries touch at a single point, that point isn't considered a boundary.) People have long suspected that the answer is four, and thus the problem can be to prove that any map can be colored with only four colors.

This assertion has been proven in various ways. One way employs graph theory—in particular, planar graphs. Remember that a planar graph is simply a graph that can be drawn on paper (that is, in two dimensions) without any edges crossing. The vertices in the graph represent countries, and the edges represent adjacencies. Thus, if a line connects two countries in a graph, the two countries share a common border. By this representation, the assertion becomes the following: Given any planar graph, a number can be associated with each vertex, and only four numbers are needed such that no two adjacent vertices share a single number. That hypothesis can then be proven using graph theory. (I won't go into the details here, but you can find information on the web if you're curious. It's called the "Four Color Theorem.")

Another famous problem that can be proven using graph theory is the "Seven Bridges" problem. The problem is based on the bridges of Konigsberg, Prussia. The problem is whether it's possible to walk across each bridge in that city once and only once (without cheating by swimming across a river), and ultimately return to the starting point. The famous mathematician Leonhard Euler solved the problem by using graph theory. (Unfortunately, his proof shows that it's impossible to perform the feat without jumping into one of the rivers.)

In Euler's proof of the Seven Bridges problem, he let the vertices of a graph represent the land masses, and the edges of the graph represented the bridges. To solve the problem, Euler associated a degree with each vertex; the degree is the number of edges touching the vertex. Euler proved that in order to complete a single circuit (that is, to cross each bridge once and only once and to return to your starting point), all the nodes must have a degree that's positive. If any nodes have an odd number of edges touching them, then the task is impossible. The seven bridges in Konigsberg were constructed such that four of the nodes have odd degrees.

Graphs, Computers, and Popular Culture

Graphs show up all over the place in the world of computers. The Web itself is one massive graph, with each page being a vertex, and each link to another page an edge. Another place you see a graph concept is in social sites such as MySpace. In that sense, each profile is a vertex, and each friendship connection is an edge. That is, profiles are linked to other profiles via friend connections, just as vertices are linked to other vertices via edges.

In fact, the friendship link concept is used in a game people play, often called "Six Degrees of Kevin Bacon." The idea is that every Hollywood movie star is linked to Kevin Bacon by at most six links, and your job is to find the links. For example, take Jamie Foxx, who is two degrees from Kevin Bacon. One link goes like this: Jamie Foxx was in Booty Call with David Hemblen, who was in Where the Truth Lies with Kevin Bacon. (How did I know? I checked it out at The Oracle of Bacon.)

One popular social networking site, Facebook, uses graph theory to tell how members are connected to other members. If you're signed in, you visit a member's page, and that member is only a couple of links away, Facebook shows the connection. It says that person A is on your friend list, who has person B on his or her friend list, who in turn is friends with the person whose profile you're looking at. The FAQ even mentions using graph theory algorithms to make those connections visible.

Constructing a Simple Graph with Boost

If you have to code a graph theory algorithm, you can either build the graph data structures yourself, or use a library. The one I'm using for this article is found in the Boost library. Let's take a look at a first sample to show you how to use the Boost library's support for graph theory.

In general, a graph can be represented in a computer as a set of vertices and a set of edges connecting the vertices; the edges are simply pairs of vertices. Further, each vertex and each edge can have additional data attached to it, such as a number representing a weight, in the case of edges. This is essentially how Boost's Graph library works.

The Boost Graph library exists as templates, which means that you create your own classes and types based on the templates. However, the parameters for the templates all have defaults, so you can create a graph easily without having to do any customization.

Here's a short piece of code that demonstrates creating a graph and inserting vertices and edges into the graph. This code compiles completely, but it doesn't really do much other than create the graph:

#include <iostream>
#include <stdlib.h>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

int main(int argc, char *argv[])
{
  adjacency_list<> mygraph; 
  add_edge(1, 2, mygraph);
  add_edge(1, 3, mygraph);
  add_edge(1, 4, mygraph);
  add_edge(2, 4, mygraph);
  return 0;
}

The mygraph variable is the graph itself. The type is adjacency_list, which is the fundamental graph template type in the Boost Graph library. I used the defaults for the parameters; thus, the parameters are an empty set with angle brackets (<>).

The add_edge function is a template helper function for adding items to the graph. To use it, you pass the values for two vertices. If the vertices don't already exist in the graph, they'll be added; then the edge connecting the two vertices will be added. Thus, the preceding code creates a graph with four vertices, numbered 1, 2, 3, and 4, with edges connecting 1 and 2, 1 and 3, 1 and 4, and finally 2 and 4.

This is just a basic example. To create more complex graphs, you'll need to define more data to associate with your edges and vertices. I take up that task in the next section.

Adding Values to Vertices and Edges

When you use a graph, normally you'll want to associate information with the vertices and edges. The Graph library uses an interesting approach for this goal. Items such as names or colors are stored in properties, which consist of a name (or tag) such as distance or name, and a type such as float or string. You can add properties to both vertices and edges.

BOOST_DEF_PROPERTY(edge, name);

When you define a graph, you can specify the types of properties associated with the graph. You can add as many properties as you want to vertices and edges. To define properties, first you create a template type for each property type, and then you define the graph type before you instantiate the graph. For example, suppose you want to attach a distance to each edge, and a city name to each vertex. Here's the code to define the two property types:

typedef property<edge_weight_t, int> EdgeWeightProperty;
typedef property<vertex_name_t, std::string> VertexNameProperty;

The first line defines the EdgeWeightProperty type. The first parameter to the template is the tag for the property. I'm using one of the predefined tags, edge_weight_t, which means edge weight. The second parameter is int, meaning this property will hold an integer. The second line defines the second property; the tag is vertex_name_t, and the type is string.

Now that you have the property types defined, you can define a graph type:

typedef adjacency_list<vecS, vecS, undirectedS,
  VertexNameProperty, EdgeWeightProperty> Graph;

I'm using three predefined values for the first three parameters. The first and second parameters (vecS in both cases) indicate that I want the graph to use vectors for its internal storage, and the third parameter (undirectedS) says that I want an undirected graph. The fourth and fifth parameters (VertexNameProperty, EdgeWeightProperty, respectively) are the property types that I just defined, with the vertex type first, followed by the edge type.

At this point, you might wonder how you can specify more than one type of property for the edges and vertices. Here's how: Chain the properties together. The basic property template includes a parameter that can contain a property you already defined. Here's the vertex property definition again, but this time I'm defining two properties for vertex, a name and an index (using the predefined tag vertex_index2_t):

typedef property<vertex_index2_t, int>
  VertexIndexProperty;
typedef property<vertex_name_t, std::string,
  VertexIndexProperty> VertexNameProperty;

I've defined the index first, but the order really doesn't matter. The VertexNameProperty contains the VertexIndexProperty as its third parameter, thus creating a chain. You then pass the VertexNameProperty type to the fourth parameter of the graph definition, as before.

You also can condense your code a bit. This code is a bit less readable to somebody who is new to the Graph library, although once you understand the property mechanism it's pretty straightforward:

typedef property<vertex_name_t, std::string,
  property<vertex_index2_t, int> > VertexProperties;

I renamed the type VertexProperties, since it now contains two different properties. Also, notice the standard required space between the closing angle brackets, which is always needed in C++ so the parser doesn't think it's an insertion operator (>>). Don't forget that space, or you'll end up with compilation errors.

Manipulating Property Values

In order to access the properties of your graph, you need to obtain a helper object from the Graph library. You obtain one object for each property type. The objects are template objects, and you can obtain them after you've created an instance of your Graph type. Here are the lines that obtain objects for the three properties I declared in the preceding section:

property_map<Graph, vertex_name_t>::type
  city_name = get(vertex_name, g);
property_map<Graph, vertex_index2_t>::type
  city_index2 = get(vertex_index2, g);
property_map<Graph, edge_weight_t>::type 
  edge_distance = get(edge_weight, g);

Don't worry that the function name is the somewhat generic word get. The function is well-defined as a typed template, so it will compile just fine.

The first statement creates an object for obtaining the vertex_name property. Look closely at the parameters. On the left, the parameters to the template are the Graph type defined earlier, along with the tag for the property, vertex_name_t. On the right, inside the call to get, is not the tag name, but rather an enumeration type associated with the property, vertex_name. Each predefined tag name also includes an enumeration for each type. The Graph object itself, g, is the second parameter to the get function.

Remember, these three calls each obtain an object that you can use for getting properties for a vertex or edge. Although the sample code pieces I've been giving you so far haven't created any vertices, here's a sample line I'll use later on to obtain a property:

std::cout << city_name[*vp.first];

where vp.first is a pointer to a vertex. The object, city_name, works like a map, and it takes a vertex object as a parameter. It then returns the appropriate property—in this case, the city name.

Adding Vertices and Edges

After you've specified your property types and defined the graph type, you're ready to create an instance of the graph and add vertices and edges to the graph, along with values for the properties associated with the vertices and edges.

Let's start with a fresh graph, define some properties, and then add the edges and vertices along with their properties. I'll list all the code here so you don't have to piece together the fragments I've given you so far.

// Property types
typedef property<edge_weight_t, int> EdgeWeightProperty;
typedef property<vertex_name_t, std::string,
  property<vertex_index2_t, int> > VertexProperties;

// Graph type 
typedef adjacency_list<vecS, vecS, undirectedS,
  VertexProperties, EdgeWeightProperty> Graph;

// Graph instance
Graph g;

// Property accessors
property_map<Graph, vertex_name_t>::type 
  city_name = get(vertex_name, g);
property_map<Graph, vertex_index2_t>::type
  city_index2 = get(vertex_index2, g);
property_map<Graph, edge_weight_t>::type
  edge_distance = get(edge_weight, g); 

// Create the vertices
typedef graph_traits<Graph>::vertex_descriptor Vertex;
Vertex u1;
u1 = add_vertex(g);
city_name[u1] = "Los Angeles";
city_index2[u1] = 3;

  Vertex u2;
   u2 = add_vertex(g);
  city_name[u2] = "Bakersfield";
  city_index2[u2] = 2;

Vertex u3;
u3 = add_vertex(g);
city_name[u3] = "New York";
city_index2[u3] = 1;

// Create the edges 
typedef graph_traits<Graph>::edge_descriptor Edge;
Edge e1;
e1 = (add_edge(u1, u2, g)).first;
edge_distance[e1] = 100;

Edge e2;
e2 = add_edge(u1, u3, g).first;
edge_distance[e2] = 2500;

In the first section I define the property types, followed by the graph type. Then I create the instance, g, of the graph. Next, I obtain the property access objects that I talked about.

Then I start adding the vertices and edges. To add the vertices, I create my own type called Vertex from the vertex_descriptor, just to simplify the code a bit. I add the vertex by calling the helper function add_vertex, passing in g.

The graph adds the vertex and returns a vertex descriptor. Then I use the property access objects to assign the two properties for the vertex: city_name and city_index2. Setting the properties is easy; I just use the vertex as an index into the map by putting the vertex name in brackets ([]).

Creating the edges is similar, except that the add_edge function returns a pair type rather than an edge type. So I just grab the .first member of the pair to get the edge itself. I save that in a variable; then I use that variable as an index to set the properties. Since mathematically an edge is really nothing more than a set of two vertices, that's all I have to pass to add_edge, along with the graph.

Iterating Through the Edges and Vertices

To iterate through the edges and vertices, you can obtain iterators by calling edges(g) and vertices(g), respectively. These functions return pairs that you can use in your iterations. Here are two blocks of code that iterate through the edges and vertices I created in the preceding section:

// Iterate through the vertices and print them out
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) 
  std::cout << city_name[*vp.first] << " " << city_index2[*vp.first] << std::endl;
std::cout << std::endl;

// Iterate through the edges and print them out
Vertex v1, v2; 
typedef graph_traits<Graph>::edge_iterator edge_iter;
std::pair<edge_iter, edge_iter> ep;
edge_iter ei, ei_end;
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
  std::cout << edge_distance[*ei] << endl;

I purposely used two approaches in these two blocks of code to demonstrate a certain feature about the pairs that are returned. When I iterated through the vertices, I got back a pair, for which I created a typedef. Then, to access the vertex, I called vp.first. That's an iterator; like most iterators in C++, to get to the instance itself, I dereferenced it. Thus, I could write out the city name and index using this:

city_name[*vp.first]

and this:

city_index2[*vp.first]

If you don't want to work with pairs, however, the library includes a handy helper function called tie, which assigns the individual parts of the pair to the variables passed into the tie function. Since edges(g) returns a pair, calling this:

tie(ei, ei_end) = edges(g)

will save the first item in the pair into ei and the second into ei_end. Then, in the loop, you can access the edge simply with *ei, like so:

edge_distance[*ei]

Solving Problems with Graphs and Boost

Although the Six Degrees of Kevin Bacon game is for fun, the technique used to solve it, called the "Shortest Path" problem, has some practical uses beyond ruminating over movie stars. For example, if you use one of the popular shipping companies to ship a product from Bakersfield, California to Lake Mary, Florida, the shipper needs to find the shortest (that is, the least expensive) path to get the package to the destination. Most likely the package will travel through at least a few cities that the shipper considers hubs. Each city, then, is a vertex on the graph, and cities are connected by edges. The graph is weighted, since the distances between cities vary, as do the time and method to move a package from one city to the next. This is where the problem differs from the Six Degrees problem, since the Six Degrees problem doesn't have weights to the edges.

Mathematicians and computer scientists have developed various algorithms to solve graph theory problems, including the Shortest Path problem. Entire books have been written on the subject of solving problems with graph theory. Certainly, many of the big problems such as those dealing with product shipping involve large numbers of vertices and edges. (Think of the number of cities in the United States, pretty much all served by the United States Post Office.) Thus, these problems are best suited for computers.

The Boost library includes several well-known graph theory algorithms so you don't have to code them yourself. It includes several different Shortest Path algorithms, for example. The thing about the fun Kevin Bacon problem is that it's actually not all that interesting from a graph theory perspective, because all the edge weights are 1; by that I mean that when two actors are connected by having been in a movie together, there isn't a physical distance associated with the connection.

When the edge weight is 1, as with the Kevin Bacon problem, the algorithm becomes identical to an algorithm called "Breadth First Search" (BFS). BFS is used for iterating over vertices, starting at a beginning vertex called the root. The idea is that you start at the root vertex, and spread out to each vertex touching the root, marking each as visited. Then you continue for each of these vertices, visiting each unvisited vertex until you've covered the graph. Or you can stop when you find a particular vertex you want, in which case you've found the shortest path to the vertex you wanted.

The documentation for the Boost library includes a good demonstration of the Kevin Bacon game. Rather than write up similar code here, I suggest just checking out the documentation.

Of more interest to a lot of programmers than the Kevin Bacon game is another interesting problem of file dependencies. Programs such as make and ant as well as spreadsheets need this algorithm. For example, if you're writing spreadsheet software, and the spreadsheet contains cells with formulas referencing other cells, you need to figure out the order in which to evaluate the formulas. If cell A1 has a formula that makes use of cell A2, and A2 has a formula, then you have to evaluate the formula in A2 before you can evaluate the one in A1. That's a dependency algorithm. The same applies to compilation order in programs such as make and ant. If file 1 depends on file 2, then you have to know to compile file 2 before file 1. The documentation for the Boost Graph library includes a sample that solves the file dependency problem.

Conclusion

The Boost library definitely has a sharp learning curve. The documentation doesn't flow nicely, and it takes awhile to wade through it to flesh out the vital topics. However, once you've passed the learning curve, the library is incredibly powerful, and really does make sense. The designers have done a fine job of implementing a library using templates.

Be sure to check out the online documentation; even though I've criticized it a bit here, it contains a lot of useful information. But also look at the samples, as they provide some good starting points. The entire library can be found at the Boost web site.

`dijkstra_shortest_paths`

// named parameter version
template <typename Graph, typename P, typename T, typename R>
void
dijkstra_shortest_paths(Graph& g,
  typename graph_traits<Graph>::vertex_descriptor s, 
  const bgl_named_params<P, T, R>& params);

// non-named parameter version
template <typename Graph, typename DijkstraVisitor , 
	  typename PredecessorMap, typename DistanceMap,
	  typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename  CombineFunction, 
	  typename DistInf, typename DistZero, typename ColorMap = default>
void dijkstra_shortest_paths
  (const Graph& g,
   typename graph_traits<Graph>::vertex_descriptor s,  
   PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 
   VertexIndexMap index_map,
   CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
   DijkstraVisitor vis, ColorMap color =  default)

This algorithm [10,8] solves the single-source shortest-paths problem on a weighted, directed or undirected graph for the case where all edge weights are nonnegative. Use the Bellman-Ford algorithm for the case when some edge weights are negative. Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one. For the definition of the shortest-path problem see Section Shortest-Paths Algorithms for some background to the shortest-path problem.

There are two main options for obtaining output from the dijkstra_shortest_paths() function. If you provide a distance property map through the distance_map() parameter then the shortest distance from the source vertex to every other vertex in the graph will be recorded in the distance map. Also you can record the shortest paths tree in a predecessor map: for each vertex u in V, p[u] will be the predecessor of u in the shortest paths tree (unless p[u] = u, in which case u is either the source or a vertex unreachable from the source). In addition to these two options, the user can provide there own custom-made visitor that can takes actions during any of the algorithm's event points.

Dijkstra's algorithm finds all the shortest paths from the source vertex to every other vertex by iteratively ``growing'' the set of vertices S to which it knows the shortest path. At each step of the algorithm, the next vertex added to S is determined by a priority queue. The queue contains the vertices in V - S[1] prioritized by their distance label, which is the length of the shortest path seen so far for each vertex. The vertex u at the top of the priority queue is then added to S, and each of its out-edges is relaxed: if the distance to u plus the weight of the out-edge (u,v) is less than the distance label for v then the estimated distance for vertex v is reduced. The algorithm then loops back, processing the next vertex at the top of the priority queue. The algorithm finishes when the priority queue is empty.

The algorithm uses color markers (white, gray, and black) to keep track of which set each vertex is in. Vertices colored black are in S. Vertices colored white or gray are in V-S. White vertices have not yet been discovered and gray vertices are in the priority queue. By default, the algorithm will allocate an array to store a color marker for each vertex in the graph. You can provide you own storage and access for colors with the color_map() parameter.

The following is the pseudo-code for Dijkstra's single-source shortest paths algorithm. w is the edge weight, d is the distance label, and p is the predecessor of each vertex which is used to encode the shortest paths tree. Q is a priority queue that supports the DECREASE-KEY operation. The visitor event points for the algorithm are indicated by the labels on the right.

DIJKSTRA(G, s, w)
  for each vertex u in V
    d[u] := infinity 
    p[u] := u 
    color[u] := WHITE
  end for
  color[s] := GRAY  
  d[s] := 0 
  INSERT(Q, s)
  while (Q != Ø)
    u := EXTRACT-MIN(Q)
    S := S U { u }
    for each vertex v in Adj[u]
       if (w(u,v) + d[u] < d[v])
        d[v] := w(u,v) + d[u]
        p[v] := u 
        if (color[v] = WHITE) 
          color[v] := GRAY
          INSERT(Q , v) 
        else if (color[v] = GRAY)
          DECREASE-KEY(Q, v)
      else
        ...
    end for
    color[u] := BLACK
  end while 
  return (d, p)

initialize vertex u






discover vertex s

examine vertex u

examine edge (u,v)

edge (u,v) relaxed



discover vertex v 



edge (u,v) not relaxed

finish vertex u

Where Defined

boost/graph/dijkstra_shortest_paths.hpp

Parameters

IN: const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph.
Python: The parameter is named graph.

IN: vertex_descriptor s

The source vertex. All distance will be calculated from this vertex, and the shortest paths tree will be rooted at this vertex.
Python: The parameter is named root_vertex.

Named Parameters

IN: weight_map(WeightMap w_map)

The weight or ``length'' of each edge in the graph. The weights must all be non-negative, and the algorithm will throw a negative_edge exception is one of the edges is negative. The type WeightMap must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map. The value type for this map must be the same as the value type of the distance map.
Default: get(edge_weight, g)
Python: Must be an edge_double_map for the graph.
Python default: graph.get_edge_double_map("weight")

IN: vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)). This is necessary for efficient updates of the heap data structure [61] when an edge is relaxed. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.
Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacenty_list with VertexList=listS does not have an internal vertex_index property.
Python: Unsupported parameter.

OUT: predecessor_map(PredecessorMap p_map)

The predecessor map records the edges in the minimum spanning tree. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree. If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source. The PredecessorMap type must be a Read/Write Property Map whose key and value types are the same as the vertex descriptor type of the graph.
Default: dummy_property_map
Python: Must be a vertex_vertex_map for the graph.

UTIL/OUT: distance_map(DistanceMap d_map)

The shortest path weight from the source vertex s to each vertex in the graph g is recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path. The type DistanceMap must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the distance map. The value type of the distance map is the element type of a Monoid formed with the combine function object and the zero object for the identity element. Also the distance value type must have a StrictWeakOrdering provided by the compare function object.
Default: iterator_property_map created from a std::vector of the WeightMap's value type of size num_vertices(g) and using the i_map for the index map.
Python: Must be a vertex_double_map for the graph.

IN: distance_compare(CompareFunction cmp)

This function is use to compare distances to determine which vertex is closer to the source vertex. The CompareFunction type must be a model of Binary Predicate and have argument types that match the value type of the DistanceMap property map.
Default: std::less<D> with D=typename property_traits<DistanceMap>::value_type
Python: Unsupported parameter.

IN: distance_combine(CombineFunction cmb)

This function is used to combine distances to compute the distance of a path. The CombineFunction type must be a model of Binary Function. The first argument type of the binary function must match the value type of the DistanceMap property map and the second argument type must match the value type of the WeightMap property map. The result type must be the same type as the distance value type.
Default: std::plus<D> with D=typename property_traits<DistanceMap>::value_type
Python: Unsupported parameter.

IN: distance_inf(D inf)

The inf object must be the greatest value of any D object. That is, compare(d, inf) == true for any d != inf. The type D is the value type of the DistanceMap.
Default: std::numeric_limits<D>::max()
Python: Unsupported parameter.

IN: distance_zero(D zero)

The zero value must be the identity element for the Monoid formed by the distance values and the combine function object. The type D is the value type of the DistanceMap.
Default: D()with D=typename property_traits<DistanceMap>::value_type
Python: Unsupported parameter.

UTIL/OUT: color_map(ColorMap c_map)

This is used during the execution of the algorithm to mark the vertices. The vertices start out white and become gray when they are inserted in the queue. They then turn black when they are removed from the queue. At the end of the algorithm, vertices reachable from the source vertex will have been colored black. All other vertices will still be white. The type ColorMap must be a model of Read/Write Property Map. A vertex descriptor must be usable as the key type of the map, and the value type of the map must be a model of Color Value.
Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.
Python: The color map must be a vertex_color_map for the graph.

OUT: visitor(DijkstraVisitor v)

Use this to specify actions that you would like to happen during certain event points within the algorithm. The type DijkstraVisitor must be a model of the Dijkstra Visitor concept. The visitor object is passed by value [2].
Default: dijkstra_visitor<null_visitor>
Python: The parameter should be an object that derives from the DijkstraVisitor type of the graph.

Complexity

The time complexity is O(V log V).

Visitor Event Points

vis.initialize_vertex(u, g) is invoked on each vertex in the graph before the start of the algorithm.
vis.examine_vertex(u, g) is invoked on a vertex as it is removed from the priority queue and added to set S. At this point we know that (p[u],u) is a shortest-paths tree edge so d[u] = delta(s,u) = d[p[u]] + w(p[u],u). Also, the distances of the examined vertices is monotonically increasing d[u₁] <= d[u₂] <= d[u_n].
vis.examine_edge(e, g) is invoked on each out-edge of a vertex immediately after it has been added to set S.
vis.edge_relaxed(e, g) is invoked on edge (u,v) if d[u] + w(u,v) < d[v]. The edge (u,v) that participated in the last relaxation for vertex v is an edge in the shortest paths tree.
vis.discover_vertex(v, g) is invoked on vertex v when the edge (u,v) is examined and v is WHITE. Since a vertex is colored GRAY when it is discovered, each reacable vertex is discovered exactly once. This is also when the vertex is inserted into the priority queue.
vis.edge_not_relaxed(e, g) is invoked if the edge is not relaxed (see above).
vis.finish_vertex(u, g) is invoked on a vertex after all of its out edges have been examined.

Example

See example/dijkstra-example.cpp for an example of using Dijkstra's algorithm.

Notes

[1] The algorithm used here saves a little space by not putting all V - S vertices in the priority queue at once, but instead only those vertices in V - S that are discovered and therefore have a distance less than infinity.

[2] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
//
// Distributed under the Boost Software License, Version  1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//======================================================================= 
#include <boost/config.hpp>
#include <iostream>
#include <fstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp> 

using namespace boost;

int
main(int, char *[])
{
  typedef adjacency_list < listS, vecS, directedS,
    no_property, property < edge_weight_t, int > > graph_t;
  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; 
  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
  typedef std::pair<int, int> Edge;

  const int num_nodes = 5;
  enum nodes { A, B, C, D, E };
  char name[] = "ABCDE"; 
  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
  };
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
  int num_arcs = sizeof(edge_array) / sizeof(Edge); 
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  graph_t g(num_nodes);
  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
  for (std::size_t j = 0; j < num_arcs; ++j) { 
    edge_descriptor e; bool inserted;
    tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
    weightmap[e] = weights[j];
  }
#else
  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); 
  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

Monday 14 January 2008

Hardware Fun with the Arduino board

http://lwn.net/Articles/262093/

Several weeks ago, your author took a look at the SquidBee project, which involves making a wireless remote sensor network from building blocks made of open-hardware components. At the heart of each of the SquidBee nodes is an Atmel AVR 8 bit RISC microprocessor, which sits on an Arduino Diecimila circuit board. This week, we'll take a look at the Arduino project:

Arduino is an open-source electronics prototyping platform based on flexible, easy-to-use hardware and software. It's intended for artists, designers, hobbyists, and anyone interested in creating interactive objects or environments. Arduino can sense the environment by receiving input from a variety of sensors and can affect its surroundings by controlling lights, motors, and other actuators. The microcontroller on the board is programmed using the Arduino programming language (based on Wiring) and the Arduino development environment (based on Processing). Arduino projects can be stand-alone or they can communicate with software on running on a computer (e.g. Flash, Processing, MaxMSP).

AVR chips programmed with the Arduino on-board library software are available in a number of different hardware configurations. The Arduino Diecimila board is the one of the more popular variations, it features a USB host connection which provides power and allows for software downloads. The Diecimila name comes from the fact that 10,000 Arduino boards have been sold, making is a fairly popular development platform. Arduino Diecimila boards are available from a number of vendors for around $35. The board was purchased online and arrived in the mail several days later.

In addition to the basic processor board, there are numerous open-design shield boards available. Shield board functions that are currently available include: motor control, biosensor interface, prototyping, XBee interface, Phidget sensor interface, and potentiometer interface. Upcoming shield boards include: sensor amplifier, external memory, external display controller, Bluetooth interface and multi-sensor interface.

To work with the Arduino board, it is necessary to install some software on a host machine. Your author used his main Athlon 64 which runs Ubuntu 7.04. There is a special Ubuntu installation document that walks the user through the package installation (and removal) steps, and explains the software setup procedure.

Running the Arduino IDE was a simple matter of typing ./arduino on the command line, which caused the IDE window to pop up. The IDE defaulted to the Diecimila board type, it was necessary to define the USB connection in the Tools/Serial Port pulldown. The first attempt at running an LED blinker test program resulted in a bit of operator confusion. The board is apparently shipped with this particular software example installed, so installing the same test software does not change the appearance of the already blinking LED.

The Blinker software was pulled into the IDE with the File->Sketchbook->Examples->Digital->Blink menu sequence. The software was built with no trouble using the Verify button and copied to the board using the Upload button. The LED started blinking again. Tweaking the delay times in the example code, then building and uploading the changed code verified that indeed, changes were being sent to the board. There is another slightly confusing interface aspect to the IDE, there are tape recorder style run/stop buttons at the top of the screen, but the run button is really the Verify (compile) function and the Stop button didn't seem to stop the running code.

The software that the Arduino board runs is written in the Arduino programming language, which looks a lot like C/C++ and is based on the wiring language. Making a few changes to the blinking LED example was so intuitive that it was not even necessary to consult the documentation. The Button example was also tried, digital input to the board worked as advertized.

Further testing of the I/O functions of the Arduino Diecimila board will require some hardware construction, which is beyond the scope of this (first) article. Your author has been building simple and complicated microcontroller projects for a number of decades; his initial impression of Arduino is that it has a very quick learning curve and provides a lot of powerful features. The Atmel AVR microcontroller provides a lot of useful I/O functionality and enough memory to build many interesting devices.

If you are looking for a convenient way to design a microcontroller based hardware project, extend the I/O capabilities of your desktop system, or just play with some cool hardware, Arduino is a quick and easy way to get started.

Simcity released as Micropolis - Open Source

http://www.donhopkins.com/home/micropolis/

Friday 11 January 2008

Briggs-Rauscher Reaction

http://library.thinkquest.org/10429/high/cool/labs/osc.htm

In this reaction three colorless solutions are mixed and stirred on a magnetic stirrer. The solution turns yellow, blue-black and clear again. The solutions will oscillate berween these colors for several minutes. Also, the electric potential oscillates with the color.

Solution A:

4.0 M H₂O₂ (410 ml of 30% hydrogen peroxide diluted to l.0 liter with distilled water)

Solution B:

0.20 M in KIO₃ and 0.077 M in H₂SO₄ (Place 43 g of potassium iodate in about 800 ml of distilled water. Add 4.3 ml of concentrated H₂SO₄. Warm and stir the mixture until the potassium iodate dissolves. Dilute the solution to 1.0 liter with distilled water.)

Solution C:

Starch solution that is 0.15 M in maloric acid and 0.02 M in MnSO₄ (Dissolve 16 g of malonic acid and 3.4 g of manganese (II) sulfate monohydrate in about 500 ml of distilled water. Mix 0.30 g of soluble starch with about 5 ml of distilled water and stir the mixture to form a slurry. Pour the slurry into 50 ml of boiling distilled water and continue heating and stirring the mixture until the starch has dissolved. Pour this starch solution into the solution of malonic acid and manganese (II) sulfate. Dilute the mixture to 1.0 liter with distilled water.)

Procedure:

Mix 150 ml of each solution in a beaker and stir on a magnetic stirrer. Observe the color changes. The initially colorless solution will become amber almost immediately. Then it will suddenly turn blue-black. The blue-black will fade to colorless. Also, you may want to record the potential of the solution as the oscillating reaction proceeds.

Explanation:

This oscillating reaction was developed by Thomas S. Briggs and Warren C. Rauscher of Galileo High School in San Francisco. In their reaction the evolution oxygen and carbon dioxide gases and the concentrations of iodine and iodide ions oscillate. Iodine is produced rapidly when the concentration of iodide ions is low. .As the concentration of iodine in the solution increases, the amber color of the solution intensifies. The production of I increases as the concentration of I₂ increases. and these ions react with iodine molecules and starch to form a blue-black complex containing the pentaiodide ion (I₅).

Upon initial mixing of the solutions IO₃ reacts with H₂O₂ to produce a little HIO₂. The HIO₂ reacts with IO₃ and HOI is formed. The HOI is reduced to I in a reaction with H₂O₂. The large amount of HOI reacts with I producing I₂. The I₂ reacts slowly with malonic acid but the concentrations of HOI, I₂, and I all increase. The amber color is present when the HOI concentration is greater than the I concentration. The dark blue color signifies that the concentration is greater than the HOI concentration. The reaction mechanism is very complex with about l2 steps. The oscillating sequence repeats until the malonic acid or IO₃ is depleted.

Safety Precautions:

1. Hydrogen peroxide is an oxidizer and a skin and eye irritant.

2. Sulfulric acid is a strong acid and is corrosive to eyes, skin and other tissue.

3. Malonic acid is a strong irritant to skin, eyes, and mucous membranes.

4. The reaction produces iodine in solution in suspension. and also as a vapor above the reaction mixture. The vapor or the solid is very irritating to the eyes. skin and mucous membranes.

5. Wear chemical-resistant gloves and goggles.

Tips:

1. Use only distilled or deionized water. Make sure all glassware is clean and rinsed in distilled or deionized water.

2. The solutions can be mixed in any order as long as they are combined quickly

Disposal:

The reaction produces elemental iodine, I₂, which should be reduced to iodide ions before disposal. Therefore, under a hood add sodium thiosulfate crystals until the mixture becomes colorless. This will be an exothermic reaction. When it cools, it may be flushed down the drain with water.

Wednesday 9 January 2008

creating a DVD from the edited video

http://lwn.net/Articles/263387/

Many of us have burned CDs and found the process to be relatively straightforward - the biggest obstacle is often just getting past the grumpiness built into cdrecord and its latter-day derivatives. Creating data DVDs is not a whole lot harder. So one might be inclined to approach the task of creating a video DVD with a "this will be easy" attitude. It is, in fact, a task just about anybody can learn to do, but it is on a different order of complexity than creating a CD full of music. A video DVD is, in truth, a program complete with its own hierarchical structure, menus, and code written for the simple virtual machine lurking within every DVD player. Creating a playable DVD requires writing that program.

If DVDs are programs, then the one compiler available for Linux systems is the command-line dvdauthor tool. Regardless of how one builds a DVD, dvdauthor will be involved in the process at some point. This tool requires a collection of video objects representing the actual video titles and also implementing the menus, subtitles, and more. It's all tied together via a complex XML file (example) which is compiled by dvdauthor to create the final product.

It is possible to create all of these pieces by hand, and, doubtless, Real Linux Video Jocks would not do it any other way. One can use dvdauthor to help with the generation of parts of the XML file. There is documentation which seems fairly complete, if a bit terse. But the fact of the matter is that most people attempting to use this tool directly will give up in despair. There is no reason why DVD authors should have to work at this level; dvdauthor is essentially an assembler which, while being absolutely essential to do most of the heavy lifting, should be hidden from most polite company. DVD creation is a visual task; there should be visually-oriented tools for this job. The good news is that these tools do, indeed, exist.

Utilities for Windows

http://www.hanselman.com/tools

Tuesday 8 January 2008

Innovative Designs and Devices

http://www.smashingmagazine.com/2008/01/07/monday-inspiration-innovative-designs-and-devices/

Monday Inspiration: Innovative Designs and Devices

Steve Jobs stated once that the "design is not just what it looks like and feels like. Design is how it works." While this statement has proven to be crucial over thousands of years, one shouldn't misinterpret it by emphasizing the functionality despite the design. When it comes to product design, the significance of aesthetics of a given device, the way its design looks and feels, determines the choice of the customer once the functionalities of multiple devices are more or less similar. If supported by sound user interface and a well-tested, clean implementation, innovative design solutions can drastically enhance the user experience.

This article presents innovative, futuristic gadgets, devices, designs and concepts. Unless explicitly specified, none of these cut-edge concepts is currently being manufactured. None of them is available for end-users which is why neither the price nor links to the stores are mentioned.

Monday 7 January 2008

Writing programs, open source flight simulator and robust copying in Vista

http://literatureandlatte.com/scrivener.html

Scrivener is a word processor and project management tool created specifically for writers of long texts such as novels and research papers. It won't try to tell you how to write - it just makes all the tools you have scattered around your desk available in one application.

http://hogbaysoftware.com/products/writeroom
For people who enjoy the simplicity of a typewriter, but live in the digital world. WriteRoom is a full-screen writing environment. Unlike the cluttered word processors you're used to, WriteRoom is just about you and your text. Requires Mac OS X 10.4 or later

http://www.flightgear.org/

The FlightGear flight simulator project is an open-source, multi-platform, cooperative flight simulator development project. Source code for the entire project is available and licensed under the GNU General Public License.

The goal of the FlightGear project is to create a sophisticated flight simulator framework for use in research or academic environments, for the development and pursuit of other interesting flight simulation ideas, and as an end-user application. We are developing a sophisticated, open simulation framework that can be expanded and improved upon by anyone interested in contributing.

There are many exciting possibilities for an open, free flight sim. We hope that this project will be interesting and useful to many people in many areas.

http://en.wikipedia.org/wiki/Robocopy

Robocopy, or "Robust File Copy", is a command-line folder replication tool. It was available as part of the Windows Resource Kit, and introduced as a standard feature of Windows Vista.

Robocopy is designed for reliable mirroring of folders or folder trees. It has features to ensure all NTFS attributes and properties are copied, and includes additional restart code for network connections subject to disruption.

http://www.microsoft.com/technet/technetmag/issues/2006/11/UtilitySpotlight/default.aspx

Friday 4 January 2008

Public domain maps

http://www.openstreetmap.org/
OpenStreetMap is a free editable map of the whole world. It is made by
people like you.

OpenStreetMap allows you to view, edit and use geographical data in a
collaborative way from anywhere on Earth.

OpenStreetMap's hosting is kindly supported by the UCL VR Centre
(http://www.vr.ucl.ac.uk/) and bytemark. http://www.bytemark.co.uk/

Thursday 3 January 2008

Obscure Google Search Tricks & Neuro-linguistic programming

http://lifehacker.com/339474/top-10-obscure-google-search-tricks

http://en.wikipedia.org/wiki/Neuro-linguistic_programming

Neuro-linguistic programming

Analyzing this further, Grinder and Bandler stated that there were a few common traits such people – whether top therapists, top executives or top salespeople – all seemed to share:

Everything they did in their work, was pro-active (rather than reactive), directed moment to moment by well-formed outcomes ^[17] rather than formalized fixed beliefs
They were exceedingly flexible in approach and refused to be tied down to using their skills in any one fixed way of thinking or working ^[18] ^[17]
They were extremely aware moment by moment, of the non-verbal feedback (unconscious communication and metaphor) they were getting, and responded to it ^[18] ^[17] - usually in kind rather than by analyzing it ^[19]
They enjoyed the challenges of difficult ("resistant") clients, seeing them as a chance to learn rather than an intractable "problem"
They respected the client as someone doing the best they knew how (rather than judging them as "broken" or "working")
They had certain common skills and things they were aware of and noticed, intuitively "wired in" ^[18] ^[20]
They worked with great precision, purpose, and skill ^[21] ^[20]
They kept trying many many different things until they learned enough about the structure holding a problem in place to change it ^[18] ^[17]

They summarized their findings:^[17]

"You need only three things to be an absolutely exquisite communicator. We have found that there are three major patterns in the behavior of every therapeutic wizard we've talked to — and executives, and salespeople. The first one is to know what outcome you want. The second is that you need flexibility in your behavior. You need to be able to generate lots and lots of different behaviors to find out what responses you get. The third is you need to have enough sensory experience to notice when you get the responses that you want..."