libgraph v0.16.0

Graph (libgraph v0.16.0)

This module defines a graph data structure, which supports directed and undirected graphs, in both acyclic and cyclic forms. It also defines the API for creating, manipulating, and querying that structure.

As far as memory usage is concerned, Graph should be fairly compact in memory, but if you want to do a rough comparison between the memory usage for a graph between libgraph and digraph, use :digraph.info/1 and Graph.info/1 on the two graphs, and both results will contain memory usage information. Keep in mind we don't have a precise way to measure the memory usage of a term in memory, whereas ETS is able to give a more precise answer, but we do have a fairly good way to estimate the usage of a term, and we use that method within libgraph.

The Graph struct is structured like so:

  • A map of vertex ids to vertices (vertices)
  • A map of vertex ids to their out neighbors (out_edges),
  • A map of vertex ids to their in neighbors (in_edges), effectively the transposition of out_edges
  • A map of vertex ids to vertex labels (vertex_labels), (labels are only stored if a non-nil label was provided)
  • A map of edge ids (where an edge id is simply a tuple of {vertex_id, vertex_id}) to a map of edge metadata (edges)
  • Edge metadata is a map of label => weight, and each entry in that map represents a distinct edge. This allows us to support multiple edges in the same direction between the same pair of vertices, but for many purposes simply treat them as a single logical edge.

This structure is designed to be as efficient as possible once a graph is built, but it turned out that it is also quite efficient for manipulating the graph as well. For example, splitting an edge and introducing a new vertex on that edge can be done with very little effort. We use vertex ids everywhere because we can generate them without any lookups, we don't incur any copies of the vertex structure, and they are very efficient as keys in a map.

Link to this section Summary

Types

edge_key()
edge_value()
edge_weight()
graph_info()
graph_type()
label()
t()
vertex()
vertex_id()

Identifier of a vertex. By default a non_neg_integer from Graph.Utils.vertex_id/1 utilizing :erlang.phash2.

vertices()

Functions

a_star(g, a, b, hfun)

Gets the shortest path between a and b.

add_edge(g, edge)

Like add_edge/3 or add_edge/4, but takes a Graph.Edge struct created with Graph.Edge.new/2 or Graph.Edge.new/3.

add_edge(g, v1, v2, opts \\ [])

Adds an edge connecting v1 to v2. If either v1 or v2 do not exist in the graph, they are automatically added. Adding the same edge more than once does not create multiple edges, each edge is only ever stored once.

add_edges(g, es)

This function is like add_edge/3, but for multiple edges at once, it also accepts edge specifications in a few different ways to make it easy to generate graphs succinctly.

add_vertex(g, v, labels \\ [])

Adds a new vertex to the graph. If the vertex is already present in the graph, the add is a no-op.

add_vertices(g, vs)

Like add_vertex/2, but takes a list of vertices to add to the graph.

arborescence_root(g)

Returns the root vertex of the arborescence, if one exists, otherwise nil.

bellman_ford(g, a)

Example

iex> g = Graph.new |> Graph.add_edges([
...>   {:b, :c, weight: -2}, {:a, :b, weight: 1},
...>   {:c, :d, weight: 3}, {:b, :d, weight: 4}])
...> Graph.bellman_ford(g, :a)
%{97 => 0, 98 => 1, 99 => -1, 100 => 2}

iex> g = Graph.new |> Graph.add_edges([
...>   {:b, :c, weight: -2}, {:a, :b, weight: -1},
...>   {:c, :d, weight: -3}, {:d, :a, weight: -5}])
...> Graph.bellman_ford(g, :a)
nil
cliques(g)

Detects all maximal cliques in the provided graph.

components(g)

Returns a list of connected components, where each component is a list of vertices.

coreness(g, v)

Calculates the k-coreness of vertex v in graph g.

degeneracy(g)

Determines the k-degeneracy of the given graph.

degeneracy_core(g)

Calculates the degeneracy core of a given graph.

degree(g, v)

Returns the degree of vertex v of graph g.

delete_edge(g, v1, v2)

Removes all edges connecting v1 to v2, regardless of label.

delete_edge(g, v1, v2, label)

Removes an edge connecting v1 to v2. A label can be specified to disambiguate the specific edge you wish to delete, if not provided, the unlabelled edge, if one exists, will be removed.

delete_edges(g, es)

Like delete_edge/3, but takes a list of edge specifications, and deletes the corresponding edges from the graph, if they exist.

delete_edges(g, v1, v2)

This function can be used to remove all edges between v1 and v2. This is useful if you are defining multiple edges between vertices to represent different relationships, but want to remove them all as if they are a single unit.

delete_vertex(g, v)

Removes a vertex from the graph, as well as any edges which refer to that vertex. If the vertex does not exist in the graph, it is a no-op.

delete_vertices(g, vs)

Like delete_vertex/2, but takes a list of vertices to delete from the graph.

dijkstra(g, a, b)

Gets the shortest path between a and b.

edge(g, v1, v2)

Get an Edge struct for a specific vertex pair, or vertex pair + label.

edge(g, v1, v2, label)
edges(graph)

Return a list of all the edges, where each edge is expressed as a tuple of {A, B}, where the elements are the vertices involved, and implying the direction of the edge to be from A to B.

edges(graph, v)

Returns a list of all edges inbound or outbound from vertex v.

edges(graph, v1, v2)

Returns a list of all edges between v1 and v2.

get_paths(g, a, b)

Builds a list of paths between vertex a and vertex b.

get_shortest_path(g, a, b)

See dijkstra/3.

has_vertex?(graph, v)

Returns true if the given vertex exists in the graph. Otherwise false.

in_degree(graph, v)

Returns the in-degree of vertex v of graph g.

in_edges(g, v)

Returns a list of Graph.Edge structs representing the in edges to vertex v.

in_neighbors(g, v)

Returns a list of vertices which all have edges coming in to the given vertex v.

info(g)

Returns a map of summary information about this graph.

is_acyclic?(g)

Returns true if and only if the graph g is acyclic.

is_arborescence?(g)

