Todo Soluciones

Dibujar grafos o estructuras de datos

13 Jul 2009 Noticias

Los grafos son una forma de representación de un conjunto de nodos (o vértices) unidos entre sí por unas líneas denominadas arcos (o aristas).

Estas representaciones, pertenecientes a la teoría de grafos, son un método muy utilizado por los ingenieros para resolver varios tipos de problemas, como los de redes de flujo.

Los que necesitemos realizar códigos en C++, Java, Perl (u otros lenguajes de programación) con grafos, podemos utilizar de forma sencilla una representación de código eficiente para tratar la información.

Sin embargo, un método para representación gráfica sería lo ideal, y esto en algunos casos ya no es tan trivial. Para ello podemos utilizar Graphviz, un software de representación de grafos, independiente del lenguaje de programación.

Veamos un ejemplo de como utilizarlo. Ante todo, necesitaremos tener el graphviz en nuestro sistema:

apt-get install graphvizCreamos un fichero llamado grafo1.dot, donde daremos atributos a sus nodos, aristas y demás:

digraph A {
1 -> 2 [label="5/8/6"];
1 -> 3 [label="3/9/4"];
2 -> 4 [label="6/6/6"];
2 -> 3 [label="0/3/4"];
3 -> 5 [label="2/4/5"];
3 -> 4 [label="1/8/4"];
4 -> 5 [label="1/4/9", style=dashed];
1 [style=bold];
5 [style=bold];
}Una vez guardado, utilizaremos la herramienta dot para convertir este fichero en una imagen .png de nuestro grafo:

dot grafo1.dot -o grafo1.png -Tpng -Grankdir=LRLo que nos generaría un fichero grafo1.png con esta apariencia:

Un sencillo grafo de 5 nodos, con sus respectivos arcos e información asociada (por ejemplo, flujo actual, coste por unidad y flujo máximo).

Esto sería muy sencillo de implementar en (por ejemplo, un código de C++), donde generaríamos el fichero .dot y con una llamada al sistema mostrarlo gráficamente:

ofstream fout("grafo.dot");
fout << "digraph G {" << endl;
for (int i = 0; i < Arco.size(); i++) {
fout << "\t" << Arco[i].getNodoOrigen() << " -> ";
fout << Arco[i].getNodoDestino() << " [label=\"";
fout << Arco[i].getFlujoAct() << "/";
fout << Arco[i].getCoste() << "/";
fout << Arco[i].getFlujoMax() << "\"];" << endl;
}
fout << "}" << endl;
fout.close();

system(”python xdot.py grafo.dot”); Guardando mediante flujos en un fichero de salida la información contenida en un vector de la STL que contenga una clase Arco con toda su información.

Al final, hago una llamada al sistema, a un script Python llamado xdot, de J.R. Fonseca, bastante simple y efectivo para lo que nos interesa. Aunque siempre podemos convertirlo a .png con el dot y luego visualizarlo con un programa como por ejemplo mirage.

Pero la potencia del dot no se queda aquí, sino que podemos representar multitud de detalles más (lineas punteadas, colores, negrita…) e incluso utilizar otras estructuras como árboles:

O muchas otras diferentes: hashes (en la imagen), registros, diagramas de flujo, modelos de entidad/relación, listas enlazadas y una larga lista de estructuras de datos.

Más abajo adjunto una detallada guía con los parámetros del dot con varios ejemplos y definiciones sobre su funcionamiento.

URL: Graphviz | PDF: Referencia del dot ~300Kb
Fuente: Emezeta