STL graph implementation

Question

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

#include <list>
#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>
#include <stdexcept>
#include <assert.h>
namespace Graph
{
 template <class T>
 class graph
 {
 public :
 explicit graph(const std::vector<std::pair<T, T> > &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<edge> &edges() const {return m_Edges;}
 private:
 std::list<edge> 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<vertex> 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 <class T>
Graph::graph<T>::graph(const std::vector<std::pair<T, T> > &vertices_relation)
{
#ifndef NDEBUG
 std::cout << "Inserting pairs: " << std::endl;
#endif
 typename std::vector<std::pair<T, T> >::const_iterator insert_it = vertices_relation.begin();
 for(; insert_it != vertices_relation.end(); ++insert_it) {
#ifndef NDEBUG
 std::cout << insert_it->first << " -- > " << insert_it->second << 
std::endl;
#endif
 insert_vertex_pair_by_keys(insert_it->first, insert_it->second);
 }
#ifndef NDEBUG
 std::cout << "Printing results: " << std::endl;
 typename std::list<vertex>::iterator print_it = m_Vertices.begin();
 for(; print_it != m_Vertices.end(); ++print_it) {
 std::cout << print_it->key();
 typename std::list<edge>::const_iterator edge_it = print_it->edges().begin();
 for(; edge_it != print_it->edges().end(); ++edge_it) {
 std::cout << "-->" << edge_it->m_Edge->key();
 }
 std::cout << std::endl;
 }
#endif
}
/*!
 * Takes in a value of type T as a key and 
 * inserts it into graph data structure if 
 * key not already present
 */
template <typename T>
void Graph::graph<T>::insert_vertex_pair_by_keys(T key1, T key2)
{
 /*!
 * Check if vertices already in graph
 */
 Graph::graph<T>::vertex *insert1 = contains_vertex(key1);
 Graph::graph<T>::vertex *insert2 = contains_vertex(key2);
 /*!
 * If not in graph then insert it and get a pointer to it
 * to pass into edge. See () for information on how
 * to build graph
 */ 
 if (insert1 == NULL) {
 m_Vertices.push_back(vertex(key1));
 insert1 = contains_vertex(key1);
 }
 if (insert2 == NULL) {
 m_Vertices.push_back(vertex(key2));
 insert2 = contains_vertex(key2);
 }
#ifndef NDEBUG
 assert(insert1 != NULL && "Failed to insert first vertex");
 assert(insert2 != NULL && "Failed to insert second vertex");
#endif
 /*!
 * At this point we should have a vertex to insert an edge on
 * if not throw an error.
 */ 
 if (insert1 != NULL && insert2 != NULL) {
 insert1->connect_edge(insert2);
 insert2->connect_edge(insert1);
 } else {
 throw std::runtime_error("Unknown");
 }
}
/*!
 * Search the std::list of vertices for key
 * if present return the vertex to indicate
 * already in graph else return NULL to indicate
 * new node
 */
template <typename T>
typename Graph::graph<T>::vertex *Graph::graph<T>::contains_vertex(T key)
{
 typename std::list<vertex >::iterator find_it = m_Vertices.begin();
 for(; find_it != m_Vertices.end(); ++find_it) {
 if (find_it->key() == key) {
 return &(*find_it);
 }
 }
 return NULL;
}
/*!
 * Take the oposing vertex from input and insert it
 * into adjacent list, you can have multiple edges
 * between vertices
 */
template <class T>
void Graph::graph<T>::vertex::connect_edge(Graph::graph<T>::vertex *adjacent)
{
 if (adjacent == NULL)
 return;
 if (!contains_edge_to_vertex_with_key(adjacent->key())) {
 Graph::graph<T>::edge e(adjacent, 1);
 m_Edges.push_back(e);
 }
}
/*!
 * Private member function that check if there is already
 * an edge between the two vertices
 */
template <class T>
bool Graph::graph<T>::vertex::contains_edge_to_vertex_with_key(const T key)
{
 typename std::list<edge>::iterator find_it = m_Edges.begin();
 for(; find_it != m_Edges.end(); ++find_it) {
 if (find_it->m_Edge->key() == key) {
 return true;
 } 
 }
 return false;
}

// main.cpp
#include "graph.h"
#include <cstdlib>
int main(int argc, char *argv[])
{
 std::vector<std::pair<int, int> > graph_vect;
 for (int i = 0; i < 100; i++) {
 graph_vect.push_back(std::pair<int, int>(rand()%20, rand()%20));
 }
 Graph::graph<int> my_graph(graph_vect);
 return 0;
}

• Christopher Creutzig: Why do your edges only have a single vertex *, and why is that pointer named m_Edge and edge?
• Matthew Hoggan: An edge can only lead to a single vertex for one. This facilitates algorithms by allowing you to traverse the edge list, then get a pointer to the vertex associated with that edge so you don't have to do a lookup on the vertex to scan its edges. m_Edge and edge where chosen because the "edge" leads to the adjacent vertex.
• Christopher Creutzig: Sorry, I hadn't realized you're storing the outgoing edges in the vertices. Still not happy with the names, though – vertex *to and vertex *m_endPoint, perhaps? Nah ...

Answer 1

As long as you use special function for checking, consider to use special function for adding. Something like

Graph::graph<T>::vertex *insert1 = contains_vertex(key1);
 ...
 if (insert1 == NULL) {
 add_vertex_in_container(vertex(key1));
 insert1 = contains_vertex(key1);
 }
/*....*/
add_vertex_in_container(vertex(key1))
{
 m_Vertices.push_back(vertex(key1));
}

I'm 99% sure the compiler will make this function inline, so there won't be an calling overhead.

pros: it's easier to change the adding logic in the future. For example to increment an counter and send an even after the adding has happened.

cons: the code could become less readble in the case all you need is m_Vertices.push_back()

---

you could rewrite contains_edge_to_vertex_with_key method in such way

{
 return find(m_Edges.begin(), m_Edges.end(), key) != m_Edges.end() ? true : false ;
}

---

upd: consider to use std::make_pair instead of std::pair. In the first case you free to not specialize template parameters explicitly

vector<pair<int, int> > v;
v.push_back(make_pair(1,2)) 
instead of 
v.push_back(pair<int, int>(1,2))

---

+1 for possibility of changing vector to list and vise versa. Speaking more detaily your graph object shouldn't be hardly related with data structure keeping the graph structure. Consider to implement it as an template parameter.

Answer 2

• 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