// ---------------------------------------------------------------------------
// - Graph.hpp                                                               -
// - standard object library - graph base class definition                   -
// ---------------------------------------------------------------------------
// - This program is free software;  you can redistribute it  and/or  modify -
// - it provided that this copyright notice is kept intact.                  -
// -                                                                         -
// - This program  is  distributed in  the hope  that it will be useful, but -
// - without  any  warranty;  without  even   the   implied    warranty   of -
// - merchantability or fitness for a particular purpose.  In no event shall -
// - the copyright holder be liable for any  direct, indirect, incidental or -
// - special damages arising in any way out of the use of this software.     -
// ---------------------------------------------------------------------------
// - copyright (c) 1999-2001 amaury darsch                                   -
// ---------------------------------------------------------------------------

#ifndef  ALEPH_GRAPH_HPP
#define  ALEPH_GRAPH_HPP

#ifndef  ALEPH_VECTOR_HPP
#include "Vector.hpp"
#endif

namespace aleph {
  /// The Edge class is the class used tp represent an edge between two
  /// nodes in a graph. An edge store a source and target nodes. Various 
  /// constructors are provided to manipulate the edge and nodes.
  /// @author amaury darsch

  class Edge : public virtual Object {
  private:
    /// the source node
    class Node* p_src;
    /// the target node;
    class Node* p_trg;
    /// the edge client object
    Object* p_clo;

  public:
    /// create an empty edge
    Edge (void);

    /// create an edge with a client object
    /// @param clo the client object
    Edge (Object* clo);

    /// create an edge with two nodes
    /// @param src the source node
    /// @param trg the traget node
    Edge (class Node* src, class Node* trg);

    /// destroy this edge
    ~Edge (void);

    /// @return the class name
    String repr (void) const;

    // make this edge a shared object
    void mksho (void);

    /// set the source node for this edge
    /// @param node the source node to attach
    void setsrc (class Node* node);

    /// set the target node for this edge
    /// @param node the target node to attach
    void settrg (class Node* node);

    /// set the edge client object
    /// @param clo the client object
    void setclo (Object* clo);

    /// @return the source node for this edge
    class Node* getsrc (void) const;

    /// @return the target node for this edge
    class Node* gettrg (void) const;

    /// @return the edge client object
    Object* getclo (void) const;

    /// reset this edge
    virtual void reset (void);

    /// create a new edge in a generic way
    /// @param argv the argument vector
    static Object* mknew (Vector* argv);

    /// apply this edge with a set of arguments and a quark
    /// @param robj   robj the current runnable
    /// @param nset   the current nameset    
    /// @param quark  the quark to apply these arguments
    /// @param argv   the arguments to apply
    Object* apply (Runnable* robj, Nameset* nset, const long quark,
		   Vector* argv);

  private:
    // make the copy constructor private
    Edge (const Edge&);
    // make the assignment operator private
    Edge& operator = (const Edge&);
  };

  /// The Node class is the class used tp represent an node in the standard
  /// graph. The node holds two arrays for the incoming and outgoing edges.
  /// @author amaury darsch

  class Node : public virtual Object {
  private:
    /// the incoming edges
    Vector* p_in;
    /// the outgoing edges
    Vector* p_out;
    /// the node client object
    Object* p_clo;

  public:
    /// create an empty node
    Node (void);

    /// create a node with a client object
    /// @param clo the client object
    Node (Object* clo);

    /// destroy this node
    ~Node (void);

    /// @return the class name
    String repr (void) const;

    // make this node a shared object
    void mksho (void);

    /// add an incoming edge to this node
    /// @param edge the edge to add
    void addin (Edge* edge);

    /// add an outgoing edge to this node
    /// @param edge the edge to add
    void addout (Edge* edge);    

    /// @return the number of incoming edges (i.e its in-degree)
    long indegree (void) const;

    /// @return the number of outgoing edges (i.e its out degree)
    long outdegree (void) const;

    /// @return the degree of this node
    long degree (void) const;

    /// @return an incoming edge by index
    Edge* getin (const long index) const;

    /// @return an outgoing edge by index
    Edge* getout (const long index) const;

    /// set the node client object
    /// @param clo the client object
    void setclo (Object* clo);

    /// @return the node client object
    Object* getclo (void) const;

    /// reset this node
    virtual void reset (void);

    /// create a new node in a generic way
    /// @param argv the argument vector
    static Object* mknew (Vector* argv);

    /// apply this node with a set of arguments and a quark
    /// @param robj   robj the current runnable
    /// @param nset   the current nameset    
    /// @param quark  the quark to apply these arguments
    /// @param argv   the arguments to apply
    Object* apply (Runnable* robj, Nameset* nset, const long quark,
		   Vector* argv);

  private:
    // make the copy constructor private
    Node (const Node&);
    // make the assignment operator private
    Node& operator = (const Node&);
  };

  /// the Graph class is the base class used to hold a graph. A graph is
  /// a set of edges and nodes (or vertices). The default constructor creates
  /// an empty graph. Another constructor uses a node and traverse the all
  /// egdes to build the graph. This assumes that all nodes have their visited
  /// flag set to false. The graph can also store a root node. A numbering
  /// method is provided to number the nodes. The number is called the node
  /// id or nid. The destruction of the graph is simply made by destrying all
  /// nodes and edges. Good luck anyway ...
  /// @author amaury darsch

  class Graph : public virtual Object {
  private:
    /// the set of nodes
    Vector* p_nodes;
    /// the set of edges
    Vector* p_edges;

  public:
    /// create an empty graph
    Graph (void);

    /// destroy this graph
    ~Graph (void);

    /// @return the class name
    String repr (void) const;

    // make this vector a shared object
    void mksho (void);

    /// @return true if a node exists in this graph
    bool exists (Node* node) const;

    /// @return true is an edge exists in this graph
    bool exists (Edge* edge) const;

    /// add a node to this graph. The node must node exists in this graph
    /// or nothing is done. The node must have a 0 degree.
    /// @param node the node to add
    void add (Node* node);

    /// add an edge to this graph.
    /// @param edge the edge to add
    void add (Edge* edge);

    /// @return the number of nodes
    long getnnodes (void) const;

    /// @return the number of edges
    long getnedges (void) const;

    /// @return a node by index
    Node* getnode (const long index) const;

    /// @return an edge by index
    Edge* getedge (const long index) const;

    /// reset all nodes
    virtual void resetnodes (void);

    /// reset all edges
    virtual void resetedges (void);

    /// reset the nodes and edges
    virtual void reset (void);

    /// create a new node in a generic way
    /// @param argv the argument vector
    static Object* mknew (Vector* argv);

    /// apply this graph with a set of arguments and a quark
    /// @param robj   robj the current runnable
    /// @param nset   the current nameset    
    /// @param quark  the quark to apply these arguments
    /// @param argv   the arguments to apply
    Object* apply (Runnable* robj, Nameset* nset, const long quark,
		   Vector* argv);
  private:
    // make the copy constructor private
    Graph (const Graph&);
    // make the assignment operator private
    Graph& operator = (const Graph&);
  };
}

#endif
