/* -*- C++ -*-

 * src/hugo/full_graph.h - Part of HUGOlib, a generic C++ optimization library

 *

 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Combinatorial Optimization Research Group, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef HUGO_FULL_GRAPH_H

#define HUGO_FULL_GRAPH_H

///\ingroup graphs

///\file

///\brief FullGraph and SymFullGraph classes.

#include <vector>

#include <climits>

#include <hugo/invalid.h>

#include <hugo/map_registry.h>

#include <hugo/array_map.h>

#include <hugo/map_defines.h>

namespace hugo {

/// \addtogroup graphs

/// @{

  ///A full graph class.

  ///This is a simple and fast directed full graph implementation.

  ///It is completely static, so you can neither add nor delete either

  ///edges or nodes.

  ///Thus it conforms to

  ///the \ref skeleton::StaticGraph "StaticGraph" concept

  ///\sa skeleton::StaticGraph.

  ///\todo What about loops?

  ///\todo Don't we need SymEdgeMap?

  ///

  ///\author Alpar Juttner

  class FullGraph {

    int NodeNum;

    int EdgeNum;

  public:

    typedef FullGraph Graph;

    class Node;

    class Edge;

    class NodeIt;

    class EdgeIt;

    class OutEdgeIt;

    class InEdgeIt;

    // Create map registries.

    CREATE_MAP_REGISTRIES;

    // Create node and edge maps.

    CREATE_MAPS(ArrayMap);

  public:

    ///Creates a full graph with \c n nodes.

    FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }

    ///

    FullGraph(const FullGraph &_g)

      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }

    ///Number of nodes.

    int nodeNum() const { return NodeNum; }

    ///Number of edges.

    int edgeNum() const { return EdgeNum; }

    /// Maximum node ID.

    /// Maximum node ID.

    ///\sa id(Node)

    int maxNodeId() const { return NodeNum-1; }

    /// Maximum edge ID.

    /// Maximum edge ID.

    ///\sa id(Edge)

    int maxEdgeId() const { return EdgeNum-1; }

    Node tail(Edge e) const { return e.n%NodeNum; }

    Node head(Edge e) const { return e.n/NodeNum; }

    NodeIt& first(NodeIt& v) const {

      v=NodeIt(*this); return v; }

    EdgeIt& first(EdgeIt& e) const { 

      e=EdgeIt(*this); return e; }

    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 

      e=OutEdgeIt(*this,v); return e; }

    InEdgeIt& first(InEdgeIt& e, const Node v) const { 

      e=InEdgeIt(*this,v); return e; }

    /// Node ID.

    /// The ID of a valid Node is a nonnegative integer not greater than

    /// \ref maxNodeId(). The range of the ID's is not surely continuous

    /// and the greatest node ID can be actually less then \ref maxNodeId().

    ///

    /// The ID of the \ref INVALID node is -1.

    ///\return The ID of the node \c v. 

    static int id(Node v) { return v.n; }

    /// Edge ID.

    /// The ID of a valid Edge is a nonnegative integer not greater than

    /// \ref maxEdgeId(). The range of the ID's is not surely continuous

    /// and the greatest edge ID can be actually less then \ref maxEdgeId().

    ///

    /// The ID of the \ref INVALID edge is -1.

    ///\return The ID of the edge \c e. 

    static int id(Edge e) { return e.n; }

    /// Finds an edge between two nodes.

    /// Finds an edge from node \c u to node \c v.

    ///

    /// If \c prev is \ref INVALID (this is the default value), then

    /// It finds the first edge from \c u to \c v. Otherwise it looks for

    /// the next edge from \c u to \c v after \c prev.

    /// \return The found edge or INVALID if there is no such an edge.

    Edge findEdge(Node u,Node v, Edge prev = INVALID) 

    {

      return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;

    }

    class Node {

      friend class FullGraph;

      template <typename T> friend class NodeMap;

      friend class Edge;

      friend class OutEdgeIt;

      friend class InEdgeIt;

      friend class SymEdge;

    protected:

      int n;

      friend int FullGraph::id(Node v); 

      Node(int nn) {n=nn;}

    public:

      Node() {}

      Node (Invalid) { n=-1; }

      bool operator==(const Node i) const {return n==i.n;}

      bool operator!=(const Node i) const {return n!=i.n;}

      bool operator<(const Node i) const {return n<i.n;}

    };

    class NodeIt : public Node {

      const FullGraph *G;

      friend class FullGraph;

    public:

      NodeIt() : Node() { }

      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }

      NodeIt(Invalid i) : Node(i) { }

      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }

      ///\todo Undocumented conversion Node -\> NodeIt.

      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }

    };

    class Edge {

      friend class FullGraph;

      template <typename T> friend class EdgeMap;

      friend class Node;

      friend class NodeIt;

    protected:

      int n; //NodeNum*head+tail;

      friend int FullGraph::id(Edge e);

      Edge(int nn) : n(nn) {}

      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}

    public:

      Edge() { }

      Edge (Invalid) { n=-1; }

      bool operator==(const Edge i) const {return n==i.n;}

      bool operator!=(const Edge i) const {return n!=i.n;}

      bool operator<(const Edge i) const {return n<i.n;}

      ///\bug This is a workaround until somebody tells me how to

      ///make class \c SymFullGraph::SymEdgeMap friend of Edge

      int &idref() {return n;}

      const int &idref() const {return n;}

    };

    class EdgeIt : public Edge {

      friend class FullGraph;

    public:

      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }

      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }

      EdgeIt (Invalid i) : Edge(i) { }

      EdgeIt() : Edge() { }

      EdgeIt& operator++() { --n; return *this; }

      ///\bug This is a workaround until somebody tells me how to

      ///make class \c SymFullGraph::SymEdgeMap friend of Edge

      int &idref() {return n;}

    };

    class OutEdgeIt : public Edge {

      const FullGraph *G;

      friend class FullGraph;

    public: 

      OutEdgeIt() : Edge() { }

      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }

      OutEdgeIt (Invalid i) : Edge(i) { }

      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}

      OutEdgeIt& operator++()

      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }

    };

    class InEdgeIt : public Edge {

      const FullGraph *G;

      friend class FullGraph;

    public: 

      InEdgeIt() : Edge() { }

      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }

      InEdgeIt (Invalid i) : Edge(i) { }

      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}

      InEdgeIt& operator++()

      { if(!((++n)%G->NodeNum)) n=-1; return *this; }

    };

  };

  /// @}  

} //namespace hugo

#endif //HUGO_FULL_GRAPH_H