import java.util.ArrayList;

class Graf {

    private ArrayList<Node> listeNoder;
    private ArrayList<Kant> listeKanter;


    public Graf(){
        listeNoder = new ArrayList<Node>();
        listeKanter = new ArrayList<Kant>();
    }


    public void finnVei(int fraTall, int tilTall){

        Node fraNode = null;
        Node tilNode = null;

        for (Node denne : listeNoder){
            if (denne.tall == fraTall){
                fraNode = denne;
            }
            if (denne.tall == tilTall){
                tilNode = denne;
            }
        }

        if (fraNode == null || tilNode == null){
            System.out.println("En av nodene eksisterer ikke!");
            return;
        }

        ArrayList<Node> besokt = new ArrayList<Node>();
        finnVeiRek(fraNode, tilNode, "Start: " + fraNode, besokt);
    }


    public void finnVeiRek(Node gjeldende, Node til, String vei, ArrayList<Node> besokt){

        if (gjeldende == til){
            System.out.print("FANT EN VEI! ");
            System.out.println(vei);
        }
        besokt.add(gjeldende);
        for (Node nabo : gjeldende.listeNaboer){

            if (!besokt.contains(nabo)){
                finnVeiRek(nabo, til, vei + " -> " + nabo, besokt);
            }
        }
        besokt.remove(gjeldende);
    }


    public void leggTilNode(int tall){
        Node ny = new Node(tall);
        listeNoder.add(ny);
    }

    public void leggTilKant(int fraTall, int tilTall){

        Node fraNode = null;
        Node tilNode = null;

        for (Node denne : listeNoder){
            if (denne.tall == fraTall){
                fraNode = denne;
            }
            if (denne.tall == tilTall){
                tilNode = denne;
            }
        }

        if (fraNode == null || tilNode == null){
            System.out.println("En av nodene eksisterer ikke!");
            return;
        }

        Kant ny = new Kant(fraNode, tilNode);
        listeKanter.add(ny);

        fraNode.listeNaboer.add(tilNode);
    }


    private class Node{

        private int tall;
        private ArrayList<Node> listeNaboer;

        public Node(int tall){
            this.tall = tall;
            listeNaboer = new ArrayList<Node>();
        }

        public String toString(){
            return Integer.toString(tall);
        }
    }

    //Denne klassen er egentlig un?dvendig i v?rt eksempel.
    private class Kant{

        private Node fra;
        private Node til;

        public Kant(Node fra, Node til){
            this.fra = fra;
            this.til = til;
        }
    }
}