Erste Schritte Baumstruktur (dynamisch)

[Chaya]

Guten Tag zusammen,
da schreibe ich jetzt meinen ersten Eintrag und habe gleich eine Frage an euch, weil ich leider keinen Einstiegspunkt finde.

Und zwar habe ich die Aufgabe das Nutzerverhalten auf einer Website zu analysieren.
Genauer gesagt sollen hier die Klickpfade dargestellt werden (wie häufig wird der gleiche Weg gegangen, ...)

Das ganze möchte ich dann in einer Baumstruktur darstellen.
Die Daten hierzu hole ich mir aus einem Logfile, das in eine Datenbank geschrieben wird. Aber das nur als Hintergrund. Der Prozess läuft
Das ganze soll dann (stark vereinfacht) ungefähr so aussehen:

Hier hätte ich dann folgende Verläufe
Startseite -> Produkte -> TV
Startseite -> Produkte -> Handys
Startseite -> Produkte -> Laptops
Startseite -> Flyer
Startseite -> Suche

Nur... wie bekomme ich das hin?
Es geht mir jetzt erstmal gar nicht um die richtigen Daten aus der Datenbank, sondern es wäre mir schon sehr geholfen, wenn ich einfach einen Baum bauen könnte, der mir den Baum aus dem Bild baut.
Alles andere ist dann das kleinere Problem, das bekomme ich dann selber hin.
Ich habe Google schon durchforstet, allerdings finde ich da großteils nur etwas zu Binärbäumen. Aber das geht ja nicht, wenn ich mehr als 2 Kinderknoten habe oder? Falls doch wäre es cool, wenn mir hier einer eine kleine Hilfe geben könnte.

Danke schon mal und viele Grüße
Chaya


Edit: Achja, was ich vergaß: kein JTree, ich will das nicht grafisch. Das ganze soll dann in eine CSV geschrieben werden.

 

[Kevin94]

Wenn das ganze ein "echter" Baum ist, d.h. jede Element nur ein übergeordnetes Element besitzt ist es relativ einfach: Jeder Node bekommt als Variablen Parent und eine Liste von Kindern, sowie wie Häufig die Seite aufgerufen wurde.
Wenn eine Seite aber von mehreren anderen Seiten aus aufgerufen werden kann, müssen sowohl Eltern als auch Kinder als List gespeichert werden bzw. als Map<Node,Aufrufe>.

 

[Chaya]

Wenn das ganze ein "echter" Baum ist, d.h. jede Element nur ein übergeordnetes Element besitzt ist es relativ einfach: Jeder Node bekommt als Variablen Parent und eine Liste von Kindern, sowie wie Häufig die Seite aufgerufen wurde.
Wenn eine Seite aber von mehreren anderen Seiten aus aufgerufen werden kann, müssen sowohl Eltern als auch Kinder als List gespeichert werden bzw. als Map<Node,Aufrufe>.

Danke für deine Antwort
Ja, es soll ein echter Baum werden.

Hast du da ein bisschen Code für mich, ich kann mir das leider nicht vorstellen, wie ich das machen muss...

 

[eMmiE]

Beispiel 1: Aufruf nur von einer Seite

class Node {

Node parent;
ArrayList<Node> childs = new ArrayList<>();
int klicks;
String name;

public Node(Node Parent,ArrayList<Node> Childs,int Klicks, String Name) {
//übernehmen der Werte
}

//getter
//...

public boolean hasChild(String name) {
for (int i = 0;i < childs.size();i++) {
if (childs.get(i).name.equals(name)) {
return true;
}
}
return false;
}

public void addChild(Node n) {
childs.add(n);
}

public void addKlicks(int i) {
klicks += i;
}
}

class LinkKlickObjekt {
//die Klasse enthält
LinkKlickObjekt Vorgänger;
LinkKlickObjekt[] Nachfolger
String name;

}

