1. Grafo genérico

Muchas soluciones a problemas pueden modelarse como grafos. Por ejemplo, redes sociales, redes de transporte, redes de comunicación, y circuitos electrónicos, entre otros. Sin embargo, la biblioteca estándar de C++ no incluye un tipo de datos abstracto para grafos. Cree un tipo de datos grafo genérico reutilizable capaz de representar grafos dirigidos o no, y pesados o no. Internamente use listas de adyacencia para representar las aristas del grafo. Ej.:

graph adjlist

Todas las operaciones que realice su grafo deben estar aseguradas con pruebas unitarias de software. Las siguientes son operaciones básicas de un grafo (adaptado de Wikipedia):

Tabla 1. Operaciones de un grafo
Method Description

isEmpty()

Returns true if graph is empty.

isAdjacent(x, y)

Tests whether there is an edge from the vertex x to the vertex y.

getNeighbors(x)

Returns all vertices y such that there is an edge from the vertex x to the vertex y.

addVertex(x)

Adds the vertex x, if it was not there returns true, otherwise returns false.

removeVertex(x)

Removes the vertex x, if it was there returns true, otherwise returns false.

addEdge(x, y, value)

Adds the edge from the vertex x to the vertex y with given value/weight. If graph is undirected, vertex is also available in the inverse direction. Returns true if the edge was not there, otherwise returns false. Launches an exception if a vertex does not exist within the graph or there is no enough memory to create the edge.

removeEdge(x, y)

Removes the edge from the vertex x to the vertex y. Same return value and exception handling than addEdge().

getEdge(x, y)

Returns the value associated with the edge (x, y).

setEdge(x, y, v)

Sets the value associated with the edge (x, y) to v.

operator()(x, y)

Returns the value associated with the edge (x, y) in both, read-only and read-write mode.

En su implementación puede usar los sinónimos node o point en lugar de vertex, y los sinónimos link, line, o arc en lugar de edge. Los grafos deben poder copiarse entre sí aunque sean de diferente naturaleza, y cuidar el buen uso de la memoria pricipal. Los grafos deben poderse imprimir a la salida estándar y exportarse a archivos de imagen.

2. Aplicación en línea de comandos

Implemente una aplicación en línea de comandos que permita crear grafos, agregarles nodos, establecer vértices con sus pesos, y realizar consultas sobre el grafo. Ejemplo de ejecución:

Entrada Salida esperada 
digraph G char ushort
vertex G a b s d
edge G a b 4
edge G a c 9
print G
vertex G c
~vertex G s
edge G a c 9
print G
edge G b c 3
edge G c b 2
edge G c d 6
edge G d d 1
print G
path G a d
path G a d Ga_d.svg
print G G.svg
graph H int
assign G to H
~vertex G c
~edge G c b
print G
erase G c
print G
print H
 
error: invalid vertex c
digraph G {
  a -> b [label="4"];
  b;
  s;
  d;
}
digraph G {
  a -> b [label="4"];
  a -> c [label="9"];
  c;
  d;
}
digraph G {
  a -> b [label="4"];
  a -> c [label="9"];
  b -> c [label="3"];
  c -> b [label="2"];
  c -> d [label="6"];
  d -> d [label="1"];
}
a b c d: 14
digraph G {
  a -> b [label="4"];
  a -> c [label="9"];
  b -> c [label="3"];
  c -> d [label="6"];
  d -> d [label="1"];
}
error: could not remove edge c, it has edges
digraph G {
  a -> b [label="4"];
  d -> d [label="1"];
}
graph H {
  97 -- 98 [label="4"];
  97 -- 99 [label="9"];
  98 -- 99 [label="5"];
  99 -- 100 [label="6"];
  100 -- 100 [label="1"];
}
Tabla 2. Instrucciones en línea de comandos
Instrucción Descripción

graph name vertex_type edge_type

Crea un grafo no dirigido con el nombre name, tipo de datos de los vértices vertex_type y tipo de datos de las aristas edge_type. Los tipos de datos permitidos se indican más adelante. Si edge_type no se provee, el grafo es no pesado. Si ya existe un grafo con el nombre name, produce un mensaje error: already exists graph <name>.