Returns true if the graph is an aborescence, a directed acyclic graph, where the root, a vertex, of the arborescence has a unique path from itself to every other vertex in the graph.

is_cyclic?(g)

Returns true if the graph g is not acyclic.

is_subgraph?(a, b)

Returns true if graph g1 is a subgraph of g2.

is_tree?(g)

Returns true if and only if the graph g is a tree.

k_cliques(g, k)

Detects all maximal cliques of degree k.

k_core(g, k)

Calculates the k-core for a given graph and value of k.

k_core_components(g)

Groups all vertices by their k-coreness into a single map.

label_vertex(g, v, vlabels)

Updates the labels for the given vertex.

loop_vertices(g)

Returns a list of vertices from graph g which are included in a loop, where a loop is a cycle of length 1.

neighbors(graph, v)

Return all neighboring vertices of the given vertex.

new(opts \\ [])

Creates a new graph using the provided options.

num_edges(graph)

Returns the number of edges in the graph.

num_vertices(graph)

Returns the number of vertices in the graph

out_degree(g, v)

Returns the out-degree of vertex v of graph g.

out_edges(g, v)

Returns a list of Graph.Edge structs representing the out edges from vertex v.

out_neighbors(g, v)

Returns a list of vertices which the given vertex v has edges going to.

postorder(g)

Returns all vertices of graph g. The order is given by a depth-first traversal of the graph, collecting visited vertices in postorder. More precisely, the vertices visited while searching from an arbitrarily chosen vertex are collected in postorder, and all those collected vertices are placed before the subsequently visited vertices.

preorder(g)

Returns all vertices of graph g. The order is given by a depth-first traversal of the graph, collecting visited vertices in preorder.

reachable(g, vs)

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path in the graph from some vertex of vs to v.

reachable_neighbors(g, vs)

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path in the graph of length one or more from some vertex of vs to v.

reaching(g, vs)

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path from v to some vertex of vs.

reaching_neighbors(g, vs)

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path of length one or more from v to some vertex of vs.

remove_vertex_labels(graph, vertex)

iex> graph = Graph.new |> Graph.add_vertex(:a, [:foo, :bar]) ...> [:foo, :bar] = Graph.vertex_labels(graph, :a) ...> graph = Graph.remove_vertex_labels(graph, :a) ...> Graph.vertex_labels(graph, :a) []

replace_vertex(g, v, rv)

Replaces vertex with new_vertex in the graph.

split_edge(g, v1, v2, v3)

Splits the edges between v1 and v2 by inserting a new vertex, v3, deleting the edges between v1 and v2, and inserting new edges from v1 to v3 and from v3 to v2.

strong_components(g)

Returns a list of strongly connected components, where each component is a list of vertices.

subgraph(graph, vs)

Builds a maximal subgraph of g which includes all of the vertices in vs and the edges which connect them.

to_dot(g)

Converts the given Graph to DOT format, which can then be converted to a number of other formats via Graphviz, e.g. dot -Tpng out.dot > out.png.

to_edgelist(g)
topsort(g)

Returns a topological ordering of the vertices of graph g, if such an ordering exists, otherwise it returns false. For each vertex in the returned list, no out-neighbors occur earlier in the list.

transpose(g)

The transposition of a graph is another graph with the direction of all the edges reversed.

update_edge(g, v1, v2, opts)

Given two vertices, this function updates the metadata (weight/label) for the unlabelled edge between those two vertices. If no unlabelled edge exists between them, an error tuple is returned. If you set a label, the unlabelled edge will be replaced with a new labelled edge.

update_labelled_edge(g, v1, v2, old_label, opts)

Like update_edge/4, but requires you to specify the labelled edge to update.

vertex_labels(graph, v)

Returns the label for the given vertex. If no label was assigned, it returns [].

vertices(graph)

Returns a list of all the vertices in the graph.

Link to this section Types

Link to this type

edge_key()

@type edge_key() :: {vertex_id(), vertex_id()}
Link to this type

edge_value()

@type edge_value() :: %{required(label()) => edge_weight()}
Link to this type

edge_weight()

@type edge_weight() :: integer() | float()
Link to this type

graph_info()

@type graph_info() :: %{
  num_edges: non_neg_integer(),
  num_vertices: non_neg_integer(),
  size_in_bytes: number(),
  type: :directed | :undirected
}
Link to this type

graph_type()

@type graph_type() :: :directed | :undirected
Link to this type

label()

@type label() :: term()
Link to this type

t()

@type t() :: %Graph{
  edges: %{required(edge_key()) => edge_value()},
  in_edges: %{required(vertex_id()) => MapSet.t()},
  out_edges: %{required(vertex_id()) => MapSet.t()},
  type: graph_type(),
  vertex_identifier: (vertex() -> term()),
  vertex_labels: %{required(vertex_id()) => term()},
  vertices: %{required(vertex_id()) => vertex()}
}
Link to this type

vertex()

@type vertex() :: term()
Link to this type

vertex_id()

@type vertex_id() :: non_neg_integer() | term()

Identifier of a vertex. By default a non_neg_integer from Graph.Utils.vertex_id/1 utilizing :erlang.phash2.

Link to this type

vertices()

@type vertices() :: %{required(vertex_id()) => vertex()}

Link to this section Functions

Link to this function

a_star(g, a, b, hfun)

@spec a_star(t(), vertex(), vertex(), (vertex(), vertex() -> integer())) :: [vertex()]

Gets the shortest path between a and b.

The A algorithm is very much like Dijkstra's algorithm, except in addition to edge weights, A also considers a heuristic function for determining the lower bound of the cost to go from vertex v to b. The lower bound must be less than the cost of the shortest path from v to b, otherwise it will do more harm than good. Dijkstra's algorithm can be reframed as A* where lower_bound(v) is always 0.

This function puts the heuristics in your hands, so you must provide the heuristic function, which should take a single parameter, v, which is the vertex being currently examined. Your heuristic should then determine what the lower bound for the cost to reach b from v is, and return that value.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :c}, {:c, :d}, {:b, :d}])
...> Graph.a_star(g, :a, :d, fn _ -> 0 end)
[:a, :b, :d]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :c}, {:b, :c}, {:b, :d}])
...> Graph.a_star(g, :a, :d, fn _ -> 0 end)
nil
Link to this function

