Why Topological Sorting?

A traditional sort algorithm, such as quicksort or bubble sort, takes a set of items and returns them in a new order based on a certain criteria (for example they may be returned in alphabetical order). For this to be possible, the algorithm needs to be able to pick out any two items from the list and be able to figure out which comes first.

Sometimes, however, we have a set of items for which this doesn’t hold true. There may be some pairs of items for which we can’t work out the correct order just by looking at those two items, and some we can. Such a set is know as a partial order.

While it may seem that elements where the order is unknown could just be put in any random order, this may not always be the case. While we can’t tell by looking at them that A comes before C, we may be able to look and see that A comes before B and B comes before C, implying that A does come before C. But that requires a more global view than taken by traditional sort function.

What is Topological Sorting?

This is where topological sort algorithms come in. They provide a means of sorting a partial order, such that the order constraints are all honoured. While they are a range of ways of performing a topological sort, the simplest is to iteratively remove nodes with no inbound edges from the partial order (viewed as a directed acyclic graph with the set elements as nodes and the order constraints as edges). The nodes placed in order of their removal then form the topologically sorted list of set elements.

Topological Sorting in PHP

So after that, here is my topological sorting function. It’s reasonably efficient, and has a smaller code-footprint than any alternatives I could find on the web.

function topological_sort($nodeids, $edges) {
	$L = $S = $nodes = array();
	foreach($nodeids as $id) {
		$nodes[$id] = array('in'=>array(), 'out'=>array());
		foreach($edges as $e) {
			if ($id==$e[0]) { $nodes[$id]['out'][]=$e[1]; }
			if ($id==$e[1]) { $nodes[$id]['in'][]=$e[0]; }
		}
	}
	foreach ($nodes as $id=>$n) { if (empty($n['in'])) $S[]=$id; }
	while (!empty($S)) {
		$L[] = $id = array_shift($S);
		foreach($nodes[$id]['out'] as $m) {
			$nodes[$m]['in'] = array_diff($nodes[$m]['in'], array($id));
			if (empty($nodes[$m]['in'])) { $S[] = $m; }
		}
		$nodes[$id]['out'] = array();
	}
	foreach($nodes as $n) {
		if (!empty($n['in']) or !empty($n['out'])) {
			return null; // not sortable as graph is cyclic
		}
	}
	return $L;
}

PHP Topological Sorting Example

To use the function just call it with an array of node ids and an array of edges (where each edge is an array of two elements, the start node followed by the end node). For example:

$nodes = array('1','2','3','4','5');
$edges = array(array('1','2'),
               array('3','1'),
               array('3','4'));
print_r(topological_sort($nodes, $edges));

This outputs the sorted partial order, like so:

Array
(
    [0] => 3
    [1] => 5
    [2] => 1
    [3] => 4
    [4] => 2
)

Well it turns out the CoolMath website has a spin-off site aimed at kids below the age of 13: CoolMath4Kids.com. CoolMath4Kids is every bit as brightly colored and packed with games, lessons and activities as it’s big brother. Guided by cute cartoon monsters such as “Spike”, your child is able to study a wide range of topics.

There are comprehensive math lessons covering all the basics: addition, subtraction, times-tables, long division, fractions and decimals.

And as your child progresses, they can move onto the more advanced topics such as fractals, polyhedra, tessellations, lattice multiplications and brain benders.

Coolmath4kids contains plenty of supporting material to help as your child moves through the lessons. For example there are flash cards to help strengthen their recall of key concepts. There are also links to the main Coolmath site so your kids can smoothly transition as their math skills improve.

If your kids are starting out learning math, CoolMath4Kids may well be worth a look.

There are three Wesbank Calculators: a vehicle payment calculator, a vehicle purchase price calculator and a business finance calculator.

Wesbank Vehicle Repayment Calculator

The vehicle repayment calculator allows you to calculate vehicle repayments based on a number of inputs such as the purchase price, extras cost, interest rate and term. It not only gives you a calculation of the total amount you can expect to repay, but it also shows how much of that goes on admin fees, interest, etc. A nice feature is that you can even add in the cost of insurance products (though the language is somewhat specific to Wesbank products).

