Credit image

¿Te gusta el diseño web? ¡Echa un vistazo a la documentación de LenguajeCSS.com!

Dibujar grafos o estructuras de datos

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.

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

Escrito por Manz, el , en programacion. Comentarios recibidos: 12.

12 comentarios de lectores
Xelso
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
sgm
sgm
2

¡Una herramienta potentísima!, y muy útil para ingeniería. Me vendrá genial para la universidad. Buen post!

  • 2
JM
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
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.

Angelverde
Angelverde
5

El programa que mencionas será de mucha ayuda para la materia de Discretas

Manz
Manz
6

Grafos es un software parecido con licencia Creative Commons, que también puede interesar. Lo encuentro gracias a Diamond, un lector de Emezeta.

Fla-x
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!

Jorge
Jorge
8

Y en leunguaje C, existe alguna forma de hacer un procedimiento de este tipo? ? ?

Patrik
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....

José
José
10

Muchas gracias por tu explicación José Román, muy claro, genial !!! Gracias también a J.R. Fonseca que escribio ese script, que capo !!!

jeiss
jeiss
11

interesante!! ya entiendo mejor el tema..

  • 1
MD
MD
12

Uff Graphviz en cuanto le pides cosas gordas, se afogona: por ejemplo el grafo" rel="nofollow">http://'>grafo de la relación de engines del Quake en la wikipedia El problema es que no hay otra alternativa libre interesante.

Publica tu opinión

Si lo deseas, puedes utilizar el siguiente formulario para publicar tu opinión o responder a alguna de las existentes:

Previsualización

Aquí se previsualizará su comentario. Revise que sea correcto antes de publicarlo.