Основная образовательная программа cb. 5005. 2016 Прикладная математика, фундаментальная информатика и программирование
 Скачать 0.51 Mb.
|
|
import java.util.Scanner; import java.io.File; import java.io.FileNotFoundException; import java.util.List; import java.util.ArrayList; public class Hamilton { private int N; private final int M; private int[] Pi; private long[] cycles; private long[] rows; static int[][] matrix; public Hamilton(long[] rows, int N, int M) { if (M < N) throw new RuntimeException("Граф не гамильтонов. Ребер меньше чем вершин"); if (M > 2*N) throw new RuntimeException("Эффективная работа алгоритма обеспечивается при выполнении равенства M < 2*N"); this.N = N; this.M = M; this.rows = rows; this.Pi = new int[M]; for (int i = 0; i < M; i++) Pi[i] = i; System.out.println("N вершин = " + N); System.out.println("M ребер = " + M); cycles = rows.clone(); gauss(cycles); System.out.println("Матрица Гаусса:"); for(int i = 0; i < N-1; i++) print(cycles[i], M); System.out.println(); System.out.println("Перестановки ребер Pi[i]:"); for(int i = 0; i < this.M; i++) System.out.print(Pi[i]+1 + " "); cycles = fundamentalCycles(cycles); this.N = N; System.out.println("\n\nФундаментальные циклы(после перестановки):"); for(int i = 0; i < cycles.length; i++) { print(cycles[i], this.M); } } public void printHamiltonCycles() { long k = 1L; long copy; long cycle; int count = 0; while (true) { copy = k; cycle = 0L; for (; copy != 0L; copy ^= Long.lowestOneBit(copy)) { int i = Long.numberOfTrailingZeros(copy); if (i > M) throw new RuntimeException("Неправильно построены фундаментальные циклы"); if (i >= cycles.length) { if (count == 0) throw new RuntimeException( "Гамильтонова цикла не существует."); return; } cycle ^= cycles[i]; } if (isCycle(rows, cycle, N)) { count++; System.out.println("\n########"); System.out.println("Гамильтонов цикл " + "№" + count + ":"); print(cycle,M); System.out.println("Матрица инцидентности:"); printEdges(rows, cycle); System.out.println("Базисная комбинация:"); print(k, M-N+1); System.out.println("########"); } k++; } } private boolean isCycle(long[] rows, long cycle, int N) { if (Long.bitCount(cycle) != N) return(false); long[] copy = rows.clone(); int sumEdges = 1; int current = 0; long bit; while (copy[current] != 0) { bit = Long.lowestOneBit(copy[current]); copy[current] ^= bit; if ((cycle & bit) != 0) { for (int j = 0; j < copy.length; j++) { if (j == current) continue; if ((copy[j] & bit) != 0) { copy[current] = 0; copy[j] ^= bit; sumEdges++; current = j; break; } } } } return sumEdges == N; } private void gauss(long[] rows) { for (int i = 0; i < N-1; i++) { long col = (1L< if ((rows[i] & col) == 0) if (!rearrange(rows, i, Pi)) throw new RuntimeException("Граф не гамильтонов. Метод Гаусса: элемент для перестановки не найден."); for (int j = 0; j < N; j++) { if (i == j) continue; if ((rows[j] & col) != 0) rows[j] ^= rows[i]; } } if (rows[--N] != 0L) throw new RuntimeException("Граф не гамильтонов. Система решений не вырождена"); for (int i = 0; i < N; i++) if (Long.bitCount(rows[i]) == 1 || Long.bitCount(rows[i]) == 0) throw new RuntimeException( "Граф не гамильтонов. Базис не может быть построен"); } private long[] fundamentalCycles(long[] rows) { long[] cycles = new long[M-N]; long basis = 1L< for (int j = 0; j < M-N; j++) { cycles[j] = basis; for (int i = 0; i < N; i++) { if ((rows[i] & basis) != 0) cycles[j] |= 1L< } cycles[j] = permutePi(cycles[j]); basis <<= 1; } for (int j = 0; j < M-N; j++) { for (int i = j + 1; i < M-N; i++) { if ((cycles[i] & cycles[j]) != 0 && ((Long.bitCount(cycles[i] ^ cycles[j]) < Math.max(Long.bitCount(cycles[i]), Long.bitCount(cycles[j]))))) { if (Long.bitCount(cycles[i]) < Long.bitCount(cycles[j])) { cycles[j] = cycles[i] ^ cycles[j]; } else{ cycles[i] = cycles[i] ^ cycles[j]; } } } } return cycles; } private boolean rearrange(long[] rows, int i, int[] Pi) { int tmp = Pi[i]; int changed = i; while ((rows[i] & (1L< if (++changed == this.M) return false; Pi[i] = Pi[changed]; Pi[changed] = tmp; long mask = (1L< for (int j = 0; j < rows.length; j++) { long jBit = rows[j] & (1L< long chgBit = rows[j] & (1L< if ((jBit != 0 || chgBit != 0) && !(jBit != 0 && chgBit != 0)) { rows[j] ^= mask; } } return true; } private long permutePi(long hamilton) { long back = 0L; for (int i = 0; i < M; i++) { if ((hamilton & (1L< { back |= 1L< } } return back; } private static void printEdges(long[] rows, long hamilton) { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if ((hamilton & (1L< System.out.print(matrix[i][j]); } System.out.println(); } } private static void print(long row, int M) { String str = ""; for (int k = 0; k < M; k++) { str += (row & (1L< } System.out.println(str); } public static void main(String[] args) { List Scanner in; try { in = new Scanner(new File(args[0])); } catch(FileNotFoundException e) { System.out.println(e.getMessage()); return; } while (in.hasNextLine()) list.add(in.nextLine()); String[] lines = list.toArray(new String[0]); int N = lines.length; int M = lines[0].length(); long[] rows = new long[N]; matrix = new int[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) if (lines[i].charAt(j) == '1') { rows[i] |= 1L< matrix[i][j] = 1; } else matrix[i][j] = 0; } try { Hamilton H = new Hamilton(rows, N, M); H.printHamiltonCycles(); } catch(Exception e){ System.out.println(e.getMessage()); } } Подгружаемый файл должен содержать матрицу инцидентности графа, аналогичного следующему:        |