[ADSx] - GraphFun

import java.util.Hashtable;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Stack;


public class GraphsFun {

    /**
     * Count all possible walks from a source to a destination with exactly k edges
     * https://www.geeksforgeeks.org/count-possible-paths-source-destination-exactly-k-edges/
     */

    static final int V = 4; //Number of vertices

    // A naive recursive function to count walks
    // from u to v with k edges
    public static int countwalks(int graph[][], int u, int v, int k) {
        // Base cases
        if (k == 0 && u == v) return 1;
        if (k == 1 && graph[u][v] == 1) return 1;
        if (k <= 0) return 0;

        // Initialize result
        int count = 0;

        // Go to all adjacents of u and recur
        for (int i = 0; i < V; i++)
            if (graph[u][i] == 1)  // Check if is adjacent of u
                count += countwalks(graph, i, v, k - 1);

        return count;
    }

    static final int INF = Integer.MAX_VALUE;

    // A naive recursive function to count walks from u to v
    // with k edges
    public static int shortestPath(int graph[][], int u, int v, int k) {
        // Base cases
        if (k == 0 && u == v) return 0;
        if (k == 1 && graph[u][v] != INF) return graph[u][v];
        if (k <= 0) return INF;

        // Initialize result
        int res = INF;

        // Go to all adjacents of u and recur
        for (int i = 0; i < V; i++) {
            if (graph[u][i] != INF && u != i && v != i) {
                int rec_res = shortestPath(graph, i, v, k - 1);
                if (rec_res != INF)
                    res = Math.min(res, graph[u][i] + rec_res);
            }
        }
        return res;
    }

    public static void main(String args[]) {
        int graph[][] = new int[][]{
                {0, 1, 1, 1},
                {0, 0, 0, 1},
                {0, 0, 0, 1},
                {0, 0, 0, 0}
        };
        int u = 0, v = 3, k = 2;
        System.out.println(countwalks(graph, u, v, k));

        graph = new int[][]{
                {0, 10, 3, 2},
                {INF, 0, INF, 7},
                {INF, INF, 0, 6},
                {INF, INF, INF, 0}
        };
        System.out.println("Weight of the shortest path is " +
                shortestPath(graph, u, v, k));
    }
}


/**
 * adjList unweighted directed
 */
class SLLNode<E> {
    protected E element;
    protected SLLNode<E> succ;

    public SLLNode(E elem, SLLNode<E> succ) {
        this.element = elem;
        this.succ = succ;
    }

    @Override
    public String toString() {
        return element.toString();
    }
}

interface Queue<E> {

    // Elementi na redicata se objekti od proizvolen tip.

    // Metodi za pristap:

    public boolean isEmpty();
    // Vrakja true ako i samo ako redicata e prazena.

    public int size();
    // Ja vrakja dolzinata na redicata.

    public E peek();
    // Go vrakja elementot na vrvot t.e. pocetokot od redicata.

    // Metodi za transformacija:

    public void clear();
    // Ja prazni redicata.

    public void enqueue(E x);
    // Go dodava x na kraj od redicata.

    public E dequeue();
    // Go otstranuva i vrakja pochetniot element na redicata.

}

class LinkedQueue<E> implements Queue<E> {

    // Redicata e pretstavena na sledniot nacin:
    // length go sodrzi brojot na elementi.
    // Elementite se zachuvuvaat vo jazli dod SLL
    // front i rear se linkovi do prviot i posledniot jazel soodvetno.
    SLLNode<E> front, rear;
    int length;

    // Konstruktor ...

    public LinkedQueue() {
        clear();
    }

    public boolean isEmpty() {
        // Vrakja true ako i samo ako redicata e prazena.
        return (length == 0);
    }

    public int size() {
        // Ja vrakja dolzinata na redicata.
        return length;
    }

    public E peek() {
        // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
        if (front == null)
            throw new NoSuchElementException();
        return front.element;
    }

    public void clear() {
        // Ja prazni redicata.
        front = rear = null;
        length = 0;
    }

    public void enqueue(E x) {
        // Go dodava x na kraj od redicata.
        SLLNode<E> latest = new SLLNode<E>(x, null);
        if (rear != null) {
            rear.succ = latest;
            rear = latest;
        } else
            front = rear = latest;
        length++;
    }

    public E dequeue() {
        // Go otstranuva i vrakja pochetniot element na redicata.
        if (front != null) {
            E frontmost = front.element;
            front = front.succ;
            if (front == null) rear = null;
            length--;
            return frontmost;
        } else
            throw new NoSuchElementException();
    }

}

class GraphNode<E> {
    private int index;//index (reden broj) na temeto vo grafot
    private E info;
    private LinkedList<GraphNode<E>> neighbors;

    public GraphNode(int index, E info) {
        this.index = index;
        this.info = info;
        neighbors = new LinkedList<GraphNode<E>>();
    }

    boolean containsNeighbor(GraphNode<E> o) {
        return neighbors.contains(o);
    }

    void addNeighbor(GraphNode<E> o) {
        neighbors.add(o);
    }

