# Lab 8 - Graph Implementation

In this lab session we will develop a simple adjacency list based weighted graph data structure. We will also implement BFS and DFS for the graph using the visitor pattern.
Graph
```// AdjacencyListGraph.h
#pragma once

#include <iterator>
#include <queue>
#include <stack>
#include <vector>

namespace csc280
{
template <typename V, typename E>
{
#include "private/ALGDefs.h"

public:
#include "private/ALGVertexIterator.h"
#include "private/ALGEdgeIterator.h"

using vertex_iterator = ALGVertexIterator<V, E>;
using edge_iterator = ALGEdgeIterator<V, E>;

explicit AdjacencyListGraph( std::size_t initialSize = 32 )
{
graph.reserve( initialSize );
}

template <typename ...Args>
auto emplace( Args... args ) -> vertex_iterator;
auto insert( V vertex ) -> vertex_iterator;

template <typename ...Args>
auto emplaceEdge( const V& source, const V& destination, Args... args ) -> edge_iterator;
auto insertEdge( const V& source, const V& destination, E value ) -> edge_iterator;

void erase( const V& vertex );
void erase( const vertex_iterator& iter );
void eraseByIndex( const std::size_t index );

using EdgeValue = std::tuple<V, E>;
auto insertEdge( const V& source, EdgeValue&& tuple ) -> edge_iterator;

void eraseEdge( const V& source, const V& destination, const E& edge );

auto cbegin() const -> vertex_iterator { return ALGVertexIterator<V,E>( graph.cbegin() ); }
auto cend() const -> vertex_iterator { return ALGVertexIterator<V, E>( graph.cend() ); }

auto cbegin( const V& vertex ) const -> edge_iterator;
auto cend( const V& vertex ) const -> edge_iterator;

auto operator[]( const std::size_t index ) const -> reference_type;
bool exists( const V& vertex ) const;
auto find( const V& vertex ) const -> vertex_iterator;

auto find( const V& source, const V& destination ) const -> edge_iterator;

std::size_t size() const { return graph.size(); }
bool empty() const { return graph.empty(); }

template <typename Visitor>
void depthFirstSearch( const Visitor& visitor ) const;

template <typename Visitor>
void breadthFirstSearch( const Visitor& visitor ) const;

private:
auto indexOf( const V& vertex ) -> typename Graph::iterator;

template <typename Visitor>
void visitDfs( const std::size_t index, Visited& visited, const Visitor& visitor ) const;

template <typename Visitor>
void visitBfs( const std::size_t index, Visited& visited, const Visitor& visitor ) const;

Graph graph;
};

#include "private/ALGImpl.h"
}
```
Definitions
```// private/ALGDefs.h
using value_type = V;
using pointer_type = value_type const*;
using reference_type = const value_type&;
using edge_value_type = E;

struct Edge
{
edge_value_type value;
std::size_t index;

bool operator==( const Edge& rhs ) const
{
return value == rhs.value && index == rhs.index;
}
};

struct Vertex
{
Vertex( value_type value ) : value{ std::move( value ) }
{
edges.reserve( 8 );
}

bool operator==( const Vertex& rhs ) const
{
return value == rhs.value;
}

value_type value;
};

using Graph = std::vector<Vertex>;
using Visited = std::vector<bool>;
```
Vertex Iterator
```// private/ALGVertexIterator.h
template <typename Vertex, typename Edge>
struct ALGVertexIterator final
{
using difference_type = std::ptrdiff_t;
using value_type = Vertex;
using reference = Vertex&;
using const_reference = const Vertex&;
using pointer = Vertex*;
using const_pointer = const Vertex*;
using iterator_category = std::bidirectional_iterator_tag;

ALGVertexIterator() = delete;
ALGVertexIterator( const ALGVertexIterator& ) = default;
ALGVertexIterator& operator= ( const ALGVertexIterator& ) = default;

ALGVertexIterator& operator++()
{
++iterator;
return *this;
}

ALGVertexIterator& operator--()
{
--iterator;
return *this;
}

bool operator==( const ALGVertexIterator& rhs ) const
{
return iterator == rhs.iterator;
}

bool operator!=( const ALGVertexIterator& rhs ) const
{
return !operator==( rhs );
}

const_reference operator*() const
{
return iterator->value;
}

const_pointer operator->() const
{
return *( iterator->value );
}

private:
explicit ALGVertexIterator( typename Graph::const_iterator iterator ) :
iterator{ iterator } {}

typename Graph::const_iterator iterator;
};
```
Edge Iterator
```// private/ALGEdgeIterator.h
template <typename VType, typename EType>
struct ALGEdgeIterator final
{
using difference_type = std::ptrdiff_t;
using value_type = EType;
using reference = EType & ;
using const_reference = const EType&;
using pointer = EType * ;
using const_pointer = const EType*;
using vertex_index = std::size_t;
using iterator_category = std::random_access_iterator_tag;

ALGEdgeIterator() = delete;
ALGEdgeIterator( const ALGEdgeIterator& ) = default;
ALGEdgeIterator& operator= ( const ALGEdgeIterator& ) = default;

ALGEdgeIterator& operator++()
{
++iterator;
return *this;
}

ALGEdgeIterator& operator--()
{
--iterator;
return *this;
}

ALGEdgeIterator& operator+=( difference_type n )
{
iterator.operator+=( n );
return *this;
}

ALGEdgeIterator operator+( difference_type n ) const
{
auto iter = iterator;
iter.operator+=( n );
return { idx, iter };
}

ALGEdgeIterator& operator-=( difference_type n )
{
iterator.operator-=( n );
return *this;
}

const_reference operator[]( difference_type n ) const
{
operator+=( n );
return operator*();
}

ALGEdgeIterator operator-( difference_type n ) const
{
auto iter = iterator;
iter.operator-=( n );
return { idx, iter };
}

bool operator==( const ALGEdgeIterator& rhs ) const
{
return idx == rhs.idx && iterator == rhs.iterator;
}

bool operator!=( const ALGEdgeIterator& rhs ) const
{
return !operator==( rhs );
}

bool operator<( const ALGEdgeIterator& rhs ) const
{
if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
return iterator.operator<( rhs.iterator );
}

bool operator<=( const ALGEdgeIterator& rhs ) const
{
if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
return iterator.operator<=( rhs.iterator );
}

bool operator>( const ALGEdgeIterator& rhs ) const
{
if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
return iterator.operator>( rhs.iterator );
}

bool operator>=( const ALGEdgeIterator& rhs ) const
{
if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
return iterator.operator>=( rhs.iterator );
}

const_reference operator*() const
{
return iterator->value;
}

const_pointer operator->() const
{
return &( iterator->value );
}

vertex_index index() const
{
return iterator->index;
}

private:
explicit ALGEdgeIterator( difference_type index, typename AdjacencyList::const_iterator iterator ) :
idx{ index }, iterator{ iterator } {}

difference_type idx;
};
```
Implementation
```// private/ALGImpl.h
template <typename V, typename E>
template <typename ... Args>
auto AdjacencyListGraph<V, E>::emplace( Args... args ) -> vertex_iterator
{
auto value{ args... };
return insert( std::move( value ) );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::insert( V value ) -> vertex_iterator
{
auto iter = std::find_if( graph.cbegin(), graph.cend(),
[&value] ( const auto& vertex ) { return vertex.value == value; } );

if ( iter == graph.cend() )
{
graph.emplace_back( Vertex( std::move( value ) ) );
iter = graph.cend();
--iter;
}

return ALGVertexIterator<V, E>( iter );
}

template <typename V, typename E>
template <typename ... Args>
auto AdjacencyListGraph<V, E>::emplaceEdge( const V& source, const V& destination, Args... args ) -> edge_iterator
{
auto value{ args... };
return insertEdge( source, destination, std::move( value ) );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::insertEdge( const V& source, const V& destination, E value ) -> edge_iterator
{
auto siter = indexOf( source );
auto diter = indexOf( destination );

Edge edge{ std::move( value ), std::distance( graph.begin(), diter ) };
auto& vector = siter->edges;
auto iter = std::find( vector.cbegin(), vector.cend(), edge );
if ( iter == vector.cend() )
{
if ( vector.empty() ) vector.reserve( 4 );
vector.emplace_back( std::move( edge ) );
iter = vector.cend();
--iter;
}

return ALGEdgeIterator<V, E>{ std::distance( graph.begin(), siter ), iter };
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::erase( const V& vertex )
{
erase( find( vertex ) );
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::erase( const vertex_iterator& iter )
{
if ( iter.iterator != graph.cend() ) eraseByIndex( std::distance( graph.cbegin(), iter.iterator ) );
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::eraseByIndex( const std::size_t index )
{
for ( auto& vertex: graph )
{
vertex.edges.erase(
std::remove_if( vertex.edges.begin(), vertex.edges.end(),
[index] ( const auto& edge ) { return index == edge.index; } ),
vertex.edges.end() );
}

auto iter = graph.cbegin();
graph.erase( iter );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::insertEdge( const V& source, EdgeValue&& tuple ) -> edge_iterator
{
return insertEdge( source, std::get<0>( tuple ), std::get<1>( tuple ) );
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::eraseEdge( const V& source, const V& destination, const E& edge )
{
auto siter = indexOf( source );
if ( siter == graph.end() ) return;
auto diter = indexOf( destination );
if ( diter == graph.end() ) return;

const Edge value{ edge, std::distance( graph.begin(), diter ) };
auto& vector = siter->edges;
auto liter = std::find( vector.cbegin(), vector.cend(), value );
if ( liter != vector.cend() ) vector.erase( liter );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::cbegin( const V& vertex ) const -> edge_iterator
{
auto iter = std::find( graph.begin(), graph.end(), vertex );
if ( iter == graph.end() ) throw std::out_of_range( "Vertex not in graph!" );
return ALGEdgeIterator<V, E>{ std::distance( graph.begin(), iter ), iter->edges.cbegin() };
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::cend( const V& vertex ) const -> edge_iterator
{
auto iter = std::find( graph.begin(), graph.end(), vertex );
if ( iter == graph.end() ) throw std::out_of_range( "Vertex not in graph!" );
return ALGEdgeIterator<V, E>{ std::distance( graph.begin(), iter ), iter->edges.cend() };
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::operator[]( const std::size_t index ) const -> reference_type
{
if ( index >= graph.size() ) throw std::out_of_range( "Index out of bounds!" );
return graph[index].value;
}

template <typename V, typename E>
bool AdjacencyListGraph<V, E>::exists( const V& vertex ) const
{
const auto iter = std::find_if( graph.cbegin(), graph.cend(),
[&vertex]( const auto& v ) { return v.value == vertex; } );
return iter != graph.cend();
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::find( const V& vertex ) const -> vertex_iterator
{
const auto iter = std::find_if( graph.cbegin(), graph.cend(),
[&vertex]( const auto& v ) { return v.value == vertex; } );
return ALGVertexIterator<V, E>{ iter };
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::find( const V& source, const V& destination ) const -> edge_iterator
{
const auto siter = std::find_if( graph.cbegin(), graph.cend(),
[&source]( const auto& v ) { return v.value == source; } );
if ( siter == graph.cend() ) return cend( source );

const auto diter = std::find_if( graph.cbegin(), graph.cend(),
[&destination]( const auto& v ) { return v.value == destination; } );
if ( diter == graph.cend() ) return cend( source );

const auto index = std::distance( graph.cbegin(), diter );
const auto iter = std::find_if( siter->edges.cbegin(), siter->edges.cend(),
[index] ( const auto& e ) { return e.index == index; } );
return ALGEdgeIterator<V, E>{ std::distance( graph.cbegin(), siter ), iter };
}

template <typename V, typename E>
template <typename Visitor>
void AdjacencyListGraph<V, E>::depthFirstSearch( const Visitor& visitor ) const
{
if ( empty() ) return;
Visited visited( size(), false );
for ( std::size_t i = 0; i < graph.size(); ++i )
{
if ( !visited[i] ) visitDfs( i, visited, visitor );
}
}

template <typename V, typename E>
template <typename Visitor>
{
if ( empty() ) return;
Visited visited( size(), false );

for ( std::size_t i = 0; i < graph.size(); ++i )
{
if ( !visited[i] ) visitBfs( i, visited, visitor );
}
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::indexOf( const V& vertex ) -> typename Graph::iterator
{
auto iter = std::find( graph.begin(), graph.end(), vertex );
if ( iter == graph.end() )
{
insert( vertex );
iter = graph.end();
--iter;
}

return iter;
}

template <typename V, typename E>
template <typename Visitor>
void AdjacencyListGraph<V, E>::visitDfs( const std::size_t index,
Visited& visited, const Visitor& visitor ) const
{
std::stack<std::size_t> stack;
stack.push( index );

while ( !stack.empty() )
{
std::size_t i = stack.top();
stack.pop();
const auto& node = graph[i];

if ( !visited[i] )
{
visited[i] = true;
visitor( node.value );
}

for ( auto iter = node.edges.cbegin(); iter != node.edges.cend(); ++iter )
{
if ( !visited[iter->index] ) stack.push( iter->index );
}
}
}

template<typename V, typename E>
template<typename Visitor>
void AdjacencyListGraph<V, E>::visitBfs( const std::size_t index,
Visited & visited, const Visitor & visitor ) const
{
std::queue<std::size_t> queue;
queue.push( 0 );

while ( !queue.empty() )
{
auto i = queue.front();
queue.pop();
const auto& node = graph[i];

visitor( node.value );
if ( !visited[i] ) visited[i] = true;

for ( auto iter = node.edges.cbegin(); iter != node.edges.cend(); ++iter )
{
if ( !visited[iter->index] )
{
visited[iter->index] = true;
queue.push( iter->index );
}
}
}
}
```
Test
```// AdjacencyListGraph.cpp
#include "catch.hpp"

#include <iostream>
#include <sstream>

namespace csc280::graph
{
struct NumberVisitor
{
void operator()( const uint32_t value ) const
{
ss << value << ", ";
}

std::string operator()() const { return ss.str(); }

private:
mutable std::stringstream ss;
};
}

SCENARIO( "Creating an adjacency list based graph of strings" )
{
GIVEN( "A graph of strings with a counter" )
{

WHEN( "Vertices are added to the graph" )
{
REQUIRE( graph.empty() );

auto iter = graph.emplace( "Chicago" );
REQUIRE( iter != graph.cend() );
REQUIRE( 1 == graph.size() );
REQUIRE_FALSE( graph.empty() );
REQUIRE( "Chicago" == graph[0] );
REQUIRE( "Chicago" == *iter );
REQUIRE( "Chicago" == *graph.find( "Chicago") );
REQUIRE( graph.exists( "Chicago" ) );
REQUIRE_FALSE( graph.exists( "New York" ) );

iter = graph.emplace( "Chicago" );
REQUIRE( iter != graph.cend() );
REQUIRE( 1 == graph.size() );

iter = graph.emplace( "New York" );
REQUIRE( iter != graph.cend() );
REQUIRE( 2 == graph.size() );
REQUIRE( "New York" == graph[1] );
REQUIRE( "New York" == *iter );
REQUIRE( "New York" == *graph.find( "New York") );
REQUIRE( graph.exists( "New York" ) );

THEN( "Edges may be added to the graph" )
{
auto eiter = graph.emplaceEdge( "Chicago", "New York", 900 );
REQUIRE( eiter != graph.cend( "Chicago" ) );
REQUIRE( 2 == graph.size() );
REQUIRE( 900 == *eiter );
REQUIRE( 1 == eiter.index() );

eiter = graph.emplaceEdge( "Chicago", "New York", 1000 );
REQUIRE( eiter != graph.cend( "Chicago" ) );
REQUIRE( 2 == graph.size() );

eiter = graph.emplaceEdge( "New York", "Chicago", 950 );
REQUIRE( eiter != graph.cend( "New York" ) );
REQUIRE( 2 == graph.size() );

graph.eraseEdge( "New York", "Chicago", 950 );
REQUIRE( graph.cbegin( "New York" ) == graph.cend( "New York" ) );

eiter = graph.insertEdge( "New York", std::make_tuple( "Chicago", 950 ) );
REQUIRE( eiter != graph.cend( "New York" ) );
REQUIRE( 2 == graph.size() );
}

AND_THEN( "New vertex and edge may be added to graph in single operation" )
{
graph.insertEdge( "Springfield", "Chicago", 60 );
REQUIRE( 3 == graph.size() );
graph.insertEdge( "Springfield", "New York", 1000 );
REQUIRE( 3 == graph.size() );
REQUIRE( graph.exists( "Springfield" ) );
REQUIRE( "Springfield" == *graph.find( "Springfield") );
}

AND_THEN( "Erasing vertex removes all dependent edges" )
{
graph.erase( "Chicago" );
REQUIRE_FALSE( graph.exists( "Chicago" ) );
const auto eiter = graph.find( "New York", "Chicago" );
REQUIRE( eiter == graph.cend( "New York" ) );
}
}
}
}

SCENARIO( "Depth first search traversal for adjacency list graph" )
{
GIVEN( "A graph of numbers" )
{
graph.insertEdge( 1, 0, false );
graph.insertEdge( 2, 1, false );
graph.insertEdge( 3, 4, false );
graph.insertEdge( 4, 0, false );

WHEN( "Traversing in depth first search mode" )
{
const auto visitor = csc280::graph::NumberVisitor{};
graph.depthFirstSearch( visitor );
REQUIRE( "1, 0, 2, 3, 4, " == visitor() );
}
}
}

{
GIVEN( "A graph of numbers" )
{
graph.insertEdge( 0, 1, false );
graph.insertEdge( 0, 2, false );
graph.insertEdge( 1, 2, false );
graph.insertEdge( 2, 0, false );
graph.insertEdge( 2, 3, false );
graph.insertEdge( 3, 3, false );

WHEN( "Traversing in depth first search mode" )
{
const auto visitor = csc280::graph::NumberVisitor{};