Fixed tabs and trailing whitespaces

[libdai.git] / include / dai / weightedgraph.h

diff --git a/include/dai/weightedgraph.h b/include/dai/weightedgraph.h
index cb9584f..bee160d 100644 (file)
--- a/include/dai/weightedgraph.h
+++ b/include/dai/weightedgraph.h
@@ -20,9 +20,11 @@
 */
 
 
-/// \file
-/// \brief Defines some utility functions for weighted graphs
-/// \todo Improve documentation
+/** \file
+ *  \brief Defines some utility functions for weighted graphs
+ *  \todo Improve documentation
+ *  \todo Improve general support for graphs and trees.
+ */
 
 
 #ifndef __defined_libdai_weightedgraph_h
@@ -35,6 +37,7 @@
 #include <set>
 #include <cassert>
 #include <limits>
+#include <climits>   // Work-around for bug in boost graph library
 
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/prim_minimum_spanning_tree.hpp>
@@ -48,7 +51,7 @@ class DEdge {
     public:
         size_t n1;  ///< First node index
         size_t n2;  ///< Second node index
-    
+
         /// Default constructor
         DEdge() {}
 
@@ -79,7 +82,7 @@ class UEdge {
     public:
         size_t  n1;  ///< First node index
         size_t  n2;  ///< Second node index
-    
+
         /// Default constructor
         UEdge() {}
 
@@ -169,7 +172,7 @@ template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G )
         // order, such that for all (i1, j1), (i2, j2) in result,
         // if j1 == i2 then (i1, j1) comes before (i2, j2) in result.
         // We do this by reordering the contents of result, effectively
-        // growing the tree starting at the root. At each step, 
+        // growing the tree starting at the root. At each step,
         // result[0..N-1] are the edges already added to the tree,
         // whereas the other elements of result still have to be added.
         // The elements of nodes are the vertices that still have to
@@ -201,17 +204,21 @@ template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G )
 /** Uses implementation in Boost Graph Library.
  */
 template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Graph ) {
-    T maxweight = Graph.begin()->second;
-    for( typename WeightedGraph<T>::const_iterator it = Graph.begin(); it != Graph.end(); it++ )
-        if( it->second > maxweight )
-            maxweight = it->second;
-    // make a copy of the graph
-    WeightedGraph<T> gr( Graph );
-    // invoke MinSpanningTreePrims with negative weights
-    // (which have to be shifted to satisfy positivity criterion)
-    for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
-        it->second = maxweight - it->second;
-    return MinSpanningTreePrims( gr );
+    if( Graph.size() == 0 )
+        return DEdgeVec();
+    else {
+        T maxweight = Graph.begin()->second;
+        for( typename WeightedGraph<T>::const_iterator it = Graph.begin(); it != Graph.end(); it++ )
+            if( it->second > maxweight )
+                maxweight = it->second;
+        // make a copy of the graph
+        WeightedGraph<T> gr( Graph );
+        // invoke MinSpanningTreePrims with negative weights
+        // (which have to be shifted to satisfy positivity criterion)
+        for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
+            it->second = maxweight - it->second;
+        return MinSpanningTreePrims( gr );
+    }
 }