Graph library - graph interface

Question

I am trying to write simple graph lib in C++, BFS, DFS etc.. I want to create class GraphI which will represent any graph and will include necessary methods so my library could work. Could I add/remove/improve something from my code?

#pragma once
#include <algorithm>
#include "colors.h"
struct Vertex;
template < typename T >
class GraphI {
public:
 struct Vertex {
 Vertex( const T& k, color col = color::w, int c = -1 )
 : key( k )
 , color(col)
 , cost( c ) {}
 int getCost() const { return cost; }
 const T& getKey() const { return key; }
 T& getKey() { return key; }
 void setColor( color c ) { color = c; }
 color getColor() { return color; }
 int cost;
 color color;
 T key;
 bool operator<( const Vertex& v1 ) const {
 return key < v1.key;
 }
 };
 using Graph = std::map<Vertex, std::list<Vertex> >;
 GraphI() = default;
 virtual ~GraphI() = default;
 virtual void add_vertex( const T& vertex ) {
 // if exists then add else do nothing
 _graph[ vertex ] = {};
 ++_size;
 } 
 virtual void add_edge( const T& from,
 const T& to,
 int cost = -1 ) {
 // if vertices do NOT exist return
 auto it = _graph.find( from );
 if ( it == _graph.end() ) return;
 auto it2 = _graph.find( to );
 if ( it2 == _graph.end() ) return;
 auto& neighbours = it->second;
 auto it_exists = std::find_if( neighbours.begin(),
 neighbours.end(),
 [&to]( const Vertex& vertex ) { return vertex.getKey() == to; } );
 // if edge already exists
 if ( it_exists != neighbours.end() ) return;
 neighbours.emplace_back( Vertex(to, color::w, cost) );
 }
 virtual void remove_vertex( const T& vertex ) {
 _graph.erase( vertex );
 --_size;
 // remove all edges going TO vertex
 for ( auto& v : _graph ) { 
 auto it = std::find_if( v.second.begin(),
 v.second.end(),
 [&vertex]( const auto& v )
 { return vertex == v.getKey(); } );
 // if vertex does NOT exist
 if ( it == v.second.end() ) return;
 v.second.erase( it );
 }
 }
 virtual void remove_edge( const T& from, const T& to ) {
 auto it = _graph.find( from );
 if ( it == _graph.end() ) return;
 auto &edges = it->second;
 auto it2 = std::find_if( edges.begin(), edges.end(),
 [&]( const auto& vertex ) { return vertex.key == to; } );
 if ( it2 == edges.end() ) return;
 edges.erase( it2 );
 }
 const Graph& graph() const { return _graph; }
 unsigned size() const { return _size; }
private:
 Graph _graph;
 unsigned _size;
};

Answer 1

The comment in add_vertex is confusing and at contradicts what the code does. If vertex already exists in _graph, the existing vertex will be replaced with an empty one, then the size increased (causing the internal _size to be incorrect). Depending on what behavior you want when adding a vertex that already exists, you can use _graph.try_emplace, _graph.insert_or_assign, or just _graph[vertex] (to add a new entry if it does not exist, and do nothing if it does).

There is no benefit to maintaining a distinct _size variable. As shown above, it can get out of sync with the actual size. It is better to just call _graph.size() whenever the user calls Graph::size.

In remove_vertex, you should check the return value from _graph.erase to see if something was actually removed. If nothing was removed there's no benefit to running any of the other code in the function. Also, the if (it == v.second.end()) check should not return, as you avoid scanning the rest of the vertexes in _graph to remove edges that connect to the vertex that was just removed. Alternatively, you can just replace that whole loop body with a call to either v.second.remove or v.second.remove_if. (The same change can be made in remove_edge.)

• sliziky: Thanks for quick answer. - _graph[ vertex ] = {}; seemed really weird to me but I tried it and it worked as if nothing happened but I there was some mistake in that code and it really (as I expected originally) replaces vector with the empty one. Is there any way how to move line using Graph = std::map<Vertex, std::list<Vertex> >; to the top ? Because if I move it there now, then the compiler shouts that Vertex is incomplete. Thanks
• 1201ProgramAlarm: Types stored in containers need to be completely defined before you can use them in the container, so you can't declare Graph before Vertex is defined.

Answer 2

As a general comment, high performance code will not use std::map (or the like) - this has been quite well explained by e.g., Chandler Carruth in several talks. Here's his talk from CppCon 2014 on the topic.

A typical high performance implementation in the field of (parallel) graph algorithms for an edge list uses two arrays (i.e., continuous chunks of memory). The first one stores all the edges and the second specifies where adjacency (sub)lists for the vertices start. For example, if your graph is the 3-vertex triangle, the first array, call it A, would be 0 1 0 2 1 2 representing the three edges (0,1), (0,2), and (1,2). The second array would be 0 2 4 meaning the adjacency list for vertex 0 starts at A[0], the adjacency list for vertex 1 is at A[2], and so on.

• Varad Mahashabde: The edge list could perhaps use an struct Edge with two variables of the appropriate type, maybe int.