(This is a follow on to this question).
Having given an implementation for some of the graph structures, here is a portion of the algorithms that are defined to work over them:
graph_degree.hpp
/*! \file graph_degree.hpp
* \brief Algorithms relating to node degree.
*
* Defines core algorithms to investigate indegree and
* outdegrees concerning a given graph. This includes finding minimum,
* maximum, average, and the distribution over a whole graph. It also has
* algorithms specifically for finding disonnected nodes (defined as nodes
* with 0 indegree, that is, inaccessible nodes), and sink nodes (defined as
* nodes with 0 outdegree, that is, nodes one cannot leave).
*
* \addtogroup graph_algorithm
* @{
*/
#ifndef GRAPH_DEGREE_SGL_HPP_
#define GRAPH_DEGREE_SGL_HPP_
#include <functional>
#include <limits>
#include <map>
#include <utility>
#include <vector>
#include "boost/optional.hpp"
namespace simplegl
{
namespace graph
{
namespace
{
//Since max and min outdegree differ only by the comparator they use,
//and indegree and outdegree differ only by functon call,
//this is the core functionality abstracted out.
template <typename Graph, typename Compare, typename Selector>
boost::optional<
std::pair<typename Graph::node_type, typename Graph::size_type>
>
find_degree(const Graph& g, Compare comparator, Selector degree_type)
{
using node_type = typename Graph::node_type;
using optional_t =
boost::optional<
std::pair<typename Graph::node_type, typename Graph::size_type>
>;
if(g.empty()) {
return optional_t();
}
auto t = g.begin()->first;
auto current = degree_type(t);
auto degree = current;
auto begin = g.begin();
std::advance(begin, 1);
for(auto it = begin; it != g.end(); ++it) {
current = degree_type(it->first);
if(comparator(current, degree)) {
degree = current;
t = it->first;
}
}
return optional_t(std::make_pair(t, degree));
}
template <typename Graph>
using optional_t =
boost::optional<
std::pair<typename Graph::node_type, typename Graph::size_type>
>;
template <typename Graph, typename Compare>
optional_t<Graph> find_outdegree(const Graph& g, Compare comparator)
{
using node_type = typename Graph::node_type;
auto select_type = [&](const node_type& n) { return g.outdegree(n); };
return find_degree(g, comparator, select_type);
}
template <typename Graph, typename Compare>
optional_t<Graph> find_indegree(const Graph& g, Compare comparator)
{
using node_type = typename Graph::node_type;
auto select_type = [&](const node_type& n) { return g.indegree(n); };
return find_degree(g, comparator, select_type);
}
} // end unnamed namespace
/*! \brief Finds the node with maximum outdegree in the Graph g.
*
* \param g The graph to search over.
* \return A std::pair containing the node with maximum outdegree as the first member,
* and the degree count as the second member. For graphs with many nodes of equal
* maximum degree, it is implementation dependent as to which node is chosen.
*/
template <typename Graph>
optional_t<Graph> max_outdegree(const Graph& g)
{
using size_type = typename Graph::size_type;
return find_outdegree(g, std::greater<size_type>());
}
/*! \brief Finds the node with minimum outdegree in the Graph g.
*
* \param g The graph to search over.
* \return A std::pair containing the node with minimum outdegree as the first member,
* and the degree count as the second member. For graphs with many nodes of equal
* minimum degree, it is implementation dependent as to which node is chosen.
*/
template <typename Graph>
optional_t<Graph> min_outdegree(const Graph& g)
{
using size_type = typename Graph::size_type;
return find_outdegree(g, std::less<size_type>());
}
/*! \brief Finds the node with maximum indegree in the Graph g.
*
* \param g The graph to search over.
* \return A std::pair containing the node with maximum indegree as the first member,
* and the degree count as the second member. For graphs with many nodes of equal
* maximum degree, it is implementation dependent as to which node is chosen.
*/
template <typename Graph>
optional_t<Graph> max_indegree(const Graph& g)
{
using size_type = typename Graph::size_type;
return find_indegree(g, std::greater<size_type>());
}
/*! \brief Finds the node with minimum indegree in the Graph g.
*
* \param g The graph to search over.
* \return A std::pair containing the node with minimum indegree as the first member,
* and the degree count as the second member. For graphs with many nodes of equal
* minimum degree, it is implementation dependent as to which node is chosen.
*/
template <typename Graph>
optional_t<Graph> min_indegree(const Graph& g)
{
using size_type = typename Graph::size_type;
return find_indegree(g, std::less<size_type>());
}
/*! \brief Returns the average indegree of all nodes in the graph.
*
* \param g The graph to search over.
* \return A double, represending the average indegree of <B>g</B>.
*/
template <typename Graph>
double average_indegree(const Graph& g)
{
double start = 0;
typename Graph::size_type total_nodes = 0;
for(auto it = g.begin(); it != g.end(); ++it) {
start += g.indegree(it->first);
++total_nodes;
}
return start/total_nodes;
}
/*! \brief Returns the average outdegree of all nodes in the graph.
*
* \param g The graph to search over.
* \return A double, represending the average outdegree of <B>g</B>.
*/
template <typename Graph>
double average_outdegree(const Graph& g)
{
double start = 0;
typename Graph::size_type total_nodes = 0;
for(auto it = g.begin(); it != g.end(); ++it) {
start += g.indegree(it->first);
++total_nodes;
}
return start/total_nodes;
}
/*! \brief Returns the distribution of outdegrees over of all nodes in the graph.
*
* \param g The graph to search over.
* \return A std::map<typename Graph::size_type, typename Graph::size_type>
* containing pairs of type <I>{outdegree : count of nodes with given outdegree}</I>.
*/
template <typename Graph>
std::map<typename Graph::size_type, typename Graph::size_type>
outdegree_distribution(const Graph& g)
{
std::map<typename Graph::size_type, typename Graph::size_type> mp;
for(auto it = g.begin(); it != g.end(); ++it) {
mp[g.outdegree(it->first)] += 1;
}
return mp;
}
/*! \brief Returns the distribution of indegrees over of all nodes in the graph.
*
* \param g The graph to search over.
* \return A std::map<typename Graph::size_type, typename Graph::size_type>
* containing pairs of type <I>{indegree : count of nodes with given indegree}</I>.
*/
template <typename Graph>
std::map<typename Graph::size_type, typename Graph::size_type>
indegree_distribution(const Graph& g)
{
std::map<typename Graph::size_type, typename Graph::size_type> mp;
for(auto it = g.begin(); it != g.end(); ++it) {
mp[g.indegree(it->first)] += 1;
}
return mp;
}
/*! \brief Finds all disconnected nodes of the given graph, inserting them into ii.
*
* \param g The graph to search over.
* \param ii An input iterator into a container that will hold the nodes that are
found to be disconnected.
* \return The number of disconnected nodes found.
*/
template <typename Graph, typename Iterator>
std::size_t disconnected_nodes(const Graph& g, Iterator ii)
{
std::size_t num_disconnected = 0;
for(auto it = g.begin(); it != g.end(); ++it) {
if(g.indegree(it->first) == 0) {
ii = it->first;
++num_disconnected;
}
}
return num_disconnected;
}
/*! \brief Finds all sink nodes (nodes with outdegree 0) of the given graph,
* inserting them into ii.
*
* \param g The graph to search over.
* \param ii An input iterator into a container that will hold the nodes that are
found to be sinks.
* \return The number of sink nodes found.
*/
template <typename Graph, typename Iterator>
std::size_t sink_nodes(const Graph& g, Iterator ii)
{
std::size_t num_sink = 0;
for(auto it = g.begin(); it != g.end(); ++it) {
if(g.outdegree(it->first) == 0) {
ii = it->first;
++num_sink;
}
}
return num_sink;
}
} //end namespace graph
} //end namespace simplegl
#endif //GRAPH_DEGREE_SGL_HPP_
/*! @} End of Doxygen Group graph_algorithm */
graph_search.hpp
/*! \file graph_search.hpp
* \brief Algorithms for searching over graphs and finding connected components.
*
* Algorithms to investigate graph connectedness. Contains basic breadth-first
* and depth-first search functionality. In addition, contains tests for
* connectedness, finding connected components, and determining whether or
* not a graph contains a cycle from a given source node.
*
* \addtogroup graph_algorithm
* @{
*/
#ifndef GRAPH_SEARCH_SGL_HPP_
#define GRAPH_SEARCH_SGL_HPP_
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
namespace simplegl
{
namespace graph
{
namespace
{
//There are obvious similarities between breadth first and depth first
//searches; in fact, the algorithms are almost identical. To take advantage
//of this, we just need to wrap queue and stack with a begin() function
//which will return a reference to the first element in each. This is required
//because they use different member functions to access the first element,
//that is, front() vs top().
template <typename Type>
Type& begin(std::queue<Type>& q)
{
return q.front();
}
template <typename Type>
Type& begin(std::stack<Type>& s)
{
return s.top();
}
//Base search, which is used by both DFS and BFS
template <typename Graph, typename Iterator, typename Container>
void search_base
(const Graph& g, const typename Graph::node_type& root, Iterator ii, Container& cont)
{
using node_type = typename Graph::node_type;
using adj_iter = typename Graph::const_adjacency_iterator;
std::set<node_type> examined_nodes;
cont.push(root);
examined_nodes.insert(root);
ii = root;
while(!cont.empty()) {
node_type current_node = begin(cont);
cont.pop();
auto adj_nodes = g.adjacent_nodes(current_node);
for(auto it = adj_nodes.first; it != adj_nodes.second; ++it) {
if(examined_nodes.find(*it) == examined_nodes.end()) {
ii = *it;
cont.push(*it);
examined_nodes.insert(*it);
}
}
}
}
} // end unnamed namespace
/*! \brief A standard breadth first search.
*
* \param g A graph to search over.
* \param root The root node from which to begin the search.
* \param ii An insert iterator ii into a container, which will hold all reachable nodes
* from <B>root</B>.
*
*/
template <typename Graph, typename Iterator>
void
breadth_first_search(const Graph& g, const typename Graph::node_type& root, Iterator ii)
{
std::queue<typename Graph::node_type> q;
search_base(g, root, ii, q);
}
/*! \brief A standard depth first search.
*
* \param g A graph to search over.
* \param root The root node from which to begin the search.
* \param ii An insert iterator ii into a container, which will hold all reachable nodes
* from <B>root</B>.
*
*/
template <typename Graph, typename Iterator>
void depth_first_search(const Graph& g, const typename Graph::node_type& root, Iterator ii)
{
std::stack<typename Graph::node_type> s;
search_base(g, root, ii, s);
}
/*! \brief Tests two nodes to see if there is a path between them in the given graph.
*
* \param g A graph to search over.
* \param from The node from which to begin the search.
* \param to The node to find a path to.
*
* \return true if there is a path connecting (from, to), false otherwise.
*/
template <typename Graph>
bool is_connected(const Graph& g, const typename Graph::node_type& from,
const typename Graph::node_type& to)
{
//Pathological case, if they're the same node, then they must
//be connected.
using key_less = typename Graph::key_compare;
auto comp = key_less();
if(!(comp(from, to) && !(comp(to, from)))) {
return true;
}
//Otherwise, utilize a BFS.
using node_type = typename Graph::node_type;
using adj_iter = typename Graph::const_adjacency_iterator;
std::queue<node_type> to_examine;
std::set<node_type> examined_nodes;
to_examine.push(from);
examined_nodes.insert(from);
while(!to_examine.empty()) {
node_type current_node = to_examine.front();
to_examine.pop();
auto adj_nodes = g.adjacent_nodes(current_node);
for(auto it = adj_nodes.first; it != adj_nodes.second; ++it) {
if(examined_nodes.find(*it) == examined_nodes.end()) {
if(*it == to) {
return true;
}
to_examine.push(*it);
examined_nodes.insert(*it);
}
}
}
return false;
}
/*! \brief Tests to see if there is a (non-trivial) cyclic path from a given node.
*
* \param g A graph to search over.
* \param node The node from which to begin the search.
*
* \return true if there is a cyclic path from <B>node</B> to itself, false otherwise.
*/
template <typename Graph>
bool is_cyclical(const Graph& g, const typename Graph::node_type& node)
{
//Utilize a BFS to see if we can get from node back to node
using node_type = typename Graph::node_type;
using adj_iter = typename Graph::const_adjacency_iterator;
std::queue<node_type> to_examine;
std::set<node_type> examined_nodes;
to_examine.push(node);
while(!to_examine.empty()) {
node_type current_node = to_examine.front();
to_examine.pop();
auto adj_nodes = g.adjacent_nodes(current_node);
for(auto it = adj_nodes.first; it != adj_nodes.second; ++it) {
if(examined_nodes.find(*it) == examined_nodes.end()) {
if(*it == node) {
return true;
}
to_examine.push(*it);
examined_nodes.insert(*it);
}
}
}
return false;
}
/*! \brief Finds all nodes reachable from a given node. Equivalent to running a depth
* or bredth-first search on that node.
*
* \param g A graph to search over.
* \param node The node from which to begin the search.
*
* \return A std::set containing all the nodes reachable from <B>node</B>.
*/
template <typename Graph>
std::set<typename Graph::node_type>
connected_component(const Graph& g, const typename Graph::node_type& node)
{
using node_type = typename Graph::node_type;
std::set<node_type> connected;
std::insert_iterator<std::set<node_type>> ins_it(connected, connected.begin());
depth_first_search(g, node, ins_it);
return connected;
}
/*! \brief Finds all connected components of a given graph.
*
* Connected components partition the graph into equivalence classes based on
* reachability. That is, any node in a given connected component is reachable
* by any other node in the same connected component, and any node not in that same
* connected component is not reachable.
*
* \param g A graph to search over.
*
* \return A std::set of std::sets, each consisting of one connected component.
*/
template <typename Graph>
std::set<std::set<typename Graph::node_type>>
all_connected_components(const Graph& g)
{
using node_type = typename Graph::node_type;
std::set<std::set<node_type>> cc;
bool found = false;
for(auto it = g.begin(); it != g.end(); ++it) {
for(auto cc_subset = cc.begin(); cc_subset != cc.end(); ++cc_subset) {
if(cc_subset->find(it->first) != cc_subset->end()) {
found = true;
break;
}
}
if(!found) {
cc.insert(connected_component(g,it->first));
}
found = false;
}
return cc;
}
/*! \brief Determines if the graph is fully connected.
*
* A fully connected graph is one in which there is a path from any node
* to any other node.
*
* \param g A graph to search over.
*
* \return true if the graph is full connected, false otherwise.
*/
template <typename Graph>
bool is_fully_connected(const Graph& g)
{
auto s = all_connected_components(g);
return s.size() == 1;
}
} //end namespace graph
} //end namespace simplegl
#endif //GRAPH_SEARCH_SGL_HPP_
/*! @} End of Doxygen Group graph_algorithm */
topological_sort.hpp
#ifndef TOPOLOGICAL_SORT_SGL_HPP_
#define TOPOLOGICAL_SORT_SGL_HPP_
#include <deque>
#include <iostream>
#include "graph/graph_traits.hpp"
namespace simplegl
{
namespace graph
{
// Returns true iff the given graph can be topologically sorted,
// false otherwise.
template <typename Graph>
bool is_topologically_sortable(const Graph& g)
{
using node_type = typename Graph::node_type;
if(!is_directed<Graph>::value) { return false; }
Graph possible_dag(g);
std::deque<node_type> zero_degree;
for(auto it = possible_dag.begin(); it != possible_dag.end(); ++it) {
if(possible_dag.indegree(it->first) == 0) {
zero_degree.push_back(it->first);
}
}
while(!zero_degree.empty()) {
node_type& w = zero_degree.front();
auto adjacent = possible_dag.adjacent_nodes(w);
for(auto it = adjacent.first; it != adjacent.second; ++it) {
possible_dag.remove_edge(w, *it);
if(possible_dag.indegree(*it) == 0) {
zero_degree.push_back(*it);
}
}
zero_degree.pop_front();
}
return possible_dag.edge_size() == 0;
}
// Topologically sorts the given graph, if possible.
// Returns a std::deque containing the topological sorting, if
// it exists, or an empty deque otherwise.
template <typename Graph>
std::deque<typename Graph::node_type> topologically_sort(const Graph& g)
{
using node_type = typename Graph::node_type;
if(!is_directed<Graph>::value) { return std::deque<node_type>(); }
Graph possible_dag(g);
std::deque<node_type> zero_degree;
std::deque<node_type> sorted;
for(auto it = possible_dag.begin(); it != possible_dag.end(); ++it) {
if(possible_dag.indegree(it->first) == 0) {
zero_degree.push_back(it->first);
}
}
while(!zero_degree.empty()) {
node_type& w = zero_degree.front();
sorted.push_back(w);
auto adjacent = possible_dag.adjacent_nodes(w);
for(auto it = adjacent.first; it != adjacent.second; ++it) {
possible_dag.remove_edge(w, *it);
if(possible_dag.indegree(*it) == 0) {
zero_degree.push_back(*it);
}
}
zero_degree.pop_front();
}
if(possible_dag.edge_size() == 0) {
return sorted;
}
return std::deque<node_type>();
}
} // end namespace graph
} // end namespace simplegl
#endif // TOPOLOGICAL_SORT_SGL_HPP_
