// 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 <stdlib.h>
#include <LINK/basic/Set.h>
#include <LINK/basic/Array.h>
#include <LINK/graph/Attribute.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/algorithm/Algorithms.h>

static int directedTriangle(Vertex* v1, Vertex* v2, Vertex* v3)
{
	Set<Vertex*> ov1 = v1->outNeighbors();
	Set<Vertex*> ov2 = v2->outNeighbors();
	Set<Vertex*> ov3 = v3->outNeighbors();

	if ((ov1.memberQ(v2) && ov2.memberQ(v3) && ov3.memberQ(v1)) ||
	    (ov2.memberQ(v1) && ov1.memberQ(v3) && ov3.memberQ(v2)))
		return TRUE;
	return FALSE;
}

// findEdge - not general (doesn't work on hypergraphs, multigraphs,
//			   which is why it's defined here & not in graph lib.)
//	      direction doesn't matter - return e where v1 and v2 are in e.
static Edge *findEdge(Vertex *v1, Vertex *v2)
{
	MSet<Edge*> v1_edges = v1->incidentEdges();
	Iterator<Edge*> get_edge(&v1_edges);
	Edge *e;
	while (get_edge(e)) 
		if (e->vertices()->memberQ(v2))
			return e;
	return 0;
}

static void processTriple(Vertex *v1, Vertex *v2, Vertex *v3)
{
	double w;
	if (directedTriangle(v1, v2, v3)) {
		Edge *e1 = findEdge(v1,v2);
		Edge *e2 = findEdge(v2,v3);
		Edge *e3 = findEdge(v3,v1);
		getAttribute((GraphObject*)e1, "weight", w);
		setAttribute((GraphObject*)e1, "weight", w+1);
		getAttribute((GraphObject*)e2, "weight", w);
		setAttribute((GraphObject*)e2, "weight", w+1);
		getAttribute((GraphObject*)e3, "weight", w);
		setAttribute((GraphObject*)e3, "weight", w+1);
	}
}
				
void Triangles(Graph *g, char *graph_view)
{
	ResetAttributes(g);
	SortedArray<Vertex*> v = g->vertices();

	int i,j,k, order = g->order();

	const MSet<Edge*>& es = g->edges();
	Iterator<Edge*> get_edge(&es);
	Edge *e;
	while (get_edge(e))
		setAttribute((GraphObject*)e, "weight", 0.0);

	for (i=0; i<order; i++)
		for (j=i; j<order; j++)
			for (k=j; k<order; k++)
				processTriple(v[i], v[j], v[k]);
}