PPMARIANSKILAB9

***Graf.java***

import java.util.List;

public interface Graf<W, S> {
    public List<W> wierzcholki();			//zwraca wszystkie wierzcholki grafu

    public S krawedz(W w1, W w2);			//pobiera etykietę krawędzi pomiędzy wierzchołkami
    //wartość NULL oznacza brak krawędzi

    public List<W> krawedzie(W w);			//zwraca wierzchołki, do których istnieje krawędz z w
}

***GrafSkierowany.java***

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Mateusz on 2017-12-04.
 */
public class GrafSkierowany<W,S> implements Graf<W,S> {
    private List<W> listaWierzcholkow;
    private List<List<W>> listaSasiedztwaWierzcholkow;
    private List<List<S>> listaSasiedztwaKrawedzi;

    public GrafSkierowany(List<W> lW, List<List<W>> lSW, List<List<S>> lSK){
        listaWierzcholkow = lW;
        listaSasiedztwaWierzcholkow = lSW;
        listaSasiedztwaKrawedzi = lSK;
    }

    @Override
    public List<W> wierzcholki(){
        return listaWierzcholkow;
    }

    @Override
    public S krawedz(W w1, W w2){
        int i=0;
        for(;i<listaWierzcholkow.size();i++){
            if(w1.equals(listaWierzcholkow.get(i))){
                break;
            }
        }
        for(int j=0; j<listaSasiedztwaWierzcholkow.get(i).size();j++){
            if(w2.equals(listaSasiedztwaWierzcholkow.get(i).get(j))){
                return listaSasiedztwaKrawedzi.get(i).get(j);
            }
        }
        return null;
    }

    @Override
    public List<W> krawedzie(W w){
        int i=0;
        for(;i<listaWierzcholkow.size();i++){
            if(w.equals(listaWierzcholkow.get(i))){
                break;
            }
        }
        return listaSasiedztwaWierzcholkow.get(i);
    }
}

***GrafTest.java***
import java.util.ArrayList;
import java.util.List;

public class GrafTest {

    public static int stopienGrafu(GrafSkierowany graf){
        int stopnieW[] = new int[graf.wierzcholki().size()];
        int max = 0;
        for(int i=0; i<stopnieW.length;i++) {
            if(graf.krawedz(graf.wierzcholki().get(i),graf.wierzcholki().get(i))!=null) {
                stopnieW[i]+=2;
            }
        }
        for(int i=0; i<stopnieW.length;i++) {
            for(int j=0; j<stopnieW.length;j++){
                if(graf.krawedz(graf.wierzcholki().get(i),graf.wierzcholki().get(j))!=null && i!=j) {
                    stopnieW[i]++;
                }
            }
        }
        for(int i=0; i<stopnieW.length;i++) {
            for(int j=0; j<stopnieW.length;j++){
                if(graf.krawedz(graf.wierzcholki().get(j),graf.wierzcholki().get(i))!=null && i!=j) {
                    stopnieW[i]++;
                }
            }
        }
        for(int i=0; i<stopnieW.length;i++){
            System.out.println(stopnieW[i]);
            if(max<stopnieW[i]){
                max = stopnieW[i];
            }
        }
        return max;
    }

    public static boolean isGraphCyclic(GrafSkierowany graf, int wierzcholek, char[] odwiedzone){
        odwiedzone[wierzcholek] = 's';
        for(int i=0; i<graf.krawedzie(graf.wierzcholki().get(wierzcholek)).size();i++){
            if(odwiedzone[i]=='s'){
                return true;
            }else if(isGraphCyclic(graf,i,odwiedzone)==true){
                return true;
            }
        }
        odwiedzone[wierzcholek]='c';
        return false;
    }

    public static boolean isCyclic(GrafSkierowany graf){
        char[] odwiedzone = new char[graf.wierzcholki().size()];
        for(int i=0; i<odwiedzone.length; i++){
            odwiedzone[i] = 'b';
        }
        for(int i=0; i<graf.wierzcholki().size();i++){
            if(isGraphCyclic(graf,i,odwiedzone)==true){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Integer w1 = new Integer(1);
        Integer w2 = new Integer(2);
        Integer w3 = new Integer(3);
        String k1_2 = new String("1do2");
        String k1_3 = new String("1do3");
        String k2_3 = new String("2do3");
        String k3_1 = new String("3do1");

        List<Integer> lW = new ArrayList<Integer>();
        lW.add(w1);
        lW.add(w2);
        lW.add(w3);

        List<List<Integer>> lSW = new ArrayList<List<Integer>>();
        List<List<String>> lSK = new ArrayList<List<String>>();
        for(int i=0; i<3; i++){
            lSW.add(new ArrayList<Integer>());
            lSK.add(new ArrayList<String>());
        }

        lSW.get(0).add(w2);
        lSW.get(0).add(w3);
        lSW.get(1).add(w3);
        lSW.get(2).add(w1);

        lSK.get(0).add(k1_2);
        lSK.get(0).add(k1_3);
        lSK.get(1).add(k2_3);
        lSK.get(2).add(k3_1);


        GrafSkierowany<Integer, String> test = new GrafSkierowany(lW,lSW,lSK);
        /*
        for(int i=0; i<test.wierzcholki().size();i++){
            System.out.print(test.wierzcholki().get(i)+", ");
        }
        System.out.println();
        System.out.println(test.krawedz(w1,w2));
        System.out.println(test.krawedz(w1,w3));
        System.out.println(test.krawedz(w2,w3));
        System.out.println(test.krawedz(w3,w1));

        for(int i=0; i<test.krawedzie(w1).size();i++){
            System.out.print(test.krawedzie(w1).get(i)+", ");
        }
        System.out.println();

        for(int i=0; i<test.krawedzie(w2).size();i++){
            System.out.print(test.krawedzie(w2).get(i)+", ");
        }
        System.out.println();

        for(int i=0; i<test.krawedzie(w3).size();i++){
            System.out.print(test.krawedzie(w3).get(i)+", ");
        }
        System.out.println();
        */
        System.out.println("Stopien grafu: "+stopienGrafu(test));
        System.out.println("Czy graf jest cykliczny: "+isCyclic(test));
    }
}