/Users/mourrain/Devel/mmx/shape/include/shape/graph.hpp

Go to the documentation of this file.

/********************************************
  Graph Representation using adjacency list.

  Assumptions:
  ! No loops (= edge starting and ending on same vertex)
  ! No edge exists if the vertices do not exist

  Angelos Mantzaflaris, GALAAD, INRIA
*********************************************/

#pragma once

# include <stack>
# include <realroot/Seq.hpp>

# define NODESTACK std::stack<gNode<T> *>
# define Viewer viewer<axel, K>


namespace mmx {
namespace shape {

template<class T> class Graph;
template<class T> class GraphDfsIter;


// gNode
template<class T>
class gNode
{

  friend class Graph<T>;
  friend class GraphDfsIter<T>;
  
private:
  T data;
  gNode<T>* vlist; // the next node of the node list
  gNode<T>* next;  // the next neighbor of this node
  gNode<T>* me;    // pointer to next appeareance of node
  gNode<T>* start; // pointer to vlist appeareance of node
  
  int m_status;
  int m_aux;
  
public:
  gNode(){ };
  
  gNode(T val)
    {
      this->data =val; //node data
      this->vlist=NULL;//next node in list
      this->next =NULL;//next neighbor of node
      this->me   =this;//next occurance of this node
      this->start=this;//pointer to this node on the node list
      this->m_status =2009;
      this->m_aux    =0;
    }   
  
  inline T get_data() {return this->data;};
  //void operator<<(T& v) {this->push_vertex(v);};
  
  inline bool adj(T& v) {
    
    gNode<T>* t;
    t= this->next;
    
    while(t!=NULL)
    {
      if(t->vlist->data==v)
        return true;
      t=t->next;
    }
    return false;
  };
  
  inline void status(int i)
    {
      this->start->m_status=i;
    };
  
  inline int status()
    {
      return this->start->m_status;
    };
  
  inline void aux(int i)
    {
      this->start->m_aux=i;
    };
  
  inline int aux()
    {
      return this->start->m_aux;
    };
  
};
  
  
  
// Graph
template<class T>
class Graph
{
  friend class GraphDfsIter<T>;
  typedef void (*func)(gNode<T> *);
  typedef bool (*test_node)(gNode<T> *);
  
private:
  gNode<T>* head; //a pointer to the head node
  unsigned nvertices, nedges;
  //bool directed;
  
public:
  
  // Initialize empty graph
  Graph()
    {
      nvertices=nedges=0;
      head=NULL;
    }
  
  void vertex_list ( Seq<T> & v) const ;
  void edge_list   ( Seq<T> & e) const ;
  Seq<T> neighbors( T e);
  
  gNode<T>* push_vertex(T val, int i=0);
  void push_edge(T v_val,T e_val);
  inline        void push_uedge(T v_val,T e_val)
    {push_edge(v_val,e_val); push_edge(e_val,v_val);};

  
  inline unsigned nbv() const { return nvertices;};
  inline unsigned nbe() const { return nedges;   };

  inline T        next(T val)   const ;
  inline bool     member(T val) const ;
  
  void delete_edge(T v_val,T e_val);
  void delete_vertex(T val);
  
  // dfs: apply function fp to nodes
  void dfs(func fp);
  void dfs_walk(gNode<T> * s, func fp);

  // dfs: return (pointer to) first node that satisfies bool fp
  gNode<T>* dfs( test_node fp );
  
  // dfs: fill "out" with the nodes in visited order
  void dfs(Seq<T> & out);
  void dfs_walk(gNode<T> * s, Seq<T> & out);
  
  // set node t as the head of the list (thus dfs starts from this node)
  bool set_start_node(T& val);
  bool set_start_node(T& v_val,T& e_val);
  gNode<T> * get_start_node();
  
  GraphDfsIter<T> * createIterator() const;
  
  
  void print()
    {
      std::cout<< "Graph: "<< std::endl;
      gNode<T> *s, *t=head;
      while(t!=NULL)
      {
        std::cout<< t->data<<" ===> ";
        s=t->next;
        while(s!=NULL)
        {   std::cout<< s->data<<", "; s=s->next;}
        std::cout<< std::endl;
        t=t->vlist;
      }
      std::cout<< std::endl;
    }

  
private:
  
