// Jens Kristian Jensen, dat2A 2002/2003
// G2, 14.--30. april 2003

#include <LEDA/list.h>
#include <LEDA/graph.h>
#include <LEDA/edge_array.h>

extern edge_array<double> W;

class _1Tree {
  graph& G;
public:
  list<edge> E;      // Edges of the tree
  node_array<int> D; // Degree of each node
  double length;     // Length of the 1-tree
  
  _1Tree (graph& G2): G(G2) {
    D.init(G, 0);
    length = 0;
  }

  _1Tree (_1Tree& T): G(T.G) {
    D.init(G);
    E = T.E;

    node n;
    forall_nodes (n, G)
      D[n] = T.D[n];

    length = T.length;
  }

  bool operator< (const _1Tree& T) {
    return (length < T.length);
  }  

  bool operator<= (const _1Tree& T) {
    return (length <= T.length);
  }  

  bool operator> (const _1Tree& T) {
    return (length > T.length);
  }  

  bool operator>= (const _1Tree& T) {
    return (length > T.length);
  }  

  _1Tree& operator= (const _1Tree& T) {
    E = T.E;
    
    node n;
    forall_nodes (n, G)
      D[n] = T.D[n];
    
    length = T.length;
  }

  bool isHamCycle () {
    // All nodes must have degree 2 (assuming that the entire graph is
    // spanned, ie. the 1-tree is connected)
    node n;
    forall_nodes (n, G) {
      if (D[n] != 2)
	return false;
    }
    
    return true;
  }

  void print() {
    cout << endl << (isHamCycle() ? "HamCycle:" : "1-Tree:") << endl;
    edge e;
    forall (e, E) {
      G.print_edge(e);
      cout << " " << W[e] << endl;
    }
    cout << "-----------------" << endl;
    cout << "           " << length << endl;

    node n;
    cout << "D";
    forall_nodes (n, G) {
      cout << "[" << D[n] << "]";
    }
    cout << endl << endl;
  }
};