#ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
#define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__

#include <map>
#include <set>
#include <vector>
#include <itkLightObject.h>
#include <itkObjectFactory.h>

namespace cpExtensions
{
  namespace DataStructures
  {
    /**
     */
    template< class V, class C, class I = unsigned long >
    class Graph
      : public itk::LightObject
    {
    public:
      typedef Graph                           Self;
      typedef itk::LightObject                Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      typedef V TVertex;
      typedef C TCost;
      typedef I TIndex;

      // Graph types
      typedef std::map< I, V >          TVertices;
      typedef std::vector< C >          TEdges;
      typedef std::map< I, TEdges >     TMatrixRow;
      typedef std::map< I, TMatrixRow > TMatrix;

    public:
      itkNewMacro( Self );
      itkTypeMacro( Graph, itk::LightObject );

    public:
      typename TVertices::iterator BeginVertices( );
      typename TVertices::iterator EndVertices( );
      typename TVertices::const_iterator BeginVertices( ) const;
      typename TVertices::const_iterator EndVertices( ) const;

      typename TMatrix::iterator BeginEdgesRows( );
      typename TMatrix::iterator EndEdgetsRows( );
      typename TMatrix::const_iterator BeginEdgesRows( ) const;
      typename TMatrix::const_iterator EndEdgesRows( ) const;

      bool HasVertexIndex( const I& index ) const;
      void InsertVertex( const I& index, V& vertex );
      V& GetVertex( const I& index );
      const V& GetVertex( const I& index ) const;

      void AddConnection( const I& orig, const I& dest, const C& cost );

      std::set< I > GetSinks( ) const;

    protected:
      Graph( );
      virtual ~Graph( );

    private:
      // Purposely not implemented
      Graph( const Self& other );
      Self& operator=( const Self& other );

    protected:
      TVertices m_Vertices;
      TMatrix   m_Matrix;
    };

  } // ecapseman

} // ecapseman

#ifndef ITK_MANUAL_INSTANTIATION
#include <cpExtensions/DataStructures/Graph.hxx>
#endif // ITK_MANUAL_INSTANTIATION

#endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__

// eof - $RCSfile$