Graph< T > Class Template Reference

#include <graph.hpp>

List of all members.

Public Member Functions

• Graph ()
• void vertex_list (Seq< T > &v) const

  Fills sequence v with node data.
  

• void edge_list (Seq< T > &e) const
• Seq< T > neighbors (T e)
• gNode< T > * push_vertex (T val, int i=0)

  Insert vertex.
  

• void push_edge (T v_val, T e_val)

  Insert edge.
  

• void push_uedge (T v_val, T e_val)
• unsigned nbv () const
• unsigned nbe () const
• T next (T val) const
• bool member (T val) const
• void delete_edge (T v_val, T e_val)

  Deletes an edge.
  

• void delete_vertex (T val)

  Deletes a vertex and all incident edges.
  

• void dfs (func fp)

  DFS traversal (run operation fp on nodes).
  

• void dfs_walk (gNode< T > *s, func fp)
• gNode< T > * dfs (test_node fp)

  DFS search (find a node that satisfies test fp).
  

• void dfs (Seq< T > &out)

  DFS traversal (output node data in DFS order).
  

• void dfs_walk (gNode< T > *s, Seq< T > &out)
• 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 ()

  Print rep of graph - for testing.
  

Friends

• class GraphDfsIter< T >

---

Detailed Description

template<class T>
class mmx::shape::Graph< T >

Definition at line 116 of file graph.hpp.

---

Constructor & Destructor Documentation

Graph

(

)

[inline]

Definition at line 130 of file graph.hpp.

    {
      nvertices=nedges=0;
      head=NULL;
    }

---

Member Function Documentation

GraphDfsIter< T > * createIterator

(

)

const [inline]

Definition at line 307 of file graph.hpp.

{
  return new GraphDfsIter<T>(this);
}

void delete_edge	(	T	v_val,
		T	e_val
	)			[inline]

Deletes an edge.

Definition at line 468 of file graph.hpp.

Referenced by Graph< T >::delete_vertex().

{
  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;
  }
  
}

void delete_vertex

(

T

val

)

[inline]

Deletes a vertex and all incident edges.

Definition at line 503 of file graph.hpp.

References Graph< T >::delete_edge().

Referenced by voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), semialgebraic2d< C, V >::run(), and arrangement2d< C, V >::run().

{
  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;
  }
}

void dfs

(

Seq< T > &

out

)

[inline]

DFS traversal (output node data in DFS order).

Definition at line 655 of file graph.hpp.

References Graph< T >::dfs_walk(), and gNode< T >::status().

{
  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;
  }
}

gNode< T > * dfs

(

test_node

fp

)

[inline]

DFS search (find a node that satisfies test fp).

Definition at line 707 of file graph.hpp.

References NODESTACK, and gNode< T >::status().

{
  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;
}

void dfs

(

func

fp

)

[inline]

DFS traversal (run operation fp on nodes).

Definition at line 604 of file graph.hpp.

References Graph< T >::dfs_walk(), and gNode< T >::status().

Referenced by mmx::shape::print_boxes(), voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), semialgebraic2d< C, V >::run(), mesher2d< C, V >::run(), and arrangement2d< C, V >::run().

{
  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;
  }
}

void dfs_walk	(	gNode< T > *	s,
		Seq< T > &	out
	)			[inline]

Definition at line 675 of file graph.hpp.

References NODESTACK, and gNode< T >::status().

{
  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;
     }

  }
}

void dfs_walk	(	gNode< T > *	s,
		func	fp
	)			[inline]

Definition at line 623 of file graph.hpp.

References NODESTACK, and gNode< T >::status().

Referenced by Graph< T >::dfs().

{
  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;
    }
  }
}

void edge_list

(

Seq< T > &

e

)

const [inline]

Definition at line 391 of file graph.hpp.

{
  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;
  }
}

gNode< T > * get_start_node

(

)

[inline]

Definition at line 554 of file graph.hpp.

{
  return head;
}

bool member

(

T

val

)

const [inline]

Definition at line 447 of file graph.hpp.

Referenced by voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), semialgebraic2d< C, V >::run(), and arrangement2d< C, V >::run().

                            {
  gNode<T> *t=head;
  while( t!=NULL)
    if(t->data==val)
      return true;
    else
      t=t->vlist;
  return false;
}

unsigned nbe

(

void

)

const [inline]

Definition at line 147 of file graph.hpp.

{ return nedges;   };

unsigned nbv

(

)

const [inline]

Definition at line 146 of file graph.hpp.

{ return nvertices;};

Seq< T > neighbors

(

T

e

)

[inline]

Definition at line 408 of file graph.hpp.

{
    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;
}

T next

(

T

val

)

const [inline]

Definition at line 431 of file graph.hpp.

Referenced by voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), semialgebraic2d< C, V >::run(), and arrangement2d< C, V >::run().

                          {
  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;
}

void print

(

)

[inline]

Print rep of graph - for testing.

Definition at line 175 of file graph.hpp.

    {
      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;
    }

void push_edge	(	T	v_val,
		T	e_val
	)			[inline]

Insert edge.

Definition at line 339 of file graph.hpp.

Referenced by Graph< Point * >::push_uedge(), voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), semialgebraic2d< C, V >::run(), mesher2d< C, V >::run(), and arrangement2d< C, V >::run().

{
  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;
  }
}

void push_uedge	(	T	v_val,
		T	e_val
	)			[inline]

Definition at line 142 of file graph.hpp.

Referenced by voronoi2dimpl< C, V >::insert_regular(), and voronoi2d< C, V >::insert_regular().

    {push_edge(v_val,e_val); push_edge(e_val,v_val);};

gNode< T > * push_vertex	(	T	val,
		int	i = 0
	)			[inline]

Insert vertex.

Definition at line 314 of file graph.hpp.

References gNode< T >::aux().

Referenced by voronoi2dimpl< C, V >::insert_regular(), voronoi2d< C, V >::insert_regular(), voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), and mesher2d< C, V >::run().

                                               : 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;
}

bool set_start_node	(	T &	v_val,
		T &	e_val
	)			[inline]

Definition at line 579 of file graph.hpp.

References Graph< T >::set_start_node().

{
  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;
}

bool set_start_node

(

T &

val

)

[inline]

Definition at line 560 of file graph.hpp.

Referenced by Graph< T >::set_start_node().

{
  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;
}

void vertex_list

(

Seq< T > &

v

)

const [inline]

Fills sequence v with node data.

Definition at line 378 of file graph.hpp.

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

---

Friends And Related Function Documentation

friend class GraphDfsIter< T > [friend]

Definition at line 118 of file graph.hpp.

---

The documentation for this class was generated from the following file:

• include/shape/graph.hpp