// -*- java -*-
//
// $Rev$
//
// Copyright (C) 2002 Alexios Chouchoulas
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2, or (at your option)
// any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  

// Some useful 'constants'.

var NODE = 1;
var EDGE = 2;
var TWOPI = Math.PI * 2.0;
var NODENAMES = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";


// Precalculated results for [Tacit, Problem 1, 3, 4, 5, and 7]. The first row
// is for nNodes=2.
var RES_TACIT = [ 1, 4, 11, 26, 57, 120, 247, 502, '1,013' ];
var RES_PROB1 = [ 2, 8, 64, '1,024', '32,768', '2,097,152', '268,435,456',
		  '68,719,476,736', '35,184,372,088,832' ];
var RES_PROB2 = [ 1, 7, 63, '1,023', '32,767', '2,097,151', '268,435,455',
		  '68,719,476,735', '35,184,372,088,831' ];
var RES_PROB3 = [ 1, 4, 41, 768, '27,449', '1,887,284', '252,522,481',
		  '66,376,424,160', '34,509,011,894,545' ];
var RES_PROB4 = [ 1, 4, 38, 728, '26,704', '1,866,256', '251,548,592',
		  '66,296,291,072', '34,496,488,594,816' ];
var RES_PROB5 = [ 2, 4, 11, 34, 156, '1,044',  '12,346', '274,668', '12,005,168' ];
var RES_PROB6 = [ 1, 3, 10, 33, 155, '1,043',  '12,345', '274,667', '12,005,167' ];
var RES_PROB7 = [ 1, 2, 6, 21, 112, 853, '11,117', '261,080', '11,716,571' ];


