Graph

Construction

type Graph vertex

A directed graph data structure.

The vertices can hold any data, but you can't have two vertices holding the same data. (Think of it as of Set.)

The edges don't hold any data, they just connect two vertices. Again, they are directed: the order does matter.

type alias Edge vertex =

{ from : vertex

, to : vertex

}

A representation of an edge between two vertices.

empty : Graph vertex

An empty graph. No vertices, no edges.

fromVerticesAndEdges : List vertex -> List (Edge vertex) -> Graph vertex

Construct a graph from a list of vertices and a list of edges.

Implicitly adds vertices that are present in the edges list, as if they were mentioned in the vertices list too.

Graph.fromVerticesAndEdges
    [ "x", "y" ]
    [ { from = "x", to = "y" }
    , { from = "y", to = "z" }
    , { from = "z", to = "x" }
    ]
    |> Graph.vertices
    |> List.length
--> 3

Modification

addVertex : vertex -> Graph vertex -> Graph vertex

Add the vertex to the graph. (Nothing happens if it's already present.)

By default it's not connected to any other vertex.

Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.vertices
--> [ "foo" ]

removeVertex : vertex -> Graph vertex -> Graph vertex

Remove the vertex from the graph. (Nothing happens if it's not present.)

Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.removeVertex "foo"
    |> Graph.isEmpty
--> True

updateVertex : vertex -> (vertex -> vertex) -> Graph vertex -> Graph vertex

Updates the vertex data. Does nothing if the vertex is not present.

Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.updateVertex "foo" String.toUpper
    |> Graph.vertices
--> [ "FOO" ]

addEdge : vertex -> vertex -> Graph vertex -> Graph vertex

Add an edge to the graph.

If any of the vertices aren't present yet, this function will add them before adding the edge.

Directed: the order of the vertices does matter.

Graph.empty
    |> Graph.addEdge "foo" "bar"
    |> Graph.vertices
--> [ "foo", "bar" ]


Graph.empty
    |> Graph.addEdge "foo" "bar"
    |> Graph.edges
--> [ { from = "foo", to = "bar" } ]

removeEdge : vertex -> vertex -> Graph vertex -> Graph vertex

Remove an edge from the first vertex to the second one. Does nothing if the edge is not present.

Directed: the order of the vertices does matter.

Graph.empty
    |> Graph.addEdge "foo" "bar"
    |> Graph.removeEdge "foo" "bar"
    |> Graph.edges
--> []

map : (vertex -> vertex2) -> Graph vertex -> Graph vertex2

Applies a function to all the vertices.

Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.addVertex "bar"
    |> Graph.map String.toUpper
    |> Graph.vertices
--> [ "FOO", "BAR" ]

reverseEdges : Graph vertex -> Graph vertex

Reverse the direction of all the edges in the graph.

Graph.empty
    |> Graph.addEdge "foo" "bar"
    |> Graph.reverseEdges
    |> Graph.edges
--> [ { from = "bar", to = "foo" } ]

Predicates

isEmpty : Graph vertex -> Bool

Is the graph empty?

hasVertex : vertex -> Graph vertex -> Bool

Is this vertex present in the graph?

Graph.empty
    |> Graph.hasVertex "x"
--> False


Graph.empty
    |> Graph.addVertex "x"
    |> Graph.hasVertex "x"
--> True

hasEdge : Edge vertex -> Graph vertex -> Bool

Is this edge present in the graph?

Graph.empty
    |> Graph.hasEdge {from = "x", to = "y"}
--> False


Graph.empty
    |> Graph.addEdge "x" "y"
    |> Graph.hasEdge {from = "x", to = "y"}
--> True


Graph.empty
    |> Graph.addEdge "y" "x"
    |> Graph.hasEdge {from = "x", to = "y"}
--> False

areAdjacent : vertex -> vertex -> Graph vertex -> Bool

Does the graph contain an edge between these two vertices (in any direction)?

Graph.empty
    |> Graph.areAdjacent "x" "y"
--> False


Graph.empty
    |> Graph.addEdge "x" "y"
    |> Graph.areAdjacent "x" "y"
--> True


Graph.empty
    |> Graph.addEdge "y" "x"
    |> Graph.areAdjacent "x" "y"
--> True

Querying

fold : (vertex -> acc -> acc) -> acc -> Graph vertex -> acc

Fold a function over all the vertices, starting with the "oldest" vertices.

Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.addVertex "bar"
    |> Graph.fold (\v acc -> acc ++ v) ""
--> "foobar"

size : Graph vertex -> Int

Determine the number of vertices in the graph.

Graph.size Graph.empty
--> 0


Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.addVertex "bar"
    |> Graph.size
--> 2

vertices : Graph vertex -> List vertex

Return a list of the vertices, starting with the "oldest".

Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.addVertex "bar"
    |> Graph.vertices
--> [ "foo", "bar" ]

edges : Graph vertex -> List (Edge vertex)

Return a list of the edges. Don't expect any sensible order - it's implementation defined.

Graph.empty
    |> Graph.addEdge "foo" "bar"
    |> Graph.addEdge "bar" "quux"
    |> Graph.edges
--> [ { from = "bar", to = "quux" }
    , { from = "foo", to = "bar" }
    ]

verticesAndEdges :

Graph vertex

-> { vertices : List vertex

, edges : List (Edge vertex)

}

Return a record with a list of vertices and list of edges in the graph.

Graph.empty
    |> Graph.addVertex "foo"
    |> Graph.addEdge "foo" "bar"
    |> Graph.verticesAndEdges
--> { vertices = [ "foo", "bar" ]
    , edges = [ { from = "foo", to = "bar" } ]
    }

outgoingEdges : vertex -> Graph vertex -> List vertex

Lists all vertices this vertex has edges to.

Directed - only lists the edges that go from the given vertex.

 Graph.empty
     |> Graph.outgoingEdges "foo"
 --> []


 Graph.empty
     |> Graph.addEdge "foo" "bar"
     |> Graph.addEdge "foo" "baz"
     |> Graph.addEdge "quux" "foo"
     |> Graph.outgoingEdges "foo"
 --> [ "bar", "baz" ]

edgeToComparable : Edge comparable -> ( comparable, comparable )

Transform the record into a (from, to) tuple.

Graph.edgeToComparable { from = "foo", to = "bar" }
--> ("foo", "bar")

Modules

Graph