Floyd-Warshall Algorithm

This is another shortest path algorithm and this will work with negative routes too (But NOT negative cycles). But this will take more time than the Dijkstra's shortest path algorithm. See the wikipedia articles for more information.



To get the shortest path from node 1 to node 3 you'd have to find what route is shorter ( 1 to 3 straight or 1 to 2 to 3). Like that you'd have to calculate the graph using 3 loops.

Now here's the C++ code for this program

#include <iostream>

using namespace std;

int N, E;
int graph[100][100];
int start, end;


int main(){
       cin >> N >> E;
       for(int i = 0; i < N; i++){
               for(int j = 0; j < N; j++){
                       graph[i][j] = 9999; // Equal to NO path
                       if(i == j) graph[i][j] == 0; // No distance from a node to that same node
               }
       }

       for(int i = 0; i < E; i++){
               int x, y, d;
               cin >> x >> y >> d;
               graph[x-1][y-1] = graph[y-1][x-1] = d;
       }
       for(int k = 0; k < N; k++){
               for(int i = 0; i < N; i++){
                       for(int j = 0; j < N; j++){
                               graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
                       }
               }
       }
       while(true){ // Prints out the shortest distances between nodes until the program is terminated
               cin >> start >> end;
               cout << graph[start-1][end-1] << endl;
       }
       return 0;
}

Read More...

Summary only...

If you have any ideas or comments please tell me.

Bad Vista To Your Desktop

There are some cool Bad Vista Wallpapers made by Joao Ribeiro da Silva.

You can get them from

• 1600x1200
• 1280x1024
• 1024x768
• Wide

Blogging Code

If you are like me and post your code on your blog youmust have noticed that the things you insert within '<' and '>' gets lost. if you want to get it the '<' and '>' correctly you'd have to use 'ANDlt;' and 'ANDgt;' , replacing your code with these things can be messy, so I created a program to convert the code into a html friendly one.

First compile the corrector.cpp file using g++ : g++ corrector.cpp -o corrector
Then run the program: ./corrector -filename -spaces

The -filename is the name of the file you want to make html friendly :P
and -spaces is either '1' to change the white spaces ' ' into ' ' or 0r '0' to just leave it.

The output file is out.cpp

Here's my code for corrector before conversion

#include 
#include 
#include 
#include 

using namespace std;

string line;
list corrected;
bool spaces;
string outfile;
string infile;

ofstream fout ("out.cpp");


int main(){
  cin >> infile >> spaces;
  char path[infile.size()];
  for(int i= 0; i < i =" 0;">'){
                          corrected.push_back(">");         
               }
               if(spaces){
                    if(line[i] == ' '){
                          corrected.push_back(" ");
                    }
               }
               if(line[i] != '<' &&amp; line[i] != '>' && ( !spaces || line[i] != ' ')){
                    string dumb = " ";
                    dumb[0] = line[i];
                    corrected.push_back(dumb);   
               }
             
       }         
       while(!corrected.empty()){
               fout <<>

Read More...

Summary only...

And after the conversion

#include <fstream>
#include <iostream>
#include <string>
#include <list>

using namespace std;

string line;
list<string> corrected;
bool spaces;
string outfile;
string infile;

ofstream fout ("out.cpp");


int main(){
   cin >> infile >> spaces;
   char path[infile.size()];
   for(int i= 0; i < infile.size(); i++){
           path[i] = infile[i];      
   }
     path[infile.size()] = '\0';
     ifstream fin (path);
     while(!fin.eof()){
        for(int i = 0; i < line.size(); i++){
                if(line[i] == '<'){
                           corrected.push_back("<");         
                }      
                if(line[i] == '>'){
                           corrected.push_back(">");         
                }
                if(spaces){
                     if(line[i] == ' '){
                           corrected.push_back(" ");
                     }
                }
                if(line[i] != '<' && line[i] != '>' && ( !spaces || line[i] != ' ')){
                     string dumb = " ";
                     dumb[0] = line[i];
                     corrected.push_back(dumb);   
                }
              
        }         
        while(!corrected.empty()){
                fout << corrected.front();
                corrected.pop_front();                      
        }
        fout << endl;
        getline(fin, line);
   }
   fout.close();
}

Read More...

Summary only...

If you are interested here's the out.cpp file for my above program. If anyone of you have any ideas please let me know :)

Eulerian Path

I haven't been able to update my blog for a long time because I have been very busy in the last few days, so now here's an update.

I'm going to jump to Eulerian Path in this post. My Program uses a recursive function to get the Eulerian Path for a given graph. For those who don't know what Eulerian Path is

"Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex"

If there is to be an Eulerian path for a given graph the graph must have lesser than three nodes with odd number of edges. If there are two nodes with odd number of edges the Euler walk must begin in an odd node and end with the other odd node.

This graph can't have an Eulerian Path.



But this graph can have an Eulerian Path.



You can download the eulerwalk.cpp file by clicking on the link.

#include <iostream>
#include <list>

using namespace std;

int graph[100][100];
int n, x, y, steps;
list<int> path;

void walk(int pos){
for(int i = 0; i < n; i++){
    if(graph[pos][i] > 0){
             graph[pos][i] --;
             graph[i][pos] --;
             walk(i);
             break;
    }
}
path.push_back(pos+1);

}

int main(){

cin >> n;
for(int i = 0; i < n; i++){
  cin >> x >> y;
  graph[x-1][y-1] ++; //we are using zero index 
}
walk(0);
while(!path.empty()){
    cout << path.back() << ' ';
    path.pop_back();
}
}

Read More...

Summary only...

Beryl

Finally I installed Beryl on my debian testing box. It was a bit hard to get AIGLX configured at first because of my ATi card. But still I managed to get Beryl working without using the proprietary ATi driver, I'm using the open source "radeon" driver.

Even with only a 256MB of RAM Beryl is working very smoothly on my machine now :) I also created a theme to make my computer look like matrix"ish". I'll post about the theme and how I got Beryl working with my ATi card in the near future.

Now for some screen shots.









If you can't see the pictures correctly try increasing the brightness of your monitor. And click on an image to get a closer look