digraph name vertex_type edge_type

Crea un grafo dirigido con el nombre name, tipo de datos de los vértices vertex_type y tipo de datos de las aristas edge_type. Los tipos de datos permitidos se indican más adelante. Si edge_type no se provee, el grafo es no pesado. Si ya existe un grafo con el nombre name, produce un mensaje error: already exists graph <name>.

~graph name

Elimina el grafo con nombre name con todos sus vértices y aristas, indiferentemente si es un grafo dirigido o no. Tras eliminado, el nombre name queda disponible para crear otro grafo con dicho nombre. Si no existe un grafo con ese nombre produce un mensaje error: graph <name> does not exist.

vertex graph list

Agrega la lista de vértices (separados por espacios en blanco) al grafo con nombre graph. Si el grafo ya tiene un vértice con el mismo nombre, se presenta el mensaje error: already exists vertex <vertex>. Si el vértice no es compatible con el tipo de datos se presenta el mensaje error: incompatible vertex type <vertex>. Si el grafo no existe produce el mensaje error: graph <graph> does not exist.

~vertex graph list

Elimina los vértices indicados en la lista (separados por espacios en blanco) del grafo con nombre graph. Si el grafo no existe produce el mensaje error: graph <graph> does not exist. Si un vértice no existe en el grafo, se presenta el mensaje error: vertex <vertex> does not exist. Si el vértice tiene aristas asociadas, se presenta el mensaje error: could not remove vertex <vertex>, it has edges.

erase graph list

Elimina los vértices indicados en la lista (separados por espacios en blanco) del grafo con nombre graph. Si el grafo no existe produce el mensaje error: graph <graph> does not exist. Si un vértice no existe en el grafo, se presenta el mensaje error: vertex <vertex> does not exist. Si un vértice tiene aristas asociadas, se elimina el vértice y todas sus aristas asociadas.

edge graph vertex1 vertex2 [weight]

Agrega una arista desde el vértice vertex1 al vértice vertex2 con el valor weight al grafo con nombre graph. Si el grafo no es pesado, la arista tendrá el valor 1. Si el grafo no existe produce el mensaje error: graph <graph> does not exist. Si alguno de los vértices no existe en el grafo, se presenta el mensaje error: vertex <vertex> does not exist. Si la arista ya existe, se presenta el mensaje error: already exists edge <vertex1> <vertex2>. Si el tipo de datos del peso no es compatible con el esperado por el grafo, se presenta el mensaje error: incompatible edge type. Si se provee un peso pero el grafo no es pesado, se presenta el mensaje error: graph <graph> is not weighted.

~edge graph vertex1 vertex2

Elimina la arista desde el vértice vertex1 al vértice vertex2 del grafo con nombre graph. Si el grafo no existe produce el mensaje error: graph <graph> does not exist. Si alguno de los vértices no existe en el grafo, se presenta el mensaje error: vertex <vertex> does not exist. Si la arista no existe, se presenta el mensaje error: edge <vertex1> <vertex2> does not exist. Si la arista es bidireccional (grafo no dirigido) se elimina la arista inversa también.

print graph [filename]

Imprime el grafo con nombre graph. Si no se provee un nombre de archivo, se imprime el grafo en notación Dot (DOT). Si se provee un nombre de archivo con extensión .svg o .png, se exporta el grafo a una imagen en memoria secundaria en la carpeta donde se invocó su programa acorde al formato indicado por la extensión. Si se provee una extensión distinta se produce el mensaje 'error: invalid image extension'. Si ya existe un archivo con el nombre indicado, se sobrescribe sin aviso. Si no se pudo crear el archivo, se presenta el mensaje error: could not save <filename>. Si el grafo no existe produce el mensaje error: graph <graph> does not exist.

path graph origin destination [filename]

