libgraph

libgraph is an Elixir library providing high-performance graph data structures and utilities. Its core components include:

• Graph: A data structure implementation designed for both directed and undirected graphs. It uses an idiomatic Elixir API that allows for pipeline-based creation and modification, and all queries take a Graph as the first parameter.
• PriorityQueue: A high-performance priority queue optimized for graph algorithms. It prioritizes lower integer values over higher ones (e.g., for Dijkstra's algorithm).
• Reducers: Two implementations for mapping or reducing over a graph structure.
• Serializer behaviour: An interface for defining custom graph serialization. A Graphviz DOT format serializer is included by default.

The PriorityQueue module provides a priority queue implementation specifically oriented towards graph algorithms.

Unlike standard priority queues, this implementation considers lower integer values to have higher priority. This behavior is ideal for common graph algorithms like Dijkstra's, where the goal is to explore nodes with the smallest cumulative weight first. It is designed to be highly performant and supports arbitrary priorities.

The library provides a Serializer behaviour that allows you to define how a graph should be converted into different formats.

Out of the box, libgraph includes a serializer for the Graphviz DOT format, which can be used to visualize your graph structures.

To use libgraph in your Elixir project, add it to your deps list in mix.exs.

Note: The version in the example below is ~> 0.16.0. Ensure you check Hex.pm for the latest version.

def deps do
  [{:libgraph, "~> 0.16.0"}]
end

Use Graph.Pathfinding.bellman_ford/2 to find the shortest distances from a starting vertex to all other vertices in the graph. This algorithm is useful for graphs that may contain negative edge weights.

It returns a map where keys are vertices and values are the shortest distance (as an integer) or :infinity if the vertex is unreachable.

# Returns %{vertex => distance | :infinity}
Graph.Pathfinding.bellman_ford(graph, start_vertex)

Performs a breadth-first traversal of the graph and applies a mapping function to each new vertex encountered.

Note: The algorithm follows lower-weighted edges first.

Returns a list of values returned from the mapper in the order the vertices were encountered.

# Example usage:
g = Graph.new |> Graph.add_vertices([1, 2, 3, 4])
g = Graph.add_edges(g, [{1, 3}, {1, 4}, {3, 2}, {2, 3}])
Graph.Reducers.Bfs.map(g, fn v -> v end)
# => [1, 3, 4, 2]

Use Graph.Serializers.Edgelist.serialize/1 to convert a Graph struct into a string representation of an edgelist. This format is designed for compatibility with external graph libraries, such as the polyglot igraph library.

The resulting string contains one line per edge, where each line consists of two space-separated vertex labels (e.g., "label1 label2").

# Assuming 'g' is a valid Graph struct
{:ok, edgelist_string} = Graph.Serializers.Edgelist.serialize(g)

Use Graph.Edge.new/2 or Graph.Edge.new/3 to define a new edge between two vertices.

By default, an edge has a weight of 1 and a nil label. You can provide optional metadata using a keyword list containing :weight and :label.

Constraints:

• The :weight must be an integer or a float. Providing a non-numeric value (like a string) will raise an ArgumentError.

# Basic edge with default weight 1
edge = Graph.Edge.new(:a, :b)

# Edge with custom weight and label
edge = Graph.Edge.new(:a, :b, weight: 5.5, label: "connection")

Use Graph.Pathfinding.a_star/4 to find the shortest path between a and b using a heuristic function. The heuristic function hfun allows you to provide a lower bound cost for a given vertex, which can significantly optimize the search compared to Dijkstra's algorithm.

The hfun must be a function with the signature (Graph.vertex() -> integer).

# hfun returns a lower bound cost for a vertex
heuristic = fn vertex -> vertex.x + vertex.y end

# Returns [vertex_a, ..., vertex_b] or nil
Graph.Pathfinding.a_star(graph, start_vertex, end_vertex, heuristic)

The Graph.Serializers.DOT module converts a Graph struct into a DOT format string. This string can be used with Graphviz tools (e.g., dot -Tpng out.dot > out.png) to visualize the graph.

Key behaviors:

• Graph Types: If the graph type is :directed, it produces a digraph. Otherwise, it produces a graph.
• Strictness: The output uses the strict keyword.
• Node Labels: Vertex labels are included using the label= attribute.
• Edge Attributes: Edges include weight and, if present, a label attribute.
• Return Value: Returns {:ok, dot_string} on success.

# Assuming a Graph struct is already constructed
{:ok, dot_string} = Graph.Serializers.DOT.serialize(my_graph)

The Graph.Serializers.Flowchart module converts a %Graph{} struct into a string formatted for Mermaid Flowchart syntax.

It supports:

• Directed Graphs: Uses -> arrows.
• Undirected Graphs: Uses - lines.
• Edge Weights: The weight determines the number of dashes used in the connection (e.g., a weight of 3 results in --- ->).
• Edge Labels: Labels are enclosed in pipes (e.g., |label|).
• Vertex Labels: Vertices are rendered with square brackets [label].

Graph.Serializers.Flowchart.serialize(graph_struct)
# Returns {:ok, mermaid_string}

Use Graph.Pathfinding.dijkstra/3 to find the shortest path between two vertices a and b in a graph. It returns the path as a list of vertices or nil if no path exists. Dijkstra's algorithm is implemented here as a special case of A* where the heuristic function always returns 0.

# Returns [vertex_a, ..., vertex_b] or nil
Graph.Pathfinding.dijkstra(graph, start_vertex, end_vertex)