weightedgraph.h File Reference

Defines some utility functions for (weighted) undirected graphs, trees and rooted trees. More...

#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>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <dai/util.h>
#include <dai/exceptions.h>
#include <dai/graph.h>

Go to the source code of this file.

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...

Namespaces
	dai
	Namespace for libDAI.

Functions
template<typename T >
RootedTree	dai::MinSpanningTree (const WeightedGraph< T > &G, bool usePrim)
	Constructs a minimum spanning tree from the (non-negatively) weighted graph G. More...
template<typename T >
RootedTree	dai::MaxSpanningTree (const WeightedGraph< T > &G, bool usePrim)
	Constructs a minimum spanning tree from the (non-negatively) weighted graph G. More...

Detailed Description

Defines some utility functions for (weighted) undirected graphs, trees and rooted trees.

Todo:

Improve general support for graphs and trees (in particular, a good tree implementation is needed).