Datová struktura - vícevrstvý graf – Java – Fórum – Programujte.com

Zdravím,

programuju aplikaci, která zobrazuje různé body (města) na mapě a spojení mezi nimi. Napsal jsem si datovou strukturu graf (Vrchol - město,  Hrana - cesta). Mapa je rozdělená na čtyři vrstvy dle podrobnosti - podle velikosti města. A teď otázka - existuje nějaká vhodná struktura, něco jako vícevrstvý graf, která by byla schopná uchovavat všechny vrstvy grafu? Zatím to řeším tak, že pro každou vrstvu mám jinou instanci grafu, ale napříč vrstvami se blbě vyhledává.

Zavedl bych entitu Vrstva a vazbu M:N mezi Vrstva a Vrchol. Kdyz budes zobrazovat urcitou vrstvu, tak se zobrazi jenom mesta (vrcholy), ktere jsou prirazene k dane vrstve, a zobrazi se jen hrany (cesty), u kterych oba vrcholy jsou prirazene k dane vrstve. Hrana je prirazena k vrcholum bez ohledu na vrstvu, takze je mozne vyhledavat, vrstvy jsou pouze pro zobrazeni.

Možná jsem to nenapsal úplně šťastně, každá nižžší vrstva obsahuje vrcholy z vrstvy předchozí, ale má jiné hrany. Potřebuju aby hrany i vrcholy byly odděleny ve vrstvách a dalo se vyhledávat napříč vrtsvami. Ilustrace jak by to mělo vypadat.

Připojen obrázek.

Základní kostra třídy grafu

public class Graph<V, E, K> {

    private final HashMap<K, Vertex> vertices;

    public Graph() {
        this.vertices = new HashMap<>();
    }

    private class Vertex {
        private V data;
        private K key;
        private ArrayList<Edge> vertexEdges;

        public Vertex(V data) {
            this.data = data;
            vertexEdges = new ArrayList<>();
        }
   }
    private class Edge {

        private E data;
        private Vertex vertex1;
        private Vertex vertex2;

        public Edge(K keyVertex1, K keyVertex2, E data) {
            this.data = data;
            this.vertex1 = vertices.get(keyVertex1);
            this.vertex2 = vertices.get(keyVertex2);
            vertex1.vertexEdges.add(this);
            vertex2.vertexEdges.add(this);
        }
    }

    public void addVertex(K key, V data) {
	//...
    }

    public void addEdge(K keyVertex1, K keyVertex2, E data){
	//...
    }

}

#3 farth

každá nižžší vrstva obsahuje vrcholy z vrstvy předchozí, ale má jiné hrany. Potřebuju aby hrany i vrcholy byly odděleny ve vrstvách a dalo se vyhledávat napříč vrtsvami

Proc na tom takto trvas? Vrcholy a hrany jsou dane bez ohledu na vrstvu. Tedy existuji vrcholy A, B a hrana AB. Dale existuje vrchol, ktery ve vrstve 2 lezi mezi vrcholy A a B - rekneme vrchol X - a hrany AX, XB. A pak existuje prirazeni vrcholu a hran vrstvam. Takze existuje prirazeni A1, A2, B1, B2, X2, AB1, AX2, XB2. Ve vrstve se zobrazi vse co je k ni prirazeno. Nevim co presne myslis vyhledavanim mezi vrstvami, ale tento model to podle mne umozni - bud chci vrcholy a hrany v jedne vrstve, ve vrstve a ve vsech nizsich vrstvach, nebo bez ohledu na vrstvu. 

#3 farth
no já bych to udělal jako P s tím, že vrstvy by byly jak u vrcholů tak i u hran, vrcholy budeš zobrazovat všechny, které spadají do vybrané a (nad/pod)řazené vrstvy a hrany jen z konkrétní vrstvy.

#5 MilanL
ještě bych to zjednodušil na společného předka pro vrcholy i hrany. U hrany ti stačí 1 vertex ve kterém budou indexy vrcholů, pak při zobrazení stačí procházet hrany dané vrstvy a k nim pak zobrazovat potřebné vrcholy.

Pro zobrazování, tak jak to chceš použít, mají ve vrstvách větší váhu hrany než vrcholy.

Jo s další vnitřní třídou "Vrstva" mi to funguje, nejdřív mi to nebylo úplně jasný jak to myslíte , ale je to vlastně v celku jednoduchý. Díky moc.