add_edge(g, edge)

@spec add_edge(t(), Graph.Edge.t()) :: t()

Like add_edge/3 or add_edge/4, but takes a Graph.Edge struct created with Graph.Edge.new/2 or Graph.Edge.new/3.

example

 Example 

iex> g = Graph.new |> Graph.add_edge(Graph.Edge.new(:a, :b))
...> [:a, :b] = Graph.vertices(g)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b}]
Link to this function

add_edge(g, v1, v2, opts \\ [])

@spec add_edge(t(), vertex(), vertex(), Graph.Edge.edge_opts()) :: t() | no_return()

Adds an edge connecting v1 to v2. If either v1 or v2 do not exist in the graph, they are automatically added. Adding the same edge more than once does not create multiple edges, each edge is only ever stored once.

Edges have a default weight of 1, and an empty (nil) label. You can change this by passing options to this function, as shown below.

example

 Example 

iex> g = Graph.new |> Graph.add_edge(:a, :b)
...> [:a, :b] = Graph.vertices(g)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: nil, weight: 1}]

iex> g = Graph.new |> Graph.add_edge(:a, :b, label: :foo, weight: 2)
...> [:a, :b] = Graph.vertices(g)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: :foo, weight: 2}]
Link to this function

add_edges(g, es)

@spec add_edges(t(), [Graph.Edge.t()] | Enumerable.t()) :: t() | no_return()

This function is like add_edge/3, but for multiple edges at once, it also accepts edge specifications in a few different ways to make it easy to generate graphs succinctly.

Edges must be provided as a list of Edge structs, {vertex, vertex} pairs, or {vertex, vertex, edge_opts :: [label: term, weight: integer]}.

See the docs for Graph.Edge.new/2 or Graph.Edge.new/3 for more info on creating Edge structs, and add_edge/3 for information on edge options.

If an invalid edge specification is provided, raises Graph.EdgeSpecificationError.

examples

 Examples 

iex> alias Graph.Edge
...> edges = [Edge.new(:a, :b), Edge.new(:b, :c, weight: 2)]
...> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edges(edges)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b}, %Graph.Edge{v1: :b, v2: :c, weight: 2}]

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}, {:a, :b, label: :foo, weight: 2}])
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: :foo, weight: 2}, %Graph.Edge{v1: :a, v2: :b}]

iex> Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edges([:a, :b])
** (Graph.EdgeSpecificationError) Expected a valid edge specification, but got: :a
Link to this function

add_vertex(g, v, labels \\ [])

@spec add_vertex(t(), vertex(), label()) :: t()

Adds a new vertex to the graph. If the vertex is already present in the graph, the add is a no-op.

You can provide optional labels for the vertex, aside from the variety of uses this has for working with graphs, labels will also be used when exporting a graph in DOT format.

example

 Example 

iex> g = Graph.new |> Graph.add_vertex(:a, :mylabel) |> Graph.add_vertex(:a)
...> [:a] = Graph.vertices(g)
...> Graph.vertex_labels(g, :a)
[:mylabel]

iex> g = Graph.new |> Graph.add_vertex(:a, [:mylabel, :other])
...> Graph.vertex_labels(g, :a)
[:mylabel, :other]
Link to this function

add_vertices(g, vs)

@spec add_vertices(t(), [vertex()]) :: t()

Like add_vertex/2, but takes a list of vertices to add to the graph.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :a])
...> Graph.vertices(g)
[:a, :b]
Link to this function

arborescence_root(g)

@spec arborescence_root(t()) :: vertex() | nil

Returns the root vertex of the arborescence, if one exists, otherwise nil.

Link to this function

bellman_ford(g, a)

@spec bellman_ford(t(), vertex()) :: [vertex()]

example

 Example 

iex> g = Graph.new |> Graph.add_edges([
...>   {:b, :c, weight: -2}, {:a, :b, weight: 1},
...>   {:c, :d, weight: 3}, {:b, :d, weight: 4}])
...> Graph.bellman_ford(g, :a)
%{97 => 0, 98 => 1, 99 => -1, 100 => 2}

iex> g = Graph.new |> Graph.add_edges([
...>   {:b, :c, weight: -2}, {:a, :b, weight: -1},
...>   {:c, :d, weight: -3}, {:d, :a, weight: -5}])
...> Graph.bellman_ford(g, :a)
nil
Link to this function

cliques(g)

@spec cliques(t()) :: [[vertex()]]

Detects all maximal cliques in the provided graph.

Returns a list of cliques, where each clique is a list of vertices in the clique.

A clique is a subset vs of the vertices in the given graph, which together form a complete graph; or put another way, every vertex in vs is connected to all other vertices in vs.

Link to this function

components(g)

@spec components(t()) :: [[vertex()]]

Returns a list of connected components, where each component is a list of vertices.

A connected component is a maximal subgraph such that there is a path between each pair of vertices, considering all edges undirected.

A subgraph is a graph whose vertices and edges are a subset of the vertices and edges of the source graph.

A maximal subgraph is a subgraph with property P where all other subgraphs which contain the same vertices do not have that same property P.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :d}, {:c, :a}])
...> Graph.components(g)
[[:d, :b, :c, :a]]
Link to this function

coreness(g, v)

@spec coreness(t(), vertex()) :: non_neg_integer()

Calculates the k-coreness of vertex v in graph g.

The k-coreness of a vertex is defined as the maximum value of k for which v is found in the corresponding k-core of graph g.

NOTE: This function decomposes all k-core components to determine the coreness of a vertex - if you will be trying to determine the coreness of many vertices, it is recommended to use k_core_components/1 and then lookup the coreness of a vertex by querying the resulting map.

Link to this function

degeneracy(g)

@spec degeneracy(t()) :: non_neg_integer()

Determines the k-degeneracy of the given graph.

The degeneracy of graph g is the maximum value of k for which a k-core exists in graph g.