class Main {

LinkKlickObjekt[][] pfade;

public Main() {
//Wenn du das jetzt als String[] (Also alle Pfade, die gegangen wurden) im Format "Startseite>Bücher>Autor>..." übergeben bekommst, dann musst //du das natürlich noch ein bisschen cutten, ich gehe von einem LinkKlickObjekt[][] aus

pfade = pfadeAnlegen();

Node root = new Node(null,null,0,hierDerName);
Node n;

for (int i = 0;i < pfade.length;i++) {
n = root;
for (int j = 0;j < pfade[i].length;j++) {

n = n.getChild(pfade[i][j]);


n.addKlicks(1);
if (j < pfade[i].length - 1) {
if (!n.hasChild(pfade[i][j+1])) {
//Neues Childelement anfügen
n.addChild(new Node(n,null,0,pfade[i][j].name));
}
}
}
}
}

}

Das sieht hier jetzt erstmal ein bisschen unübersichtlich aus

1. Du legst eine Liste (LinkKlickObjekt[][]) mit allen Pfaden (LinkKlickObjekt[]) an, die zur Verfügung stehen
2. Die iterierst du durch
Am Anfang eines Pfads steht ja immer die Startseite
Am Anfang jedes Pfads wird der "bearbeitende Node" (n) auf root, den Anfangsknoten gesetzt
Der hat logischerweise keinen Vorgänger

Jedes Mal, wenn dann das nächste LKO aus einem Pfad aufgerufen wird, wird der n zur Referenz auf den jeweiligen Child-Knoten (...getChild())
Er fügt erst dem Objekt einen Klick zu, dann guckt er, ob das Ende des Pfads erreicht ist (Er muss dann keinen Knoten anfügen) oder ob der nächste Child-Knoten noch nicht enthalten ist.
Dann fügt er einen neuen hinzu.

So sollten dann alle Pfade in Knoten und Werte aufgeteilt sein

Gruß eMmiE

P.S.: Ist nur ein Ansatz, also bitte nicht hauen

 

[Chaya]

@eMmiE:
ja genau

ich habe als Beispiel die folgenden Pfade:
Startseite -> Produkte -> TV
Startseite -> Produkte -> Handys
Startseite -> Produkte -> Laptops
Startseite -> Flyer
Startseite -> Suche

Dann möchte ich, dass mein Oberpunkt die "Startseite" ist, von da aus sollen dann Äste weggehen zu "Produkte", "Flyer" und "Suche". "Produkte" gabelt sich dann wieder auf in "TV", "Handys" und "Laptops".

Gespeichert werden sollte es dann so:

Startseite;Produkte (3);TV (1)
Startseite;Produkte (3);Handys (1)
Startseite;Produkte (3);Laptops (1)
Startseite;Flyer (1)
Startseite;Suche (1)

aber das Speichern ist erst mal nicht so wichtig, eher, dass ich diese Struktur hinbekomme.

Oh je, ich hoffe ich habe das gescheit erklärt :/

 

[eMmiE]

Siehe oben

(Wird leider nicht mehr angezeigt, wenn ein Beitrag zugefügt wurde, während du einen schreibst...)

Bei mehreren Startseiten natürlich mehrere Bäume

 

[Chaya]

oh wow, super, ich danke dir
Das werde ich mir gleich mal genauer anschauen. Genau sowas habe ich gebraucht! :toll:

Wenn ich dazu noch fragen habe, dann melde ich mich wieder.

Nochmals tausend Dank!

 

[Chaya]

hm, okay... irgendwie komme ich nicht so drauf wie ich die pfadeAnlegen() Methode füllen soll

 

[eMmiE]

Frage: WIE bekommst du deine Pfade?
1. String[] oder String[][]
2. In welchem Format sind die (Bsp. 1: "Start>Bücher.Bücher>Comics.Comics>Superman[...]" o. Bsp. 2: "Start>Bücher>Comics[...]" (Was Anderes fällt mir jetzt gar nicht ein))
3. Am besten mit Codesnippet

Gruß eMmiE

 

[Chaya]

Guten Morgen

Ich habe mich jetzt nochmal mit einem Kollegen zusammen gesetzt und wir sind das ganze durchgegangen (schade, dass ich es nicht alleine schaffen konnte)
Der Ansatz ist jetzt ein bisschen anders, als der von dir @eMmiE
Die Pfade kommen übrigens aus einer Datenbank. Die Zusammengehörigkeit wird durch die SessionID gekennzeichnet.

