Los grafos dirigidos en Erlang se implementan como dos módulos, digraph y digraph_utils. El módulo digraph básicamente permite la construcción y modificación de un grafo dirigido: manipular aristas y vértices, encontrar caminos y ciclos, etc. Por otro lado, digraph_utils permite navegar por un grafo (postorder, preorder), probar ciclos, arborescencias o árboles, encontrar vecinos, etc.
En Erlang, los grafos dirigidos se implementan utilizando los módulos digraph y digraph_utils, que forman parte de la librería estándar. Aquí tienes ejemplos de cómo usarlos:
El módulo digraph permite crear y manipular grafos. Veamos un ejemplo básico:
-module(digraph_example).
-export([create_graph/0, add_nodes_and_edges/1, print_graph/1]).
create_graph() ->
digraph:new().
add_nodes_and_edges(Graph) ->
% Agregar nodos
Node1 = digraph:add_vertex(Graph, node1, "Nodo 1"),
Node2 = digraph:add_vertex(Graph, node2, "Nodo 2"),
Node3 = digraph:add_vertex(Graph, node3, "Nodo 3"),
% Agregar aristas dirigidas
digraph:add_edge(Graph, Node1, Node2),
digraph:add_edge(Graph, Node2, Node3),
digraph:add_edge(Graph, Node1, Node3),
Graph.
print_graph(Graph) ->
Vertices = digraph:vertices(Graph),
Edges = digraph:edges(Graph),
io:format("Nodos: ~p~n", [Vertices]),
io:format("Aristas: ~p~n", [Edges]).
Veamos como podemos usarlo:
1> c(digraph_example).
2> Graph = digraph_example:create_graph().
3> Graph = digraph_example:add_nodes_and_edges(Graph).
4> digraph_example:print_graph(Graph).
Nodos: [#Ref<0.0.0.247>,#Ref<0.0.0.248>,#Ref<0.0.0.249>]
Aristas: [#Ref<0.0.0.250>,#Ref<0.0.0.251>,#Ref<0.0.0.252>]
El módulo digraph_utils provee funciones para analizar y transformar grafos, como encontrar caminos, ciclos, o calcular componentes conexas.
find_path_example() ->
Graph = digraph:new(),
Node1 = digraph:add_vertex(Graph, node1),
Node2 = digraph:add_vertex(Graph, node2),
Node3 = digraph:add_vertex(Graph, node3),
digraph:add_edge(Graph, Node1, Node2),
digraph:add_edge(Graph, Node2, Node3),
Path = digraph_utils:path(Graph, Node1, Node3),
io:format("Camino de Node1 a Node3: ~p~n", [Path]),
digraph:delete(Graph).
1> c(digraph_example).
2> digraph_example:find_path_example().
Camino de Node1 a Node3: [node1,node2,node3]
Para detectar ciclos en un grafo dirigido:
detect_cycle_example() ->
Graph = digraph:new(),
Node1 = digraph:add_vertex(Graph, node1),
Node2 = digraph:add_vertex(Graph, node2),
digraph:add_edge(Graph, Node1, Node2),
digraph:add_edge(Graph, Node2, Node1),
Cycles = digraph_utils:strong_components(Graph),
io:format("Ciclos detectados: ~p~n", [Cycles]),
digraph:delete(Graph).
1> digraph_example:detect_cycle_example().
Ciclos detectados: [[node1,node2]]
digraph es eficiente para representar grafos con un gran número de nodos y aristas.
digraph_utils complementa digraph con funciones analíticas, como encontrar componentes fuertes o caminos mínimos.
Debido a que los grafos dirigidos están estrechamente relacionados con la teoría de conjuntos, el módulo sofs contiene algunas funciones que permiten convertir familias en dígrafos y dígrafos en familias.
