Thursday, January 14, 2010

SyntaxHighlighter for Blogger


Installing SyntaxHighlighter in Blogspot blogs



Hello code bloggers, here is a short description and quick guide on how to install SyntaxHighlighter in your blogs and sites as well to beautify your codes. Actually nothing is more painful than reading out rusty codes no matter how cool they really are, so presentation does matter.

To go straight forward, go to Dashboard &rArr Layout &rArr Edit Html. Here you will see your current template. First save the current code to your hard drive before changing anything, so in-case you destroy the whole thing mistakenly, you have nothing to worry, just paste that again here, and every change is reverted. Actually it is good to store every working version of the template in your hard drive.

Now find the part in the html code:

</body>

</html>

First, we need to add some javascript links here, i.e. between these two tags. The files are located on the author's own host, http://alexgorbatchev.com/pub/sh/current/. The version I used for this blog is also uploaded here.We'll use it from there. But if you have your own host, you can download the files and make changes (as this project is open source) and upload it there, then use your links.

First add (I mean copy and paste) SyntaxHighlighter Core scripts:

<!-- SyntaxHighlighter core js files -->
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shLegacy.js' type='text/javascript'></script>
<!-- -->

Now add highlighting brushes for your favorite languages:

<!-- SyntaxHighlighter brushes -->
<!-- some are added here, explore the hosted files for more language supports -->
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCpp.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushBash.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJava.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPython.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPlain.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushVb.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushXml.js' type='text/javascript'></script>
<!-- -->

When you paste the above lines, it will include highlighting functionality for C++, Bash, Java, Python, Plain Text, Visual Basic, XML. To add more, you can add more links to the files in this directory http://alexgorbatchev.com/pub/sh/current/scripts/. You should only add the files which has a name in the following format: "shBrush<language_name>.js". Clearly, it will add the functionality for "language_name" language.

Now the core style and theme:

<!-- SyntaxHighlighter core style -->
<link href='http://alexgorbatchev.com/pub/sh/current/styles/shCore.css' rel='stylesheet' type='text/css'/>
<!-- -->

<!-- SyntaxHighlighter theme -->
<link href='http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css' rel='stylesheet' type='text/css'/>
<!-- -->

You can only use one theme at a time, Default theme is added here, its best in my opinion. However, you can check other themes from this directory: http://alexgorbatchev.com/pub/sh/current/styles/. You can change the link of SyntaxHighlighter theme to any of the files having name pattern "shTheme<theme_name>.js" from this directory.

Now add the main script that will invoke SyntaxHighlighter, also, here you can put some initial parameters (see below) as well:

<!-- SyntaxHighlighter main js -->
<script type='text/javascript'>
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/current/scripts/clipboard.swf';
SyntaxHighlighter.config.tagName = 'pre';
SyntaxHighlighter.defaults['wrap-lines'] = false;
SyntaxHighlighter.defaults['ruler'] = true;
SyntaxHighlighter.all()
</script>
<!-- -->

Here you see, some defaults like line wrapping disabled, ruler visible, and also, SyntaxHighlighter is associated with the <pre>...</pre> tag. The clipboardSwf is the background style. And one special parameter for blogger blogs: bloggerMode = true. For the complete configuration list, visit http://alexgorbatchev.com/wiki/SyntaxHighlighter:Configuration.
All done, just save it...

How to write codes in pre-tag? Well, all you need to do is just invoke the classes in pre tag... for example, you might want to add a c++ code, you should do this:

<pre class="brush: cpp">
/*
** write your codes here.
** make sure you convert all < to &lt; and > to &gt;, important!
** do not use tabs, use 4/8 spaces instead, no break tags needed.
*/
</pre>

Clearly, the brush names are those "language_names" that you included above, for example, "shBrushCpp.js" will be invoked with "cpp", "shBrushXml.js" will be invoked with "xml", etc etc... Actually, in general, the class inclusion might look like class="param_list"
For complete usage, demonstration, and information, visit: http://alexgorbatchev.com/wiki/SyntaxHighlighter in the For Users section.

Hope this helps... not a big deal. Happy blogging.

Wednesday, January 6, 2010

Kruskal's Algorithm in C++



Minimum Spanning Tree, Kruskal's Algorithm


Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). This algorithm is based on greedy approach.

Performance


This algorithm needs to sort the edges and uses a disjoint set data structure to keep track which vertex is in which component. We know the best comparison sorting is O(e*lg(e)), i.e. the merge sort or quick sort, where e is the number of edges, and the set operations can be implemented such a way that they are almost constant. The algorithm itself is linear to the number of edges e. So the total complexity can be achieved is O(e*lg(e)). Also note that, e can be max v*v (when it is a complete graph).

Algorithm


Do some study and paper-work before you proceed:
1. the algorithm and analysis
2. another good pseudo-code
3. read in wikipedia
4. text: Introduction to Algorithms (CLRS, MIT press), Chapter 23.

Implementation


Here is a short and in general implementation in C++ using the STL library. This solves for one graph, if you need it for multiple graphs inputs, don't forget to reset the vectors and arrays appropriately.

Input


N, E // number of nodes and edges.
E edges containing u, v, w; where, the edge is (u, v) and edge weight is w.

C++ code



#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define edge pair< int, int >
#define MAX 1001

// ( w (u, v) ) format
vector< pair< int, edge > > GRAPH, MST;
int parent[MAX], total, N, E;

int findset(int x, int *parent)
{
if(x != parent[x])
parent[x] = findset(parent[x], parent);
return parent[x];
}

void kruskal()
{
int i, pu, pv;
sort(GRAPH.begin(), GRAPH.end()); // increasing weight
for(i=total=0; i<E; i++)
{
pu = findset(GRAPH[i].second.first, parent);
pv = findset(GRAPH[i].second.second, parent);
if(pu != pv)
{
MST.push_back(GRAPH[i]); // add to tree
total += GRAPH[i].first; // add edge cost
parent[pu] = parent[pv]; // link
}
}
}

void reset()
{
// reset appropriate variables here
// like MST.clear(), GRAPH.clear(); etc etc.
for(int i=1; i<=N; i++) parent[i] = i;
}

void print()
{
int i, sz;
// this is just style...
sz = MST.size();
for(i=0; i<sz; i++)
{
printf("( %d", MST[i].second.first);
printf(", %d )", MST[i].second.second);
printf(": %d\n", MST[i].first);
}
printf("Minimum cost: %d\n", total);
}

int main()
{
int i, u, v, w;

scanf("%d %d", &N, &E);
reset();
for(i=0; i<E; i++)
{
scanf("%d %d %d", &u, &v, &w);
GRAPH.push_back(pair< int, edge >(w, edge(u, v)));
}
kruskal(); // runs kruskal and construct MST vector
print(); // prints MST edges and weights

return 0;
}

Have fun and please notify for any bug...

Sunday, January 3, 2010

Online Compiler / Interpreter



Visit http://www.ideone.com/
This is a free online compiler introduced and being developed by SPOJ team, a lots of thanks goes to them! and supports almost all available languages on SPOJ system.

So, if you are a C++ programmer, or like to learn some new esoteric or functional programming, or want to use gcc/g++ but don't have linux, or server side programming languages but don't want to setup a new IDE or virtual server, you can use this site... free for all!!!

Have fun...