Como crear un SVN Externals y no morir en el intento

Hoy se me planteó la necesidad de generar un externals en un repositotio svn de un proyecto complejo, la documentación que encontré fue bastante buena, pero siempre quedan esos "detalles" que nos pueden hacer perder un poco de tiempo

Para empezar, hacemos referencia a que el soft del svn que usamos es el tortoise y tomamos el link de la help para este caso.

Bien, según la ayuda, nos dice que la forma de agregar un externals es la siguiente:

Vamos a la carpeta contenedora de las carpetas que queremos tener como externals

• Clic derecho sobre ésta, TortoiseSVN->properties
  
  
• Clic en new(o add, depende de la versión del svn)
  
  
• De la lista seleccionamos "svn:externals".
  
  Dentro del cuadro de texto, vamos a colocar una o mas instrucciones, cada una representa un external distinto.

• El comando a introducir en el cuadro de texto tiene el siguiente formato:
  carpeta_destino http://ruta_al_repo/carpeta_origen/
  
  Observaciones:
  
  1. Todo el contenido dentro de "carpeta_origen" se copiará dentro de la "carpeta_destino" (que a su vez se creará dentro de la capeta donde definimos el external).
     carpeta_destino es un "alias" a la carpeta apuntada por el external, por lo tanto no debe existir en el repo de destino, si existe, habría un conflicto con entre las dos rutas que deberá leer al momento de hacer el update.
     
  2. La ruta debe terminar con la "/"
  3. Debe haber un espacio entre carpeta_destino y su url en el repo
     
     
• Una vez completada la lista de externals, damos clic en OK y veremos que nos queda solo una línea donde en la columna "Property" aparece el comando "svn:externals" y en "value" aparecen todos los externals definidos separados por un espacio.
  
• Paso siguiente importantísimo, debemos hacer un commit del external para que el svn se de cuenta de ello, y luego, recién allí estamos habilitados para hacer un update del repo para poder ver como (satisfactoriamente) se crean las carpetas (alias) con el contenido de los externals.

Con eso veremos satisfactoriamente como se puede generar un externals sin arrancarse los pelos :D

DFS - Depth First Search

Es muy parecido al BFS, pero más simple..

En este caso vamos a caminar hasta el último de los adyacentes de la rama más a la izquierda, para ir subieno y visitando sus ramas derechas.

