graphdrawing.java

toocom源代码,主要应用在本体匹配方面!

package toocom.ui;

import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.geom.*;
import java.awt.font.*;
import toocom.ocgl.*;

/**
 * This class implements the force directed algorithm for helping in graph
 * drawing. It has it's own representation of a graph, which is optimized
 * for applying the algorithm. The attributes nnodes, nodes, nedges and edges
 * provide an optimized representation of graphs: the pointer vectors allow
 * a fast access to nodes and edges, access is linear. The temperature represents
 * the maximum amount of movement allowed for each point (in pixels). It may be
 * decreased along the time. A pointer to The AxiomPanel allows to redraw it
 * frequently, as the GraphDrawing class executes the algorithm in a separated
 * thread.
 * 
 * @author Nicolas Roy
 * @author Matthieu Le Gall
 * @author Dounia Keda
 */
public class GraphDrawing implements Runnable{

	//Request for stopping the thread
	boolean stopRequest=false;

	//The nodes
	int nnodes;
    Node nodes[];
	
	//The edges
    int nedges;
    Edge edges[];

	//The ideal length of edges
	int k;

	//Temperature of the algorithm
	double temperature;

	//Half size of the biggest box in the graph
	int boxHalfSizeX;
	int boxHalfSizeY;

	//Link to the panel in which the graph is drawned
	AxiomsPanel axiomsPanel;

	/** Constructor */
	public GraphDrawing(AxiomsPanel aP, Axiom a){
		axiomsPanel=aP;
		loadAxiom(a);
		Thread t=new Thread(this);
		t.start();
	}


	/** Search method : Returns the position of the node n in the nodes list */
	private int findNode(Node n)
	{
		for (int i = 0 ; i < nnodes ; i++) {
			if (nodes[i].equals(n)) return i;
		}
		return (-1);
	}


	
	/** Returns the number of Nodes of an Axiom */
	private int AxiomNodesNumber(Axiom a){
		int n=0;
		for(Iterator i = a.getHypothesisRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			n++;
		}
		for(Iterator i = a.getHypothesisConcepts().iterator();i.hasNext();){
			Concept c = (Concept) i.next();
			n++;
		}
		for(Iterator i = a.getConclusionRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			n++;
		}
		for(Iterator i = a.getConclusionConcepts().iterator();i.hasNext();){
			Concept c = (Concept) i.next();
			if(!a.hasHypothesisConclusionConcept(c)) {
				n++;
			}
		}
		return (n);
	}


	
	/** Returns the number of edges of an Axiom */
	private int AxiomEdgesNumber(Axiom a){
		int n=0;
		//Hypothesis relations
		for(Iterator i = a.getHypothesisRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			int rIndex=findNode(r);
			if(r.getType() != null){
				for (int j=1; j<=r.getType().getArity(); j++ ) {
					if (r.getLinkedConcept(j) != null) {
						n++;
					}
				}
			}
			else{
				for (int j=1; j<= CGConstants.RELATION_TYPE_MIN_ARITY; j++ ) {
					if (r.getLinkedConcept(j) != null) {
						n++;
					}
				}
			}
		}
		//Conclusion Relations
		for(Iterator i = a.getConclusionRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			int rIndex=findNode(r);
			if(r.getType() != null){
				for (int j=1;j <= r.getType().getArity(); j++ ) {
					if (r.getLinkedConcept(j) != null) {
						n++;
					}
				}
			}
			else{
				for (int j=1;j <= CGConstants.RELATION_TYPE_MIN_ARITY; j++ ) {
					if (r.getLinkedConcept(j) != null) {
						n++;
					}
				}
			}
		}
		return (n);
	}

	/** Loading method for axioms : Initializes edges, nodes, nedges, nnodes, k,
	 * temperature, boxHalfSizeX and boxHalfSizeY with the given axiom.
	 */
	private void loadAxiom(Axiom a){
		//Allocate memory for the edges and nodes
		nodes = new Node[AxiomNodesNumber(a)];
		edges = new Edge[AxiomEdgesNumber(a)];
		nnodes=0;
		nedges=0;

		//This Fills the nodes vector
		for(Iterator i = a.getHypothesisRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			nodes[nnodes]=r;
			nnodes++;
		}
		for(Iterator i = a.getHypothesisConcepts().iterator();i.hasNext();){
			Concept c = (Concept) i.next();
			nodes[nnodes]=c;
			nnodes++;
		}
		for(Iterator i = a.getConclusionRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			nodes[nnodes]=r;
			nnodes++;
		}
		for(Iterator i = a.getConclusionConcepts().iterator();i.hasNext();){
			Concept c = (Concept) i.next();
			if(!a.hasHypothesisConclusionConcept(c)) {
				nodes[nnodes]=c;
				nnodes++;
			}
		}

		//This fills the edges
		//Hypothesys relations
		for(Iterator i = a.getHypothesisRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			int rIndex=findNode(r);
			for (int j=1; j<=r.getType().getArity(); j++ ) {
				if (r.getLinkedConcept(j)!=null) {
					//Adding the edge (r, getLinkedConcept(j))
					edges[nedges]=new Edge(rIndex,findNode(r.getLinkedConcept(j)),150);
					nedges++;

				}
			}
		}
		//Conclusion relations
		for(Iterator i = a.getConclusionRelations().iterator();i.hasNext();){
			Relation r = (Relation) i.next();
			int rIndex=findNode(r);
			for (int j=1; j<=r.getType().getArity(); j++ ) {
				if (r.getLinkedConcept(j)!=null) {
					//ajout de l'ar阾e r-getLinkedConcept(j)
					edges[nedges]=new Edge(rIndex,findNode(r.getLinkedConcept(j)),150);
					nedges++;
				}
			}
		}

		
		//Calculate the ideal length of edges
		Dimension d = axiomsPanel.getSize();
		k=(int) Math.sqrt(d.getHeight()*d.getWidth()/nnodes)/2;
		for (int i = 0 ; i < nedges ; i++) {
		    Edge e = edges[i];
			e.setLength(k);
		}

		//Record the half size of the biggest box (for borders)
		boxHalfSizeX=0;
		boxHalfSizeY=0;
		for (int i = 0 ; i < nnodes ; i++) {
			Node n = nodes[i];
			boxHalfSizeX=Math.max(boxHalfSizeX,(int) n.getBounds(axiomsPanel.getGraphics(), axiomsPanel.getOntologyLanguage()).getWidth());
			boxHalfSizeY=Math.max(boxHalfSizeY,(int) n.getBounds(axiomsPanel.getGraphics(), axiomsPanel.getOntologyLanguage()).getHeight());
		}
		boxHalfSizeX=boxHalfSizeX/2+1;
		boxHalfSizeY=boxHalfSizeY/2+1;
	}

