Representing Graph Data Structure in Ballerina

This article was written using Ballerina 2201.6.0 (Swan Lake Update 6)

Link to the code :- https://github.com/prakanth97/network

A graph is a data structure that consists of a collection of nodes and edges, which represent the relationships between the nodes. Graphs are commonly used to model real-world problems, like computer networks, transportation networks, and social networks. The nodes in a graph can represent entities such as people, places, or things, while the edges represent the connections or interactions between them. The weight of an edge is a numerical value assigned to the edge, which represents some kind of cost or distance associated with traversing that edge.

Graph

Ballerina allows us to create new object types using its type definition syntax (object types). In Ballerina, an object type is a type definition without any implementation. The following example demonstrates an object type that represents a graph. It encompasses all the essential methods required to work with graphs.

public type Graph object {
    public function getGraphTable() returns GraphTb;

    public function addNode(string v);

    public function removeNode(string v) returns Node?;

    public function numberOfNodes() returns int;

    // Returns the number of nodes in the graph
    public function 'order() returns int;

    public function hasNode(string v) returns boolean;

    public function getNodes() returns string[];

    public function addEdge(string u, string v, int weight = 1);

    public function removeEdge(string u, string v) returns boolean;

    public function hasEdge(string u, string v) returns boolean;

    public function getEdgeWeight(string u, string v) returns int|error;

    // Remove all nodes and edges from the graph
    public function clear();

    public function clearEdges();

    public function isDirectedGraph() returns boolean;

    // Returns a copy of the graph
    public function copy() returns Graph;

    public function size(boolean weight = false) returns int;

    public function numberOfEdges(string? u = null, string? v = null) returns int;

    // Returns names of successors of the specific node as array
    public function successor(string u) returns string[]|error;

    // Returns all the neighbors of node u
    public function neighbors(string u) returns map<int>|error;
};

Ballerina provides a data structure called a table (table types) that can be used to store data in a structured manner. GraphTb is an example of a table type that can be utilized to store information about a graph, while Node is a record type that can be employed to represent an individual node in the graph.

public type GraphTb table<Node> key(vertex);

public type Node record {|
    readonly string vertex;
    map<int> edges = {};
|};

There are two main categories of graph.

1. Directed Graphs (Digraphs): A directed graph, also known as a digraph, is a graph in which the edges have a direction associated with them. This means the relationship between vertices is one-way, with each edge connecting a source vertex to a destination vertex. Directed graphs can be used to model systems where there is a flow or directionality involved, such as traffic flow, communication networks, or the flow of resources in a supply chain.
2. Undirected Graphs: An undirected graph is a graph in which the edges do not have any direction associated with them. This means the relationship between vertices is two-way, with each edge connecting two vertices without a specific direction. An undirected graph can be used to model systems where there is no inherent directionality involved, such as social networks, friendship graphs, or computer networks.

Ballerina allows implementing interfaces, similar to Java, by using object type inclusion. Below is an implementation of a directed graph.

public class DiGraph {
    *Graph;

    private GraphTb graphtb = table [];

    public function getGraphTable() returns GraphTb {
        return self.graphtb;
    }

    public function addNode(string v) {
        if !self.graphtb.hasKey(v) {
            self.graphtb.add({vertex: v});
        }
    }

    public function removeNode(string v) returns Node? {
        if self.graphtb.hasKey(v) {
            Node n = self.graphtb.remove(v);
            foreach string edge in n.edges.keys() {
                Node edgeNode = self.graphtb.get(edge);
                _ = edgeNode.edges.remove(v);
            }
            return n;
        }
        return;
    }

    public function numberOfNodes() returns int {
        return self.graphtb.length();
    }