Wesbank Vehicle Purchase Price Calculator

In many ways the vehicle purchase price calculator is the inverse of the vehicle payment calculator. Given the amount you are willing to spend on repayments each month, it’ll tell you the maximum price of car you can buy that will fit your monthly budget. This calculator is the simpler of the two, having less fields to fill out. Like the repayment calculator it is well laid out with the option of entering values manually or via a slider.

Wesbank Finance Calculator

If you’re taking out a business loan or other form of business financing, you’re going to want to know what your total repayment amount will be. That’s where the business finance calculator comes in. You enter the level of financing you are taking on, any deposit you’re contributing, the interest rate and the repayment frequency. From that it will calculate the repayment amount and the total amount you’ll repay. Simple, but very useful.

There are a few different ways of calculating percentages. You may want to calculate a percent of a number. Or you may want to calculate what percentage one number is of another. Either way, there is no need to do it by in your head when you can use one of these percentage calculators:

What is X% of Y?

Use the calculator below to calculate a percentage of a number.

Powered by

What % of X is Y?

Use this calculator to calculate what percentage one number is of another.

Powered by

Other Percent Calculations

Want to do another percentage calculation? Then just head on over to our main calculator page where you can enter any calculation you like.

CoolMath is a site aimed at making math cool for kids. A major focus of the site is math lessons in the form of games, such as “bloxorz”, “coffee shop”, “crazy taxi” and “lemonade stand”. The games each target a particular math skill.

The CoolMath site is also home to a vast array of math-based content, including math lessons, math practice and a comprehensive math dictionary.

The site is colorful and engaging, with core concepts presented in fun, clear diagrams. It is definitely a good place to introduce and build your child’s math skills without the stigma and difficulty of traditional textbooks. A very good, well established resource.

Coolmath Games

Coolmath offers a wide range of games which introduce math concepts in a fun, memorable way. Here are a few of the more popular math games.

Coolmath Bloxorz

Bloxorz is a neat logic puzzle game in which you move blocks around increasingly complex levels, manipulating switches and bridges to keep your blocks from falling of the edge. A very slick and entertaining head scratcher.

Coolmath Coffee Shop

In Coffee Shop you own your own “Starbucks”-style coffee shop. Using your maths skills, you must stock your shop and find the best price to sell at in order to make a profit.

Coolmath Crazy Taxi

The focus of Crazy Taxi is practising the times tables. You are the driver of a taxi on a busy street. To make your way as quick as possible you must crash into cars whose number is a multiple of a particular number, while avoiding other cars. Great fun, but perhaps not suitable for every child.

Coolmath Lemonade Stand

In Lemonade Stand your ability to distinguish between fractions, decimals and whole numbers is put to the test as you attempt to make a profit selling lemonade.

Update: I’ve just put up a review of Cool Math 4 Kids, a related site aimed at under 13s.

Having a vegetarian wife, I find myself making a lot of meat-free meals – often using beans as a substitute. And being naturally lazy, I am always on the lookout for quick, easy meals. So it’s natural that at some point I’d end up making these quick and easy vegetarian bean wraps.

The recipe has a base of grated zucchini, but we’ve also used carrot as an good alternative.  The rest of the recipe is similarly up for negotiation: we tend to use whatever beans we have to hand, and throw in other ingredients such as mushrooms if they are going spare.

Quick and Easy Vegetarian Bean Wraps

A flavoursome, healthy meat-free Mexican dish.

• 2 tbsp olive oil
• 1/2 onion (chopped)
• 1 red capsicum (diced)
• 1 tomato (diced)
• 1 large zucchini (grated)
• 1 tsp chilli flakes
• 400g can of sweetcorn (drained)
• 400g can of kidney beans (drained)
• Cracked black pepper
• 6 wraps (mountain bread or tortillas)
• 1/3 cup taco sauce
• 1/3 cup grated cheese (optional)

Preheat the oven to 180 degrees celcius.

