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). Con Graphviz podremos representarlos gráficamente.

desarrollo
12

Escrito por

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 graphviz

Creamos 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=LR

Lo 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

RELACIONADOS La historia de la Abadía del crimen RELACIONADOS Pasar a PDF RELACIONADOS Javascript Cheatsheet (Chuleta JS)
Manz

12 comentarios

Xelso
1

Grafos... que estarías haciendo, para publicar sobre ellos. jejeje. Los grafos una vez que los has aprobado son divertidos e interesantes...

  • 2
JM
3

Un post muy interesante ... ¡como siempre! Me pregunto si los ingenieros usáis el sistema LaTeX y, en tal caso, si conoces el paquete Tikz. Este paquete permite, entre otras muchas cosas, representar grafos de una manera sencilla.

  • 1
welnder
4

Que tal a todos, este si que es un buen post!!, ya que justo estaba realizando un trabajo sobre el tema, la verdad d todo es que necesito mucha ayuda, par los algoritmos, referente a los vectore y matrices, ojala alguno pueda ayudarme superarme mas ya que lo necesito, adema por el trabjo que tengo y la universidad significa un gran sacrificio.

Fla-x
7

¡Muchas gracias! ¡Es increiblemente bueno este post! Estaba buscando algo que me ayudara a mostrar el flujo de trabajo de un sistema Workflow en web que estoy programando. He estado pensando qué hacer para mejorar la parte visual desde hace mes y medio! Lo probé y funciona a la perfección. Hoy encontré la solución. ¡Pura vida desde Costa Rica!

Patrik
9

Q tal.... muy buena informacion, pero como puedo agregar varios atributos distintos en un nodo del grafo, mi grafo es de una lista doble circular enlazada, pero solo he podido ingresar un dato en cada nodo....si pudieras ayudarme...te lo agradeceria....!! Saludos....

Publica tu opinión