	/** Attractive force function**/
	private double fa(double z) {
		return (z*z/k)/10;
	}

	/** Repulsive force function**/
	private double fr(double z) {
		return (k*k/z)/10;
	}

	/** This method calculate the new position of the nodes **/
	void relax() {

		//Repulsive forces
		for (int i = 0 ; i < nnodes ; i++) {
			Node v = nodes[i];
			for (int j = 0 ; j < nnodes ; j++) {
			    Node u = nodes[j];
				if (i!=j)
				{
					int deltaX=v.x-u.x;
					int deltaY=v.y-u.y;
					if (deltaX==0 && deltaY==0) {
						//Case of two points at the same position
						deltaX=(int) Math.ceil(Math.random()*11)-5;
						deltaY=(int) Math.ceil(Math.random()*11)-5;
					}
					double deltaNorme = Math.sqrt(deltaX * deltaX + deltaY * deltaY);
					v.dx+=deltaX*fr(deltaNorme)/deltaNorme;
					v.dy+=deltaY*fr(deltaNorme)/deltaNorme;
				}
			}
		}

		//Attractive forces
		for (int i = 0 ; i < nedges ; i++) {
		    Edge e = edges[i];
			int deltaX=nodes[e.to].x-nodes[e.from].x;
			int deltaY=nodes[e.to].y-nodes[e.from].y;
		    double deltaNorme = Math.sqrt(deltaX * deltaX + deltaY * deltaY);
			nodes[e.to].dx-=deltaX*fa(deltaNorme)/deltaNorme;
			nodes[e.to].dy-=deltaY*fa(deltaNorme)/deltaNorme;
			nodes[e.from].dx+=deltaX*fa(deltaNorme)/deltaNorme;
			nodes[e.from].dy+=deltaY*fa(deltaNorme)/deltaNorme;
		}
	
		//bounds the points displacement
		Dimension d = axiomsPanel.getSize();
		for (int i = 0 ; i < nnodes ; i++) {
		    Node v = nodes[i];
			if (!v.fixed()) {
				//The point is not fixed
				double vNorme=Math.sqrt(v.dx * v.dx + v.dy * v.dy);
	//			Those functions are the ones described in the original algorithm
	//			int dx=(int) ((v.dx/vNorme)*Math.max(Math.min(v.dx,temperature),-temperature));
	//			int dy=(int) ((v.dy/vNorme)*Math.max(Math.min(v.dy,temperature),-temperature));
				int dx=(int) v.dx;
				int dy=(int) v.dy;
				dx=Math.max(Math.min(dx,(int)temperature),-(int)temperature);
				dy=Math.max(Math.min(dy,(int)temperature),-(int)temperature);

				v.x+=dx;
				v.y+=dy;
				//Remaining displacement (<3 improves inerty)
				if (Math.abs(dx)<3) v.dx-=dx;
				else v.dx=0;

				if (Math.abs(dy)<3) v.dy-=dy;
				else v.dy=0;
/*
				v.dx-=dx;
				v.dy-=dy;
*/

				//Keeps all the points inside the drawing area, taking care of the borders
				v.x=Math.min(d.width-boxHalfSizeX, Math.max(boxHalfSizeX, v.x));
				v.y=Math.min(d.height-boxHalfSizeY, Math.max(boxHalfSizeY, v.y));
		    }
			else {
				//The point is fixed
				v.dx=0;
				v.dy=0;
			}
		}
	}


	/** Run method of the thread (implements Runnable)**/
	public void run() {
		temperature=20;
		while (stopRequest==false) {
			//Calculate the new position of the nodes
			relax();
		
			//Redraw the panel
			axiomsPanel.repaint();
			
			//Break
			try { Thread.sleep(10);}
				catch (InterruptedException e) {break;}
		}
	}

	/** Method to be called to stop the thread **/
	public void stop(){
		stopRequest=true;
	}
}