Graph Implementation

graph.groovy

int vertices = 4
int edges = 5
int[][] edgeWeightArr = [[1,2,7],[1,4,6],[4,2,9],[4,3,8],[2,3,6]]
// LIFO
class Stack {
    int [] arr
    int top = 0
    public Stack(int size) {
        arr = new int[size]
    }
    
    def push(item) {
        if (top >= arr.size()) {
            throw Exception("Stack Full")
        }
        arr[top++] = item
    }
    
    def pop() { 
        if (top == 0 ) { 
            throw Exception("Stack Empty")
        }
        def tmp = arr[top]
        arr[top] = -1
        top--;
        return tmp;
    }
    
    def isEmpty() {
        return top == 0 ? true : false;
    }
}


// FIFO
class Queue {
    int [] arr
    int top = 0
    public Queue(int size) {
        arr = new int[size]
    }
    
    def enqueue(item) {
        if (top >= arr.size()) {
            throw Exception("Queue Full")
        }
        arr[top++] = item
    }
    
    def dequeue() { 
        if (top == 0 ) { 
            throw Exception("Queue Empty")
        }
        def tmp = arr[top]
        arr[top] = -1
        top--;
        return tmp;
    }
    
    def isEmpty() {
        return top == 0 ? true : false;
    }
}

class Pair {
    int n
    int w
    Pair(int node, int weight) {
        n = node
        w = weight
    }
    
    public String toString(){
        return "n:"+n+" w:"+w
    }
}

def graphRep(edgeWeightArr,vertices,edges,directed,list) {
    List<Pair>[] directedAdjacencyList = new List<Pair>[vertices];
    int[][] directedAdjacencyMatrix = new int[vertices][edges]
    List<Pair>[] undirectedAdjacencyList = new List<Pair>[vertices];
    int[][] undirectedAdjacencyMatrix = new int[vertices][edges]
    for (int i = 0 ; i <edges; i++) {
        int[] r = edgeWeightArr[i]
        Pair p = new Pair(r[1]-1,r[2])
        // directed
        // adjacencyList
        List<Pair> existing = directedAdjacencyList[r[0]-1]
        if (!existing) {
            existing = new ArrayList<>();
            directedAdjacencyList[r[0]-1] = existing;
        }        
        existing.add(p)
        // adjacencyMatrix
        directedAdjacencyMatrix[r[0]-1][r[1]-1] = r[2]
        
        // undirected
        // adjacencyList
        List<Pair> existing2 = undirectedAdjacencyList[r[0]-1]
        if (!existing2) {
            existing2 = new ArrayList<>();
            undirectedAdjacencyList[r[0]-1] = existing2;
        }        
        existing2.add(p)
        List<Pair> existing3 = undirectedAdjacencyList[r[1]-1]
        if (!existing3) {
            existing3 = new ArrayList<>();
            undirectedAdjacencyList[r[1]-1] = existing3;
        }
        Pair p2 = new Pair(r[0]-1,r[2])
        existing3.add(p2)
        // adjacencyMatrix
        undirectedAdjacencyMatrix[r[0]-1][r[1]-1] = r[2]
        undirectedAdjacencyMatrix[r[1]-1][r[0]-1] = r[2]
    }

    println "directedAdjacencyList "+ directedAdjacencyList
    println "directedAdjacencyMatrix "+ directedAdjacencyMatrix
    println "undirectedAdjacencyList" + undirectedAdjacencyList
    println "undirectedAdjacencyMatrix" + undirectedAdjacencyMatrix
    
    if (directed) {
        if (list) {
            return directedAdjacencyList     
        } else {
            return directedAdjacencyMatrix
        }
    } else {
        if (list) {
            return undirectedAdjacencyList
        } else {
            return undirectedAdjacencyMatrix
        }
    }
}

def bfs(adjacencyList, vertices, source, searchItem) {
    Queue q = new Queue(vertices)
    q.enqueue(source)
    int[] visited = new int[vertices]
    visited[source] = 1;
    def level = 0;
    done:
    while (!q.isEmpty()) {
        def node = q.dequeue()
        def neighbours = adjacencyList[node]
        for (def neighbour : neighbours) {
            if (neighbour.n == searchItem) {
                println "found at level -> " + level
                break done
            }
            if (visited[neighbour.n] != 1) {
                visited[neighbour.n] = 1
                q.enqueue(neighbour.n)                
            }            
        }
        level++;
    }
    println "Search Complete"
}

def dfs(adjacencyList, vertices, source, searchItem) {
    Stack s = new Stack(vertices)
    s.push(source)
    int[] visited = new int[vertices]
    visited[source] = 1;
    def level = 0;
    done:
    while (!s.isEmpty()) {
        def node = s.pop()
        def neighbours = adjacencyList[node]
        for (def neighbour : neighbours) {
            if (neighbour.n == searchItem) {
                println "found at level -> " + level
                break done
            }
            if (visited[neighbour.n] != 1) {
                visited[neighbour.n] = 1
                s.push(neighbour.n)                
            }            
        }
        level++;
    }
    println "Search Complete"
}

def g = graphRep(edgeWeightArr,vertices,edges, true, true)
bfs(g, vertices, 0, 2)
dfs(g, vertices, 0, 2)