Γράφοι χωρίς συντεταγμένες.

Σε μια εργασία που είχα πρόσφατα για τεχνητή 
νοημοσύνη μας δίνονταν γράφοι με την εξής μορφή:

	# Estimation until Bucharest
	Timisoara 329
	Lugoj 246
	Mahadia 247
	Dobreta 242
	...
	# Origin destination cost
	Timisoara Arad 110
	Arad Zerind 75
	Arad Sibiu 140
	Zerind Oradea 71
	Oradea Sibiu 151
	Timisoara Lugoj 111
	...

view raw graph.txt hosted with ❤ by GitHub

Μπορείτε να δείτε όλοκληρο το text εδώ

και έπρεπε να εμφανίζουμε το path από ένα αρχικό 
κόμβο σε έναν τελικό κόμβο δοκιμάζοντας
διάφορους αλγόριθμους αναζήτησης όπως ο A* , 
uniform cost , depth first search , breadth first search.

Οπότε μετά το πέρας της εργασίας απέκτησα το εξής ερώτημα:

-Πως θα μπορούσε κάποιος να απεικονήσει τους παραπάνω γράφους χωρίς να γνωρίζει λεπτομέρειες όπως συντεταγμένες.

Η αρχική ιδέα ήταν να δημιουργήσω ομογενείς κύκλους με κέντρο τον κόμβο που έχει ευρετικό 0. Άρα με βάση την ευρετική τιμή του κάθε κόμβου η ευρετική τιμή θα αποτελούσε την ακτίνα του κόμβου από το 0,0 όπου βρίσκεται ο κόμβος - στόχος αυτός που έχει ευρετικό 0.
Και για να μην είναι όλοι οι κόμβοι στην ίδια ευθεία πολύ απλά ο καθένας θα έχει γωνία: (count / πλήθος των κόμβων * 2π)
Όπου το count θα ξεκινάει από το 1 και θα ανεβαίνει κατα 1 για κάθε κόμβο. O κώδικας που χρησιμοποιήθηκε είναι της παρακάτω μορφής και έβγαζε έναν γράφο όπως αυτόν

-Τό πρόβλημα με το εξής σύστημα είναι ότι οι γραμμές και οι κόμβοι τέμνονται συχνά.

	public void constructGraph(){
	visualNodes.clear();
	visualEdges.clear();
	int count = 1;
	for (String name: graph.graph.keySet()){
	visualNode currentNode = new visualNode();
	currentNode.actualNode = graph.graph.get(name);
	currentNode.nodeNumberId = count;
	currentNode.nodeCount = graph.graph.size();
	currentNode.nodeColor = graph.graph.get(name).nodeColor;
	visualNodes.put(graph.graph.get(name), currentNode);
	count +=1;
	...
	}
	}

view raw heuristic.java hosted with ❤ by GitHub

Η δεύτερη ιδέα είναι ξεκινόντας από έναν κόμβο να αρχίσεις να τοποθετείς γύρω του σε έναν κύκλο όλους τους γειτονικούς του κόμβους οι οποίοι δεν έχουν ήδη τοποθετηθεί .Η φόρμουλα των γωνιών του κύκλου είναι όμοια με την παραπάνω: (count / πλήθος των γειτονικών κόμβων * 2π)

-Το κακό είναι ότι αυτή η μέθοδος λειτουργεί μόνο για γράφους των οποίων ΌΛΟΙ οι κόμβοι είναι συνδεδεμένοι στον γράφο.

	while (!openQueue.isEmpty()) {
	currentNode = openQueue.poll();
	closedList.add(currentNode);
	double firstDeg = 0;
	double divisions = currentNode.actualNode.costs.size()+1;
	for (Node neighbor: currentNode.actualNode.costs.keySet()){
	double wideX=80, wideY=80;
	firstDeg +=1;
	visualNode currentNeighbor = visualNodes.get(neighbor);
	if (closedList.contains(currentNeighbor)) continue;
	boolean positionedProperly = false;
	while (!positionedProperly){
	// Ελένγχει αν έχει τοποθετηθεί πολύ κοντά ένας
	// κόμβος σε έναν άλλον.
	positionedProperly = true;
	currentNeighbor.calcX(wideX, currentNode.x, firstDeg/divisions);
	currentNeighbor.calcY(wideY, currentNode.y, firstDeg/divisions);
	for (visualNode otherNode: closedList){
	double d = Math.sqrt(Math.pow(otherNode.x - currentNeighbor.x, 2)+Math.pow(otherNode.y - currentNeighbor.y, 2));
	if (d < shouldBeAwayDistance){
	positionedProperly = false;
	break;
	}
	}
	wideX += 50;
	wideY += 50;
	}
	if (!closedList.contains(currentNeighbor)) {
	openQueue.add(currentNeighbor);
	}
	}
	}

view raw expandNodes.java hosted with ❤ by GitHub