    public function 'order() returns int {
        return self.graphtb.length();
    }

    public function hasNode(string v) returns boolean {
        return self.graphtb.hasKey(v);
    }

    public function getNodes() returns string[] {
        return self.graphtb.keys();
    }

    public function addEdge(string u, string v, int weight = 1) {
        if !self.graphtb.hasKey(u) {
            self.addNode(u);
        }

        if !self.graphtb.hasKey(v) {
            self.addNode(v);
        }

        Node n1 = self.graphtb.get(u);
        n1.edges[v] = weight;
    }

    public function removeEdge(string u, string v) returns boolean {
        if !self.graphtb.hasKey(u) {
            return false;
        }

        if !self.graphtb.hasKey(v) {
            return false;
        }

        Node n1 = self.graphtb.get(u);
        return n1.edges.removeIfHasKey(v) !is ();
    }

    public function hasEdge(string u, string v) returns boolean {
        if self.graphtb.hasKey(u) {
            return self.graphtb.get(u).edges.hasKey(v);
        }
        return false;
    }

    public function getEdgeWeight(string u, string v) returns int|error {
        if self.graphtb.hasKey(u) {
            int? weight = self.graphtb.get(u).edges[v];
            if weight is int {
                return weight;
            }
            return error(string `${u} doesn't have edge ${v}`);
        }
        return error(string `${u} is not exist`);
    }

    public function clear() {
        self.graphtb.removeAll();
    }

    public function clearEdges() {
        foreach Node node in self.graphtb {
            node.edges.removeAll();
        }
    }

    public function isDirectedGraph() returns boolean {
        return true;
    }

    public function copy() returns DiGraph {
        DiGraph g = new ();
        GraphTb graphtb = g.getGraphTable();
        foreach Node node in self.graphtb {
            Node cloneNode = node.clone();
            graphtb.add(cloneNode);
        }
        return g;
    }

    public function size(boolean weight = false) returns int {
        int edgeCountOrWeight = 0;

        if weight {
            foreach Node node in self.graphtb {
                edgeCountOrWeight += node.edges.reduce(
                    function(int total, int value) returns int {
                    return total + value;
                }, 0);
            }
        } else {
            foreach Node node in self.graphtb {
                edgeCountOrWeight += node.edges.length();
            }
        }
        return edgeCountOrWeight;
    }

    public function numberOfEdges(string? u = null, string? v = null) returns int {
        if u is () && v is () {
            return self.size();
        }

        if u is () || v is () {
            return 0;
        }
        return self.hasEdge(u, v) ? 1 : 0;
    }

    public function successor(string u) returns string[]|error {
        if !self.graphtb.hasKey(u) {
            return error(string `${u} not found`);
        }

        return self.graphtb.get(u).edges.keys();
    }

    public function neighbors(string u) returns map<int>|error {
        if !self.graphtb.hasKey(u) {
            return error(string `${u} not found`);
        }

        return self.graphtb.get(u).edges;
    }

    public function predecessor(string u) returns string[]|error {
        string[] predecessors = [];

        if !self.graphtb.hasKey(u) {
            return error(string `${u} not found`);
        }

        foreach Node node in self.graphtb {
            if node.edges.hasKey(u) {
                predecessors.push(node.vertex);
            }
        }
        return predecessors;
    }

    public function inDegree(string u) returns int|error {
        if !self.graphtb.hasKey(u) {
            return error(string `${u} not found`);
        }

        int count = 0;
        foreach Node node in self.graphtb {
            if node.edges.hasKey(u) {
                count += 1;
            }
        }
        return count;
    }

    public function outDegree(string u) returns int|error {
        if !self.graphtb.hasKey(u) {
            return error(string `${u} not found`);
        }

        return self.graphtb.get(u).edges.length();
    }
}

Example:

Directed graph

import ballerina/io;

public function main() {
    Graph A = new DiGraph();

    A.addEdge("1", "2", 2);
    A.addEdge("2", "3", 2);
    A.addEdge("3", "4", 2);
    A.addEdge("5", "1", 1);
    A.addEdge("5", "4", 2);
    A.addNode("6");
    
    // `A` is an directed graph. So, 1 -> 5 does not exist for `A`.
    io:println(A.getEdgeWeight("1", "5")); // output : error("1 doesn't have edge 5")

    io:println(A.getEdgeWeight("5", "1")); // output : 1

    // only `4` can be a successor of `3`.
    io:println(A.successor("3")); // output : ["4"]
}

Below is the implementation of the undirected graph.

public class UnDiGraph {
    *Graph;

    private GraphTb graphtb = table [];

    public function getGraphTable() returns GraphTb {
        return self.graphtb;
    }

    public function addNode(string v) {
        if !self.graphtb.hasKey(v) {
            self.graphtb.add({vertex: v});
        }
    }

    public function removeNode(string v) returns Node? {
        if self.graphtb.hasKey(v) {
            Node n = self.graphtb.remove(v);
            foreach string edge in n.edges.keys() {
                Node edgeNode = self.graphtb.get(edge);
                _ = edgeNode.edges.remove(v);
            }
            return n;
        }
        return;
    }

