X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FDataStructures%2FGraph.hxx;fp=lib%2Ffpa%2FDataStructures%2FGraph.hxx;h=4d348d5421d02c266cdf8513eef1f33ff8311f65;hb=2047276c8f1a02432fbcc7014722d460d6c1e60f;hp=0000000000000000000000000000000000000000;hpb=3c639e5da479c7216a0a302ffa156ac6762caeed;p=FrontAlgorithms.git

diff --git a/lib/fpa/DataStructures/Graph.hxx b/lib/fpa/DataStructures/Graph.hxx
new file mode 100644
index 0000000..4d348d5
--- /dev/null
+++ b/lib/fpa/DataStructures/Graph.hxx
@@ -0,0 +1,270 @@
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
+#ifndef __fpa__DataStructures__Graph__hxx__
+#define __fpa__DataStructures__Graph__hxx__
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+Clear( )
+{
+  this->m_Vertices.clear( );
+  this->m_Matrix.clear( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+bool fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RenameVertex( const TIndex& old_index, const TIndex& new_index )
+{
+  typename TVertices::iterator old_v = this->m_Vertices.find( old_index );
+  typename TVertices::iterator new_v = this->m_Vertices.find( new_index );
+  if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
+  {
+    // Replace vertex
+    this->m_Vertices[ new_index ] = old_v->second;
+    this->m_Vertices.erase( old_index );
+
+    // Duplicate edges
+    typename TMatrix::iterator mIt = this->m_Matrix.begin( );
+    typename TMatrix::iterator found_row = this->m_Matrix.end( );
+    for( ; mIt != this->m_Matrix.end( ); ++mIt )
+    {
+      if( mIt->first == old_index )
+        found_row = mIt;
+
+      typename TMatrixRow::iterator rIt = mIt->second.begin( );
+      for( ; rIt != mIt->second.end( ); ++rIt )
+      {
+        if( mIt->first == old_index )
+          this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
+        else if( rIt->first == old_index )
+          this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;
+
+      } // rof
+
+    } // rof
+
+    // Delete old edges
+    if( found_row != this->m_Matrix.end( ) )
+      this->m_Matrix.erase( found_row );
+
+    mIt = this->m_Matrix.begin( );
+    for( ; mIt != this->m_Matrix.end( ); ++mIt )
+    {
+      typename TMatrixRow::iterator rIt = mIt->second.begin( );
+      while( rIt != mIt->second.end( ) )
+      {
+        if( rIt->first == old_index )
+        {
+          mIt->second.erase( rIt );
+          rIt = mIt->second.begin( );
+        }
+        else
+          ++rIt;
+
+      } // elihw
+
+    } // rof
+    return( true );
+  }
+  else
+    return( false );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RemoveVertex( const TIndex& index )
+{
+  typename TVertices::iterator i = this->m_Vertices.find( index );
+  if( i != this->m_Vertices.end( ) )
+  {
+    // Delete vertex
+    this->m_Vertices.erase( i );
+
+    // Delete edges starting from given vertex
+    typename TMatrix::iterator mIt = this->m_Matrix.find( index );
+    if( mIt != this->m_Matrix.end( ) )
+      this->m_Matrix.erase( mIt );
+
+    // Delete edges arriving to given vertex
+    mIt = this->m_Matrix.begin( );
+    for( ; mIt != this->m_Matrix.end( ); ++mIt )
+    {
+      typename TMatrixRow::iterator rIt = mIt->second.begin( );
+      while( rIt != mIt->second.end( ) )
+      {
+        if( rIt->first == index )
+        {
+          mIt->second.erase( rIt );
+          rIt = mIt->second.begin( );
+        }
+        else
+          ++rIt;
+
+      } // elihw
+
+    } // rof
+
+  } // fi
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+typename
+fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+TEdges&
+fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+GetEdges( const TIndex& orig, const TIndex& dest )
+{
+  static TEdges null_edges;
+  typename TMatrix::iterator o = this->m_Matrix.find( orig );
+  if( o != this->m_Matrix.find( orig ) )
+  {
+    typename TMatrixRow::iterator d = o->second.find( dest );
+    if( d == o->second.end( ) )
+    {
+      null_edges.clear( );
+      return( null_edges );
+    }
+    else
+      return( d->second );
+  }
+  else
+  {
+    null_edges.clear( );
+    return( null_edges );
+
+  } // fi
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+const typename 
+fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+TEdges&
+fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+GetEdges( const TIndex& orig, const TIndex& dest ) const
+{
+  static const TEdges null_edges;
+  typename TMatrix::iterator o = this->m_Matrix.find( orig );
+  if( o != this->m_Matrix.find( orig ) )
+  {
+    typename TMatrixRow::iterator d = o->second.find( dest );
+    if( d == o->second.end( ) )
+      return( null_edges );
+    else
+      return( d->second );
+  }
+  else
+    return( null_edges );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+bool fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+HasEdge( const TIndex& orig, const TIndex& dest ) const
+{
+  typename TMatrix::const_iterator mIt = this->m_Matrix.find( orig );
+  if( mIt != this->m_Matrix.end( ) )
+    return( mIt->second.find( dest ) != mIt->second.end( ) );
+  else
+    return( false );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
+{
+  typename TMatrix::iterator m = this->m_Matrix.find( orig );
+  if( m != this->m_Matrix.end( ) )
+  {
+    typename TMatrixRow::iterator r = m->second.find( dest );
+    if( r != m->second.end( ) )
+    {
+      typename TEdges::iterator e = r->second.end( );
+      for(
+        typename TEdges::iterator i = r->second.begin( );
+        i != r->second.end( ) && e == r->second.end( );
+        ++i
+        )
+        if( *i == cost )
+          e = i;
+      if( e != r->second.end( ) )
+      {
+        r->second.erase( e );
+        if( r->second.size( ) == 0 )
+        {
+          m->second.erase( r );
+          if( m->second.size( ) == 0 )
+            this->m_Matrix.erase( m );
+
+        } // fi
+
+      } // fi
+
+    } // fi
+
+  } // fi
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RemoveEdges( const TIndex& orig, const TIndex& dest )
+{
+  typename TMatrix::iterator m = this->m_Matrix.find( orig );
+  if( m != this->m_Matrix.end( ) )
+  {
+    typename TMatrixRow::iterator r = m->second.find( dest );
+    if( r != m->second.end( ) )
+    {
+      m->second.erase( r );
+      if( m->second.size( ) == 0 )
+        this->m_Matrix.erase( m );
+
+    } // fi
+
+  } // fi
+
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+std::set< _TIndex, _TIndexCompare >
+fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+GetSinks( ) const
+{
+  std::set< _TIndex, _TIndexCompare > sinks;
+
+  typename TVertices::iterator vIt = this->m_Vertices.begin( );
+  for( ; vIt != this->m_Vertices.end( ); ++vIt )
+    sinks.insert( vIt->first );
+  typename TMatrix::iterator mIt = this->m_Matrix.begin( );
+  for( ; mIt != this->m_Matrix.end( ); ++mIt )
+    sinks.erase( mIt->first );
+
+  return( sinks );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+Graph( )
+  : Superclass( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+~Graph( )
+{
+}
+
+#endif // __fpa__DataStructures__Graph__hxx__
+// eof - $RCSfile$