Encuentra el camino más corto desde el vértice origin al vértice destination del grafo con nombre graph. Si el grafo no existe produce el mensaje error: graph <graph> does not exist. Si alguno de los vértices no existe en el grafo, se presenta el mensaje error: vertex <vertex> does not exist. Si no hay camino entre los dos vértices, se presenta el mensaje no path from <origin> to <destination>. Si no se provee un nombre de archivo, se imprimen los vértices que conforman la ruta en la salida estándar, y si el grafo es pesado, la suma de pesos de la ruta. Si se provee un nombre de archivo con extensión .svg o .png, se exporta el grafo a una imagen en memoria secundaria en la carpeta donde se invocó su programa acorde al formato indicado por la extensión resaltando las aristas que conforman camino más corto en rojo. Si se provee una extensión distinta se produce el mensaje 'error: invalid image extension'. Si ya existe un archivo con el nombre indicado, se sobrescribe sin aviso. Si no se pudo crear el archivo, se presenta el mensaje error: could not save <filename>.

assign source to target

Copia el grafo con nombre source al grafo con nombre target. Si el grafo target ya existe, se sobrescribe, descartando sus vértices y aristas previos. Si el grafo source no existe, se presenta el mensaje error: graph <source> does not exist. Si los tipos de datos de los vértices y las aristas son distintos, se hará una conversión de tipos. Por ejemplo, si se asigna un grafo con aristas de punto flotante a un grafo con aristas de punto fijo, perderá los decimales. Si los tipos de los vértices son caracteres y se copia a un grafo con vértices enteros, se convertirán los caracteres a su valor entero ASCII. Si un grafo pesado se copia a uno no pesado, las aristas del destino tendrán un peso de 1. Si un grafo no pesado se copia a uno pesado, las aristas del destino tendrán un peso de 1. Si un grafo dirigido se copia a uno no dirigido y entre dos nodos origen hay dos aristas, la arista destino tendrá la suma de las aristas origen. Si un grafo no dirigido se copia a uno dirigido, cada arista origen generará dos aristas destino entre los mismos nodos, ambas con el mismo peso que la arista origen. La asignación nunca modifica el grafo origen. Si el grafo destino no existe, se crea con los tipos de datos del grafo origen. Si no se pudo crear el grafo destino, se presenta el mensaje error: could not create graph <target>. Después de una asignación, los dos grafos son independientes, por lo que si se modifica uno, no se modifica el otro. Si se asigna un grafo a sí mismo, la acción no tiene efecto en el grafo y no se presenta un mensaje de error.

Tipos de datos permitidos para los vértices y las aristas:

bool
char
uchar
short
ushort
int
uint
long
ulong
longlong
ulonglong
float
double
ldouble

3. Evaluación

En todos los rubros de implementación se evaluará la convención de estilos (cpplint), la documentación de interfaces (Doxygen), la documentación de implementaciones (comentarios dentro de subrutinas), la modularización del código, la reutilización de código, y la eficiencia del código.

  1. [5%] Repositorio de control de versiones. .gitignore. Estructura de directorios de un proyecto (bin/, build/). Facilitar la construcción de la solución (ej.: Makefile).

  2. [5%] Documento de análisis (readme.md o readme.adoc).

  3. [10%] Plantilla para generar clases grafo. Representa vértices con arreglo asociativo. Representa aristas con lista de adyacencia. Los tipos de datos para los vértices y las aristas son arbitrarios y podrían ser distintos. El grafo es dinámico, por lo que se pueden agregar o eliminar nodos y aristas en el tiempo. Se puede crear un grafo con una capacidad inicial de nodos para incrementar la eficiencia. Regla de los cinco.

  4. [25%] Implementa las operaciones básicas de un grafo (véase Tabla 1).

  5. [20%] Aplicación (ejecutable) de pruebas unitarias para el grafo con un framework (GoogleTest). Todas las operaciones de la plantilla grafo deben tener su correspondiente procedimiento de pruebas.

  6. [5%] Crea al menos dos casos de prueba de cada negra manuales por estudiante. Un caso con datos correctos. Otro caso con instrucciones incorrectas. Usa notación sugerida para compartir casos de prueba con el grupo.

  7. [20%] Implementa el intérprete de instrucciones de la Tabla 2. Usa la plantilla de grafo.

  8. [10%] Usa biblioteca de terceros para generar/exportar gráficos de los grafos (ej.: Graphviz).