import java.util.*;

class Knoten{
    String  name;
    ArrayList<Knoten> nachbarn;
    Knoten(String s){ name = s; nachbarn = new ArrayList<Knoten>();}
    public String toString(){ return name;}
}

class Graph{
	  
	  int knotenZahl;
    Knoten[] knotenArray; 
    
    Graph(){
    	  Knoten k1 = new Knoten("1"), k2 = new Knoten("2"), k3 = new Knoten("3"),
               k4 = new Knoten("4"), k5 = new Knoten("5"), k6 = new Knoten("6"),
               k7 = new Knoten("7"), k8 = new Knoten("8"), k9 = new Knoten("9");
        
        Knoten[] ka = {k1,k2,k3,k4,k5,k6,k7,k8,k9};
    	  knotenArray = ka;
    	  knotenZahl  = ka.length;
        
         //Kanten definieren
        k1.nachbarn.add(k4);
        k2.nachbarn.add(k2); k2.nachbarn.add(k4); k2.nachbarn.add(k3);
        k5.nachbarn.add(k2); k5.nachbarn.add(k3); k5.nachbarn.add(k4); k5.nachbarn.add(k8);
        k6.nachbarn.add(k7);
        k7.nachbarn.add(k7);
        k8.nachbarn.add(k5);
        
    }
    
    int index(Knoten k){
    	  for (int i=0; i < knotenZahl; i++)
            if (k == knotenArray[i]) return i;
        return -1;    
        }    
    
    int index(String s){
    	  for (int i=0; i < knotenZahl; i++)
            if (s.equals(knotenArray[i].name)) return i;
        return -1;    
        }
        
    Knoten find(String s){
    	  for (int i=0; i < knotenZahl; i++)
            if (s.equals(knotenArray[i].name)) return knotenArray[i];
        return null;    
        }    
    
    
        
    boolean kante(Knoten k1, Knoten k2){
    	  for (Knoten i1 : knotenArray)
    	    if (i1 == k1) for (Knoten i2 : k1.nachbarn)
    	       if (i2 == k2) return true;
        return false;    
        }           

    void nachbarn(){
    	for (Knoten k1 : knotenArray)
    	  for (Knoten k2 : k1.nachbarn)
    		  System.out.println("Kante von "+k1+" nach "+k2+" vorhanden");
    		}
    		
}

public class GraphT {

    public static void main(String args[]) {
        System.out.println("Graph Tester");
        Graph g = new Graph();
        g.nachbarn();
        
        Knoten k1 = g.find("1");
        Knoten k2 = g.find("2");
        if ((k1 != null) && (k2 != null)) 
          if (g.kante(k1,k2)) System.out.println("Kante von "+k1+" nach "+k2+" vorhanden");
          else  System.out.println("Kante von "+k1+" nach "+k2+" nicht vorhanden");
        
    }
}