Demnach habe ich folgende Klassen:

package tree;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;

public class DbConnection {
	String host = "jdbc:mysql://localhost:3306/";
	String dbname = "acceslogs";
	String username = "root";
	String password = "";

	String shorturl = host + dbname;
	
	public Connection getConnection() throws SQLException, ClassNotFoundException {
		Class.forName("com.mysql.jdbc.Driver");
		Connection conn = DriverManager.getConnection(shorturl, username, password);
		return conn;
	}
}

package tree;

import java.util.ArrayList;

public class Node {
	Node parent;
	ArrayList<Node> children = new ArrayList<Node>();
	int clicks;
	String name;
	
	Node(Node parent, String name){
		this.parent = parent;
		if (parent != null)
			parent.addChild(this);
		this.clicks = 1;
		this.name = name;
	}
	

	
	Node(){
		this.parent = null;
		this.children = null;
		this.clicks = 0;
		this.name = null;
	}
	
	Node(String name) {
		this.clicks = 1;
		this.name =name;
	}



	public Node getParent(){
		return parent;
	}
	
	public int getClicks(){
		return clicks;
	}
	
	public ArrayList<Node> getChildren(){
		return children;
	}
	
	public void setParent(Node parent){
		this.parent = parent;
	}
	
	public void addClicks(){
		this.clicks += 1;
	}
	
	public void addChild(Node child){
		child.setParent(this);
		this.children.add(child);
	}
	
	public boolean hasChild(String child){
		return false;		
	}
	
	
	
	
	public String toString() {
		String ret = "";
		if (parent!= null) {
			ret += parent.toString();
		}
		ret += "/" + name;
		return ret;
	}
	
	public String toStringDown(){
		String ret = name+"("+clicks+")"+"\n";
		int lvl = getHierachyDepth();
		for(Node child: children) {
			for(int i=0;i<lvl;i++) ret +="   ";
			ret += "|--" + child.toStringDown();
		}
		return ret;
	}
	
	public int getHierachyDepth(){
		int ret = 1;
		if(parent!=null)
			ret += parent.getHierachyDepth();
		return ret;
	}

	
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((name == null) ? 0 : name.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Node other = (Node) obj;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}

	

	public Node getChild(Node newNode) {
		return children.get(children.indexOf(newNode));
	}

}

package tree;

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;

public class Run {
	
	
	
	public static void main(String[] args) throws ClassNotFoundException, SQLException, FileNotFoundException, UnsupportedEncodingException{
		DbConnection conn = new DbConnection();
		Statement stmt = conn.getConnection().createStatement();
		
		System.out.println("Query");
		
		ResultSet res = stmt.executeQuery("select accesstime, uripath, sessionid "
				+ "from acceslogs.logs "
				+ "where sessionid is not null "
				+ "order by sessionid,accesstime");
		
		
		
		Node root = new Node(null, "Start");
		String tmp = "";
		Node toAddChild = root;
		System.out.println("Executed. Starting rendering");
		while(res.next()){			
			if(!tmp.equals(res.getString(3))){
				toAddChild=root;
				tmp = res.getString(3);
			}			
			String path = res.getString(2); //substr
			int index = path.indexOf('?');
			if(index > 0)
				path = path.substring(0, index);
			Node newNode = new Node(path); //konstruktor
			if(toAddChild.getChildren().contains(newNode)) {
				newNode = toAddChild.getChild(newNode);
				newNode.addClicks(); //bauen
			} else {
				toAddChild.addChild(newNode);
			}
			toAddChild = newNode;
		}
		
		conn.getConnection().close();
		
		
		System.out.println("Starting to print");
		
		
		PrintWriter writer = new PrintWriter("paths_full.txt", "UTF-8");
		writer.println(root.toStringDown());
		writer.close();
		
		System.out.println("Done");
		
	}

}

Aber ohne deinen Vorschlag wäre ich da auch mit Hilfe nicht durchgestiegen. Danke