// 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 <iostream.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/DBinGraph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
    
//
//  This class of tournaments (requested by Dr. Brenda Latka)
//  is specified as follows:  given n, define a graph on 2n+1 vertices
//  0..2n such that i->j iff  (j-i)mod(2n+1) in {0,...,n-1,n+1}
//   
DBinGraph*
GenLatkaTournament(int n, int k)
{
    DBinGraph* 	graph = new DBinGraph(); // Directed binary graph

    int ok_bounds = 0;

    // Create vertices in the graph
    graph->addVertices(2*n+1);
    Vertex** vertices = graph->vertexStart();
    int num_vertices = graph->order();

    //  Generate edges of graph
    int modulus;
    for (int i=0; i < num_vertices; i++) {
        for (int j=i+1; j < num_vertices; j++) {
		    Sequence<Vertex*> s;
		    modulus = (j-i) % (2*n+1);
		    if (modulus < 0) modulus += (2*n+1);
		    s.insert(vertices[i]);
		    if ((modulus <= (n-k)) || 
                        (modulus >= (n-k+2) && (modulus<=n)) ||
		        (modulus == n+k)) {
		    	s.append(vertices[j]);
		    } else {
		    	s.insert(vertices[j]);
		    }
                    Edge* edge = graph->addEdge(s);
	}
    }
    return graph;
}