Algorithms on Graphs

Depth-First-Search (DFS)

The first kind of visit in a graph is the DFS and its output is:

  • Generate a spanning forest;
  • Visit every edge and every vertex;
  • Determine if the graph is connected;
  • Calculate the connected components of the graph.

First Part – First Labeling

The first labeling part will initialize the graph. In a non-directed graph we have these statuses:

  • Vertices can be:
    • UNEXPLORED
    • VISITED
  • Edges can be:
    • UNEXPLORED
    • DISCOVERY
    • BACK

Second Part – True Labeling

In the second part we choose visited and discovery edges.

Direct Depth First Search (D-DFS)

In a direct graph

  • Vertices has two fields:
    • int discovery_label – a progessive number 0, 1, 2 … n (if zero vertex is UNEXPLORED)
    • int leaving_label – a progressive number 0, 1, 2, … n
  • Edges can be:
    • UNEXPLORED
    • DISCOVERY/TREE
    • BACK
    • FORWARD
    • CROSS

We also define two methods:

  • getNextLLabel – which generate the next leaving_label progessive number;
  • getNextDLabel -which generate the next discovery_label progessive number.

Strong connected di-graphs

A di-graph is connected if for every pair of vertices A and B we have an oriented path from A to B and from B to A.

Connection test algorithm

We can use the just explained D-DFS in order to understand if a graph is connected, we have to follow these steps:

  1. D-DFS on a graph G. After that we have every vertex and every label assigned, starting from whatever vertex;
  2. Check for UNEXPLORED vertex. If there’s even only one vertex labeled UNEXPLORED the graph isn’t connected;
  3. Transpose the graph to G’. Let’s invert every edge orientation to get a transposed graph;
  4. D-DFS on G’. Another labeling but now on the transposed graph;
  5. Check for UNEXPLORED vertices. As before, if we have no UNEXPLORED vertices the graph G’ is connected and at this point even G is connected.

Calculate the connected components algorithm

Suppose we have a not connected graph. If we try to execute the previous algorithm at the step 5. or 2. it ends telling us that the graph is not connected but.. we have a connected component ready! So could try another D-DFS but starting from an unexeplored vertex but how can we choose it?

We have to note somewhere (an array) the leaving order of the vertex because we will start from the last leaved vertext but unexplored!

Breadth-First-Search (BFS)

Let’s see the breadth-first-search that it’s useful if we have to calculate shortest paths or if we want to visit every discendet of a vertices before go on in the search.

Dijkstra’s shortest path algorithm

Let’s view now a simple example of a Dijkstra’s algorithm for finding the shortest path from a vertex.

Redirect 301 to change domain name

When you’ve finished  the domain trasfer of out web site as explained in the previous guide , you have to inform all the search engines of the change you made, and to create an automatic redirect from the old site to the new one. The aim that you certainly have is not to lose the Search Engine Optimization (SEO) you had obtained with the previous domain. The way that leads you to success is very easy: you have to create a redirect 301, a permanently moved that redirect the visitors who click on old links, but at the same time it inform the visitor of our site permanent tranfer. Afterwards with Filezilla (that was a matter of the previous guide), you have to visit the old site , search in the site root the file .htaccess and modify it clicking on “View/ Modify“.
The notepad will be launched, now all you have to do is copy and paste the code I have written below, being careful while replacing  “iltuodominio.it”  with your own domain:

[code language=”text”]
Options +FollowSymLinks
RewriteEngine on
RewriteRule (.*) http://www.iltuodominio.it/$1 [R=301,L]
[/code]

Then you can close the notepad and save the changes. To check if your redirect works and gives back the code “301”, you can click here and write your old link. If you made no mistakes, this will be the result:

urltest-1-tuttodinternet

A screenshot from the free url-test program , made by tuttodinternet

Note:
If in the new link you want to remove, for example, “/blog/” , to have a redirect from:

www.iltuodominio.it/blog/post342 –> www.ilnuovodominio.it/post342

so you have to write:

 

[code language=”text”]
Options +FollowSymLinks
RewriteEngine on
RewriteRule ^blog/(.*) http://www.iltuodominio.it/$1 [R=301,L]
[/code]

If, instead, you would like to add “/blog/” to the new domain, you have to write:

[code language=”text”]
Options +FollowSymLinks
RewriteEngine on
RewriteRule (.*) http://www.iltuodominio.it/blog/$1 [R=301,L]
[/code]

 Translated by senzacca