  static void discover(gNode<T> * v);
  
};
  
  
template<class T>
class GraphDfsIter
{
  const Graph<T> *g;
  gNode<T> * current, * next_start; 
    NODESTACK q;
  
public:
  
  GraphDfsIter(const Graph<T> s)
    {
      g = &s;
    }
  
  void first()
    {
      current = g->head;
      next_start=current->vlist;
      
      gNode<T>* t=current;
      while(t!=NULL)// Mark all as not visited
      {
        t->status(-1);
        t=t->vlist;
      }
      current->status(0);
    }

  bool isLast()
    {

      if ( q.empty() )
      {
        
        while( next_start!=NULL)
        {
          if ( next_start->status()==-1) 
          {
            next_start->status(0);
            q.push(next_start); 
            next_start=next_start->vlist;
            break;
          }
          next_start=next_start->vlist;
        }
      }

        if (next_start==NULL)
          return true;
        else
          return false;
    }
  
  void next()
    {
      
      if ( q.empty() )
      {
        
        while( next_start!=NULL)
        {
          if ( next_start->status()==-1) 
          {
            next_start->status(0);
            q.push(next_start); 
            next_start=next_start->vlist;
            break;
          }
          next_start=next_start->vlist;
        }
        
        if (next_start==NULL)// Finished
        {
          current= NULL; //isDone
          return;
        }
        
      }
      
      // q not empty
      current= q.top();
      q.pop();
      
      gNode<T>* t=current;       
      while(t->next!=NULL)
      {
        if ( t->next->status() == -1 )
        {
          t->next->status(0); // mark as visited 
          q.push(t->next->start); 
        }
        t=t->next;
      }
      
      return;
    }
    
  bool isDone()
    {
      return current == NULL;
    }
  
