WordGraph.cpp

#include "WordGraph.hpp"

WordGraph::WordGraph()
{};

void WordGraph::set( const WordsT & words )
{
	if( words.size() > 0 )
	{
		addWord( *words.begin() );
		
		for(	auto it = std::next( words.begin() ), et = words.end();
			it != et;
			++it )
		{
			addWord( *it );
			connectWords( *std::prev( it ), *it );
		}
	}
};

bool WordGraph::has( const std::string & word )
{
	return wordVertexDescriptorMap.count( word ) > 0;
};

WordGraph::WordsT WordGraph::get( const std::string & word )
{
	if( wordVertexDescriptorMap.count( word ) != 0 )
	{
		const auto					nameMap		= boost::get( boost::vertex_name, graph );
		const VertexDescriptorsT	vertices	= getSubtreeVertices( wordVertexDescriptorMap[ word ] );
		WordsT						result;
		
		std::transform(	vertices.begin(),
					   vertices.end(),
					   std::inserter( result, result.begin() ),
					   [&]( const VertexDescriptorT & input ) { return nameMap[ input ]; } );
		
		return result;
	}
	
	return WordsT{};
};

void WordGraph::addWord( const std::string & word )
{
	if( wordVertexDescriptorMap.count( word ) == 0 )
	{
		const auto descriptor	= boost::add_vertex( graph );
		
		boost::put( boost::vertex_name_t{}, graph, descriptor, word );
		boost::put( boost::vertex_index_t{}, graph, descriptor, wordVertexDescriptorMap.size() );
		
		wordVertexDescriptorMap.insert( StringVertexDescriptorMapT::value_type{ word, descriptor } );
	}
};

void WordGraph::connectWords( const std::string & word1, const std::string & word2 )
{
	boost::add_edge( wordVertexDescriptorMap.at( word1 ), wordVertexDescriptorMap.at( word2 ), graph );
};

WordGraph::VertexDescriptorsT WordGraph::getSubtreeVertices( const VertexDescriptorT & root )
{
	using EdgeVisitorFuncT		= std::function<void(const VertexDescriptorT&)>;
	
	VertexDescriptorsT	result;
	EdgeVisitorFuncT	edgeVisitor;
	
	edgeVisitor					= [&]( const VertexDescriptorT & vertex )
	{
		GraphT::in_edge_iterator it;
		GraphT::in_edge_iterator et;
		
		for(	boost::tie( it, et ) = boost::in_edges( vertex, graph );
			it != et;
			++it
			)
		{
			VertexDescriptorT	source	= boost::source( *it, graph );
			VertexDescriptorT	target	= boost::target( *it, graph );
			
			if( source != root && result.count( source ) == 0 )
			{
				result.insert( source );
				edgeVisitor( source );
			}
			
			if( target != root && result.count( target ) == 0 )
			{
				result.insert( target );
				edgeVisitor( target );
			}
		}
	};
	
	edgeVisitor( root );
	
	return result;
};

WordGraph.hpp

#pragma once

#include <set>
#include <string>
#include <utility>
#include <functional>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/depth_first_search.hpp>

class WordGraph
{
	
public:
	
	using WordsT						= std::set<std::string>;
	
private:
	
	using IndexPropT					= boost::property<boost::vertex_index_t, std::size_t>;
	using VertexNamePropT				= boost::property<boost::vertex_name_t, std::string, IndexPropT>;
	using GraphT						= boost::adjacency_list<	boost::setS,
																	boost::setS,
																	boost::undirectedS,
																	VertexNamePropT
																	>;
	using VertexDescriptorT				= GraphT::vertex_descriptor;
	using VertexDescriptorsT			= std::set<VertexDescriptorT>;
	using StringVertexDescriptorMapT	= std::map<std::string, VertexDescriptorT>;
	
public:
	
	WordGraph();
	
public:
	
	void set( const WordsT & words );
	bool has( const std::string & word );
	WordsT get( const std::string & word );
	
private:
	
	void addWord( const std::string & word );
	void connectWords( const std::string & word1, const std::string & word2 );
	VertexDescriptorsT getSubtreeVertices( const VertexDescriptorT & root );
	
private:
	
	GraphT						graph;
	StringVertexDescriptorMapT	wordVertexDescriptorMap;
};