STL graph implementation

I'm looking for a code review on the following C++/STL graph implementation:

```
#include
#include
#include
#include
#include
#include
#include

namespace Graph
{
template
class graph
{
public :
explicit graph(const std::vector > &vertices);
~graph()
{}
void insert_vertex_pair_by_keys(T key1, T key2);

// Private contained classes
private:
// Forward Definition of vertex
class vertex;

struct edge
{
edge(vertex *edge, T weight) :
m_Edge(edge),
m_Weight(weight)
{}
vertex *m_Edge;
T m_Weight;
}; // END EDGE

class vertex
{
public:
vertex(T key) :
m_Key(key)
{}
void connect_edge(vertex *adjacent);
const T key() const {return m_Key;}
const std::list &edges() const {return m_Edges;}
private:
std::list m_Edges;
T m_Key;
bool contains_edge_to_vertex_with_key(const T key);
}; // END VERTEX

// Private methods and member variables
private:
std::list m_Vertices;
vertex *contains_vertex(const T key);
};
}

/*!
* Constructor of graph: Take a pair of vertices as connection, attempt
* to insert if not already in graph. Then connect them in edge list
*/
template
Graph::graph::graph(const std::vector > &vertices_relation)
{
#ifndef NDEBUG
std::cout >::const_iterator insert_it = vertices_relation.begin();
for(; insert_it != vertices_relation.end(); ++insert_it) {
#ifndef NDEBUG
std::cout first " second first, insert_it->second);
}
#ifndef NDEBUG
std::cout ::iterator print_it = m_Vertices.begin();
for(; print_it != m_Vertices.end(); ++print_it) {
std::cout key();
typename std::list::const_iterator edge_it = print_it->edges().begin();
for(; edge_it != print_it->edges().end(); ++edge_it) {
std::cout " m_Edge->key();
}
std::cout
void Graph::graph::insert_vertex_pair_by_keys(T key1, T key2)
{
/*!
* Check if vertices already in graph
*/
Graph::gr

-
This is a directed weighted graph. You may want to indicate this by name. If you wish to be more general you can have two type parameters, one for vertex data and one for edge data. Also think about undirected graphs.

-
I guess namespace Graph and class name graph is redundant

-
Depending on expected usage pattern of verticies, you may want to use vector instead of list

-
Another way to represent edges is by a matrix where M[i,j] represents the edge between i and j.

Worth reading is this:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs1

StackExchange Code Review Q#10697, answer score: 4