Diskuze: Teorie grafů: Nalezení kružnice určité délky

Java Java Teorie grafů: Nalezení kružnice určité délky

Avatar
mnauik
Člen
Avatar
mnauik:

Ahoj,
hledám nejrychlejší způsob (i paměťově nenáročný), jak prohledat graf, abych našel všechny kružnice délky n, kde n je počet vrcholů kružnice. Vrcholy se neopakují.

Není to úplně domácí úkol, zadání domácího úkolu je jiné, pouze jsem si určil tuto metodu přes kružnice, jak úkol vyřešit.

Pokud to nechceš/nechcete kódit, tak stačí napsat, jak bys/byste to řešili.

Příklad:

Graf:
http://primes.utm.edu/…kbrgraph.gif

má kružnice n = 2:
AB, AC

má kružnice n = 3:
ABD, ACD, BCD

má kružnice n = 4:
ABCD

Odpovědět 24.3.2015 23:17
minusuj mě, ale zdůvodni to ;)
Avatar
xfhxd
Člen
Avatar
xfhxd:

Prohledávání do hloubky.

Nahoru Odpovědět 25.3.2015 12:43
Ježíš zaplatil za naše hříchy a tím nás zachránil od věčné smrti a zatracení. [Evangelium] Čtěte bibli, napravte se. ...
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na mnauik
Silvinios:

Uvážíme-li úplný graf, pak kružnici délky n tvoří libovolných n vrcholů v libovolném pořadí. Myslím, že obecně neexistuje lepší řešení než vygenerovat všechny n-tice vrcholů a ověřit, zda tvoří kružnici.

Bez dodatečných předpokladů je těžké hledat nejrychlejší řešení. Víš např. jak velké je n nebo kolik vrcholů a hran graf má?

 
Nahoru Odpovědět 26.3.2015 21:57
Avatar
mnauik
Člen
Avatar
mnauik:

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;
    }
}
Editováno 29.3.2015 20:44
Nahoru Odpovědět 29.3.2015 20:42
minusuj mě, ale zdůvodni to ;)
Avatar
Odpovídá na mnauik
Lukáš Hruda (Luckin):

Šel bych na to spíš přes průchod do hloubky. Podívej se po nějaký algoritmech pro hledání silně souvislých komponent orientovaných grafů, většina z nich funguje právě na principu hledání kružnic. Možná bys některý z nich mohl modifikovat tak, aby hledal pouze nejmenší kružnice. Zkusil bych třeba Cheriyan-Mehlhornův algoritmus. Každopádně si myslím, že je to problém, který by měl jít vyřešit jedním průchodem.

 
Nahoru Odpovědět 29.3.2015 23:00
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.