Link to this function

degeneracy_core(g)

@spec degeneracy_core(t()) :: t()

Calculates the degeneracy core of a given graph.

The degeneracy core of a graph is the k-core of the graph where the value of k is the degeneracy of the graph. The degeneracy of a graph is the highest value of k which has a non-empty k-core in the graph.

Link to this function

degree(g, v)

@spec degree(t(), vertex()) :: non_neg_integer()

Returns the degree of vertex v of graph g.

The degree of a vertex is the total number of edges containing that vertex.

For directed graphs this is the same as the sum of the in-degree and out-degree of the given vertex. For undirected graphs, the in-degree and out-degree are always the same.

example

 Example 

iex> g = Graph.new(type: :undirected) |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b)
...> Graph.degree(g, :b)
1

iex> g = Graph.new() |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b)
...> Graph.degree(g, :b)
1
Link to this function

delete_edge(g, v1, v2)

@spec delete_edge(t(), vertex(), vertex()) :: t()

Removes all edges connecting v1 to v2, regardless of label.

If no such edge exists, the graph is returned unmodified.

example

 Example

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}]) ...> g = Graph.delete_edge(g, :a, :b) ...> [:a, :b] = Graph.vertices(g) ...> Graph.edges(g) []

iex> g = Graph.new(type: :undirected) |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}]) ...> g = Graph.delete_edge(g, :a, :b) ...> [:a, :b] = Graph.vertices(g) ...> Graph.edges(g) []

Link to this function

delete_edge(g, v1, v2, label)

@spec delete_edge(t(), vertex(), vertex(), label()) :: t()

Removes an edge connecting v1 to v2. A label can be specified to disambiguate the specific edge you wish to delete, if not provided, the unlabelled edge, if one exists, will be removed.

If no such edge exists, the graph is returned unmodified.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}])
...> g = Graph.delete_edge(g, :a, :b, nil)
...> [:a, :b] = Graph.vertices(g)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: :foo}]

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}])
...> g = Graph.delete_edge(g, :a, :b, :foo)
...> [:a, :b] = Graph.vertices(g)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: nil}]

iex> g = Graph.new(type: :undirected) |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}])
...> g = Graph.delete_edge(g, :a, :b, :foo)
...> [:a, :b] = Graph.vertices(g)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: nil}]
Link to this function

delete_edges(g, es)

@spec delete_edges(t(), [{vertex(), vertex()}]) :: t() | no_return()

Like delete_edge/3, but takes a list of edge specifications, and deletes the corresponding edges from the graph, if they exist.

Edge specifications can be Edge structs, {vertex, vertex} pairs, or {vertex, vertex, label: label} triplets. An invalid specification will cause Graph.EdgeSpecificationError to be raised.

examples

 Examples 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b)
...> g = Graph.delete_edges(g, [{:a, :b}])
...> Graph.edges(g)
[]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b, label: :foo)
...> g = Graph.delete_edges(g, [{:a, :b}])
...> Graph.edges(g)
[]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b, label: :foo)
...> g = Graph.delete_edges(g, [{:a, :b, label: :bar}])
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: :foo}]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b, label: :foo)
...> g = Graph.delete_edges(g, [{:a, :b, label: :foo}])
...> Graph.edges(g)
[]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b)
...> Graph.delete_edges(g, [:a])
** (Graph.EdgeSpecificationError) Expected a valid edge specification, but got: :a
Link to this function

delete_edges(g, v1, v2)

@spec delete_edges(t(), vertex(), vertex()) :: t()

This function can be used to remove all edges between v1 and v2. This is useful if you are defining multiple edges between vertices to represent different relationships, but want to remove them all as if they are a single unit.

examples

 Examples 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}, {:b, :a}])
...> g = Graph.delete_edges(g, :a, :b)
...> Graph.edges(g)
[%Graph.Edge{v1: :b, v2: :a}]

iex> g = Graph.new(type: :undirected) |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}, {:b, :a}])
...> g = Graph.delete_edges(g, :a, :b)
...> Graph.edges(g)
[]
Link to this function

delete_vertex(g, v)

@spec delete_vertex(t(), vertex()) :: t()

Removes a vertex from the graph, as well as any edges which refer to that vertex. If the vertex does not exist in the graph, it is a no-op.

example

 Example 

iex> g = Graph.new |> Graph.add_vertex(:a) |> Graph.add_vertex(:b) |> Graph.add_edge(:a, :b)
...> [:a, :b] = Graph.vertices(g)
...> [%Graph.Edge{v1: :a, v2: :b}] = Graph.edges(g)
...> g = Graph.delete_vertex(g, :b)
...> [:a] = Graph.vertices(g)
...> Graph.edges(g)
[]
Link to this function

delete_vertices(g, vs)

@spec delete_vertices(t(), [vertex()]) :: t()

Like delete_vertex/2, but takes a list of vertices to delete from the graph.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.delete_vertices([:a, :b])
...> Graph.vertices(g)
[:c]
Link to this function

dijkstra(g, a, b)

@spec dijkstra(t(), vertex(), vertex()) :: [vertex()]

Gets the shortest path between a and b.

As indicated by the name, this uses Dijkstra's algorithm for locating the shortest path, which means that edge weights are taken into account when determining which vertices to search next. By default, all edges have a weight of 1, so vertices are inspected at random; which causes this algorithm to perform a naive depth-first search of the graph until a path is found. If your edges are weighted however, this will allow the algorithm to more intelligently navigate the graph.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :c}, {:c, :d}, {:b, :d}])
...> Graph.dijkstra(g, :a, :d)
[:a, :b, :d]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :c}, {:b, :c}, {:b, :d}])
...> Graph.dijkstra(g, :a, :d)
nil
Link to this function

edge(g, v1, v2)

@spec edge(t(), vertex(), vertex()) :: Graph.Edge.t() | nil

