Graph.h

Aller à la documentation de ce fichier.

/***************************************************************************
                          Graph.h  -  description
                             -------------------
    begin                : sam jui 26 2003
    copyright            : (C) 2003 by Michel DUBOIS, Yann Le Guyadec 
    email                : Michel.Dubois@univ-ubs.fr, Yann.Le-Guyadec@univ-ubs.fr 
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef GRAPH_H
#define GRAPH_H

#include "nommgr.h"
#include <vector>
#include "mmgr.h"

class Graph;
class Edge;
class Connection;
class Vertex;

class Graph {
  friend class Edge;
  friend class Connection;
  private:
  public:
      Graph();
      virtual ~Graph();

  public:
    unsigned int    getVertexCount() const;
    Vertex *        getVertex(unsigned int index) const;
    int             getVertexIndex (Vertex * aVertex) const;
    unsigned int    getConnectionCount() const;
    unsigned int    getConnectionCount(unsigned int index1,unsigned int index2) const;
    Connection *    getConnection(unsigned int index1,unsigned int index2) const;
    Connection *    getConnection(unsigned int index1,unsigned int index2,unsigned int index3) const;
    Connection *    getConnection(unsigned int index) const;
    int             getConnectionIndex (Connection * aConnection) const;
    unsigned int    getEdgeCount() const;
    Edge *          getEdge(unsigned int index1,unsigned int index2) const;
    Edge *          getEdge(unsigned int index) const;
    int             getEdgeIndex (Edge * anEdge) const;

    void virtual    printVertices() const;
    void virtual    printEdges() const;
    void virtual    printConnections() const;
    void virtual    printAdjacencyMatrix() const;
    void virtual    printConnectedComponentID() const;
    void virtual    print();

    void            addVertex    (Vertex * aVertex);
        void            removeVertex (Vertex * aVertex);
        void            insertConnection   (Connection*   Connection);
        void            removeConnection   (Connection*   Connection);

    void            computeConnectedComponent();
    void            computeConnectedComponent(unsigned int vertexIndex);
    void            setBaseConnectedComponent(unsigned int vertexIndex);
    unsigned int    getConnectedComponentCount() const;
    bool            isConnected(unsigned int vertexIndex, unsigned int anotherVertexIndex) const;
    unsigned int    getConnectedComponentCard(unsigned int connectedComponentIndex) const;
//    void            adjItInit(unsigned int vertexIndex) ;
//    int             adjItBeg() ;
//    int             adjItNext() ;
//    bool            adjItEnd() const;
    bool            hasMultipleConnections() const;
    virtual void    destroyGraph(Graph * aGraph)=0;
    virtual Graph * createGraph ()=0;
    class adjIterator;
    class ConnectedComponent;
    
  protected:    
        std::vector<Vertex *> vertices;
        unsigned int vertexCount;
        std::vector<std::vector <Connection *> > adj;
        unsigned int connectionCount;
    unsigned int edgeCount;
    std::vector<int> connectedComponentID;
    int connectedComponentCount;
//    int adjItPos;
//    int adjItVertex;
    friend class Graph::adjIterator;

};

class Graph::adjIterator
{
  private :
    const Graph * G;
    int i,v;
  public :
  adjIterator(const Graph * G, int v);
  int beg ();
  int nxt ();    
  bool end ();

};

/*
class Graph::ConnectedComponent
{
  private :
    const Graph * G;
    int ccnt;
    std::vector <int> id;
    void ccR(int w)
    {
      id[w]=ccnt;
      Graph::adjIterator it=Graph::adjIterator(G,w);
      
      for (int v=it.beg();!it.end();v=it.nxt())
      {
        printf("ccR(%i)->CCID[%i]=%i : info CCID[%i]=%i\n",w,w,id[w],v,id[v]);
        if (id[v]==-1)
          ccR(v);
      }  
    }
  public :
  ConnectedComponent(const Graph * G) : G(G), ccnt(0), id(G->getVertexCount(),-1)
  {
    for (int v=0; v<G->getVertexCount();v++)
      if (id[v]==-1)
      {
        ccR(v);
        ccnt++;
      }  
  }
  int count() const
  {
      return ccnt;
  }
  bool connect(int s,int t) const
  {
    return id[s]==id[t];
  }
  
};
*/

class Connection {
  class Edge;
  friend class Edge;
  friend class Graph;
  protected :
    Graph * graph;
    Vertex * vertex1;
    Vertex * vertex2;
  public :
    Connection(Vertex * aVertex, Vertex * anotherVertex);
    virtual ~Connection();
    virtual unsigned int getConnectionCount() const;
    virtual int getConnectionIndex (Connection * aConnection) const;
    virtual void print() const;
    virtual Connection * getConnection(unsigned int index);
    virtual void swap()=0;
    Graph * getGraph() const;
    Vertex * getVertex1() const;
    Vertex * getVertex2() const;    
  protected:
    void setGraph(Graph * aGraph);
};

class Edge : public Connection {
  friend class Graph;
  friend class Connection;
  public:
    Edge(Vertex * aVertex, Vertex * anotherVertex);
    ~Edge();
    Vertex * vertex1;
    Vertex * vertex2;
    Graph * graph;
    std::vector<Connection*> connections;
    Connection * getConnection(unsigned int index);
    int getConnectionIndex (Connection * aConnection) const;
    unsigned int getConnectionCount() const;
    void addConnection(Connection * aConnection);
    void removeConnection(Connection * Connection);
    void print() const;
    void swap();
};


class Vertex {
  friend class Graph;
  friend class Connection;
    protected :
     Graph * graph;
    public :
      Vertex();
      Graph * getGraph() const;
      void setGraph(Graph * aGraph);
      virtual ~Vertex();
      virtual void print()=0;
};


/*
 * Classes de test
 */
class TestC;
class TestV;
class TestG;

class TestV : public Vertex
{
  public :
    int ID;
    std::vector<TestC *> testCs;
    
  TestV();
  ~TestV();
  
  void print()  ;
  void connect(TestV * aTestV);
  void disconnect();
};

class TestC : public Connection
{
  public :
    int ID;
    TestC(TestV * t1, TestV * t2);
    void print() const ;
    void swap();    
};

class TestG : public Graph
{
  public :
    int ID;
    TestG();
    ~TestG();
    virtual void destroyGraph(Graph * aGraph);
    virtual Graph * createGraph () ;
    void print() ;      
};

#endif

---