Hierarchische Beziehung 'flachdrücken'

[bloody_beginner]

Hallo,
ich habe folgendes Problem:

Eine CSV-Datei beinhaltet die beiden Spalten PARENT;CHILD.
Darüber ist eine n-m Beziehung (Hierarchie) in der Datei hinterlegt.
Die Aufgabe besteht nun darin, zu einem gegebenen PARENT alle (hierarchisch) untergeordneten Elemente auszugeben.

Hier ist ein Beispiel.

Hat die Datei folgenden Inhalt:

1;6
2;5
3;4
4;6
5;2
8;9
6;3
6;4
6;5
2;1
9;8
4;3
4;7
4;1
3;2
3;1
9;10

so soll für das Parent-Element "1" folgende Ausgabe der hierarchisch untergeordnete Elemente erzuegt werden:

2
3
4
5
6
7

Für eine 'richtige Hierarchie' (1:n Beziehungen) habe ich das mittels Hashmaps realisiert. Hier weiß ich nicht wie's gehen soll.
Kann mir jemand helfen?

 

[Michael...]

So ganz kapier ich nicht wie man aus dem Dateiinhalt auf die Ausgabe kommen soll.

Ausserdem: Wie kann es sein, dass ein Kindelement Vaterelement seines Vaterelements sein kann?

...4;6
...
6;4
...

 

[bloody_beginner]

Ja,
es ist halt keine wirkliche Hierarchie sondern ein Beziehungsmodell, in dem diese Konstellation erlaubt ist.
Wenn ich die gefundenen CHILDS in einen StringBuffer packe, ist das Finden eines neuen CHILDS, das dort bereits vorhanden ist, eine Abbruchbedingung.

 

[maki]

Wie bereits gesagt, das ist keine Hierarchie, sondern ein sog. "rekursives Netzwerk".

Würde mir da erstmal ein richtiges Modell zurechtlegen, StringBuffer (wozu eigentlich??) und HashMap sind da wohl zu allgemein.

 

[bloody_beginner]

Um's mal zu verdeutlichen:

Beginne ich mit der 1 so finde ich dazu die 6.

Zur 6 finde ich dann 3,4 und 5.

Zur 3 finde ich 4,1 und 2. (Die 4 und die 1 sind keine 'neuen' CHILDS und benötigen keine weitere Verarbeitung.)

Zur 4 finde ich 6,3 und 7. (Die 6 und die 3 sind keine 'neuen' CHILDS...)

Zur 5 finde ich die 2.

Zu 2 und 7 finde ich dann ebenfalls keine neuen CHILDS mehr und bin fertig.

Alle der 1 'untergeordneten' Elemente sind also: 6,3,4,5,2,7

 

[bloody_beginner]

Wie bereits gesagt, das ist keine Hierarchie, sondern ein sog. "rekursives Netzwerk".

Okay.

Würde mir da erstmal ein richtiges Modell zurechtlegen, StringBuffer (wozu eigentlich??) und HashMap sind da wohl zu allgemein.

Diese Ideen kommen daher, dass ich was ähnliches (allerdings für eine richtige Hierachie mit Ausgabe des gesamten Hierachiestrings für jeden Ast des Hierarchiebaums) schon mal gemacht habe:

HashMap <String, String> parent = new HashMap<String, String>();
HashMap <String, String> ids = new HashMap<String, String>();

Iterator<String> p = parent.keySet().iterator();
String startId;

while (p.hasNext())
{
    startId = p.next();
    if(ids.get(startId) == null) {
        StringBuffer sb =new StringBuffer();
        sb.append(startId);
        for(String id = startId; parent.get(id) != null; id=parent.get(id))
        {
            sb.append(","+parent.get(id));
        }
        HIER_STRING=sb.toString();
        generateRow();
    }
}

Wenn ich das richtig sehe, dann hilft mir das hier aber nicht weiter. Wie gehe ich da am besten vor?

 

[Marco13]

Wenn ich das richtig sehe ist das einfach nur eine Graphentraversierung...?! ???:L

 

[bloody_beginner]

Ob 'rekursives Netzwerk' oder 'Graphentraversierung',
die Begriffe alleine helfen mir nicht so richtig dabei, das Problem durch ein kleines Programm zu lösen.

Nebenbei bemerkt:

Wie man vermutlich unschwer erkennen kann, sind mein JAVA-Kenntnisse höchst überschaubar. Im Grunde genommen beschäftige ich mich eigentlich mit einer graphischen Entwicklungsumgebung in der JAVA gewissermaßen als User-Exit für besondere Anwendungsfälle genutzt werden kann.

Daher würde ich es sehr zu schätzen wissen, in dieser Sache etwas an der Hand genommen zu werden.

 

[Marco13]

Hm..

import java.util.*;


class Traverse
{
    private class Node
    {
        String name;
        List<Edge> edges = new ArrayList<Edge>();

        public Node(String name)
        {
            this.name = name;
        }

        public int hashCode()
        {
            return name.hashCode();
        }

        public boolean equals(Object object)
        {
            if (object instanceof Node)
            {
                Node other = (Node)object;
                return other.name.equals(name);
            }
            return false;
        }

    }

    private class Edge
    {
        Node n0;
        Node n1;
    }

    private Map<String,Node> nodeMap = new HashMap<String,Node>();
    private Set<Edge> edges = new HashSet<Edge>();

    public void createEdge(String name0, String name1)
    {
        Node n0 = nodeMap.get(name0);
        if (n0==null)
        {
            n0 = new Node(name0);
            nodeMap.put(name0,n0);
        }
        Node n1 = nodeMap.get(name1);
        if (n1==null)
        {
            n1 = new Node(name1);
            nodeMap.put(name1,n1);
        }
        Edge edge = new Edge();
        edge.n0 = n0;
        edge.n1 = n1;
        n0.edges.add(edge);
        n1.edges.add(edge);
    }




    public static void main(String args[])
    {
        Traverse traverse = new Traverse();
        System.out.println(traverse.doIt("1"));
    }

    public Traverse()
    {
        createEdge("1","6");
        createEdge("2","5");
        createEdge("3","4");
        createEdge("4","6");
        createEdge("5","2");
        createEdge("8","9");
        createEdge("6","3");
        createEdge("6","4");
        createEdge("6","5");
        createEdge("2","1");
        createEdge("9","8");
        createEdge("4","3");
        createEdge("4","7");
        createEdge("4","1");
        createEdge("3","2");
        createEdge("3","1");
        createEdge("9","10");
    }

    public String doIt(String name)
    {
        Node first = nodeMap.get(name);
        Set<Node> visited = new LinkedHashSet<Node>();
        traverse(first, visited);
        visited.remove(first);


        StringBuffer result = new StringBuffer();
        for (Node node : visited)
        {
            result.append(node.name+", ");
        }
        return result.toString();
    }

    private void traverse(Node node, Set<Node> visited)
    {
        if (visited.contains(node))
        {
            return;
        }
        visited.add(node);
        for (Edge edge : node.edges)
        {
            if (edge.n0.equals(node))
            {
                traverse(edge.n1, visited);
            }
            if (edge.n1.equals(node))
            {
                traverse(edge.n0, visited);
            }
        }
    }


}

 

[bloody_beginner]

@Marco13: Vielen Dank!