// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#include<LINK/basic/Set.h>
#include<LINK/algorithm/Algorithms.h>
#include<LINK/graph/Attribute.h>
#include<LINK/graph/Graph.h>
#include<LINK/graph/Vertex.h>

Set<Vertex*> MaximalClique(Graph* graph, char *graph_view)
{
    Set<Vertex*> result;

    ResetAttributes(graph);
    const SortedArray<Vertex*>& vertices = graph->vertices();
    int maxd = 0, i, order = graph->order();
    Vertex *maxv;
	
    for (i=0;i<order;i++) {
	if (graph->degree(vertices[i]) > maxd) {
		maxv = vertices[i];
		maxd = graph->degree(vertices[i]);
	}
    }
    result.insert(maxv);
    animateVertex(maxv, graph_view, "vcolor", "color", 0, YELLOW);

    MSet<Vertex*> neighbors = maxv->neighbors();
    Iterator<Vertex*> next_neigh(&neighbors);
    Vertex* neigh;
    while (next_neigh(neigh)) {
    	Iterator<Vertex*> next_neigh2(&neighbors);
    	Vertex* neigh2;
	while (next_neigh2(neigh2) && (neigh != neigh2));
	while (next_neigh2(neigh2)) {
		if (!graph->adjacentQ(neigh, neigh2)) 
			setAttribute((GraphObject*)neigh2, "mark", 1);
	}
    }
    next_neigh.reset();
    while (next_neigh(neigh)) {
	int mark;
	getAttribute((GraphObject*)neigh, "mark", mark);
	if (!mark) {
		result.insert(neigh);
    		animateVertex(neigh, graph_view, "vcolor", "color", 0, YELLOW);
	}
    }
    return(result);
}