  gNode<T> * currentItem()
    {
      return current;
    }
};
  
template<class T>
GraphDfsIter<T> *Graph<T>::createIterator() const
{
  return new GraphDfsIter<T>(this);
}

template<class T>
 gNode<T>* Graph<T>::push_vertex(T val,int i)// i: sets aux parameter
{
 gNode<T>* temp=new gNode<T>(val);
 temp->aux(i);

   nvertices++;
   if(head==NULL)
    {
     head=temp;
     head->me=temp;
     return temp;
    }

   gNode<T>* t=head;
   while(t->vlist!=NULL)
    t=t->vlist;

   t->vlist=temp;
   temp->start=temp;
   temp->me=temp;
   return temp;
}

template<class T>
void Graph<T>::push_edge(T v_val,T e_val)
{
  if(head==NULL)
    return;
  nedges++;
  
  gNode<T>* t=head;
  
  while(t!=NULL) //find vertex v
  {
     if(t->data==v_val)
     {  
       gNode<T>* temp=new gNode<T>(e_val);
       
       while(t->next!=NULL)
         t=t->next;
       t->next=temp;// add e to v's neighbors
       
       t=head;//update node info
       while(t!=NULL)
       {
         if(t->data==e_val)
         {
           temp->me=t->me;
           t->me=temp;               
           //temp->vlist=t->vlist;
           temp->start=t;
         }
         t=t->vlist;
       }
       
       return;
     }
     t=t->vlist;
  }
}

template<class T>
void Graph<T>::vertex_list( Seq<T>& v) const 
{
  gNode<T>* t= head;
  
  while(t!=NULL)
  {
    v << t->data;
    t=t->vlist;
  }
}

// i,j are added consecutively in the list iff there is the edge (i,j)
template<class T>
void Graph<T>::edge_list (Seq<T>& e) const 
{
  gNode<T>*s, *t=head;
  while( t!=NULL)
  {
    s=t;
    while ( s->next!=NULL)
    {
      e<< t->data << s->next->data ;
      s=s->next;
    }
    t=t->vlist;
  }
}

// Neighbors of vertex v_val
template<class T>
Seq<T> Graph<T>::neighbors ( T v_val)
{
    Seq<T> e;
    gNode<T>*s, *t=head;
    while( t!=NULL)
    {
      if(t->data==v_val)
      {         
        s=t;
           while ( s->next!=NULL)
           {
             //e<< t->data << s->next->data ;
             e<< s->next->data ;
             s=s->next;
           }
      }
      t=t->vlist;
    }
    return e;
}

// Returns a neighbor of vertex val
template<class T> inline T
Graph<T>::next(T val) const {
  gNode<T> *t=head;
  while( t!=NULL){
    if(t->data==val)
    {   if (t->next==NULL)
        std::cout<<"no neighbor!"<<std::endl;
      return t->next->data;
    }
    t=t->vlist;
  }
  std::cout<< "Node not in graph."<<std::endl;
  return NULL;
}

// true iff val is a node of the graph
template<class T> inline bool
Graph<T>::member(T val) const {
  gNode<T> *t=head;
  while( t!=NULL)
    if(t->data==val)
      return true;
    else
      t=t->vlist;
  return false;
}



// call as              dfs( &discover ) to run DFS.
template<class T>
void Graph<T>::discover(gNode<T> * v)
{
 //             std::cout<< "m_status="<< t->m_status<<std::endl;
}

template<class T>
void Graph<T>::delete_edge(T v_val,T e_val)
{
  if(head==NULL)
    return;
  
  gNode<T> *s, *t=head;
  
  while(t!=NULL)
  {                  
    if(t->data==v_val)         
    {                         
      s=t;
      t=t->next;
      while(t!=NULL)
      {               
        if(t->data==e_val)
         {           
           s->next=t->next;
           t->vlist=NULL; 
           delete t;
           nedges--;
           return;
         }
        s=t;
        t=t->next;
      }
      return;                                            
    }
    t=t->vlist;
  }
  
}

template<class T>
void Graph<T>::delete_vertex(T v_val)
{
  if(head==NULL)
    return;
  nvertices--;
  
  gNode<T>* e=head;
  
  // Delete edges from other vertices lists
  while(e!=NULL)
     {
       delete_edge(e->data,v_val);
       e=e->vlist;
     }
  
  // Delete incident edges
  e=head;
  while(e!=NULL)
     {
       delete_edge(v_val,e->data);
       e=e->vlist;
     }
  
  //Delete Vertex
  if(head->data==v_val)
  {
    gNode<T>* temp=head;
    head=head->vlist;
    delete temp;
    return;
  }
  
  gNode<T>* p1=head->vlist;
  gNode<T>* p2=head;
  
  while(p1!=NULL)
  {
    if(p1->data==v_val)
    {
      p2->vlist=p1->vlist;
      p1=NULL;
      delete p1;
      return;
    }
    p2=p1;
    p1=p1->vlist;
  }
}


template<class T>
gNode<T> * Graph<T>::get_start_node()
{
  return head;
}

template<class T>
bool Graph<T>::set_start_node(T& val)
{
  gNode<T>* k=head;
  
  while(k->vlist!=NULL)  //check that vertex exists
  {
    if(k->vlist->data==val)
      break;
    k=k->vlist;
  }
  if (k->vlist==NULL) return false;
  
  gNode<T> *u= k->vlist;
  k->vlist  = u->vlist;
  u->vlist  = this->head;
  this->head= u;
}

template<class T>
bool Graph<T>::set_start_node(T& v_val,T& e_val)
{
  gNode<T>* k=this->head->next;
  
  if (!set_start_node(v_val)) return false;
  
  while(k->next!=NULL)
  {
    if(k->next->data==e_val)
      break;
    k=k->next;
  }
  if (k->next==NULL) return false;
  
  gNode<T> *u= k->next;
  k->next  = u->next;
  u->next  = this->head->next;
  this->head->next= u;
}



template<class T>
void Graph<T>::dfs( func fp )
{
  gNode<T>* t=head;
  
  while(t!=NULL)
  {
    t.status(-1);
    t=t->vlist;
  }
  
  t=head;
  while(t!=NULL)
  {
    if (t->status()==-1) dfs_walk(t,fp);
    t=t->vlist;
  }
}

template<class T>
void Graph<T>::dfs_walk(gNode<T> * s, func fp)
{
  NODESTACK q;
  gNode<T> * t;
  
  q.push(s);
  s->status(0);                  // mark as visited
  
  while ( !q.empty() )
  {
    t=q.top();
    q.pop();
    
    if (fp!=NULL) (*fp)(t);       // run operation on node
    //std::cout<< t->data<<std::endl;
    
    while(t->next!=NULL)
    {
      if (t->next->status()==-1)
      {
        t->status(0); // mark as visited 
        q.push(t->next->start); 
      }
      t=t->next;
    }
  }
}


template<class T>
void Graph<T>::dfs(Seq<T>& out)
{
  gNode<T>* t=head;
  
  while(t!=NULL)
  {
    t->status(-1);
    t=t->vlist;
  }
  
  t=head;
  while(t!=NULL)
  {
    if (t->status()==-1) 
      dfs_walk(t,out);
    t=t->vlist;
  }
}

template<class T>
void Graph<T>::dfs_walk(gNode<T> * s, Seq<T>& out)
{
  NODESTACK q;
  gNode<T> * t;
  
  q.push(s);
  
  while ( !q.empty() )
  {
    t=q.top();
    q.pop();
    if ( t->status()==-1)
    {
    out<< t->data; // output node data
    t->status(0); // mark as visited 
    }
     while(t->next!=NULL)
     {
       if ( t->next->status() == -1 )
       {
         q.push(t->next->start); 
       }
       t=t->next;
     }

  }
}


template<class T>
gNode<T>* Graph<T>::dfs( test_node fp )
{
  gNode<T>* t=head;
  
  while(t!=NULL)
  {
    t->status(-1);
    t=t->vlist;
  }
  
  t=head;
  while(t!=NULL)
  {
    if (t->status()==-1) 
    {
      NODESTACK q;
      gNode<T> * s;
      
      q.push(t);
      t->status(0);    // mark as visited
      
      while ( !q.empty() )
      {
        s=q.top();
        q.pop();
        

        if (fp!=NULL)
          if ( (*fp)(s) ) // check node
            return s;
        
        while(t->next!=NULL)
        {
          if (t->next->status()==-1)
          {
            t->status(0); // mark as visited
            q.push(t->next->start); 
          }
          
          t=t->next;
        }
      }
    }
    t=t->vlist;
  }
  
  return NULL;
}
  
// Function to be passed to the DFS procedure
template<class T>
void write_edge(gNode<T>* v)
{
  std::cout<<"Ok"<<std::endl;
}

template<class O, class V> struct viewer; struct axel;

template<class K, class T> Viewer&
operator<<(Viewer& out, const Graph<T>& g) {
  

  //Seq<T> vertices;

  if (g.nbe()==0) return out;
  
  Seq<T> edges;
  g.edge_list(edges);
  
  out<<" <curve type=\"mesh\">\n<vect>\nVECT\n";
  out<<g.nbe()<<" "
    //<<g.nbv()<<" "
     <<2*g.nbe()<<" "
     <<g.nbe()<<"\n";
  
  for(unsigned i=0; i<g.nbe();i+=2) out<<"2 ";//
  out<<"\n";
  
  // for(unsigned i=0; i<g.nbv();i++) out<<"1 ";
  // out<<"\n";
  for(unsigned i=0; i<g.nbe();i+=2) out<<"1 ";//
  out<<"\n";

  //g.dfs( vertices );
  //print edges
  // unsigned i;
  // for (i=1;i<vertices.size(); i++)
  // {
  //            out <<vertices[i-1]->x()<<" "<<vertices[i-1]->y()  <<" 0 "
  //                            <<vertices[i]->x()  <<" "<<vertices[i]->y()<<" 0 "
  //                            <<"\n";
  // }
  //            out <<vertices[i-1]->x()<<" "<<vertices[i-1]->y()  <<" 0 "
  //                            <<vertices[0]->x()  <<" "<<vertices[0]->y()<<" 0 "
  //                            <<"\n";
  
      
  //print edges
  for (unsigned i=0;i<edges.size(); i+=2)
    {
      out <<edges[i]->x()  <<" "<<edges[i]->y()  <<" 0 "
          <<edges[i+1]->x()<<" "<<edges[i+1]->y()<<" 0 "
          <<"\n";
    }
  
  
  for(unsigned i=0; i<g.nbe();i++) 
    out<< "0.314 0.979 1 1\n";
  
  out<<" </vect>\n </curve>\n";
  
  return out;
}


} ; // namespace shape
} ; // namespace mmx

#undef NODESTACK
#undef Viewer