/*
 * graph.c
 *
 * The author of this software is Alain K\"{a}gi.
 *
 * Copyright (c) 1993 by Alain K\"{a}gi and the University of Wisconsin
 * Board of Trustees.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR NOR THE UNIVERSITY OF
 * WISCONSIN MAKE ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING
 * THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
 * PURPOSE.
 *
 * ------------------------------------------------------------------------
 *
 * The graph etc.
 *
 * ------------------------------------------------------------------------
 *
 * $Id$
 *
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

#define TRUE 1
#define FALSE 0

#ifdef __MINGW32__
#define random() rand()
#endif

#define GET_WEIGHT	(random() + 1) % MAX_WEIGHT

/*
 * Local variables.
 */
static int generatedEdges;

/*
 * Local functions.
 */
Vertices * GenTree(int vertex);
Vertices * AddEdges(Vertices * graph, int nVertex, int nEdge);
Vertices * PickVertex(Vertices * graph, int whichVertex);
void      Connect(Vertices * vertex1, Vertices * vertex2);
int       Duplicate(Vertices * vertex1, Vertices * vertex2);
Vertices * NewVertex();
Edges * NewEdge();
void      PrintNeighbors(Vertices * vertex);

/*
 * Local variables.
 */
static id = 1;

/*
 * Generates random connected undirected graphs.  Unfortunately this current
 * implementation does not generate the graphs with a uniform distribution.
 *
 * Apparently a good reference is Tinhofer G., ,
 * C. Hanser, Verlag, M\"{u}nchen 1980.
 */
Vertices *
GenGraph(int nVertex, int nEdge)
{
  Vertices * graph;

  assert(nEdge + 1 >= nVertex);
  assert(nEdge <= nVertex * (nVertex - 1) / 2);

  generatedEdges = 0;

  graph = GenTree(nVertex);
  graph = AddEdges(graph, nVertex, nEdge - nVertex + 1);
  return(graph);
}

Vertices *
GenTree(int nVertex)
{
  int       i;
  int       weight;
  Vertices * vertex;
  Vertices * graph;
  Edges * edge;

  graph = NewVertex();
  NEXT_VERTEX(graph) = graph;

  for(i = 1; i < nVertex; i++)
  {
    vertex = NewVertex();
    edge = NewEdge();

    /*
     * The newly created vertex has one edge ...
     */
    EDGES(vertex) = edge;

    /*
     * ... which is connected to the graph so far generated.  The connection
     * point in the graph is picked at random.
     */
    VERTEX(edge) = PickVertex(graph, random() % i);
    weight = GET_WEIGHT;
    WEIGHT(edge) = weight;
    SOURCE(edge) = vertex;

    /*
     * Link the new vertex into the graph.
     */
    NEXT_VERTEX(vertex) = NEXT_VERTEX(graph);
    NEXT_VERTEX(graph) = vertex;

    /*
     * Add an edge to the vertex randomly picked as the connection point.
     */
    edge = NewEdge();
    WEIGHT(edge) = weight;
    SOURCE(edge) = VERTEX(EDGES(vertex));
    VERTEX(edge) = vertex;
    NEXT_EDGE(edge) = EDGES(VERTEX(EDGES(vertex)));
    EDGES(VERTEX(EDGES(vertex))) = edge;
   }

  return(graph);
}

Vertices *
AddEdges(Vertices * graph, int nVertex, int nEdge)
{
  int       i;
  Vertices * vertex1;
  Vertices * vertex2;

  assert(graph != NULL_VERTEX);
  assert(nEdge >= 0);

  for(i = 0; i < nEdge; i++)
  {
    do
    {
      vertex1 = PickVertex(graph, random() % nVertex);
      vertex2 = PickVertex(NEXT_VERTEX(vertex1), (random() % nVertex) - 1);
      assert(vertex1 != vertex2);
    }
    while(Duplicate(vertex1, vertex2));

    Connect(vertex1, vertex2);
  }
  
  return(graph);
}

Vertices *
PickVertex(Vertices * graph, int whichVertex)
{
  int       i;

  for(i = 0; i < whichVertex; i++)
  {
    graph = NEXT_VERTEX(graph);
  }

  return(graph);
}

void
Connect(Vertices * vertex1, Vertices * vertex2)
{
  int    weight;
  Edges * edge;

  weight = GET_WEIGHT;

  edge = NewEdge();
  WEIGHT(edge) = weight;
  SOURCE(edge) = vertex1;
  VERTEX(edge) = vertex2;
  NEXT_EDGE(edge) = EDGES(vertex1);
  EDGES(vertex1) = edge;
  
  edge = NewEdge();
  WEIGHT(edge) = weight;
  SOURCE(edge) = vertex2;
  VERTEX(edge) = vertex1;
  NEXT_EDGE(edge) = EDGES(vertex2);
  EDGES(vertex2) = edge;
}

int
Duplicate(Vertices * vertex1, Vertices * vertex2)
{
  Edges * edge;

  edge = EDGES(vertex1);

  while(edge != NULL_EDGE)
  {
    if(VERTEX(edge) == vertex2)
    {
      return(TRUE);
    }

    edge = NEXT_EDGE(edge);
  }

  return(FALSE);
}

Vertices *
NewVertex()
{
  Vertices * vertex;

  vertex = (Vertices *)malloc(sizeof(Vertices));

  if(vertex == NULL)
  {
    fprintf(stderr, "Could not malloc\n");
    exit(1);
  }

  ID(vertex) = id++;
  EDGES(vertex) = NULL;
  NEXT_VERTEX(vertex) = NULL;

  return(vertex);
}

Edges *
NewEdge()
{
  Edges * edge;

  edge = (Edges *)malloc(sizeof(Edges));

  if(edge == NULL)
  {
    fprintf(stderr, "Could not malloc\n");
    exit(1);
  }

  WEIGHT(edge) = 0;
  VERTEX(edge) = NULL;
  NEXT_EDGE(edge) = NULL;
  
  return(edge);
}

void
PrintGraph(Vertices * graph)
{
  Vertices * vertex;

  assert(graph != NULL);

  vertex = graph;
  do
  {
    printf("Vertex %d is connected to:", ID(vertex));
    PrintNeighbors(vertex);
    printf("\n");
    vertex = NEXT_VERTEX(vertex);
  }
  while(vertex != graph);
}

void
PrintNeighbors(Vertices * vertex)
{
  Edges * edge;

  edge = EDGES(vertex);
  while(edge != NULL)
  {
    printf(" %d(%d)[%d]", ID(VERTEX(edge)), WEIGHT(edge), ID(SOURCE(edge)));
    edge = NEXT_EDGE(edge);
  }
}