Heat the oil in a frying pan over a medium high heat and fry the onion until soft (2-3 mins). Add the capsicum, tomato and grated zucchini and cook for 3-4 mins. Add the chilli flakes, sweetcorn and kidney beans and cook for a further until any liquid has reduced to a thick sauce-like consistency. Remove from the heat.

Spoon the mixture onto the wraps (approx 1/3 – 1/2 cup each), and roll them up. Place in a greased oven-proof dish. Spoon the taco sauce over the top of the wraps and spread evenly. Top with the cheese, if using.

Place the wraps in the oven and cook until they begin to brown, then remove and serve immediately. Serves 3-4.

However, there were a number of niggling aspects of using the calculator on the iPhone screen. I’ve made a number of improvements to address these.

Improved Layout

Previously, when I first loaded Calcatraz in the iPhone, the page would be tiny and I would need to zoom into to get it to fill the screen appropriately. And if you clicked in the calculation box the screen would zoom right in and fail to zoom out again when you had finished entering the calculation.

To fix this, I created an all new iPhone-specific layout. Calcatraz now detects the use of an iPhone and adjusts the screen layout to make the most of the available space. The new layout is shown on the left.

This layout eliminates the need to adjust the zoom level, and makes it much easier to view and interact with the calculator.

Keyboard Selection

When entering a calculation, the iPhone would default to showing the qwerty keyboard. As the majority of calculations involve numbers and symbols, this wasn’t an ideal selection.

I’ve changed this so that the numeric keypad is shown by default. This should speed up calculation entry and get you to your answer faster.

I’ve been separately planning to make a barbeque sauce and a taco sauce. Putting the chaining principle to work, I realised that they both have (or at least can have) a common base – tomato sauce (aka ketchup). So rather than make each from scratch, I figured I’d make a tomato sauce first, then add to it as necessary to make the barbeque and taco sauces. In doing so, I was able to make the three sauces (tomato, bbq and taco), with less effort than it would have been to make just two sauces (bbq and taco) separately.

The flip side of this is that you need to ensure the base is good, otherwise you could end up spoiling both sauces. A ketchup-style sauce is made by reducing a large quantity of tomato then flavouring with various spices, a bit of vinegar and some sugar. There is a lot of latitude in this for varying the added flavourings to a taste you like. But I’ve found the recipe below produces both a very enjoyable tomato ketchup, and makes a great base other tomato-based sauces, like the Kansas City barbeque sauce and the taco sauce below.

Tomato Sauce (Ketchup)

A rich, flavoursome tomato sauce. Feel free to use whatever tomatoes you have at hand (canned, vine ripened, cherry, etc.). A mix of half canned and half fresh gives a good balance between a fresh taste and a ketchupy consistency.

• 1.5kg tomatoes (roughly chopped)
• 1/8th cup extra virgin olive oil
• 1/2 brown onion (chopped)
• 1 clove of garlic (minced)
• 1/4 cup brown sugar
• 200ml white-wine vinegar
• 1/2 tsp paprika
• 1 tsp cloves
• 1 tsp allspice
• 1 tsp cracked black pepper
• 1 tsp salt

Heat the oil in a large pan over a medium-high heat. Add onion and garlic and cook until starting to brown, 4-5 mins. Add the tomatoes. Cover, bring to a gentle boil, then reduce the heat and simmer until the tomatoes are very tender (approx 1hr). Cool slightly, transfer into a blender and process until smooth. Return to a clean pan and stir in the vinegar and sugar. Add in the spices and seasoning. Then continue to simmer until it has reduced down to the consistency of a standard ketchup (1-2hrs). Pass through a sieve to remove any remaining pulp. Decant into sterilized bottles and store in the fridge. Makes 3 cups of sauce.

Kansas City Barbeque Sauce

An intense, fiery sauce that’s not for the faint-hearted.

• 1 cup tomato sauce (recipe above)
• 1/4 cup water
• 1/4 cup vinegar
• 1/4 cup brown sugar
• 3 tbsp olive oil
• 2 tbsp smoked paprika
• 1 tbsp chilli
• 2 cloves garlic (minced)