Get an Edge struct for a specific vertex pair, or vertex pair + label.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :contains}, {:a, :b, label: :uses}])
...> Graph.edge(g, :b, :a)
nil

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :contains}, {:a, :b, label: :uses}])
...> Graph.edge(g, :a, :b)
%Graph.Edge{v1: :a, v2: :b}

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :contains}, {:a, :b, label: :uses}])
...> Graph.edge(g, :a, :b, :contains)
%Graph.Edge{v1: :a, v2: :b, label: :contains}

iex> g = Graph.new(type: :undirected) |> Graph.add_edges([{:a, :b}, {:a, :b, label: :contains}, {:a, :b, label: :uses}])
...> Graph.edge(g, :a, :b, :contains)
%Graph.Edge{v1: :a, v2: :b, label: :contains}
Link to this function

edge(g, v1, v2, label)

@spec edge(t(), vertex(), vertex(), label()) :: Graph.Edge.t() | nil
Link to this function

edges(graph)

@spec edges(t()) :: [Graph.Edge.t()]

Return a list of all the edges, where each edge is expressed as a tuple of {A, B}, where the elements are the vertices involved, and implying the direction of the edge to be from A to B.

NOTE: You should be careful when using this on dense graphs, as it produces lists with whatever you've provided as vertices, with likely many copies of each. I'm not sure if those copies are shared in-memory as they are unchanged, so it should be fairly compact in memory, but I have not verified that to be sure.

example

 Example 

iex> g = Graph.new |> Graph.add_vertex(:a) |> Graph.add_vertex(:b) |> Graph.add_vertex(:c)
...> g = g |> Graph.add_edge(:a, :c) |> Graph.add_edge(:b, :c)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :c}, %Graph.Edge{v1: :b, v2: :c}]
Link to this function

edges(graph, v)

@spec edges(t(), vertex()) :: [Graph.Edge.t()]

Returns a list of all edges inbound or outbound from vertex v.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :c}])
...> Graph.edges(g, :b)
[%Graph.Edge{v1: :a, v2: :b}, %Graph.Edge{v1: :b, v2: :c}]

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :c}])
...> Graph.edges(g, :d)
[]
Link to this function

edges(graph, v1, v2)

@spec edges(t(), vertex(), vertex()) :: [Graph.Edge.t()]

Returns a list of all edges between v1 and v2.

example

 Example 

iex> g = Graph.new |> Graph.add_edge(:a, :b, label: :uses)
...> g = Graph.add_edge(g, :a, :b, label: :contains)
...> Graph.edges(g, :a, :b)
[%Graph.Edge{v1: :a, v2: :b, label: :contains}, %Graph.Edge{v1: :a, v2: :b, label: :uses}]

iex> g = Graph.new(type: :undirected) |> Graph.add_edge(:a, :b, label: :uses)
...> g = Graph.add_edge(g, :a, :b, label: :contains)
...> Graph.edges(g, :a, :b)
[%Graph.Edge{v1: :a, v2: :b, label: :contains}, %Graph.Edge{v1: :a, v2: :b, label: :uses}]
Link to this function

get_paths(g, a, b)

@spec get_paths(t(), vertex(), vertex()) :: [[vertex()]]

Builds a list of paths between vertex a and vertex b.

The algorithm used here is a depth-first search, which evaluates the whole graph until all paths are found. Order is guaranteed to be deterministic, but not guaranteed to be in any meaningful order (i.e. shortest to longest).

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :c}, {:c, :d}, {:b, :d}, {:c, :a}])
...> Graph.get_paths(g, :a, :d)
[[:a, :b, :c, :d], [:a, :b, :d]]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :c}, {:b, :c}, {:b, :d}])
...> Graph.get_paths(g, :a, :d)
[]
Link to this function

get_shortest_path(g, a, b)

@spec get_shortest_path(t(), vertex(), vertex()) :: [vertex()] | nil

See dijkstra/3.

Link to this function

has_vertex?(graph, v)

@spec has_vertex?(t(), vertex()) :: boolean()

Returns true if the given vertex exists in the graph. Otherwise false.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b])
...> Graph.has_vertex?(g, :a)
true

iex> g = Graph.new |> Graph.add_vertices([:a, :b])
...> Graph.has_vertex?(g, :c)
false
Link to this function

in_degree(graph, v)

Returns the in-degree of vertex v of graph g.

The in-degree of a vertex is the number of edges directed inbound towards that vertex.

For undirected graphs, the in-degree and out-degree are always the same - the sum total of all edges inbound or outbound from the vertex.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b)
...> Graph.in_degree(g, :b)
1
Link to this function

in_edges(g, v)

@spec in_edges(t(), vertex()) :: Graph.Edge.t()

Returns a list of Graph.Edge structs representing the in edges to vertex v.

In the case of undirected graphs, it delegates to edges/2.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}, {:b, :c}])
...> Graph.in_edges(g, :b)
[%Graph.Edge{v1: :a, v2: :b, label: :foo}, %Graph.Edge{v1: :a, v2: :b}]
Link to this function

in_neighbors(g, v)

@spec in_neighbors(t(), vertex()) :: [vertex()]

Returns a list of vertices which all have edges coming in to the given vertex v.

In the case of undirected graphs, it delegates to neighbors/2.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}, {:b, :c}])
...> Graph.in_neighbors(g, :b)
[:a]
Link to this function

info(g)

@spec info(t()) :: graph_info()

Returns a map of summary information about this graph.

NOTE: The size_in_bytes value is an estimate, not a perfectly precise value, but should be close enough to be useful.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = g |> Graph.add_edges([{:a, :b}, {:b, :c}])
...> match?(%{type: :directed, num_vertices: 4, num_edges: 2}, Graph.info(g))
true
Link to this function

is_acyclic?(g)

@spec is_acyclic?(t()) :: boolean()

Returns true if and only if the graph g is acyclic.

Link to this function

is_arborescence?(g)

@spec is_arborescence?(t()) :: boolean()

Returns true if the graph is an aborescence, a directed acyclic graph, where the root, a vertex, of the arborescence has a unique path from itself to every other vertex in the graph.

Link to this function

is_cyclic?(g)

@spec is_cyclic?(t()) :: boolean()

Returns true if the graph g is not acyclic.

Link to this function

