How are directed and undirected graphs represented and manipulated in functional programming?

In functional programming, directed and undirected graphs are represented as adjacency lists or matrices and manipulated using pure functions.

In more detail, a graph is a set of vertices and edges where each edge connects a pair of vertices. In a directed graph, edges have a direction, from one vertex to another, while in an undirected graph, there is no direction. In functional programming, these graphs are typically represented using data structures like adjacency lists or matrices.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbours of a vertex in the graph. This representation is efficient in terms of storage because it only needs to store the vertices that are connected by an edge. For example, in Haskell, an adjacency list can be represented as a list of tuples, where the first element of the tuple is the vertex and the second element is a list of its neighbours.

An adjacency matrix, on the other hand, is a 2D array of size V x V where V is the number of vertices in the graph. The value of an entry A[i][j] is either 1 or 0 depending on whether there is an edge from vertex i to vertex j. This representation is efficient when the graph is dense, that is, when the number of edges is close to the number of vertices squared.

Manipulating these graphs in functional programming involves using pure functions, which are functions that do not have side effects and always produce the same output for the same input. For example, to add a vertex in a graph represented by an adjacency list, you would create a new list that includes the new vertex and all the existing vertices and edges. Similarly, to remove a vertex, you would create a new list that includes all the vertices and edges except the ones related to the vertex to be removed. This approach ensures that the original graph is not modified, which is a key principle in functional programming.