• 1 cup tomato sauce (recipe above)
• 1/4 cup water
• 1/4 tsp chilli powder
• 1 tsp cumin
• 1 tbsp onion (chopped)
• 1 tbsp white vinegar
• 1/2 clove garlic (minced)
• 1/4 tsp salt
• 1/4 tsp paprika
• 1/4 tsp sugar
• 1/4 tsp chilli flakes

Blend ingredients together until smooth. Transfer to a pan and simmer for 15 mins. Cool and store in a sterilized bottle.

Overview

Sorbets despite their sophisticated appearance, have a notably unsophisticated base. At its most basic, a sorbet is little more than frozen sugar water. While tricks like adding alcohol or egg whites help make a smoother sorbet, a very acceptable result can be achieved without this extra complexity.

A typical ratio of water to sugar seems to be three units of water per unit of sugar. The water is heated to dissolve the sugar, and then cooled before freezing.

The only other thing that must be added is the flavor-giving ingredients themselves. The simple, neutral base makes it possible to concoct a wide-range of flavours. If these ingredients contain water or sugar themselves, it may be necessary to adjust the ratio used in the base.

The real magic in the sorbet is in how it is frozen. Rather than putting it in the freezer and forgetting about it, the sorbet should be stirred well while it is freezing. The purpose of this is to break up the large ice-crystals which form, resulting in a smoother sorbet. (At the other extreme, where large ice-crystals are actively sought, is the Italian dessert, granita). I find the easiest and most effective way to do this is to freeze the sorbet until it is firm, but not fully frozen, then blend it for 15 seconds or so. The result is a very smooth, thick but runny sorbet which can be re-tubbed and returned to the freezer to freeze completely.

Here are the recipes for the sorbets I have made.

Dark Chocolate Sorbet

A rich, decadent dark chocolate sorbet balancing bitterness and sweetness.

• 1 cup sugar
• 3/4 cup cocoa powder
• pinch of salt
• 170g dark chocolate (70% cocoa is ideal)
• 1/2 tsp vanilla extract

In a large pan, combine the the sugar, cocoa powder, salt and 1 1/2 cups of water. Bring to the boil, while stirring. Remove from the heat after 45s. Then add the chocolate and stir until fully melted. Add the vanilla extract and 3/4 cup of water. Blend the mixture for 15s. Allow to cool, then transfer to a tub and place in the freezer until firm, but not fully frozen. Remove from the freezer, blend until smooth and then return to the freezer to finish freezing. When ready to eat, remove from the freezer and sit for 5 mins to soften before serving.

Mixed Berry and Watermelon Sorbet

A light, refreshing sorbet.

• 2 cups watermelon, diced
• 2 cups mixed berries
• 1/2 cup sugar
• 1 tbsp fresh mint, finely chopped

In a large pan, combine the the sugar with 1 cup of water. Heat, stirring until the sugar has fully dissolved. Remove from the heat and allow to cool slightly. Tip mixture into a blender and add the watermelon and berries. Blend until smooth (2-3mins), then sieve into a tub to remove the pips. Allow to cool, then transfer to a tub and place in the freezer. Stir after 1 hour, adding the mint as you do so. Return to the freezer until firm, but not fully frozen. Remove from the freezer, blend until smooth and then return to the freezer to finish freezing. When ready to eat, remove from the freezer and sit for 5 mins to soften before serving.

Lemon, Lime and Bitters Sorbet

A delicious twist on a traditional lemon sorbet.

• Juice of two limes
• Juice of four lemons
• 1/2 cup white wine
• 2 tbsp Angostura bitters
• 2/3 cup sugar

Combine the lime juice, lemon juice, wine, bitters, sugar and 1/2 cup of water in a small pan. Heat, stirring until the sugar has fully dissolved. Then remove from the heat and allow to cool slightly. Transfer to a tub and place in the freezer until firm, but not fully frozen. Remove from the freezer, blend until smooth and then return to the freezer to finish freezing. When ready to eat, remove from the freezer and sit for 5 mins to soften before serving.