is_subgraph?(a, b)

@spec is_subgraph?(t(), t()) :: boolean()

Returns true if graph g1 is a subgraph of g2.

A graph is a subgraph of another graph if it's vertices and edges are a subset of that graph's vertices and edges.

example

 Example 

iex> g1 = Graph.new |> Graph.add_vertices([:a, :b, :c, :d]) |> Graph.add_edge(:a, :b) |> Graph.add_edge(:b, :c)
...> g2 = Graph.new |> Graph.add_vertices([:b, :c]) |> Graph.add_edge(:b, :c)
...> Graph.is_subgraph?(g2, g1)
true

iex> g1 = Graph.new |> Graph.add_vertices([:a, :b, :c, :d]) |> Graph.add_edges([{:a, :b}, {:b, :c}])
...> g2 = Graph.new |> Graph.add_vertices([:b, :c, :e]) |> Graph.add_edges([{:b, :c}, {:c, :e}])
...> Graph.is_subgraph?(g2, g1)
false
Link to this function

is_tree?(g)

@spec is_tree?(t()) :: boolean()

Returns true if and only if the graph g is a tree.

This function always returns false for undirected graphs.

NOTE: Multiple edges between the same pair of vertices in the same direction are considered a single edge when determining if the provided graph is a tree.

Link to this function

k_cliques(g, k)

@spec k_cliques(t(), non_neg_integer()) :: [[vertex()]]

Detects all maximal cliques of degree k.

Returns a list of cliques, where each clique is a list of vertices in the clique.

Link to this function

k_core(g, k)

@spec k_core(t(), k :: non_neg_integer()) :: t()

Calculates the k-core for a given graph and value of k.

A k-core of the graph is a maximal subgraph of g which contains vertices of which all have a degree of at least k. This function returns a new Graph which is a subgraph of g containing all vertices which have a coreness >= the desired value of k.

If there is no k-core in the graph for the provided value of k, an empty Graph is returned.

If a negative integer is provided for k, a RuntimeError will be raised.

NOTE: For performance reasons, k-core calculations make use of ETS. If you are sensitive to the number of concurrent ETS tables running in your system, you should be aware of it's usage here. 2 tables are used, and they are automatically cleaned up when this function returns.

Link to this function

k_core_components(g)

@spec k_core_components(t()) :: %{required(k :: non_neg_integer()) => [vertex()]}

Groups all vertices by their k-coreness into a single map.

More commonly you will want a specific k-core, in particular the degeneracy core, for which there are other functions in the API you can use. However if you have a need to determine which k-core each vertex belongs to, this function can be used to do just that.

As an example, you can construct the k-core for a given graph like so:

k_core_vertices =
  g
  |> Graph.k_core_components()
  |> Stream.filter(fn {k, _} -> k >= desired_k end)
  |> Enum.flat_map(fn {_, vs} -> vs end)
Graph.subgraph(g, k_core_vertices)
Link to this function

label_vertex(g, v, vlabels)

@spec label_vertex(t(), vertex(), term()) ::
  t() | {:error, {:invalid_vertex, vertex()}}

Updates the labels for the given vertex.

If no such vertex exists in the graph, {:error, {:invalid_vertex, v}} is returned.

example

 Example 

iex> g = Graph.new |> Graph.add_vertex(:a, :foo)
...> [:foo] = Graph.vertex_labels(g, :a)
...> g = Graph.label_vertex(g, :a, :bar)
...> Graph.vertex_labels(g, :a)
[:foo, :bar]

iex> g = Graph.new |> Graph.add_vertex(:a)
...> g = Graph.label_vertex(g, :a, [:foo, :bar])
...> Graph.vertex_labels(g, :a)
[:foo, :bar]
Link to this function

loop_vertices(g)

@spec loop_vertices(t()) :: [vertex()]

Returns a list of vertices from graph g which are included in a loop, where a loop is a cycle of length 1.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :a)
...> Graph.loop_vertices(g)
[:a]
Link to this function

neighbors(graph, v)

@spec neighbors(t(), vertex()) :: [vertex()]

Return all neighboring vertices of the given vertex.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :a}, {:b, :c}, {:c, :a}])
...> Graph.neighbors(g, :a)
[:b, :c]

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :a}, {:b, :c}, {:c, :a}])
...> Graph.neighbors(g, :d)
[]
Link to this function

new(opts \\ [])

Creates a new graph using the provided options.

options

 Options

  • type: :directed | :undirected, specifies what type of graph this is. Defaults to a :directed graph.

  • vertex_identifier: a function which accepts a vertex and returns a unique identifier of said vertex. Defaults to Graph.Utils.vertex_id/1, a hash of the whole vertex utilizing :erlang.phash2/2.

example

 Example 

iex> Graph.new()
#Graph<type: directed, vertices: [], edges: []>

iex> g = Graph.new(type: :undirected) |> Graph.add_edges([{:a, :b}, {:b, :a}])
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b}]

iex> g = Graph.new(type: :directed) |> Graph.add_edges([{:a, :b}, {:b, :a}])
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b}, %Graph.Edge{v1: :b, v2: :a}]

iex> g = Graph.new(vertex_identifier: fn v -> :erlang.phash2(v) end) |> Graph.add_edges([{:a, :b}, {:b, :a}])
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b}, %Graph.Edge{v1: :b, v2: :a}]
Link to this function

num_edges(graph)

@spec num_edges(t()) :: non_neg_integer()

Returns the number of edges in the graph.

Pseudo-edges (label/weight pairs applied to an edge) are not counted, only distinct vertex pairs where an edge exists between them are counted.

example

 Example 

iex> g = Graph.add_edges(Graph.new, [{:a, :b}, {:b, :c}, {:a, :a}])
...> Graph.num_edges(g)
3
Link to this function

num_vertices(graph)

@spec num_vertices(t()) :: non_neg_integer()

Returns the number of vertices in the graph

example

 Example 

iex> g = Graph.add_vertices(Graph.new, [:a, :b, :c])
...> Graph.num_vertices(g)
3
Link to this function

out_degree(g, v)

