← Back to the index page

Graph

The graph is a data structure that represents vertices connected by edges and the relationship between them. The graph is one of the more fundamental and advanced data structures. Graphs are widely used for pathfinding, detecting cycles, making maps, social and computer networking, etc.

In mathematics, there is a large discipline—graph theory.

Figure 01: Graph Example

Anatomy of the graph

Graph operations

Usually, DFS (Deep-First Search) and BFS (Breadth-First Search) methods are used to search and traverse the graph. For even more complex cases, there might be more advanced algorithms (e.g., taking into account the weight of vertices).

Types of graphs

There are lots of graph types, some of which are pretty rarely used, especially in Lua. language, because Lua is an interpreted language and might have performance issues. For analysis of the graph, it is better to use more performant languages like C/C++, Rust, Go, Java, etc., and use computers with high calculation power.

Finite Graphs

It is a graph with a finite number of vertices and edges. The number of edges and vertices can be calculated.

Finite Graph

Infinite Graph

It is a graph with infinite numbers of vertices and edges. The size of the graph cannot be calculated and is infinite.

Infinite Graph

Trivial Graph:

It is the simplest graph, with only one vertex and no edges. Usually, The trial graph is the first step when more complex graphs start to build. Later, more edges and vertices can be added.

Trivial Graph

Simple Graph

It is a graph that contains only one edge between the pair of vertices.

Simple Graph

Multi Graph

Any graph that contains some parallel edges but doesn’t contain any self-loops. Maps are a good example of multi-graphs, where you can achieve point B from point A in different ways.

Multi Graph

Null Graph

It is a graph where all vertices are isolated and have no edges. There is no connection between vertices.

Null Graph

Complete (Full) Graph

A graph with n vertices is called a complete graph if one vertex is attached with n-1 edges or the rest of the vertices in the graph. In other words, each vertex is connected to others with one edge. A pentagram is an example of the complete graph.

Complete Graph

Pseudo Graph

A graph with a self-loop and multiple edges is called a pseudo-graph. In comparison to a simple graph, a simple graph does not allow loops.

Pseudo Graph

Regular Graph

A graph is regular if all vertices are of equal degree. In regular graphs, every vertex has the same number of edges or neighbors. All complete graphs are regular.

Regular Graph

Bipartite Graph

A graph G=(V, E) is a bipartite graph where its vertices set V(G) can be partitioned into two non-empty disjoint subsets, V1(G) and V2(G) in such a way that each edge of E(G) has one end in V1(G) and another end in V2(G). The partition V1 ∪ V2 = V is called the bipartite of G.

Here in the figure: V1(G)={C, D, E, F} and V2(G)={A, B}

Bipartite Graph

Labeled Graph

It is any graph where vertices and/or edges have labels, dates, weights, or any other kind of label.

Labeled Graph

Directed Graph (Digraph)

The ordered pair of (Vi, Vj) means an edge between Vi and Vij with an arrow directed from Vi to Vj.

Edges in figure: E1(A, B), E2(B, C), E3(C, D), E4(D, E), E5(B, E), E6(B, D)

Directed Graph

Subgraph

A graph G1=(V1, E1) is called a subgraph of a graph G(V, E) if V1(G) is a subset of V(G) and E1(G) is a subset of E(G) such that each edge of G1 has same end vertices as in G. In other words, a subgraph is a part of a graph.

Mathematical equivalent: G1(V1, E1) ⊆ G(V, E) or vice versa supergraph G(V, E) ⊇ G1(V1, E1).

Subgraphs Examples

Connected and Disconnected Graph

The graph is connected if there is at least one path between every pair of vertices, otherwise the graph is disconnected.

Connected Graph Connected Graph

Disconnected Graph Disconnected Graph

Cyclic Graph

In a cyclic graph, the number of vertices should be more than 3, otherwise cyclic graph is impossible.

Common rule

Vertices: V1, V2…Vn

Edges: (V1, V2), (V2, V3), (V3, V4)…(Vn, Vn+1)

Cyclic Graph

Graph class implementation in Lua

Here is a simple implementation of the generic graph with some basic methods.

Class implementation with OOP principles and annotations.

Methods implemented:

Warning

Due to Lua language features in the implementation below a graph’s vertex cannot be nil.

Tip

In the large graphs, there might be issues with performance using Graph:BFS() method. Due to implementation uses table module. To avoid performance issues with elements shifting try Queue class.

Graph.lua

---@class Graph
---@field public adjencyList table
---@field public vertices table
---@field private _size number
local Graph = {}
Graph.__index = Graph

---Creates a new graph and returns the pointer // to it.
---@return Graph
function Graph:new()
    local t = {
        _size = 0,
        vertices = {},
        adjencyList = {},
    }
    return setmetatable(t, self)
end

---Adds 2 vertices and an edge between them.
---@param u any
---@param v any
function Graph:addEdge(u, v)
    self:addVertices(u, v)
    self.adjencyList[u] = {
        next = self.adjencyList[u],
        value = v,
    }
end

---Adds vertices to the graph, also create adjacency list for each
---vertex. Later adjacency list can be empty, if vertex does not connect
---to any other vertices.
---@param ...any
function Graph:addVertices(...)
    for _, v in pairs({ ... }) do
        if not self.vertices[v] then
            self._size = self._size + 1
        end
        self.vertices[v] = (self.vertices[v] or 0) + 1
    end
end

---Gets number of vertices in the graph.
---@return number
function Graph:size()
    return self._size
end

---Len gets number of vertices in the graph.
---@return boolean
function Graph:isEmpty()
    return self._size == 0