Mojito Sorbet

Part cocktail, part dessert…

• 1/2 cup sugar
• 4 limes
• Large handful fresh mint leaves
• 5 tbsp rum

Combine sugar, zest of two of the limes and 2 1/2 cups of water in a small pan. Bring to the boil, stirring until the sugar has fully dissolved. Then remove from the heat and add the mint. Allow to cool, then refrigerate for 10 mins. Add the juice of the 4 limes, along with the rum. Transfer to a tub and place in the freezer until firm, but not fully frozen. Remove from the freezer, blend until smooth and then return to the freezer to finish freezing. When ready to eat, remove from the freezer and sit for 5 mins to soften before serving.

Overview

The essential ingredient in any mustard is, of course, the mustard seed. It comes in two basic forms: wholegrain (i.e. just the seed), and powder (i.e. ground seeds). The seeds come in several colours, namely the milder yellow seed and the more potent brown and black seeds. A wholegrain mustard will often mix yellow and brown seeds for balance and visual appeal.

To make the mustard proper, the seed is soaked in a cool or cold liquid, such as water, which kicks off a chemical reaction (between the myrosinase enzyme and glucosilinates present in the seeds) and produces the ‘heat’ of the mustard. The longer the reaction runs the hotter the resulting mustard will be. Vinegar and salt are usually used to control the reaction, and hence heat, and to enhance the flavour.

For wholegrain mustard, the heat-generating reaction will generally take 2-3 days to reach a suitable level and, after blending, the mustard may take several days (and sometimes upto several months) to ‘mature’ to its final taste. With mustard powder, the heat-generating reaction is a lot faster, taking a matter of hours. The powerfully anti-bacterial mustard seed when combined with vinegar and salt will be very resiliant and long-lasting. Note, though, that the addition of short-lived flavour ingredients such as fresh herbs will reduce the shelf-life of the mustard.

Flavours can be introduced in the liquid used, for instance swapping the vinegar for a flavoured variety (white wine, apple cider) or an alcohol (such as whisky or beer) with enough vinegar (or other acid) added to attain and balance the desired heat. Alternatively, or additionally, flavours can be mixed in at the blending stage, for instance adding herbs, seasoning and spices. A sweetener, such as sugar or honey, is often added as well. The combinations which can be made are practically (and perhaps actually) limitless.

Here’s the recipe I used, along with the three variants I made. As I had ran out of black mustard seeds by the time I got to the red wine mustard, I used 4 tbsp yellow mustard seeds instead.

Wholegrain Mustard

A basic wholegrain mustard, from which endless variations can be produced.

• 2 tbsp mustard seeds (yellow)
• 2 tbsp mustard seeds (black)
• 100ml white wine vinegar
• 1 tsp sugar
• 1/2 tsp salt

Mix the mustard seeds and vinegar in a non-metallic bowl. Cover with cling-film and leave to stand for 2-3 days (3 days for a hotter mustard). Check occasionally and add extra vinegar if it has all been absorbed.

Then, drain any excess liquid and set aside. In a mortar and pestle (or blender), blend the seeds into a paste. Blend in the salt and sugar, along with some of the reserved liquid (if required) to get the right consistency.

Decant the resulting mustard into a clean, sterilised jar. Cap and leave to mature for 2 days prior to use.

Dark Ale and Honey Mustard

Replace the white wine vinegar with 100ml of your favourite dark ale, mixed with 2 tsp of white vinegar. Replace the sugar with 1 tsp of honey.

Spicy Whisky Mustard

Replace the white wine vinegar with a mixture of 50ml whisky, 50ml white wine vinegar and 1/2 tsp chilli flakes. Replace the sugar with 1 tsp honey and 1 tsp nutmeg.

Red wine, Rosemary and Thyme Mustard

Replace the white wine vinegar with a mixture of 50ml water, 50ml red wine vinegar, 2 tsp dried thyme and 2 tsp dried rosemary. Use brown sugar in place of normal sugar.