@spec out_degree(t(), vertex()) :: non_neg_integer()

Returns the out-degree of vertex v of graph g.

The out-degree of a vertex is the number of edges directed outbound from that vertex.

For undirected graphs, the in-degree and out-degree are always the same - the sum total of all edges inbound or outbound from the vertex.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b)
...> Graph.out_degree(g, :a)
1
Link to this function

out_edges(g, v)

@spec out_edges(t(), vertex()) :: Graph.Edge.t()

Returns a list of Graph.Edge structs representing the out edges from vertex v.

In the case of undirected graphs, it delegates to edges/2.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}, {:b, :c}])
...> Graph.out_edges(g, :a)
[%Graph.Edge{v1: :a, v2: :b, label: :foo}, %Graph.Edge{v1: :a, v2: :b}]
Link to this function

out_neighbors(g, v)

@spec out_neighbors(t(), vertex()) :: [vertex()]

Returns a list of vertices which the given vertex v has edges going to.

In the case of undirected graphs, it delegates to neighbors/2.

example

 Example 

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:a, :b, label: :foo}, {:b, :c}])
...> Graph.out_neighbors(g, :a)
[:b]
Link to this function

postorder(g)

@spec postorder(t()) :: [vertex()]

Returns all vertices of graph g. The order is given by a depth-first traversal of the graph, collecting visited vertices in postorder. More precisely, the vertices visited while searching from an arbitrarily chosen vertex are collected in postorder, and all those collected vertices are placed before the subsequently visited vertices.

example

 Example

Our example code constructs a graph which looks like so:

    :a
                 :b
      /           :c   :d
    /
   :e

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d, :e])
...> g = Graph.add_edges(g, [{:a, :b}, {:b, :c}, {:b, :d}, {:c, :e}])
...> Graph.postorder(g)
[:e, :c, :d, :b, :a]
Link to this function

preorder(g)

@spec preorder(t()) :: [vertex()]

Returns all vertices of graph g. The order is given by a depth-first traversal of the graph, collecting visited vertices in preorder.

example

 Example

Our example code constructs a graph which looks like so:

     :a
                   :b
       /           :c   :d
     /
   :e

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d, :e])
...> g = Graph.add_edges(g, [{:a, :b}, {:b, :c}, {:b, :d}, {:c, :e}])
...> Graph.preorder(g)
[:a, :b, :c, :e, :d]
Link to this function

reachable(g, vs)

@spec reachable(t(), [vertex()]) :: [[vertex()]]

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path in the graph from some vertex of vs to v.

As paths of length zero are allowed, the vertices of vs are also included in the returned list.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :d}])
...> Graph.reachable(g, [:a])
[:d, :c, :b, :a]
Link to this function

reachable_neighbors(g, vs)

@spec reachable_neighbors(t(), [vertex()]) :: [[vertex()]]

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path in the graph of length one or more from some vertex of vs to v.

As a consequence, only those vertices of vs that are included in some cycle are returned.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :d}])
...> Graph.reachable_neighbors(g, [:a])
[:d, :c, :b]
Link to this function

reaching(g, vs)

@spec reaching(t(), [vertex()]) :: [[vertex()]]

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path from v to some vertex of vs.

As paths of length zero are allowed, the vertices of vs are also included in the returned list.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :d}])
...> Graph.reaching(g, [:d])
[:b, :a, :c, :d]
Link to this function

reaching_neighbors(g, vs)

@spec reaching_neighbors(t(), [vertex()]) :: [[vertex()]]

Returns an unsorted list of vertices from the graph, such that for each vertex in the list (call it v), there is a path of length one or more from v to some vertex of vs.

As a consequence, only those vertices of vs that are included in some cycle are returned.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :a}, {:b, :d}])
...> Graph.reaching_neighbors(g, [:b])
[:b, :c, :a]
Link to this function

remove_vertex_labels(graph, vertex)

@spec remove_vertex_labels(t(), vertex()) ::
  t() | {:error, {:invalid_vertex, vertex()}}

iex> graph = Graph.new |> Graph.add_vertex(:a, [:foo, :bar]) ...> [:foo, :bar] = Graph.vertex_labels(graph, :a) ...> graph = Graph.remove_vertex_labels(graph, :a) ...> Graph.vertex_labels(graph, :a) []

iex> graph = Graph.new |> Graph.add_vertex(:a, [:foo, :bar]) ...> [:foo, :bar] = Graph.vertex_labels(graph, :a) ...> Graph.remove_vertex_labels(graph, :b) {:error, {:invalid_vertex, :b}}

Link to this function

replace_vertex(g, v, rv)

@spec replace_vertex(t(), vertex(), vertex()) :: t() | {:error, :no_such_vertex}

Replaces vertex with new_vertex in the graph.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:b, :c}, {:c, :a}, {:c, :d}])
...> [:a, :b, :c, :d] = Graph.vertices(g)
...> g = Graph.replace_vertex(g, :a, :e)
...> [:b, :c, :d, :e] = Graph.vertices(g)
...> Graph.edges(g)
[%Graph.Edge{v1: :b, v2: :c}, %Graph.Edge{v1: :c, v2: :d}, %Graph.Edge{v1: :c, v2: :e}, %Graph.Edge{v1: :e, v2: :b}]
Link to this function

split_edge(g, v1, v2, v3)

@spec split_edge(t(), vertex(), vertex(), vertex()) :: t() | {:error, :no_such_edge}

Splits the edges between v1 and v2 by inserting a new vertex, v3, deleting the edges between v1 and v2, and inserting new edges from v1 to v3 and from v3 to v2.

The resulting edges from the split will share the same weight and label as the old edges.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :c]) |> Graph.add_edge(:a, :c, weight: 2)
...> g = Graph.split_edge(g, :a, :c, :b)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, weight: 2}, %Graph.Edge{v1: :b, v2: :c, weight: 2}]

iex> g = Graph.new(type: :undirected) |> Graph.add_vertices([:a, :c]) |> Graph.add_edge(:a, :c, weight: 2)
...> g = Graph.split_edge(g, :a, :c, :b)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, weight: 2}, %Graph.Edge{v1: :b, v2: :c, weight: 2}]
Link to this function

