/*
 * Testing the performance of Kruskal's algorithm.
 *
 * MINIMUM SPANNING TREE PROBLEM
 *
 * Input: An undirected weighted graph G = (V, E, w), where V is a set of n
 * vertices, E a set of m edges, and w is a function giving the weight of
 * edges. We assume that the weights are positive integers less than 2^{32}.
 *
 * Output: A tree (which is also a graph) containing a set of edges that 
 * spans the vertices of G and that has the lowest possible weight over 
 * all such trees, the weight of a tree being the sum of the weights on
 * its edges.
 *
 * The graph class written by Jyrki Katajainen. 
 * Version: 1.1
 * Copyright: Jyrki Katajainen, October 1998
 *
 * Compiled and run at DIKU:
 * > g++ -Wall -fguiding-decls graph.cpp
 * > a.out
 */

#include <iostream>
#include "random_permutation.c"

typedef unsigned int vertex;

template <class W>
class edge {
public:
  edge();
  edge(vertex, vertex, W);
  vertex first() const;
  vertex second() const;
  W weight() const;
  friend ostream& operator<<(ostream&, edge<W>&);
private:
  vertex u;
  vertex v;
  W w;
};

template <class W>
edge<W>::edge() : u(0), v(0), w(W()) {
}

template <class W>
edge<W>::edge(vertex x, vertex y, W z) : u(x), v(y), w(z) {
}

template <class W>
inline vertex edge<W>::first() const {
  return u;
}

template <class W>
inline vertex edge<W>::second() const {
  return v;
}

template <class W>
inline W edge<W>::weight() const {
  return w;
}

template <class W>
ostream& operator<<(ostream& s, edge<W>& e) {
  s << "w({" << e.u << ", " << e.v << "}) = " << e.w;
  return s;
}

template <class W>
class graph {
public:
  typedef W weight_type;
  typedef unsigned int size_type;
  typedef bool* vertex_iterator;
  typedef edge<W>* edge_iterator;
  graph();
  ~graph();
  size_type number_of_vertices() const;
  size_type number_of_edges() const;
  bool empty() const;
  vertex_iterator begin_vertex();
  vertex_iterator end_vertex();
  vertex_iterator next_vertex();
  vertex_iterator choose_vertex() const;
  void add_vertex(const vertex & v);
  edge_iterator begin_edge();
  edge_iterator end_edge();
  edge_iterator next_edge();
  edge_iterator choose_edge() const;
  void add_edge(const edge<W>& e);
  graph<W>& operator=(const graph<W>& g);
  graph<W>& operator+=(const graph<W>& g);
  friend ostream& operator<<(ostream&, graph<W>&);
private:
  static const size_type min_size = 1024;
  size_type vertex_space;
  size_type edge_space;
  size_type n;
  size_type m;
  bool* V;
  edge<W>* E;
  vertex_iterator current_vertex;
  edge_iterator current_edge;
};

template <class W>
graph<W>::graph() : n(0), m(0), current_vertex(0), current_edge(0) {
  vertex_space = min_size;
  V = new bool[min_size];
  size_type i;
  for (i = 0; i < min_size; ++i) V[i] = false;
  edge_space = min_size;
  E = new edge<W>[min_size];
  
}

template <class W>
graph<W>::~graph() {
  delete[] V;
  delete[] E;
}

template <class W>
inline typename graph<W>::size_type graph<W>::number_of_vertices() const {
  return n;
}

template <class W>
inline typename graph<W>::size_type graph<W>::number_of_edges() const {
  return m;
}

template <class W>
inline bool graph<W>::empty() const {
  return n == 0 && m == 0;
}

template <class W>
inline typename graph<W>::vertex_iterator graph<W>::begin_vertex() {
  vertex_iterator q;
  for (q = V; q < V + vertex_space; ++q) 
    if (*q) break;
  return current_vertex = q;
}

template <class W>
inline typename graph<W>::vertex_iterator graph<W>::end_vertex() {
  return V + vertex_space;
}

template <class W>
inline typename graph<W>::vertex_iterator graph<W>::next_vertex() {
  if (current_vertex != V + vertex_space) {
    vertex_iterator q;
    for (q = current_vertex + 1; q < V + vertex_space; ++q) 
      if (*q) break;
    current_vertex = q;
  }
  return current_vertex;
}

template <class W>
inline graph<W>::vertex_iterator graph<W>::choose_vertex() const {
  size_type k = irand(1, n);
  size_type i;
  for ((*this).begin_vertex(), i = 1; i < k; (*this).next_vertex(), ++i) {
  }
  return current_vertex;
}  

template <class W>
inline void graph<W>::add_vertex(const vertex & v) {
  size_type used_space = vertex_space;
  if (v >= used_space) {
    while (v >= vertex_space) vertex_space += vertex_space;
    bool* Vprime = new bool[vertex_space];
    size_type i;
    for (i = 0; i < used_space; ++i) Vprime[i] = V[i];
    for (i = used_space; i < vertex_space; ++i) Vprime[i] = false;
    delete[] V;
    V = Vprime;
  }
  if (! V[v]) {
    n = n + 1; V[v] = true;
  }
}

template <class W>
inline typename graph<W>::edge_iterator graph<W>::begin_edge() {
  return current_edge = E;
}

