Diskuze: Teorie grafů: Nalezení kružnice určité délky
V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.
Člen
mnauik:29.3.2015 20:42
Editováno 29.3.2015 20:44
Ahoj, zkusil jsem to do šířky a potřeboval bych to nějak optimalizovat, co nejvíc zrychlit. Kód hledá kružnice délky 5 - tzv. komplexy, ale mezi vrcholy nesmí být kratší smyčky. Komplexy pak seřazené vypisuje. Nejdůležitější je ale co nejrychlejší kód, aby rychle zpracoval i velmi mnoho vrcholů a jejich hran.
Program jsem okomentoval, aby bylo jasné, o co jde, hledám posloupnost
pěti vrcholů tzv. komplexů, nesmí mít mezi sebou žádné smyčky, tzn,
žádné menší kružnice. Už s tím bojuju asi 3 dny a stále nevím, kde je
problém. Prosím moc o pomoc 
package alg;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;
import java.util.logging.Level;
import java.util.logging.Logger;
;
/**
*
* @author mnaw
* vyuzivam teorie grafu, kazda molekula predstavuje vrchol grafu, dvojice
* molekul jsou hrany.
* http://teorie-grafu.cz/
*
* Co je to graf?
* Graf je dvojice dvou mnozin - mnozin vrcholu a mnozin hran
* vrchol je jakysi bod
* hrana je spojnice mezi body
* kruznice delky n je posloupnost n vrcholu, kruznice musi vest pres hrany
*
*
* Komplexy hledam prohledavanim do hloubky, kde hledam kruznice grafu o
* velikosti 5 vrcholu.
*
* Omezujici podminky - ktere vrcholy neprohledavam:
* 1) vrcholy mensi nez pocatecni vrchol
* 2) vrcholy, ktere uz v kruznici mam
* 3) vrcholy, ktere sousedi s vrcholy v kruznici, krome pripadu, kdy posledni
* vrchol spojuje pocatek a tim uzavre kruh
*
* petice jeste otestuju, zda nejsou duplicitni podminkou, zda posledni prvek
* je vetsi nez druhy
*
*
*
*
*
* na uloze delam cca 60 h
* vetsinu casu zabralo snizeni casu
*/
public class Main {
static int[][] vertices; // tabulka vrcholu, pole vrcholu
// vertices[x] hrany vrcholu x,
// vertices[x][h] nejaka konkretni
// hrana
static final int[] petice = new int[5]; // petice cisel
static int pocatek; // cislo vrcholu, od ktereho
// prohledavam
static int pocetHranSouseda = 0; // poloha nejakeho sousedniho prvku
static final LinkedList<int[]> komplexy = new LinkedList<>(); // seznam komplexu
static final boolean FROM_FILE = true;
static final boolean SHOW_TIME = true;
static final String TEST_FILE = "pub04.in";
static final OutputStream out = new BufferedOutputStream(System.out);
private static int pocetVPetici; // kde v pětici jsem (nebo kolik je v petici
// platnych prvku nebo na jakou pozici zapise)
private static int[] pocetHran; // pocetHran[x] - pocet hran vrcholu x
private static int[] serazenaPetice = new int[5];
public static void main(String[] args) throws IOException {
// TODO code application logic here
long start = System.currentTimeMillis();
BufferedReader sc = null;
if (FROM_FILE) {
try {
sc = new BufferedReader(new InputStreamReader(new FileInputStream(new File("public/" + TEST_FILE))));
} catch (FileNotFoundException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
}
} else {
sc = new BufferedReader(new InputStreamReader(System.in));
}
//nacteni vstupu
String ln = sc.readLine();
int nodes = Integer.parseInt(ln.split(" ")[0]);
int edges = Integer.parseInt(ln.split(" ")[1]);
vertices = new int[nodes][200];
pocetHran = new int[nodes];
//for - nacteni hran a pridani do poli vrcholů (vertices)
for (int i = 0; i < edges; i++) {
String line = sc.readLine();
int refVert1 = Integer.parseInt(line.split(" ")[0]);
int refVert2 = Integer.parseInt(line.split(" ")[1]);
vertices[refVert1][pocetHran[refVert1]] = refVert2;
pocetHran[refVert1]++;
vertices[refVert2][pocetHran[refVert2]] = refVert1;
pocetHran[refVert2]++;
}
sc.close();
// for - kazdy vrchol volim jako pocatek a prohledavam od nej
for (int i = 0; i < vertices.length - 1; i++) {
pocatek = i;
//prohledavam
dfs(pocatek);
pocetVPetici = 0;
// zapisu na vystup nalezene petice
for (int[] petice1 : komplexy) {
for (int cislo = 0; cislo < 5; cislo++) {
out.write((petice1[cislo] + "").getBytes());
if (cislo < 4) {
out.write((" ").getBytes());
}
}
out.write(("\n").getBytes());
}
// vyprazdnim seznam komplexu
komplexy.clear();
out.flush();
}
long end = System.currentTimeMillis();
if (SHOW_TIME) {
System.out.println("Time: " + (end - start) + " ms");
}
out.close();
}
/**
* Prohledavani do hloubky
*
* @param v vrchol ze ktereho prohledavam
*/
public static void dfs(Integer v) {
// vracim se, kdyz uz mam v petici 5 prvku
// vracim se, pokud vrchol je mensi nez pocatek - tim uz jsem prochazel
// vracim se, pokud vrchol ma mene nez 2 hrany - nemuze byt v komplexu
if (pocetVPetici == 5 || v < pocatek || pocetHran[v] < 2) {
return;
}
// pokud se nevracim, pridam si ho do sve petice,
// tim se zvysi i pocet v petici
petice[pocetVPetici] = v;
pocetVPetici++;
// for - prochazim hrany vrcholu
prochazeniSousedu:
for (int hrana = 0; hrana < pocetHran[v]; hrana++) {
// v1 je soused v
int v1 = vertices[v][hrana];
// vrcholy s mensim cislem nez pocatek zahazuji
// pokud maji mene hran nez dve, taky zahazuji
if (v1 < pocatek || pocetHran[v1] < 2) {
continue;
}
// pokud mam 4 cisla a sousedni vrchol je pocatek - pak se kruh uzavira
// treti podminka plni funkci jednosmerky
if (pocetVPetici >= 5 && v1 == pocatek && petice[4] > petice[1]) {
// vytvorim novou petici, prekopiruji do ni prvky ze stare petice
serazenaPetice = new int[5];
// nakopiruju si pole, do noveho pole, ktere chci pridat do seznamu
System.arraycopy(petice, 0, serazenaPetice, 0, 5);
// seradim novou petici
Arrays.sort(serazenaPetice);
// zapisu do seznamu komplexu
int ksize = komplexy.size();
if (ksize == 0) {
komplexy.add(serazenaPetice);
}
for (int i = 0; i < ksize; i++) {
if (compare(serazenaPetice, komplexy.get(ksize - 1 - i))) {
komplexy.add(ksize - i, serazenaPetice);
break;
} else {
komplexy.add(ksize - i - 1, serazenaPetice);
break;
}
}
// chci se vratit, proto "odstranim" prvek z petice
pocetVPetici--;
return;
}
for (int i = 0; i < pocetVPetici; i++) {
if (petice[i] == (v1)) {
continue prochazeniSousedu;
}
}
pocetHranSouseda = pocetHran[v1];
// nez pujdu do hloubky:
// overuji, zda cislo sousedniho vrcholu je vetsi nez cislo pocatecniho
// overuji, zda souseda nemam v petici
// overuji, zda soused netvori smycky s petici (aby kazdy prvek petice sousedil prave dvakrat)
if (v1 >= pocatek && !contains(petice, v1) && pocetSpolecnychPrvku(petice, vertices[v1]) < 2) {
dfs(v1);
}
}
// prohledany vsechny hrany, vracim se
if (pocetVPetici > 0) {
pocetVPetici = pocetVPetici - 1;
}
}
/**
* pocet spolecnych prvku v poli, pokud mam 4 prvky v petici, tak ocekavam smycku s
* pocatkem (odecitam 1)
*
* @param l1
* @param l2
* @return
*/
public static int pocetSpolecnychPrvku(int[] l1, int[] l2) {
int ret = 0;
if (pocetVPetici >= 4) {
ret -= 1;
}
for (int i = 0; i < pocetVPetici; i++) {
for (int j = 0; j < pocetHranSouseda; j++) {
if ((l2[j] == l1[i])) {
ret++;
}
if (ret >= 2) {
return ret;
}
}
}
return ret;
}
/**
* zda obsahuje pole array hodnotu value
*
* @param array pole, ktere otestuji
* @param value hodnota, kterou hledam v poli
* @return
*/
public static boolean contains(int[] array, Integer value) {
for (int i = 0; i < pocetVPetici; i++) {
if (array[i] == (value)) {
return true;
}
}
return false;
}
/**
* porovnani dvou poli, porovnava se podle prvniho prvku, pokud jsou prvni
* prvky stejne, porovnava se s druhym, atd....
*
* @param a1
* @param a2
* @return true, pokud je prvni pole vetsi, jinak false
*/
public static boolean compare(int[] a1, int[] a2) {
for (int i = 1; i < 5; i++) {
if (a1[i] > a2[i]) {
return true;
}
if (a1[i] < a2[i]) {
return false;
}
}
return false;
}
}
Zobrazeno 5 zpráv z 5.