class CGraph extends MovieClip {
	
	var urlToGraph;
	private var data;
	
	function CGraph() {
		if (urlToGraph != undefined && this['area'] == undefined) loadGraph(urlToGraph);
	}
	
	var onGraphLoad:Function;
	function loadGraph(wGraph) {
		urlToGraph = wGraph;
		if (urlToGraph instanceof XML) {
			data = urlToGraph;
			data.ignoreWhite = true;
			onDataReady();
		} else {
			data = new XML('<graph></graph>');
			data.ignoreWhite = true;
			data._parent = this;
			data.onLoad = function (success) {
				this._parent.onDataReady(); 
				delete this._parent;
			}
			if (urlToGraph != undefined) data.load(urlToGraph);
		}
	}
	private function onDataReady() {
		data.ready = true;
		trigger('onDataChange');
		onGraphLoad();
	}
	
	var eventList;
	private function trigger(wEvent) {
		if (eventList == undefined) eventList = [ ];
		for (var prop in eventList) if (eventList[prop] == wEvent) return;
		eventList.push(wEvent);
		onEnterFrame = function () {
			delete onEnterFrame;
			while (eventList.length) this[eventList.pop()]();
		}
	}
	
	/*- generate */ 
	function generate(wMinNodes, wMaxNodes, wXOffset, wYOffset, wXMLString) {
		if (wMinNodes == undefined) wMinNodes = 3; 
		if (wMaxNodes == undefined) wMaxNodes = 5; 
		if (wXOffset == undefined) wXOffset = 0; 
		if (wYOffset == undefined) wYOffset = 0; 
		if (wXMLString == undefined) wXMLString = '<graph><assets><icon id="1" uri="icComputer" attach="true" /><edge id="1" uri="egStraight" attach="true" /></assets><nodes defaulticon="1"></nodes><links defaultedge="1"></links></graph>';
		// 
		var gphXML = new XML(wXMLString);
		var nodes = gphXML.firstChild.firstChild.nextSibling, nNodes, iNode;
		var links = nodes.nextSibling, nLinks, iLink, usedLink = [ ];
		var i;
		// 
		nNodes = wMinNodes + Math.floor(Math.random()*(wMaxNodes-wMinNodes+1));
		for (i = 1; i <= nNodes; i++) {
			var iNode = gphXML.createElement('node');
			iNode.attributes.name = '' + i;
			iNode.attributes.id = i;
			iNode.attributes.x = Math.round(Math.sin(2*Math.PI*(i-1)/nNodes - 5*Math.PI/6)*35) +50 +wXOffset;
			iNode.attributes.x += Math.round(Math.random()*15)-7;
			iNode.attributes.y = Math.round(Math.cos(2*Math.PI*(i-1)/nNodes - 5*Math.PI/6)*35) +50 +wYOffset;
			iNode.attributes.y += Math.round(Math.random()*15)-7;
			nodes.appendChild(iNode);
		}
		// 
		nLinks = nNodes + 1 + Math.floor(Math.random()*(wMaxNodes-nNodes));
		if (nLinks > nNodes*(nNodes-1)/2) nLinks = nNodes*(nNodes-1)/2; 
		var nLeft = [ ], nNodeX, nNodeY; 
		for (i = 1; i <= nNodes; i++) nLeft.push(i); 
		nNodeX = nLeft.splice(Math.floor(Math.random()*nLeft.length), 1)[0]; 
		for (i = 1; i < nNodes; i++) {
			var iLink = gphXML.createElement('link');
			nNodeY = nLeft.splice(Math.floor(Math.random()*nLeft.length), 1)[0]; 
			iLink.attributes.nodex = nNodeX;
			iLink.attributes.nodey = nNodeY;
			usedLink[(nNodeX-1)*nNodes+nNodeY-1] = true;
			iLink.attributes.cost = 
				Math.round(Math.sqrt(
					Math.pow(nodes.childNodes[nNodeX-1].attributes.x-nodes.childNodes[nNodeY-1].attributes.x, 2) + 
					Math.pow(nodes.childNodes[nNodeX-1].attributes.y-nodes.childNodes[nNodeY-1].attributes.y, 2)
				));
			if (iLink.attributes.cost > 99) iLink.attributes.cost = 99; 
			links.appendChild(iLink);
			nNodeX = nNodeY; 
		}
		for (/* */; i <= nLinks; i++) {
			var iLink = gphXML.createElement('link');
			do {
				nNodeX = 1 + Math.floor(Math.random()*nNodes);
				nNodeY = 1 + Math.floor(Math.random()*nNodes);
			} while (usedLink[(nNodeX-1)*nNodes+nNodeY-1] || usedLink[(nNodeY-1)*nNodes+nNodeX-1] || nNodeX == nNodeY);
			iLink.attributes.nodex = nNodeX;
			iLink.attributes.nodey = nNodeY;
			usedLink[(iLink.attributes.nodex-1)*nNodes+iLink.attributes.nodey-1] = true;
			iLink.attributes.cost = 
				Math.round(Math.sqrt(
					Math.pow(nodes.childNodes[nNodeX-1].attributes.x-nodes.childNodes[nNodeY-1].attributes.x, 2) + 
					Math.pow(nodes.childNodes[nNodeX-1].attributes.y-nodes.childNodes[nNodeY-1].attributes.y, 2)
				));
			if (iLink.attributes.cost > 99) iLink.attributes.cost = 99; 
			links.appendChild(iLink);
		}
		// 
		loadGraph(gphXML);
	}
	