template <class W>
inline typename graph<W>::edge_iterator graph<W>::end_edge() {
  return E + m;
}

template <class W>
inline typename graph<W>::edge_iterator graph<W>::next_edge() {
  return ++current_edge;
}

template <class W>
inline typename graph<W>::edge_iterator graph<W>::choose_edge() const {
  return E + irand(0, m - 1);
}

template <class W>
inline void graph<W>::add_edge(const edge<W>& e) {
  add_vertex(e.first());
  add_vertex(e.second());
  if (m == edge_space) {
    edge<W>* Eprime = new edge<W>[2 * edge_space];
    size_type i;
    for (i = 0; i < edge_space; ++i) Eprime[i] = E[i];
    delete[] E;
    edge_space += edge_space;
    E = Eprime;
  }
  E[m++] = e;
}

template <class W>
graph<W>& graph<W>::operator=(const graph<W>& g) {
  if (this != &g) {
    delete[] V;
    delete[] E;
    vertex_space = g.vertex_space; edge_space = g.edge_space;
    n = g.n; m = g.m;
    current_vertex = g.current_vertex; current_edge = g.current_edge;
    V = new bool[vertex_space];
    size_type i;
    for (i = 0; i < g.vertex_space; ++i) V[i] = g.V[i];
    E = new edge<W>[edge_space];
    for (i = 0; i < g.m; ++i) E[i] = g.E[i];
  }
  return *this;
}

template <class W>
graph<W>& graph<W>::operator+=(const graph<W>& g) {
  int delta = 0;
  for (size_type i = 0; i < g.vertex_space; ++i)
    if (V[i]) delta = i;
  size_type gamma;
  for (gamma = 0; gamma < vertex_space; ++gamma)
    if (V[gamma]) break;
  delta = delta - gamma + 1;

  if (this != &g) {
    for (size_type i = 0; i < g.vertex_space; ++i) 
      if (g.V[i]) add_vertex(i + delta);
    for (size_type i = 0; i < g.m; ++i)
      add_edge(edge<W>(g.E[i].first() + delta,
		       g.E[i].second() + delta,
		       g.E[i].weight()));
  }
  else {
    size_type old_vertex_space = vertex_space;
    size_type old_m = m;
    bool* Vtemp = new bool[old_vertex_space];
    for (size_type i = 0; i < old_vertex_space; ++i) 
      Vtemp[i] = V[i];
    edge<W>* Etemp = new edge<W>[edge_space];
    for (size_type i = 0; i < old_m; ++i) 
      Etemp[i] = E[i];
    for (size_type i = 0; i < old_vertex_space; ++i) 
      if (Vtemp[i]) add_vertex(i + delta);
    for (size_type i = 0; i < old_m; ++i) 
      add_edge(edge<W>(Etemp[i].first() + delta,
		       Etemp[i].second() + delta,
		       E[i].weight()));
    delete[] Vtemp;
    delete[] Etemp;
  }
  return *this;
}    

template <class W>
graph<W> operator+(const graph<W>& g, const graph<W>& h) {
  graph<W> f(g);
  return f += h;
}

/*

Need routines for generating random graphs.

graph::random_connected() {
}

graph::random_two_clusters() {
}
*/

template <class W>
ostream& operator<<(ostream& s, graph<W>& g) {
  s << "n: " << g.n << endl;
  s << "m: " << g.m << endl;
  s << "V: {";
  graph<W>::vertex_iterator p = g.begin_vertex();
  if (p != g.end_vertex()) { 
    s << (p - g.V);
    p = g.next_vertex();
  }
  while (p != g.end_vertex()) {
    s << ", ";
    s << (p - g.V);
    p = g.next_vertex();
  }
  s << "}" << endl;

  s << "w: {";
  graph<W>::edge_iterator q = g.begin_edge();
  if (q != g.end_edge()) {
    s << *q;
    q = g.next_edge();
  }
  while (q != g.end_edge()) {
    s << ", ";
    s << *q;
    q = g.next_edge();
  }
  s << "}" << endl;
  return s;
}

/* 
 * Examples of the usage.
 */

int main() {
  edge<unsigned int> e[7];
  e[0] = edge<unsigned int>(1, 2, 3);
  e[1] = edge<unsigned int>(1, 3, 4);
  e[2] = edge<unsigned int>(1, 4, 5);
  e[3] = edge<unsigned int>(2, 3, 5);
  e[4] = edge<unsigned int>(2, 4, 6);
  e[5] = edge<unsigned int>(2, 5, 7);
  e[6] = edge<unsigned int>(3, 4, 7);

  graph<unsigned int> g;
  unsigned int i;
  for (i = 0; i < 7; ++i) {
    g.add_edge(e[i]);
  }
  std::cout << "Graph g:" << endl;
  std::cout << g << endl;

  graph<unsigned int> h;
  h.add_edge(edge<unsigned int>(1, 2, 0));
  std::cout << "Graph h:" << endl;
  std::cout << h << endl;

  h += h;
  std::cout << "Graph h += h:" << endl;
  std::cout << h << endl;

  graph<unsigned int> f = g + h;
  std::cout << "Graph g + h:" << endl;
  std::cout << f << endl;

  return 0;
}