    void removeNeighbor(GraphNode<E> o) {
        if (neighbors.contains(o))
            neighbors.remove(o);
    }

    @Override
    public String toString() {
        String ret = "INFO:" + info + " SOSEDI:";
        for (int i = 0; i < neighbors.size(); i++)
            ret += neighbors.get(i).info + " ";
        return ret;

    }

    @Override
    public boolean equals(Object obj) {
        @SuppressWarnings("unchecked")
        GraphNode<E> pom = (GraphNode<E>) obj;
        return (pom.info.equals(this.info));
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public E getInfo() {
        return info;
    }

    public void setInfo(E info) {
        this.info = info;
    }

    public LinkedList<GraphNode<E>> getNeighbors() {
        return neighbors;
    }

    public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
        this.neighbors = neighbors;
    }


}

class Graph<E> {

    int num_nodes;
    GraphNode<E> adjList[];

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes, E[] list) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            adjList[i] = new GraphNode<E>(i, list[i]);
    }

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
    }

    int adjacent(int x, int y) {
        // proveruva dali ima vrska od jazelot so
        // indeks x do jazelot so indeks y
        return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
    }

    void addEdge(int x, int y) {
        // dodava vrska od jazelot so indeks x do jazelot so indeks y
        if (!adjList[x].containsNeighbor(adjList[y])) {
            adjList[x].addNeighbor(adjList[y]);
        }
    }

    void deleteEdge(int x, int y) {
        adjList[x].removeNeighbor(adjList[y]);
    }

    void dfsSearch(int node) {
        // visited array filled with false
        boolean visited[] = new boolean[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            visited[i] = false;

        dfsRecursive(node, visited);
    }

    void dfsRecursive(int node, boolean visited[]) {
        // set currently searched node to true
        visited[node] = true;
        // print it
        System.out.println(node + ": " + adjList[node].getInfo());

        // for all of its neighbors
        for (int i = 0; i < adjList[node].getNeighbors().size(); i++) {
            GraphNode<E> pom = adjList[node].getNeighbors().get(i);
            // if you find one that isn't visited, recursively do it for it, the neighbor
            if (!visited[pom.getIndex()])
                dfsRecursive(pom.getIndex(), visited);
        }
    }

    void dfsNonrecursive(int node) {
        // visted[] array
        boolean visited[] = new boolean[num_nodes];
        // visted[] array fill with false
        for (int i = 0; i < num_nodes; i++)
            visited[i] = false;
        // starting node set to visited
        visited[node] = true;
        System.out.println(node + ": " + adjList[node].getInfo());

        // start pushed in stack
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(node);

        GraphNode<E> topmost;

        while (!stack.isEmpty()) {
            // get topmost of stack
            topmost = adjList[stack.peek()];
            GraphNode<E> neighbor = null;
            // loop through all of topmosts neighbors
            for (int i = 0; i < topmost.getNeighbors().size(); i++) {
                neighbor = topmost.getNeighbors().get(i);
                // if you find a neighbor which is not visited, the first one
                if (!visited[neighbor.getIndex()])
                    break;
            }
            if (neighbor != null && !visited[neighbor.getIndex()]) {
                // mark that unvisited neighbor as visited
                visited[neighbor.getIndex()] = true;
                // print it and push it in the stack
                System.out.println(neighbor.getIndex() + ": " + neighbor.getInfo());
                stack.push(neighbor.getIndex());
            } else {
                stack.pop();
            }
        }

    }

    void bfs(int node) {

        // visited array filled with false
        boolean visited[] = new boolean[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            visited[i] = false;

        // mark start as true
        visited[node] = true;
        // print it
        System.out.println(node + ": " + adjList[node].getInfo());

        // enqueue the start
        Queue<Integer> q = new LinkedQueue<Integer>();
        q.enqueue(node);

        GraphNode<E> rearmost;

        while (!q.isEmpty()) {
            // dequeue the rear-most
            rearmost = adjList[q.dequeue()];
            GraphNode<E> neighbor = null;

            // for all of its neighbors
            for (int i = 0; i < rearmost.getNeighbors().size(); i++) {
                neighbor = rearmost.getNeighbors().get(i);

                // find the first neighbor that isn't visited
                if (!visited[neighbor.getIndex()]) {
                    // mark it as visited
                    visited[neighbor.getIndex()] = true;
                    System.out.println(neighbor.getIndex() + ": " + neighbor.getInfo());
                    // enqueue that neighbor
                    q.enqueue(neighbor.getIndex());
                }
            }
        }

    }

    @Override
    public String toString() {
        String ret = new String();
        for (int i = 0; i < this.num_nodes; i++)
            ret += i + ": " + adjList[i] + "\n";
        return ret;
    }

}

class GraphMaze {

    int num_nodes; // broj na jazli
    int adjMat[][];  // matrica na sosednost

    public GraphMaze(int num_nodes) {
        this.num_nodes = num_nodes;
        adjMat = new int[num_nodes][num_nodes];

        for (int i = 0; i < this.num_nodes; i++)
            for (int j = 0; j < this.num_nodes; j++)
                adjMat[i][j] = 0;
    }

    public GraphMaze(int num_nodes, int[][] adjMat) {
        this.num_nodes = num_nodes;
        this.adjMat = adjMat;
    }


    int adjacent(int x, int y) {  // proveruva dali ima vrska od jazelot so indeks x do jazelot so indeks y
        return (adjMat[x][y] != 0) ? 1 : 0;
    }

    void addEdge(int x, int y) {  // dodava vrska megu jazlite so indeksi x i y
        adjMat[x][y] = 1;
        adjMat[y][x] = 1;
    }

    void deleteEdge(int x, int y) {
        // ja brise vrskata megu jazlite so indeksi x i y
        adjMat[x][y] = 0;
        adjMat[y][x] = 0;
    }

    public int getNum_nodes() {
        return num_nodes;
    }

    public void setNum_nodes(int num_nodes) {
        this.num_nodes = num_nodes;
    }


    @Override
    public String toString() {
        String ret = "  ";
        for (int i = 0; i < num_nodes; i++)
            ret += i + " ";
        ret += "\n";
        for (int i = 0; i < num_nodes; i++) {
            ret += i + " ";
            for (int j = 0; j < num_nodes; j++)
                ret += adjMat[i][j] + " ";
            ret += "\n";
        }
        return ret;
    }


}


class Maze {

    //Kje se koristi nenasocen graf implementiran so martica na sosednost
    //za pretstavuvanje na lavirintot
    //Teminjata vo grafot se samo indeksi
    //Iminjata na teminjata se preveduvaat vo broevi preku hash tabela
    //T.e. na pr. 1,1 kje se prevede vo 1 (1,1 kje se zacuva kako string)

    GraphMaze g;
    int start_node; //indeks temeto koe e vlez
    int end_node; //indeks na temeto koe e izlez

    Hashtable<String, Integer> h;

    public Maze() {
        h = new Hashtable<String, Integer>();
    }

    void generateGraph(int rows, int columns, String[] in) {

        int num_nodes = 0;

        String key;

        for (int i = 1; i < rows - 1; i++) {
            for (int j = 1; j < columns - 1; j++) {
                if (in[i].charAt(j) != '#') {
                    key = i + "," + j;
                    h.put(key, num_nodes);
                    if (in[i].charAt(j) == 'S')
                        start_node = num_nodes;
                    if (in[i].charAt(j) == 'E')
                        end_node = num_nodes;
                    num_nodes++;
                }
            }
        }

        g = new GraphMaze(num_nodes);

        int x;
        int y;
        //generiranje na matrica na sosednost
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                if (in[i].charAt(j) != '#') {
                    //dali ima teme pred nego
                    if (in[i].charAt(j - 1) != '#') {
                        x = h.get(i + "," + j);
                        y = h.get(i + "," + (j - 1));
                        g.addEdge(x, y);
                    }
                    //dali ima teme posle nego
                    if (in[i].charAt(j + 1) != '#') {
                        x = h.get(i + "," + j);
                        y = h.get(i + "," + (j + 1));
                        g.addEdge(x, y);
                    }
                    //dali ima teme nad nego
                    if (in[i - 1].charAt(j) != '#') {
                        x = h.get(i + "," + j);
                        y = h.get((i - 1) + "," + j);
                        g.addEdge(x, y);
                    }
                    //dali ima teme pod nego
                    if (in[i + 1].charAt(j) != '#') {
                        x = h.get(i + "," + j);
                        y = h.get((i + 1) + "," + j);
                        g.addEdge(x, y);
                    }
                }
            }
        }
    }

    // Essentially DFS Non-Recursive for a given adjacency matrix
    void findPath() {
        boolean visited[] = new boolean[g.getNum_nodes()];
        for (int i = 0; i < g.getNum_nodes(); i++)
            visited[i] = false;
        visited[start_node] = true;
        Stack<Integer> s = new Stack<>();
        s.push(start_node);

        int pom;
        while (!s.isEmpty() && s.peek() != end_node) {
            pom = s.peek();
            int pom1 = pom;
            for (int i = 0; i < g.getNum_nodes(); i++) {
                if (g.adjacent(pom, i) == 1) {
                    pom1 = i;
                    if (!visited[i])
                        break;
                }
            }
            if (!visited[pom1]) {
                visited[pom1] = true;
                s.push(pom1);
            } else
                s.pop();
        }
        if (s.isEmpty())
            System.out.println("Nema reshenie");
        else {
            Stack<Integer> os = new Stack<Integer>();
            while (!s.isEmpty())
                os.push(s.pop());
            while (!os.isEmpty())
                System.out.println(os.pop());
        }
    }


    public static void main(String args[]) {
        Maze m = new Maze();
        int rows = 6;
        int columns = 6;
        String[] in = new String[rows];

        in[0] = "######";
        in[1] = "# # ##";
        in[2] = "# # S#";
        in[3] = "# # ##";
        in[4] = "# E  #";
        in[5] = "######";

        m.generateGraph(rows, columns, in);
        System.out.println("Pateka:");
        m.findPath();
    }

}