	/*- verificare */ 
	function isConnex() {
		if (links.childNodes.length < nodes.childNodes.length-1) return false; 
		var nodes = data.nodes, links = data.links; 
		var i, ccon = [ ], min, max; 
		for (var iNode = nodes.firstChild; iNode; iNode = iNode.nextSibling) {
			i = Number(iNode.attributes.id); 
			ccon[i] = i; 
		} 
		for (var iLink = links.firstChild; iLink; iLink = iLink.nextSibling) {
			min = Math.min( ccon[iLink.attributes.nodex], ccon[iLink.attributes.nodey] ); 
			max = Math.max( ccon[iLink.attributes.nodex], ccon[iLink.attributes.nodey] ); 
			for (i = 1; i <= ccon.length; i++) if (ccon[i] == max) ccon[i] = min; 
		} 
		for (i = 1; i < ccon.length; ) {
			if (ccon[i] == undefined) ccon.splice(i, 1); 
			else i++; 
		} 
		for (i = 1; i < ccon.length-1; i++) {
			if (ccon[i] != ccon[i+1]) return false;
		} 
		return true; 
	}
	
	/*- get APM Kruskal */
	function getAPM() {
		return getAPMKruskal();
	}
	function getAPMKruskal() {
		var errorMessage = ''; 
		var aSubGraph = new CSubGraph(this); 
		var nNodes, iNode, nodes = data.nodes;
		var nLinks, iLink, links = data.links;
		var usedNode = new Array(), usedLink = new Object();
		// count Nodes
		nNodes = 0;
		for (iNode = nodes.firstChild; iNode; iNode = iNode.nextSibling) {
			nNodes++;
			usedNode[iNode.attributes.id] = iNode.attributes.id;
		}
		if (nNodes == 0) {
			errorMessage += 'Nu exista computere.';
			return errorMessage;
		} else if (nNodes == 1) {
			errorMessage += 'Exista doar un computer.';
			return errorMessage;
		}
		// count Links
		nLinks = 0;
		for (iLink = links.firstChild; iLink; iLink = iLink.nextSibling) {
			nLinks++;
		}
		if (nLinks == 0) {
			errorMessage += 'Nu exista legături.';
			return errorMessage;
		} else if (nLinks < nNodes-1) {
			errorMessage += 'Nu toate computerele sunt legate între ele.';
			return errorMessage;
		}
		// 
		var minLink, minNode;
		var iSafetyBreak = 0;
		while (true) {
			if (++iSafetyBreak == 100000) break;
			// stop condition 1
			for (iNode = nodes.firstChild; iNode.nextSibling; iNode = iNode.nextSibling) {
				if (usedNode[iNode.attributes.id] != usedNode[iNode.nextSibling.attributes.id]) break;
			}
			if (iNode.nextSibling == null) break;
			// get minimum
			minLink = null;
			for (iLink = links.firstChild; iLink; iLink = iLink.nextSibling) {
				//! trace(' » [' + iLink.attributes.nodex + ', ' + iLink.attributes.nodey + ']: ' + usedLink[iLink.attributes.nodex + '_' + iLink.attributes.nodey]);
				if (usedLink[iLink.attributes.nodex + '_' + iLink.attributes.nodey] == true) continue;
				if (minLink == null || Number(iLink.attributes.cost) < Number(minLink.attributes.cost)) {
					minLink = iLink;
				}
			}
			// stop condition 2
			if (minLink == null) break;
			iLink = minLink;
			// mark as chosen
			usedLink[iLink.attributes.nodex + '_' + iLink.attributes.nodey] = true;
			// verify connexity
			if (usedNode[iLink.attributes.nodex] == usedNode[iLink.attributes.nodey]) continue;
			minNode = usedNode[iLink.attributes.nodex];
			for (iNode = nodes.firstChild; iNode; iNode = iNode.nextSibling) {
				if (usedNode[iNode.attributes.id] == minNode) usedNode[iNode.attributes.id] = usedNode[iLink.attributes.nodey];
			}
			// mark 
			aSubGraph.addLink(iLink); 
		}
		// test conexity
		for (iNode = nodes.firstChild; iNode.nextSibling; iNode = iNode.nextSibling) {
			if (usedNode[iNode.attributes.id] != usedNode[iNode.nextSibling.attributes.id]) break;
		}
		if (iNode.nextSibling != null) {
			errorMessage += 'Nu toate computerele sunt legate între ele.';
			return errorMessage;
		}
		return aSubGraph;
	}
	
