• 1

• 11.1k
• 2
• 31
• 66

• 11.1k
• 2
• 31
• 66

(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_