Pseudo-código

  DFS(int inicio, Grafo g, int*& visitados){ 

	visitados[inicio] = 1;

	listaAdyacentes = obtenerListaAdyacentes(g, inicio);

	while(!esVacia(listaAdyacentes){

		w = listaPrimero(listaAdyacentes);

		listaAdyacentes = listaResto(listaAdyacentes);

		if(!visitados[w]){

			!visitados[w] = 1;

			DFS(w, g);

		}

	}

}

  void Recorrido_DFS(Grafo g){ 

	int n = cantidadNodos(g);

	for(i=0; i		visitados[i] = 0;

	}

	for(i=0; i		if(!visitados[i])

			DFS(i, g, visitados);

		{

	}

}

BFS - Breadth First Search

Es un algoritmo para recorrer elementos en un grafo, intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo.
A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.

Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución.
El algoritmo no usa ninguna estrategia heurística.


En español:

Dado un vértice de inicio, tomo la lista de sus adyacentes y los recorro, antes de entrar en profundidad de los adyacentes de éstos.

Finalizado el nivel, entro a recorrer mis nuevos adyacentes no visitados aún (que son adyacentes de uno de los adyacentes del nodo inicial).

Pseudo-código:

  BFS(grafo G, nodo_fuente s)
{
   // recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
   // distancia INFINITA y padre de cada nodo NULL
   for u ∈ V[G] do
   {
      estado[u] = NO_VISITADO;
      distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
      padre[u] = NULL;
   }
   estado[s] = VISITADO;
   distancia[s] = 0;
   Encolar(Q, s);
   while !vacia(Q) do
   {
      // extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
      u = extraer(Q);
      for  v ∈ adyacencia[u]  do
      {
         if estado[v] == NO_VISITADO then
         {
              estado[v] = VISITADO;
              distancia[v] = distancia[u] + 1;
              padre[v] = u;
              Encolar(Q, v);
         }
      }
   }
}

El tiempo de ejecución es O(|V|+|E|). Nótese que cada nodo es puesto a la cola una vez y su lista de adyacencia es recorrida una vez también.

Fuente: wikipedia

Algoritmo de Prim

El algoritmo de Prim

Es un algoritmo de la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.


Pseudo-código

PRIM (Grafo G, nodo_fuente s)
     // inicializamos todos los nodos del grafo. La distancia la ponemos a infinito
     // y el padre de cada nodo a NULL
      for each u ∈ V[G] do
          distancia[u] = INFINITO
          padre[u] = NULL
      distancia[s]=0
      //encolamos todos los nodos del grafo
      Encolar(cola, V[G])
      while cola != 0 do
          // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición 
          // de Cola de prioridad
          u = extraer_minimo(cola)
          for v ∈ adyacencia[u] do
              if ((v ∈ cola) && (distancia[v] > peso(u, v)) do
                  padre[v] = u
                  distancia[v] = peso(u, v)

En español:

• Como debemos tener un vértice de partida, tomamos este vértice y armamos una lista con las aristas de sus adyacentes.
  Esa lista la confeccionamos en orden descendiente según su costo.
• Tomamos la arista de menor costo (siempre y cuando, al agregar esta arista, no generemos un ciclo) y la agregamos a nuestro árbol.
• Para el siguiente paso, vamos a tener que utilizar el vértice que acabamos de colocar, agregamos las aristas adyacentes de éste de la misma manera que lo hicimos anteriormente.
• Y así sucesivamente hasta tener todos los vértices del grafo, dentro del A.C.C.M.

fuente: wikipedia (pseudo-código) y apuntes mios

Algoritmo de Kruskal

Kruskal

El algoritmo de Kruskal es un algoritmo (ávido) de la teoría de grafos para encontrar un árbol de recubriumiento mínimo en un grafo conexo y ponderado.
Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo

En este caso me limitaré al caso de grafos conexos con costos no negativos en sus aristas

Funcionamiento:

Se parte colocando todos los vértices del grafo separados, y se decide partir por un vértice de "Inicio".

Dado el vértice actual (en el comienzo es el de inicio), armamos una lista de todas las aristas que posee, ordenadas en forma decreciente según su ponderación (costo de la arista).

Tomamos la de menor coste, retiramos de la lista de candidatos a la arista utilizada y agregamos las nuevas aristas que nos proporciona el nuevo vértice.

Así sucesivamente, generando subgrafos conexos hasta llegar a conectar todos los subgrafos conexos formando un Árbol de cubrimiento de costo mínimo.

Un excelente ejemplo se encuentra en el artículo dedicado a este algoritmo en wikipedia

Algoritmo de Dijkstra

Dijkstra en un algoritmo voraz que sirve para hallar la menor distancia entre dos nodos en un grafo conexo, acíclico, dirijido y con costos no negativos en sus aristas.

De esto hay mucho en wikipedia, por lo que solo me voy a limitar a dar algunas consideraciones que, en el estudio de este algoritmo fueron apareciendo a mi vista :D

El algoritmo sirve para hallar el mínimo camino entre un par de nodos o bien si es aplicado a cada par de nodos, obtendremos el mínimo camino entre todo par de nodos.

El algoritmo no necesita ser recursivo, basta usar 3 for anidados (para el caso anterior).

El orden del algoritmo para encontrar el mínimo camino entre un par de nodos es O(n^2) y para encontrar el mínimo entre todo par de nodos (usando Programación dinámica) es el mismo, notar que no depende del tipo de implementación que se use (cola de prioridad ó vector de visitados)


Inicialmente S contiene únicamente el nodo origen y al final contendráá todos los nodos de G.
En cada paso se selecciona aquél nodo de C cuya distancia al origen sea mínima y lo añadimos a S.
Cuando se detiene el algoritmo todos los nodos del grafo pertenecen a S

Pseudo-código

void dijkstra(int fuente, Grafo g, matriz costoAristas){
S = {fuente}
n = cantidadVertices(g)
for(i=0; i //vector de costos
costos[i] = costoAristas[fuente, i] //inicializo el costo desde la fuente hasta los otros vértices ( infinito en el caso que no exista relación)
//vector de camino final (si acaso necesitamos recontruir el camino más corto)
caminoRecorrido[i] = fuente
visitados[i] = 0; //inicializo un vector de nodos visitados
}
visitados[fuente] = 1;//marco a la fuente como visitada

for(i=0; i if(i != fuente){
w = obtenerMinimoVerticeDisponible(g) //esto es : el minimo del conjunto (V - S)
S = S U {w} //agrego el vértice utilizado
visitados[w] = 1 //lo marco como visitado
for(j=0; j if(visitados[j] != 1){
//que es menos costoso, ir directamente -> costos [j] o ir mediante un w intermedio?
if(costos[w] + costoAristas[w, j] < costos[j]){
//es menos costoso ir mediante w
costos[j] = costos[w] + costoAristas[w, j];
caminoRecorrido[j] = w //agrego el nodo utilizado
}
}
}
}
}
}