end

---DFS (Deep-First Search) is an algorithm for searching all vertices
---of the graph or tree data structure. Visiting all rtices of the
---graph. Returns table of vertices in the order or visiting.
---@param v any
---@param fn? fun(vert: any) Callback when visiting the vertex.
---@return table
function Graph:DFS(v, fn)
    local path = {}
    if not self:containsVertex(v) then
        warn(string.format("%s is not in the graph", v))
        return path
    end
    local stack, visited, instack = {}, {}, {}
    stack[#stack + 1] = v
    instack[v] = true

    while #stack > 0 do
        local c = stack[#stack]
        stack[#stack] = nil
        instack[c] = nil
        visited[c] = true
        path[#path + 1] = c
        if fn then
            fn(c)
        end
        local li = self.adjencyList[c]
        while li ~= nil do
            local val = li.value
            if not visited[val] and not instack[val] then
                stack[#stack + 1] = val
                instack[val] = true
            end
            li = li.next
        end
    end
    return path
end

---BFS (Breadth-First Search) is an algorithm for searching all vertices
---of the graph or tree data structure. Visiting all vertices of the graph.
---Returns table of vertices in the order or visiting.
---@param v any
---@param fn? fun(vert: any) Callback when visiting the vertex.
---@return table
function Graph:BFS(v, fn)
    local path = {}
    if not self:containsVertex(v) then
        warn(string.format("%s is not in the graph", v))
        return path
    end
    local queue, visited, inqueue = {}, {}, {}
    table.insert(queue, 1, v)
    inqueue[v] = true

    while #queue > 0 do
        local c = queue[1]
        table.remove(queue, 1)
        inqueue[c] = nil
        visited[c] = true
        path[#path + 1] = c
        if fn then
            fn(c)
        end
        local li = self.adjencyList[c]
        while li ~= nil do
            local val = li.value
            if not visited[val] and not inqueue[val] then
                queue[#queue + 1] = val
                inqueue[val] = true
            end
            li = li.next
        end
    end
    return path
end

---Calculates and returns the adjacency matrix of the graph.
---@return table
function Graph:calculateAdjacencyMatrix()
    local matrix = {}
    for u, _ in pairs(self.vertices) do
        matrix[u] = {}
        for v, _ in pairs(self.vertices) do
            matrix[u][v] = 0
            local li = self.adjencyList[u]
            while li ~= nil do
                matrix[u][li.value] = 1
                li = li.next
            end
        end
    end
    return matrix
end

---Checks is graph is bipartite.
---@return boolean
function Graph:isBipartite()
    local queue = {}
    local blue, red = -1, 0

    -- "Paint" the graph
    local colors = {}
    for k, _ in pairs(self.vertices) do
        colors[k] = blue
    end

    local start
    for k in pairs(self.vertices) do
        start = k
        break
    end
    colors[start] = red
    table.insert(queue, 1, start)

    while #queue > 0 do
        local v = queue[1]
        table.remove(queue, 1)
        local li = self.adjencyList[v]
        while li ~= nil do
            local u = li.value
            if colors[u] == colors[v] then
                return false
            end
            if colors[u] == blue then
                colors[u] = 1 - colors[u]
                table.insert(queue, 1, u)
            end
            li = li.next
        end
    end
    return true
end

---@return boolean
function Graph:isTrivial()
    return #self.vertices == 1
end

---Checks the graph contains vertex v.
---@param v any
---@return boolean
function Graph:containsVertex(v)
    return not not self.vertices[v]
end

return Graph

Usage of Graph class

local graph = Graph:new()
graph:addEdge("A", "B")
graph:addEdge("A", "D")
graph:addEdge("B", "A")
graph:addEdge("B", "C")
graph:addEdge("B", "D")
graph:addEdge("C", "B")
graph:addEdge("C", "D")
graph:addEdge("C", "G")
graph:addEdge("D", "A")
graph:addEdge("D", "B")
graph:addEdge("D", "C")
graph:addEdge("D", "E")
graph:addEdge("E", "D")
graph:addEdge("E", "F")
graph:addEdge("F", "E")
graph:addEdge("F", "G")
graph:addEdge("G", "C")
graph:addEdge("G", "F")
graph:addEdge("G", "H")
graph:addEdge("H", "G")
graph:addEdge("H", "I")
graph:addEdge("H", "J")
graph:addEdge("I", "H")
graph:addEdge("J", "H")
graph:addEdge("J", "K")
graph:addEdge("K", "J")

local t = {}
graph:DFS("A", function(v)
    t[#t + 1] = v
end)
print(table.concat(t, "-")) --> A-B-C-G-F-E-H-I-J-K-D

t = {}
graph:BFS("A", function(v)
    t[#t + 1] = v
end)
print(table.concat(t, "-")) --> A-D-B-E-C-F-G-H-J-I-K

-- Check if a graph is bipartite
local biparteGraph = Graph:new()
biparteGraph:addEdge("A", "B")
biparteGraph:addEdge("A", "C")
biparteGraph:addEdge("B", "D")
biparteGraph:addEdge("C", "D")
biparteGraph:addEdge("D", "E")
biparteGraph:addEdge("E", "F")
biparteGraph:addEdge("E", "G")
biparteGraph:addEdge("E", "H")
biparteGraph:addEdge("G", "I")
print(biparteGraph:isBipartite()) --> true

References

Feedback

For feedback, please check the contacts section. Before writing, please specify where you came from and who you are. Sometimes spammers go insane. Thank you in advance for your understanding.

← Back to the index page