// Calculate the distance of a point to a line in Cartesian 2D
// geometry. The position vector (xp, yp) is the point, while the line
// is defined by the two position vectors (x1, y1), (x2, y2).
function dp2l (xp, yp, x1, y1, x2, y2)
{
    return Math.abs ((x2 - x1) * (y1 - yp) - (x1 - xp) * (y2 - y1)) /
	Math.sqrt ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

// Monkey-patch Array to add comb method to yield set of combinations of n
// members of an array.
Array.prototype.comb = function (n)
{
    if (n === 1) {
	var len = this.length;
	var retval = [];
	for (var i = 0; i < len; i++) retval.push([this[i]]);
	return retval;
    } else {
	var len = this.length;
	var retval = [];
	for (var i = 0; i < len; i++) {
	    var a = this[i];
	    var b = this.slice(i + 1).comb(n - 1);
	    var lenb = b.length;
	    for (var j = 0; j < lenb; j++) {
		var val = b[j];
		val.push (a);
		retval.push (val);
	    }
	}
	return retval;
    }
    return [];
};

// Monkey-patch Array to add comparison method..
Array.prototype.equal = function (list)
{
    var len = this.length;
    var lenb = list.length;
    if (len != lenb) return false;
    for (var i = 0; i < len; i++) {
	if (this[i].compare && !this[i].compare(list[i])) return false;
	else if (this[i] !== list[i]) return false;
    }
    return true;
};

// Monkey-patch Array to add a method to look for certain sequences. Bletch:
// this is O(n^2) because of the sequential 'equal' method. Thankfully, we'll
// be using this on very small arrays.
Array.prototype.findSeq = function (list)
{
    var len = this.length;
    var lenb = list.length;
    for (var i = 0; i < len; i++) {
	if (this.slice (i, i + lenb).equal (list)) {
	    return i;
	}
    }
    return -1;
};

// Monkey-patch Array to add a method that creates and returns a new array that
// contains this array times n.
Array.prototype.times = function (n)
{
    var len = this.length;
    var retval = [];
    for (var i = 0; i < n; i++) {
	retval = retval.concat(this);
    }
    return retval;
};




PolyExplorer = Class.create();

PolyExplorer.prototype.initialize = function(w, h)
{
    try {
	this.input_n = $('input_n');
	this.input_setn = $('input_setn');
	this.input_clear = $('input_clear');
	this.input_connect = $('input_clear');
	this.canvas = $('canvas');
	this.adjTable = $('adjacency');
	
	// Touch up the progress indicator.
	this.progress = $('progress');
	this.progress.hide();
	
	// Form the layers.
	//this.canvas2 = $('canvas2');
	//this.canvas3 = $('canvas3');
	//this.canvas2.absolutize();
	//this.canvas3.absolutize();
	//this.canvas2.clonePosition (this.canvas);
	//this.canvas3.clonePosition (this.canvas);
	//this.canvas2.show();
	//this.canvas3.show();
	
	this.drawn = false;
	this.ctx = this.canvas.getContext("2d");
	//this.ctx2 = this.canvas2.getContext("2d");
	//this.ctx3 = this.canvas3.getContext("2d");
	
	// Hovering
	this.lastHovered = null;

	// Selecting nodes.
	this.nodeA = -1;
	
	// Fade effects.
	this.alphaStep = 0;
	this.alpha = 0.0;
	
	this.w = w;
	this.h = h;
	
	this.padding = 20;
	this.nodeRadius = 10;
	this.nodeRadiusHover = this.nodeRadius;
	this.nodeRadiusClicked = this.nodeRadius + 5;
	this.nodeRadiusInGraph = this.nodeRadius;
	this.nodeCircleMasking = 5;
	
	this.BG = "#111";
	this.nodeFG = "#888";
	this.nodeFGHover = "orange";
	this.nodeFGClicked = "rgba(255,255,255,0.25)";
	this.nodeFGInGraph = "#0470A1";
	
	this.edgeFG = "#1b1b1b";
	this.edgeFGHover = this.nodeFGHover;
	this.edgeFGClicked = this.nodeFGClicked;
	this.edgeFGInGraph = this.nodeFGInGraph;
	
	this.edgeLW = 10;
	this.edgeLineMaskingLW = this.edgeLW + this.nodeCircleMasking + 4;
	this.edgeLWHover = this.edgeLW;
	this.edgeLWClicked = this.edgeLW;
	this.edgeLWInGraph = this.edgeLW;
	
	this.edgeHoverThreshold = this.edgeLW + 5;
	
	Event.observe ($('input_n'), 'change', function(event){
		this.input_setn.disabled=false;
	    }.bindAsEventListener(this));
	
	Event.observe ($('input_setn'), 'click',
		       this.input_setn_onClick.bindAsEventListener(this));
	
	Event.observe ($('input_clear'), 'click',
		       this.input_clear_onClick.bindAsEventListener(this));
	
	Event.observe ($('input_connect'), 'click',
		       this.input_connect_onClick.bindAsEventListener(this));
	
	Event.observe (this.canvas, 'mousemove',
		       this.canvas_onMouseMove.bindAsEventListener(this));
	
	Event.observe (this.canvas, 'click',
		       this.canvas_onClick.bindAsEventListener(this));
	
	Event.observe (this.canvas, 'mouseout',
		       this.canvas_onMouseOut.bindAsEventListener(this));
	
	this.setNodes ($F(this.input_n));
    }
    catch (err) {
	$('no_canvas').show();
	$('poly_explorer').hide();
	$('poly_form').hide();
    }
};


PolyExplorer.prototype.input_setn_onClick = function(event)
{
    event.stop();
    this.setNodes ($F(this.input_n));
};


PolyExplorer.prototype.input_clear_onClick = function(event)
{
    event.stop();
    this.setNodes (this.nNodes);
};


PolyExplorer.prototype.input_connect_onClick = function(event)
{
    event.stop();
    this.hotSpots.each (function (hs) {
	    if (hs.t == EDGE) {
		hs.inGraph = true;
		var edge0 = Math.min(hs.edge[0], hs.edge[1]);
		var edge1 = Math.max(hs.edge[0], hs.edge[1]);
		$('edge_' + edge0 + '_' + edge1).addClassName('edgeInGraph');
	    }
	});
    this.draw();
    // Recalculate stuff (allow a time-out, and run it in the background).
    if (this.calcTimeout) clearTimeout (this.calcTimeout);
    this.progress.show();
    this.calcTimeout = setTimeout (this.calcVolatiles.bind(this), 250);
};


PolyExplorer.prototype.canvas_onMouseMove = function(event)
{
    var x = event.clientX;
    var y = event.clientY;
    var pos = event.target.viewportOffset();
    //console.log ('pos = ' + pos);
    //console.log ('viewport = ' + event.target.viewportOffset());
    //console.log ('client = ' + x + ' ' + y);
    x -= pos[0];
    y -= pos[1];

    var found = null;
    var bestEdge = null;
    var minEdgeDist = this.edgeHoverThreshold;

    // Look for a node.
    this.hotSpots.each(function(hs){
	    /*if ((hs.t == NODE) &&
		(x >= hs.x0) && (x <= hs.x1) &&
		(y >= hs.y0) && (y <= hs.y1)) {
		// If we're in the node's bounding box, highlight it.
		found = hs;
		throw $break;
		} else */ 

	    if (hs.t == EDGE) {
		// Edges may overlap, so defer highlighting until the
		// loop is done. Then, if no node has been
		// highlighted, highlight the node closest to the cursor.
		var dist = dp2l (x, y, hs.x0, hs.y0, hs.x1, hs.y1);
		if (dist < minEdgeDist) {
		    bestEdge = hs;
		    minEdgeDist = dist;
		}
	    }
	}.bind(this));

    // If we haven't found a node, see if we found an edge.
    if (!found) found = bestEdge;
    // This could still be null, but that's alright: highlight() needs this.
    this.highlight (found);
};


PolyExplorer.prototype.canvas_onMouseOut = function(event)
{
    this.highlight(null);
    //console.log('out');
};


PolyExplorer.prototype.canvas_onClick = function(event)
{
    var x = event.clientX;
    var y = event.clientY;
    var pos = event.target.viewportOffset();
    var pos = event.target.positionedOffset();

    var hs = this.lastHovered;
    if (hs !== null) {
	event.stop();
	if (hs.t == NODE) {
	    if (this.nodeA == hs.node) {
		this.nodeA = -1;
	    } else {
		this.nodeA = hs.node;
	    }
	} else if (hs.t == EDGE) {
	    // Toggle edge.
	    hs.inGraph = !hs.inGraph;
	    // Kill the hover selection (makes the change to the graph
	    // immediately obvious without moving the mouse).
	    var oldCursor = document.body.style.cursor;
	    this.highlight(null);
	    this.nodeA = -1;
	    // But keep the cursor the way it was, and reset
	    // lastHovered so another Click event will process the
	    // same edge.
	    document.body.style.cursor = oldCursor;
	    this.lastHovered = hs;

	    // Update the adjacency table.
	    var edge0 = Math.min(hs.edge[0], hs.edge[1]);
	    var edge1 = Math.max(hs.edge[0], hs.edge[1]);
	    $('edge_' + edge0 + '_' + edge1).toggleClassName('edgeInGraph');

	    // Recalculate stuff (allow a time-out, and run it in the background).
	    if (this.calcTimeout) clearTimeout (this.calcTimeout);
	    this.progress.show();
	    this.calcTimeout = setTimeout (this.calcVolatiles.bind(this), 250);
	}
	this.draw();
    } else {
	event.stop();
	this.nodeA = -1;
	this.draw();
    }
};


PolyExplorer.prototype.highlight = function(hs)
{
    //var c = this.ctx2;
    var c = this.ctx;

    if (!hs && !this.lastHovered) return;
    
    if (this.lastHovered !== hs) {
	// Clear the highlight layer
	//console.log('clearing');
	this.draw();
	//c.clearRect (0, 0, this.w, this.h);
    }
    if (hs === null) {
	//console.log('no selection');
	this.lastHovered = null;
	document.body.style.cursor = '';
	// Clear the adjacency table hover class.
	this.adjTable.select('td.edge').each(function(el){el.removeClassName('edgeHover')});
	return;
    }

    if (this.lastHovered === hs) {
	//console.log('no change');
	return;
    }

    // Draw the highlighted thing.

    this.lastHovered = hs;
    if (hs.t == NODE) {
	c.fillStyle = this.nodeFGHover;
	c.beginPath();
	c.arc (hs.xc, hs.yc, this.nodeRadiusHover, 0, TWOPI, 0);
	c.fill();

    } else if (hs.t == EDGE) {
	// Draw the edge line mask.
	c.strokeStyle = this.BG;
	c.lineWidth = this.edgeLineMaskingLW;
	c.beginPath();
	c.moveTo (hs.x0, hs.y0);
	c.lineTo (hs.x1, hs.y1);
	c.stroke();

	// Draw the edge line.
	c.strokeStyle = this.edgeFGHover;
	c.lineWidth = this.edgeLWHover;
	c.beginPath();
	c.moveTo (hs.x0, hs.y0);
	c.lineTo (hs.x1, hs.y1);
	c.stroke();

	// Now draw the two nodes.
	var r = this.nodeRadiusHover;
	c.fillStyle = this.nodeFGHover;
	hs.edge.each (function (i) {
		var node = this.nodes[i];
		c.beginPath();
		c.arc (node[0], node[1], r, 0, TWOPI, 0);
		c.fill();
	    }.bind(this));

	// Now highlight the adjacency table.
	var tdid = 'edge_' + hs.edge[1] + '_' + hs.edge[0];
	this.adjTable.select('td.edge').each(function(el) {
		if (el.id == tdid) {
		    el.addClassName('edgeHover');
		} else {
		    el.removeClassName('edgeHover');
		}
	    });
    }

    // Redraw the node labels.
    this.drawNodeLabels();

    document.body.style.cursor = 'pointer';
};


PolyExplorer.prototype.makeNodes = function()
{
    var n = this.nNodes;
    this.nodes = new Array();

    if (n == 2) {
	this.nodes.push ([0, 0.5]);
	this.nodes.push ([1, 0.5]);
    } else if (n == 3) {
	this.nodes.push ([0, .854]);
	this.nodes.push ([1, .854]);
	this.nodes.push ([0.5, .147]);
    } else if (n == 4) {
	this.nodes.push ([0, 0]);
	this.nodes.push ([1, 0]);
	this.nodes.push ([1, 1]);
	this.nodes.push ([0, 1]);
    } else {
	var step = 2 * Math.PI / n;
	for (var t = 2 * Math.PI; t >= 0.0; t -= step) {
	    var x = 0.5 + 0.5 * Math.sin (t);
	    var y = 0.5 - 0.5 * Math.cos (t);
	    this.nodes.push ([x, y]);
	}
    }

    // Now un-normalise the nodes, and scale/translate them to their
    // appropriate places on the canvas.
    var p = this.padding;
    var w = this.w - (2 * this.padding);
    var h = this.h - (2 * this.padding);
    for (var i = n - 1; i >= 0; i--) {
	var node = this.nodes[i];
	node[0] = Math.round(p + node[0] * w);
	node[1] = Math.round(p + node[1] * h);
    }
};


PolyExplorer.prototype.makeHotSpots = function()
{
    var n = this.nNodes;
    var r = this.nodeRadius;
    var hs = Array();
    var edges = Array();

    // Hot spots for nodes and edges get adde here.
    for (i = n - 1; i >= 0; i--) {
	var xc = this.nodes[i][0];
	var yc = this.nodes[i][1];
	hs.push ({t:NODE, node:i,
		    xc:xc, yc:yc,
		    x0:xc - 2*r, y0:yc - 2 * r,
		    x1:xc + 2 * r, y1:yc + 2 *r});

	// Add edges involving this node. Triangular loop, as this
	// graph is undirected.
	for (j = i - 1; j >= 0; j--) {
	    var xc2 = this.nodes[j][0];
	    var yc2 = this.nodes[j][1];

	    var e = {t:EDGE, edge:[i, j], inGraph:false,
		     x0:xc, y0:yc, x1:xc2, y1:yc2};
	    hs.push (e);
	    edges.push (e);
	}
    }
    this.hotSpots = hs;
};


PolyExplorer.prototype.setNodes = function(n)
{
    var same = n === this.nNodes;
    this.nNodes = n;

    // Reset the form controls.
    this.input_setn.disabled = true;
    this.input_n.selectedIndex = this.nNodes - 2;

    // Calculate the positions of nodes, edges and hot spots.
    this.makeNodes();
    this.makeHotSpots();

    // Unselect everything.
    this.nodeA = -1;

    // Calculate stuff for this graph.
    this.calcBasics();
    this.calcVolatiles();
    
    // Draw (or cross-fade if we're changing number of nodes).
    if (!this.drawn || same) {
	this.draw();
	this.drawn = true;
    } else {
	if (this.effect) {
	    clearTimeout (this.effect);
	}
	this.alpha = 0;
	this.alphaStep = 0.15;
	this.effect = setTimeout (this.appear.bind(this), 30);
    }

    // Recreate the adjacency table.
    this.makeAdjacencyTable();
};


PolyExplorer.prototype.calcBasics = function()
{
    var edges = [];
    var n = this.nNodes;
    for (var i = 0; i < n; i++) {
	for (var j = i + 1; j < n; j++) {
	    edges.push ([i, j]);
	}
    }
    this.allPossibleEdges = edges;

    $('info_numEdges').update(edges.length);

    this.nEdges = 0;

    // Update some information that doesn't change often.
    $('info_nodes').update (this.nNodes);
    // Report numbers of combinations/configurations/permutations:
    $('info_probTacit').update (RES_TACIT[this.nNodes - 2]);
    $('info_prob1').update (RES_PROB1[this.nNodes - 2]);
    $('info_prob2').update (RES_PROB2[this.nNodes - 2]);
    $('info_prob3').update (RES_PROB3[this.nNodes - 2]);
    $('info_prob4').update (RES_PROB4[this.nNodes - 2]);
    $('info_prob5').update (RES_PROB5[this.nNodes - 2]);
    $('info_prob6').update (RES_PROB6[this.nNodes - 2]);
    $('info_prob7').update (RES_PROB7[this.nNodes - 2]);


};

// Returns an array of all nodes involved in graph edges.

PolyExplorer.prototype.getNodes = function()
{
    var retval = [];
    this.hotSpots.each (function (hs) {
	    if (hs.t == EDGE && hs.inGraph) {
		retval.push(hs.edge[0]);
		retval.push(hs.edge[1]);
	    }
	});
    return set(retval);
};

// Returns an array of node degrees. Item 0 contains the number of
// edges involving Node 0, item 1 contains the number of edges
// involving Node 1, etc.

PolyExplorer.prototype.getNodeDegrees = function()
{
    var retval = [];
    for (var i = this.nNodes - 1; i >=0; i--) {
	retval[i] = 0;
    }
    this.hotSpots.each (function (hs) {
	    if (hs.t == EDGE && hs.inGraph) {
		retval[hs.edge[0]]++;
		retval[hs.edge[1]]++;
	    }
	}.bind (this));
    return retval;
};

// Return the degree sequence of the graph.

PolyExplorer.prototype.getDegreeSequence = function()
{
    var degseq = this.getNodeDegrees();
    degseq.sort(function(a, b) { return b - a; });
    return degseq;
};


PolyExplorer.prototype.calcVolatiles = function()
{
    this.progress.hide();
    var oldCursor = document.body.style.cursor;
    document.body.style.cursor = 'wait';

    // Find all nodes involved in edges.
    var involvedNodes = [];
    this.hotSpots.each (function(hs){
	    if (hs.t == EDGE && hs.inGraph) {
		involvedNodes[hs.edge[0]] = 1;
		involvedNodes[hs.edge[1]] = 1;
	    }
	}.bind (this));
    var numInvolvedNodes = 0;
    involvedNodes.each(function(x){if(x)numInvolvedNodes++;});

    var degseq = this.getDegreeSequence();
    var fullyConnected = this.nEdges === this.allPossibleEdges.length;

    // Any quints or higher order fully connected subgraphs? We need at least
    // 5-node graphs for these.
    var quintsOrHigher = false;
    if (this.nNodes >= 5) {
	quintsOrHigher = fullyConnected;
	if (!quintsOrHigher) quintsOrHigher = quintsOrHigher || this.hasAnyConnectedSubgraph(5);
    }

    $('info_edges').update (this.nEdges);
    $('info_degseq').update ('{' + degseq + '}');
    
    this.updateBool ('info_empty', this.nEdges === 0);
    this.updateBool ('info_fullyConnected', fullyConnected);
    this.updateBool ('info_hasSingles', numInvolvedNodes < this .nNodes);

    this.updateBool ('info_hasConnected2Subgraph', this.hasConnectedSubgraph(2));
    this.updateBool ('info_hasConnected3Subgraph', this.hasConnectedSubgraph(3));
    this.updateBool ('info_hasConnected4Subgraph', this.hasConnectedSubgraph(4));

    this.updateBool ('info_hasConnectedNSubgraph', quintsOrHigher);

    // Poly by generally understood meaning?
    this.updateBool ('info_polyCriterion', degseq[0] > 1);

    // Evaluate the Tacit criterion.
    this.updateBool ('info_tacitCriterion', this.tacitCriterion());

    document.body.style.cursor = oldCursor;
};


PolyExplorer.prototype.appear = function()
{
    this.alpha = Math.min (this.alpha + this.alphaStep, 1.0);
    this.ctx.globalAlpha = this.alpha;
    this.draw();
    if (this.alpha < 1.0) {
	this.effect = setTimeout (this.appear.bind(this), 30);
    } else {
	this.effect = null;
    }
};


PolyExplorer.prototype.draw = function()
{
    var c = this.ctx;
    c.fillStyle = this.BG;
    c.fillRect (0, 0, this.w, this.h);
    
    var n = this.nNodes;
    var r = this.nodeRadius;
    var nodesInGraph = new Array();

    // First, draw edges NOT in the graph (these go in the background);
    c.strokeStyle = this.edgeFG;
    c.lineWidth = this.edgeLW;
    this.hotSpots.each (function (hs) {
	    if (hs.t === EDGE && !hs.inGraph) {
		nodesInGraph[hs.edge[0]] = false;
		nodesInGraph[hs.edge[1]] = false;
		c.beginPath();
		c.moveTo (hs.x0, hs.y0);
		c.lineTo (hs.x1, hs.y1);
		c.stroke();
	    }
	}.bind(this));

    // Then, draw edges in the graph.
    this.nEdges = 0;
    c.strokeStyle = this.edgeFGInGraph;
    c.lineWidth = this.edgeLWInGraph;
    this.hotSpots.each (function (hs) {
	    if (hs.t === EDGE && hs.inGraph) {
		this.nEdges++;
		nodesInGraph[hs.edge[0]] = true;
		nodesInGraph[hs.edge[1]] = true;
		c.beginPath();
		c.moveTo (hs.x0, hs.y0);
		c.lineTo (hs.x1, hs.y1);
		c.stroke();
	    }
	}.bind(this));

    // Draw the highlighted nodes.
    if (this.nodeA >= 0) {
	c.strokeStyle = this.edgeFGClicked;
	c.lineWidth = this.edgeLWClicked;
	var xc1 = this.nodes[this.nodeA][0];
	var yc1 = this.nodes[this.nodeA][1];
	c.beginPath();
	for (j = n - 1; j >= 0; j--) {
	    if (j == this.nodeA) continue;
	    var xc2 = this.nodes[j][0];
	    var yc2 = this.nodes[j][1];
	    c.moveTo (xc1, yc1);
	    c.lineTo (xc2, yc2);
	}
	c.stroke();
    }

    // Draw the nodes.
    hs = Array();
    for (i = n - 1; i >= 0; i--) {
	var xc = this.nodes[i][0];
	var yc = this.nodes[i][1];

	if (i === this.nodeA) {
	    c.fillStyle = this.nodeFGClicked;
	    r = this.nodeRadiusClicked;
	} else if (nodesInGraph[i]) {
	    c.fillStyle = this.nodeFGInGraph;
	    r = this.nodeRadiusInGraph;
	} else {
	    c.fillStyle = this.nodeFG;
	    r = this.nodeRadius;
	}

	// Draw the mask.
	c.save();
	c.fillStyle = this.BG;
	c.beginPath();
	c.arc (xc, yc, r + this.nodeCircleMasking, 0, TWOPI, 0);
	c.fill();
	c.restore();

	// And the node disc.
	c.beginPath();
	c.arc (xc, yc, r, 0, TWOPI, 0);
	c.fill();
    }

    // Redraw the node labels.
    this.drawNodeLabels();
};


PolyExplorer.prototype.drawNodeLabels = function()
{
    //var c = this.ctx3;
    var c = this.ctx;
    //c.clearRect (0, 0, this.w, this.h);

    // Does this browser support text?
    if (!c.fillText) {
	return;
    }

    // Node labels.
    c.textAlign = 'center';
    c.textBaseline = 'middle';
    c.fillStyle = '#000';
    c.lineWidth = 0.5;
    c.font = 'bold 12px Arial';
    for (var i = 0; i < this.nNodes; i++) {
	var w = c.measureText(NODENAMES[i]).width;
	//var data = LABELS[i];
	//var x = this.nodes[i][0] - data[0] / 2;
	//var y = this.nodes[i][1] - data[1] / 2;
	//c.drawImage (data[2], 100, 20 + 12 * i);
	var x = this.nodes[i][0] + 1;
	var y = this.nodes[i][1] + 2;
	c.fillText (NODENAMES[i], x, y);
	c.save();
	c.fillStyle = '#fff';
	c.fillText (NODENAMES[i], x - 1, y - 1);
	c.restore();
    }
};


PolyExplorer.prototype.makeAdjacencyTable = function()
{
    var t = this.adjTable;
    t.select('*').each(function(el){el.remove();});

    // Make the first row.
    var tr = new Element('tr', {'class':'heading'});
    for (var i = 1; i < this.nNodes; i++) {
	tr.appendChild (new Element ('th', {'class':'node'}).update(NODENAMES[i]));
    }
    tr.appendChild (new Element ('th', {'class':'triangular'}));
    t.appendChild (tr);

    // Make subsequent rows
    for (var i = 0; i < this.nNodes - 1; i++) {
	var oe = (i & 1) ? 'even': 'odd';
	var tr = new Element('tr', {'class':oe, 'id':'row_node' + i});
	// Heading
	// if (i === 0) {
	//     tr.appendChild (new Element ('th', {'class':'node', 'id':'node' + i}).update(NODENAMES[i]));
	// } else {
	//     tr.appendChild (new Element ('td', {'class':'triangular'}));
	// }
	// Data
	for (var j = 1; j < this.nNodes; j++) {
	    var cls = 'edge';
	    if (i == j) {

		// Heading
		//tr.appendChild (new Element ('th', {'class':'node', 'id':'node' + i}).update(NODENAMES[i]));
		//continue;

		cls = 'self';
	    } else if (j < i) {
		cls = 'triangular';
	    }
	    var tdid = 'edge_' + i + '_' + j;
	    var a = NODENAMES [i];
	    var b = NODENAMES [j];
	    var title = 'Click here to toggle the relationship between ' + a + ' and ' + b + '.';
	    var td = new Element ('td', {'class':cls, 'id':tdid,
					 'title':title}).update('&nbsp;');
	    // Observe events.
	    if (j > i) {
		td._edge = [i, j];
		Event.observe (td, 'click', this.adj_table_onClick.bindAsEventListener(this));
		Event.observe (td, 'mouseover', this.adj_table_mouseOver.bindAsEventListener(this));
		Event.observe (td, 'mouseout', this.adj_table_mouseOut.bindAsEventListener(this));
	    }
	    
	    tr.appendChild (td);
	}
	tr.appendChild (new Element ('th', {'class':'node', 'id':'node' + i}).update(NODENAMES[i]));
	t.appendChild (tr);
    }
};

PolyExplorer.prototype.hasConnectedSubgraph = function(n)
{
    /*
        Return true if this graph has a fully connected ``n``-subgraph (that is
        isolated from all other nodes) for any n <= this.nNodes (i.e. it also
        returns true if this is a fully connected graph).

        o---o         Graph(2) with a fully connected 2-subgraph.
                      deg seq = [1, 1]

        o---o   o     Graph(3) with a fully connected 2-subgraph.
                      deg seq = [1, 1, 0]

        o---o         
         \ /          Graph(3) with a fully connected 3-subgraph.
          o           deg seq = [2, 2, 2]

        o---o   o         
         \ /          Graph(5) with a fully connected 3-subgraph.
          o   o       deg seq = [2, 2, 2, 0, 0]

	Naive corollary: a graph has an fully connected n-subgraph if its
	degree sequence contains the sub-sequence [n-1, n-1, ..., n-1] (n
	times).

        Realistically, checking the degree sequence isn't sufficient
        though. For example, see these two 5-node graphs:
        
        o   o
        |\ /|  degree_sequence = [2, 2, 2, 1, 1]
        o o o
        
        o---o
         \ /   degree_sequence = [2, 2, 2, 0, 0]
        o o o

        For n=3, both contain the n_connected pattern [2, 2, 2] in their
        degree sequences, but only the second has a connected 3-subgraph. We
        need to check the topology itself, which we do using individual node
        degrees. We try all combinations of n (n-1)-degree nodes, and ensure
        any edges that involve them only involve n-1-degree nodes too.

    */

    // Sanity check.
    if (n < 2 || n > this.nNodes) {
	return false;
    }

    // Trivial case: only a fully-connected n-node graph has a fully-connected
    // n-subgraph. (duh)
    if (n == this.nNodes && this.nEdges === this.allPossibleEdges.length) {
	return this.nEdges;
    }

    // Check degree sequence (naive check).
    var n_connected = [n - 1].times(n);
    var degseq = this.getDegreeSequence();
    if (degseq.findSeq (n_connected) < 0) {
	return false;
    }

    // Find nodes with degree n-1.
    var nodes = [];
    var degs = this.getNodeDegrees();
    for (var i = degs.length - 1; i >= 0; i--) if (degs[i] == (n - 1)) nodes.push(i);

    // Now look for all n-subsets of this node set, and ensure all members
    // involve only each other.
    var combos = nodes.comb (n);
    for (var i = combos.length - 1; i >= 0; i--) {
	var nodes = combos[i].sort().uniq();
	var edges = this.findEdgesInGraphInvolving (combos[i]);
	var nodes2 = edges.flatten().sort().uniq();
	// Do these edges ONLY involve these nodes?
	if (nodes.equal (nodes2)) {
	    // This is guaranteed to be > 0 (thus not false-like).
	    return edges.length;
	}
    }

    return false;
};


PolyExplorer.prototype.hasAnyConnectedSubgraph = function(minOrder)
{
    minOrder = minOrder || 2;
    for (var i = this.nNodes - 1; i >= minOrder; i--) {
	if (this.hasConnectedSubgraph(i)) return true;
    }
    return false;
};


// Evaluate the tacit criterion. The graph must contain one and only one
// fully-connected n-subgraph (2 >= n >= nEdges), and no other edges.

PolyExplorer.prototype.tacitCriterion = function()
{
    for (var i = this.nNodes; i >= 2; i--) {
	var x = this.hasConnectedSubgraph(i);
	if (x !== false && x == this.nEdges) return true;
    }
    return false;
};


PolyExplorer.prototype.findEdge = function(edge)
{
    var a = edge[0];
    var b = edge[1];
    var found = null;
    this.hotSpots.each(function(hs){
	    if (hs.t == EDGE) {
		if ((a == hs.edge[0] && b == hs.edge[1]) ||
		    (a == hs.edge[1] && b == hs.edge[0])) {
		    found = hs;
		    throw $break;
		}
	    }
	});
    return found;
};
    
// Return a list of edges involving any of the nodes in list.
PolyExplorer.prototype.findEdgesInGraphInvolving = function(list)
{
    var found = [];
    this.hotSpots.each(function(hs){
	    if (hs.t == EDGE && hs.inGraph) {
		if (list.indexOf (hs.edge[0]) >= 0 ||
		    list.indexOf (hs.edge[1]) >= 0) {
		    found.push(hs.edge);
		}
	    }
	});
    return found;
}

PolyExplorer.prototype.adj_table_onClick = function(event)
{
    var edge = this.findEdge (event.target._edge);
    this.canvas_onClick(event);
};


PolyExplorer.prototype.adj_table_mouseOver = function(event)
{
    var edge = this.findEdge (event.target._edge);
    this.highlight (edge);
};


PolyExplorer.prototype.adj_table_mouseOut = function(event)
{
    this.highlight (null);
};

PolyExplorer.prototype.updateBool = function(el, val)
{
    el = $(el);
    if (!el) return;
    if (val) {
	el.update('Yes');
	el.addClassName('yes');
	el.removeClassName('no');
    } else {
	el.update('No');
	el.addClassName('no');
	el.removeClassName('yes');
    }
};


// End of file.