#include <vector>
#include <map>
#include <iostream>
#include <set>
#include <limits>
#include <climits>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
Go to the source code of this file.
Namespaces | |
namespace | dai |
Classes | |
class | dai::DEdge |
Represents a directed edge. More... | |
class | dai::UEdge |
Represents an undirected edge. More... | |
class | dai::GraphEL |
Represents an undirected graph, implemented as a std::set of undirected edges. More... | |
class | dai::WeightedGraph< T > |
Represents an undirected weighted graph, with weights of type T, implemented as a std::map mapping undirected edges to weights. More... | |
class | dai::RootedTree |
Represents a rooted tree, implemented as a vector of directed edges. More... | |
Typedefs | |
typedef GraphEL | dai::Graph |
Functions | |
template<typename T> | |
RootedTree | dai::MinSpanningTreePrims (const WeightedGraph< T > &G) |
Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G. | |
template<typename T> | |
RootedTree | dai::MaxSpanningTreePrims (const WeightedGraph< T > &G) |
Use Prim's algorithm to construct a maximal spanning tree from the (positively) weighted graph G. | |
GraphEL | dai::RandomDRegularGraph (size_t N, size_t d) |
Constructs a random undirected graph of N nodes, where each node has connectivity d. |