strong_components(g)

@spec strong_components(t()) :: [[vertex()]]

Returns a list of strongly connected components, where each component is a list of vertices.

A strongly connected component is a maximal subgraph such that there is a path between each pair of vertices.

See components/1 for the definitions of subgraph and maximal subgraph if you are unfamiliar with the terminology.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :d}, {:c, :a}])
...> Graph.strong_components(g)
[[:d], [:b, :c, :a]]
Link to this function

subgraph(graph, vs)

@spec subgraph(t(), [vertex()]) :: t()

Builds a maximal subgraph of g which includes all of the vertices in vs and the edges which connect them.

See the test suite for example usage.

Link to this function

to_dot(g)

@spec to_dot(t()) :: {:ok, binary()} | {:error, term()}

Converts the given Graph to DOT format, which can then be converted to a number of other formats via Graphviz, e.g. dot -Tpng out.dot > out.png.

If labels are set on a vertex, then those labels are used in the DOT output in place of the vertex itself. If no labels were set, then the vertex is stringified if it's a primitive type and inspected if it's not, in which case the inspect output will be quoted and used as the vertex label in the DOT file.

Edge labels and weights will be shown as attributes on the edge definitions, otherwise they use the same labelling scheme for the involved vertices as described above.

NOTE: Currently this function assumes graphs are directed graphs, but in the future it will support undirected graphs as well.

example

 Example 

> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
> g = Graph.add_edges([{:a, :b}, {:b, :c}, {:b, :d}, {:c, :d}])
> g = Graph.label_vertex(g, :a, :start)
> g = Graph.label_vertex(g, :d, :finish)
> g = Graph.update_edge(g, :b, :d, weight: 3)
> IO.puts(Graph.to_dot(g))
strict digraph {
    start
    b
    c
    finish
    start -> b [weight=1]
    b -> c [weight=1]
    b -> finish [weight=3]
    c -> finish [weight=1]
}
Link to this function

to_edgelist(g)

@spec to_edgelist(t()) :: {:ok, binary()} | {:error, term()}
Link to this function

topsort(g)

@spec topsort(t()) :: [vertex()] | false

Returns a topological ordering of the vertices of graph g, if such an ordering exists, otherwise it returns false. For each vertex in the returned list, no out-neighbors occur earlier in the list.

Multiple edges between two vertices are considered a single edge for purposes of this sort.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :d}])
...> Graph.topsort(g)
[:a, :b, :c, :d]

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c, :d])
...> g = Graph.add_edges(g, [{:a, :b}, {:a, :c}, {:b, :c}, {:c, :d}, {:c, :a}])
...> Graph.topsort(g)
false
Link to this function

transpose(g)

@spec transpose(t()) :: t()

The transposition of a graph is another graph with the direction of all the edges reversed.

example

 Example 

iex> g = Graph.new |> Graph.add_vertices([:a, :b, :c]) |> Graph.add_edge(:a, :b) |> Graph.add_edge(:b, :c)
...> g |> Graph.transpose |> Graph.edges
[%Graph.Edge{v1: :b, v2: :a}, %Graph.Edge{v1: :c, v2: :b}]
Link to this function

update_edge(g, v1, v2, opts)

@spec update_edge(t(), vertex(), vertex(), Graph.Edge.edge_opts()) ::
  t() | {:error, :no_such_edge}

Given two vertices, this function updates the metadata (weight/label) for the unlabelled edge between those two vertices. If no unlabelled edge exists between them, an error tuple is returned. If you set a label, the unlabelled edge will be replaced with a new labelled edge.

example

 Example 

iex> g = Graph.new |> Graph.add_edge(:a, :b) |> Graph.add_edge(:a, :b, label: :bar)
...> %Graph{} = g = Graph.update_edge(g, :a, :b, weight: 2, label: :foo)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: :bar}, %Graph.Edge{v1: :a, v2: :b, label: :foo, weight: 2}]
Link to this function

update_labelled_edge(g, v1, v2, old_label, opts)

@spec update_labelled_edge(t(), vertex(), vertex(), label(), Graph.Edge.edge_opts()) ::
  t() | {:error, :no_such_edge}

Like update_edge/4, but requires you to specify the labelled edge to update.

Th implementation of update_edge/4 is actually update_edge(g, v1, v2, nil, opts).

example

 Example 

iex> g = Graph.new |> Graph.add_edge(:a, :b) |> Graph.add_edge(:a, :b, label: :bar)
...> %Graph{} = g = Graph.update_labelled_edge(g, :a, :b, :bar, weight: 2, label: :foo)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: :foo, weight: 2}, %Graph.Edge{v1: :a, v2: :b}]

iex> g = Graph.new(type: :undirected) |> Graph.add_edge(:a, :b) |> Graph.add_edge(:a, :b, label: :bar)
...> %Graph{} = g = Graph.update_labelled_edge(g, :a, :b, :bar, weight: 2, label: :foo)
...> Graph.edges(g)
[%Graph.Edge{v1: :a, v2: :b, label: :foo, weight: 2}, %Graph.Edge{v1: :a, v2: :b}]
Link to this function

vertex_labels(graph, v)

@spec vertex_labels(t(), vertex()) :: term() | []

Returns the label for the given vertex. If no label was assigned, it returns [].

example

 Example 

iex> g = Graph.new |> Graph.add_vertex(:a) |> Graph.label_vertex(:a, :my_label)
...> Graph.vertex_labels(g, :a)
[:my_label]
Link to this function

vertices(graph)

@spec vertices(t()) :: vertex()

Returns a list of all the vertices in the graph.

NOTE: You should be careful when using this on large graphs, as the list it produces contains every vertex on the graph. I have not yet verified whether Erlang ensures that they are a shared reference with the original, or copies, but if the latter it could result in running out of memory if the graph is too large.

example

 Example 

iex> g = Graph.new |> Graph.add_vertex(:a) |> Graph.add_vertex(:b)
...> Graph.vertices(g)
[:a, :b]