include/dai/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>

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.


Detailed Description

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

Todo:
Improve general support for graphs and trees.

Generated on Thu Feb 11 12:26:00 2010 for libDAI by  doxygen 1.5.5