Graphs

package MyGraphs;

import java.util.Scanner;

public class Graphs
{
    byte    destVertex  = 0;
    byte    chain[];
    int     minDist     = 5000;
    boolean flag[];
    long    operationCounter;
    boolean isPrint     = true; // Выводить ли информацию о результатах поиска путей?

    /**
     *
     * @param a
     *            - исходный массив. Размер равен размеру массива
     * @param startVertex
     *            - с какой вершины рассматривать
     * @return найденный минимальный путь
     */
    public long bruteForce(int a[][], byte startVertex)
    {
        return bruteForce(a, startVertex, a.length);
    }

    /**
     *
     * @param a
     * @param startVertex
     *            - с какой вершины рассматривать
     * @param N
     *            - Размер массива a ( <= a.length)
     * @return найденный минимальный путь
     */
    public long bruteForce(int a[][], byte startVertex, int N)
    {
        operationCounter = 0;
        if (isPrint) System.out.println("\nАлгоритм полного перебора:");

        minDist = 5000;
        destVertex = startVertex;
        flag = new boolean[N];
        chain = new byte[N];
        for (int i = 0; i < N; i++)
        {
            flag[i] = false;
            chain[i] = 0;
        }

        flag[startVertex] = true;
        doBruteForce(startVertex, 0, a, N);
        flag[startVertex] = false;

        if (isPrint) System.out.println("\nМинимальный путь: " + minDist + "\n\nКоличество элементарных операций: " + operationCounter);
        return operationCounter;

    }

    /**
     * Рекурсивный вызов обхода полным перебором
     *
     * @param vertex
     * @param dist
     * @param a
     * @param N
     */
    private void doBruteForce(byte vertex, int dist, int a[][], int N)
    {
        chain[getCount() - 1] = (byte) (vertex + 1);

        if (testFlag() && dist != 0)
            if ((dist + a[vertex][destVertex]) < minDist && a[vertex][destVertex] != 0)
            {
                minDist = dist + a[vertex][destVertex];

                if (isPrint)
                {
                    System.out.print("\nПуть: ");
                    printArray(chain);
                    System.out.print("\nВес пути: " + minDist);
                }
            }
            else
                ;
        else
            for (byte i = 0; i < N; i++)
            {
                if (!flag[i] && a[vertex][i] != 0)
                {
                    flag[i] = true;
                    operationCounter++;
                    doBruteForce(i, dist + a[vertex][i], a, N);
                    flag[i] = false;
                }
            }
    }

    /**
     * Жадный алгоритм поиска кратчайшего пути.
     *
     * @param a
     *            - Исходный массив
     * @param curVertex
     *            - с какой вершины рассматривать обход?
     * @return Найденное расстояние
     */
    public long greedy(int a[][], byte curVertex)
    {
        return greedy(a, curVertex, a.length);
    }

    /**
     * Жадный алгоритм поиска кратчайшего пути.
     *
     * @param a
     *            - Исходный массив
     * @param curVertex
     *            - с какой вершины рассматривать обход?
     * @param N
     *            - Какой размер из массива а рассматривать? (<= a.length)
     * @return Найденное расстояние
     */
    public long greedy(int a[][], byte curVertex, int N)
    {

        operationCounter = 0;
        if (isPrint) System.out.println("Жадный алгоритм:\n");

        int dist = 0;
        byte startVertex = curVertex;

        flag = new boolean[N];
        chain = new byte[N];
        byte current = 0;

        for (int i = 0; i < N; i++)
        {
            flag[i] = false;
            chain[i] = 0;
        }

        flag[curVertex] = true;
        chain[current] = (byte) (curVertex + 1);

        for (byte i = 0; i < N - 1; i++)
        {
            byte nextVertex = getMinWay(a, curVertex, N);
            dist += a[curVertex][nextVertex];
            curVertex = nextVertex;
            flag[curVertex] = true;
            current++;
            chain[current] = (byte) (curVertex + 1);
        }

        if (isPrint)
        {
            if (a[curVertex][startVertex] != 0)
            {
                System.out.print("Путь: ");
                printArray(chain);
                System.out.print("\nВес: " + (dist + a[curVertex][startVertex]));
                System.out.print("\nЭлементарных операций: " + operationCounter);
            }
            else
                System.out.println("\nПолный обход не найден");
        }
        return operationCounter;
    }

