Implementación de grafo

Diego
11 de Abril del 2006
Hace un tiempo, tuve que entregar unas prácticas en las que había que definir un grafo, implementado tanto con una matriz de adyacencias (una matriz de doubles) como con una lista de adyacencias(un array de listas de doubles). Como la programación orientada a objetos está para aplicarla, definí la clase abstracta Grafo, que implementaba casi toda la funcionalidad, que llamaba a los métodos abstractos:
void setCoste(nodoOrigen,nodoDestino,Coste)
double getCoste(nodoOrigen,nodoDestino)
void construye(nroNodos,simetrico)
Grafo clone() // Este último no es estrictamenten necesario
Estos métodos permiten abstraer la estructura de datos subyacente a la subclase de grafo que los implementa, y definir sus métodos crearEnlace, borrarEnlace, hayEnlace,etc. en base a estos.
De este modo mientras GrafoMatriz definía únicamente los métodos abstractos, GrafoLista sobreescribía algunos más, para mejorar la eficiencia, dado que el acceder secuencialmente a cada uno de los elementos de una lista es mucho más eficiente hacerlo de una vez, que recorrerla para cada elemento en la posición x, x veces. El problema en cuestión, es que para hacer que el grafo sea simétrico se puede resolver de dos maneras, que se almacene información redundante, o que se almacena la mitad de la información y que si nodoOrigen<nodoDestino, se inviertan los roles. El problema radica en que tanto una como otra solución me obligaron a comprobar la propiedad simetrico en cada uno de los métodos, ya que podría haber definido una subclase GrafoSimetrico que herede de Grafo, pero entonces también habría que hacer dos GrafoMatriz y GrafoLista que hereden tanto de Grafo como de GrafoDirigido, creando un número, a mi parecer excesivo de clases, aunque dentro de cada uno de ellas el código sería más claro. En este caso y en general ¿qué preferis vosotros?¿más clases más simples o menos clases más complejas?
Gracias por opinar.