	/*- get APM Prim */
	function getAPMPrim() {
		var errorMessage = ''; 
		var aSubGraph = new CSubGraph(this);
		var inod, nodes = data.nodes;
		var ilink, nLinks, links = data.links;
		var i, n, j, ii, jj, min, ok;
		var prim = new Array(), notes = new Array();
		n=0;
		for(inod = nodes.firstChild;inod;inod = inod.nextSibling){
		    prim[inod.attributes.id] = new Array();
			n++;
		}
		if (n == 0) {
			errorMessage += 'Nu exista computere.';
			return errorMessage;
		} else if (n == 1) {
			errorMessage += 'Exista doar un computer.';
			return errorMessage;
		}
		for (ilink = links.firstChild; ilink; ilink = ilink.nextSibling) {
			nLinks++;
		}
		if (nLinks == 0) {
			errorMessage += 'Nu exista legături.';
			return errorMessage;
		}
		else if (nLinks < n-1) {
			errorMessage += 'Nu toate computerele sunt legate între ele.';
			return errorMessage;
		}
		for(ilink = links.firstChild;ilink;ilink = ilink.nextSibling){
			prim[ilink.attributes.nodex][ilink.attributes.nodey] = Number(ilink.attributes.cost);
			prim[ilink.attributes.nodey][ilink.attributes.nodex] = Number(ilink.attributes.cost);
		}
		notes[1] = 1;
		min = 100;
		ok=1;
		while(ok){
			ok=0;
			min=100;
			for(i = 1; i<=n;i++)
				if(notes[i])
					for(j=1; j<=n; j++)
						if(!notes[j]){
							if(prim[i][j] != undefined && min > prim[i][j]){
								min=prim[i][j];
								ii = i;
								jj = j;
								ok=1;
							}
						}
			if (!ok) break; 
			notes[jj]=1;
			for(ilink = links.firstChild;ilink;ilink = ilink.nextSibling){
				if(ilink.attributes.nodex == ii && ilink.attributes.nodey == jj) aSubGraph.addLink(ilink);
				else if(ilink.attributes.nodey == ii && ilink.attributes.nodex == jj) aSubGraph.addLink(ilink);
			}
		}
	 for(i=1; i<=n; i++)
	      if(!notes[i]){
			errorMessage += 'Nu toate computerele sunt legate între ele.';
			return errorMessage;
		}
	 return aSubGraph;
	}
}