    private boolean testFlag()
    {
        for (int i = 0; i < flag.length; i++)
            if (!flag[i]) return false;

        return true;
    }

    /**
     * Возвращает кол-во посещенных вершин в графе. Вызывается алгоритмами поиска путей.
     *
     * @return кол-во пройденных вершин
     */
    private byte getCount()
    {
        byte counter = 0;
        for (int i = 0; i < flag.length; i++)
            if (flag[i]) counter++;

        return counter;
    }

    /**
     * Поиск соседней непосещенной вершины с наименьшим весом ребра.
     *
     * @param a
     * @param vertex
     * @param N
     * @return Возвращает номер вершины
     */
    private byte getMinWay(int a[][], byte vertex, int N)
    {
        byte minEdge = 127;
        byte minVertex = 0;

        for (byte i = 0; i < N; i++)
        {
            operationCounter++;
            if (!flag[i] && a[vertex][i] != 0 && a[vertex][i] < minEdge)
            {
                minEdge = (byte) a[vertex][i];
                minVertex = i;
            }
        }

        return minVertex;

    }

    /**
     * Инициализация графа а матрицей смежности. Консольный интерфейс.
     *
     * @param a
     *            - инициализируемый массив
     */
    public void init(int a[][])
    {
        int N = a.length;

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                a[i][j] = 0;
            }

        Scanner in = new Scanner(System.in);

        System.out.println("Ввод смежных вершин. Введите 0 для перехода к следующей вершине.");
        for (int i = 0; i < N; i++)
        {
            int num = 0; // tmp - номер вершины, w - вес.
            int w = 1;
            do
            {
                System.out.println("\nВведите смежную вершину для вершины " + (i + 1));
                num = in.nextInt() - 1;
                if (num > 0 && num <= N)
                {
                    System.out.println("Введите вес ребра " + (i + 1) + "-" + (num + 1));
                    w = in.nextInt();
                    a[i][num] = w;
                    a[num][i] = w;
                }

            }
            while (num > 0);
        }
        in.close();
        System.out.println("Конец инициализации графа...");
    }

    /**
     * Инициализация массива а с помощью координат на координатной плоскости. Веса вычисляются автоматически.
     *
     * @param a
     */
    public void initByCord(int a[][])
    {
        Scanner in = new Scanner(System.in);
        int N = a.length;
        byte x[] = new byte[N];
        byte y[] = new byte[N];

        System.out.println("Кол-во координат: " + N);
        for (int i = 0; i < N; i++)
        {
            System.out.println("Введите координаты (x,y) №" + i);
            x[i] = in.nextByte();
            y[i] = in.nextByte();
        }

        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++)
            {
                a[i][j] = (int) Math.round(Math.hypot(x[j] - x[i], y[j] - y[i]));
                a[j][i] = a[i][j];
            }

        in.close();
    }

    public void initByCordDefault(int[][] a)
    {
        int N = a.length;
        byte x[] = { 0, 4, 1, 15, 15, 18, 8, 3 };
        byte y[] = { 0, 3, 7, 7, 4, 0, 0, 1 };

        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++)
            {
                a[i][j] = (int) Math.round(Math.hypot(x[j] - x[i], y[j] - y[i]));
                a[j][i] = a[i][j];
            }

    }

    public void initDefault(int a[][])
    {
        int b[] = { 0, 2, 0, 4, 0, 3, 2, 0, 2, 0, 0, 5, 0, 2, 0, 4, 2, 3, 4, 0, 4, 0, 1, 2, 0, 0, 2, 1, 0, 2, 3, 5, 3, 2, 2, 0 };
        int counter = 0;
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a.length; j++)
            {
                a[i][j] = b[counter];
                counter++;
            }
    }

    /**
     * Выводит массив a[][] на консоль
     *
     * @param a
     */
    public void printDoubleArray(int a[][])
    {
        for (int i = 0; i < a.length; i++)
        {
            for (int j = 0; j < a.length; j++)
                System.out.print(a[i][j] + " ");
            System.out.println();
        }
    }

    public void printArray(byte[] a)
    {
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
    }

    public void printArray(int[] a)
    {
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
    }

    public void printTestResult(long a[], String name)
    {
        System.out.println("\n" + name);
        System.out.println("N\tОпераций:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.println((i + 1) + "\t" + a[i]);
        }
    }

    public Graphs()
    {
        System.out.println("Class Graphs init...");
    }

}