    public function numberOfNodes() returns int {
        return self.graphtb.length();
    }

    public function 'order() returns int {
        return self.graphtb.length();
    }

    public function hasNode(string v) returns boolean {
        return self.graphtb.hasKey(v);
    }

    public function getNodes() returns string[] {
        return self.graphtb.keys();
    }

    public function addEdge(string u, string v, int weight = 1) {
        if !self.graphtb.hasKey(u) {
            self.addNode(u);
        }

        if !self.graphtb.hasKey(v) {
            self.addNode(v);
        }

        Node n1 = self.graphtb.get(u);
        n1.edges[v] = weight;

        Node n2 = self.graphtb.get(v);
        n2.edges[u] = weight;
    }

    public function removeEdge(string u, string v) returns boolean {
        if !self.graphtb.hasKey(u) {
            return false;
        }

        if !self.graphtb.hasKey(v) {
            return false;
        }

        Node n1 = self.graphtb.get(u);
        Node n2 = self.graphtb.get(v);
        return n1.edges.removeIfHasKey(v) !is () && n2.edges.removeIfHasKey(u) !is ();
    }

    public function hasEdge(string u, string v) returns boolean {
        if self.graphtb.hasKey(u) {
            return self.graphtb.get(u).edges.hasKey(v);
        }
        return false;
    }

    public function getEdgeWeight(string u, string v) returns int|error {
        if self.graphtb.hasKey(u) {
            int? weight = self.graphtb.get(u).edges[v];
            if weight is int {
                return weight;
            }
            return error(string `${u} doesn't have edge ${v}`);
        }
        return error(string `${u} is not exist`);
    }

    public function clear() {
        self.graphtb.removeAll();
    }

    public function clearEdges() {
        foreach Node node in self.graphtb {
            node.edges.removeAll();
        }
    }

    public function isDirectedGraph() returns boolean {
        return false;
    }

    public function copy() returns UnDiGraph {
        UnDiGraph g = new ();
        GraphTb graphtb = g.getGraphTable();
        foreach Node node in self.graphtb {
            Node cloneNode = node.clone();
            graphtb.add(cloneNode);
        }
        return g;
    }

    public function size(boolean weight = false) returns int {
        int edgeCountOrWeight = 0;
        string[] visitedNode = [];

        if weight {
            foreach Node node in self.graphtb {
                visitedNode.push(node.vertex);
                foreach string edge in node.edges.keys() {
                    if visitedNode.indexOf(edge) is int {
                        continue;
                    }
                    edgeCountOrWeight += node.edges.get(edge);
                }
            }
        } else {
            foreach Node node in self.graphtb {
                visitedNode.push(node.vertex);
                foreach string edge in node.edges.keys() {
                    if visitedNode.indexOf(edge) is int {
                        continue;
                    }
                    edgeCountOrWeight += 1;
                }
            }
        }
        return edgeCountOrWeight;
    }

    public function numberOfEdges(string? u = null, string? v = null) returns int {
        if u is () && v is () {
            return self.size();
        }

        if u is () || v is () {
            return 0;
        }
        return self.hasEdge(u, v) ? 1 : 0;
    }

    public function successor(string u) returns string[]|error {
        if !self.graphtb.hasKey(u) {
            return error(string `${u} not found`);
        }

        return self.graphtb.get(u).edges.keys();
    }

    public function neighbors(string u) returns map<int>|error {
        if !self.graphtb.hasKey(u) {
            return error(string `${u} not found`);
        }

        return self.graphtb.get(u).edges;
    }
}

Example:

Undirected graph

import ballerina/io;

public function main() {
    Graph A = new UnDiGraph();

    A.addEdge("1", "2", 2);
    A.addEdge("2", "3", 2);
    A.addEdge("3", "4", 2);
    A.addEdge("5", "1", 1);
    A.addEdge("5", "4", 2);
    A.addNode("6");
    
    // `A` is an undirected graph. So, 1 -> 5 exist for `A`.
    io:println(A.getEdgeWeight("1", "5")); // output : 1

    // `2, 4` can be a successor because there is no direction between nodes.
    io:println(A.successor("3")); // output : ["2","4"]
}

References

1. https://ballerina.io/learn/by-example/
2. https://networkx.org/