Changed license from GPL v2+ to FreeBSD (aka BSD 2-clause) license
[libdai.git] / include / dai / weightedgraph.h
index 8f907db..edb1422 100644 (file)
@@ -1,17 +1,14 @@
 /*  This file is part of libDAI - http://www.libdai.org/
  *
 /*  This file is part of libDAI - http://www.libdai.org/
  *
- *  libDAI is licensed under the terms of the GNU General Public License version
- *  2, or (at your option) any later version. libDAI is distributed without any
- *  warranty. See the file COPYING for more details.
+ *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
  *
  *
- *  Copyright (C) 2006-2010  Joris Mooij  [joris dot mooij at libdai dot org]
- *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
+ *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
  */
 
 
 /** \file
  *  \brief Defines some utility functions for (weighted) undirected graphs, trees and rooted trees.
  */
 
 
 /** \file
  *  \brief Defines some utility functions for (weighted) undirected graphs, trees and rooted trees.
- *  \todo Improve general support for graphs and trees.
+ *  \todo Improve general support for graphs and trees (in particular, a good tree implementation is needed).
  */
 
 
  */
 
 
@@ -27,6 +24,7 @@
 #include <climits>   // Work-around for bug in boost graph library
 #include <dai/util.h>
 #include <dai/exceptions.h>
 #include <climits>   // Work-around for bug in boost graph library
 #include <dai/util.h>
 #include <dai/exceptions.h>
+#include <dai/graph.h>
 
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/prim_minimum_spanning_tree.hpp>
 
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/prim_minimum_spanning_tree.hpp>
@@ -40,34 +38,28 @@ namespace dai {
 class DEdge {
     public:
         /// First node index (source of edge)
 class DEdge {
     public:
         /// First node index (source of edge)
-        union {
-            size_t n1;
-            size_t first;   /// alias
-        };
+        size_t first;
 
         /// Second node index (target of edge)
 
         /// Second node index (target of edge)
-        union {
-            size_t n2;
-            size_t second;   /// alias
-        };
+        size_t second;
 
         /// Default constructor
 
         /// Default constructor
-        DEdge() : n1(0), n2(0) {}
+        DEdge() : first(0), second(0) {}
 
         /// Constructs a directed edge pointing from \a m1 to \a m2
 
         /// Constructs a directed edge pointing from \a m1 to \a m2
-        DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
+        DEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
 
         /// Tests for equality
 
         /// Tests for equality
-        bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
+        bool operator==( const DEdge &x ) const { return ((first == x.first) && (second == x.second)); }
 
         /// Smaller-than operator (performs lexicographical comparison)
         bool operator<( const DEdge &x ) const {
 
         /// Smaller-than operator (performs lexicographical comparison)
         bool operator<( const DEdge &x ) const {
-            return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
+            return( (first < x.first) || ((first == x.first) && (second < x.second)) );
         }
 
         /// Writes a directed edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
         }
 
         /// Writes a directed edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
-            os << "(" << e.n1 << "->" << e.n2 << ")";
+            os << "(" << e.first << "->" << e.second << ")";
             return os;
         }
 };
             return os;
         }
 };
@@ -77,47 +69,40 @@ class DEdge {
 class UEdge {
     public:
         /// First node index
 class UEdge {
     public:
         /// First node index
-        union {
-            size_t n1;
-            size_t first;   /// alias
-        };
+        size_t first;
+
         /// Second node index
         /// Second node index
-        union {
-            size_t n2;
-            size_t second;  /// alias
-        };
+        size_t second;
 
         /// Default constructor
 
         /// Default constructor
-        UEdge() : n1(0), n2(0) {}
+        UEdge() : first(0), second(0) {}
 
         /// Constructs an undirected edge between \a m1 and \a m2
 
         /// Constructs an undirected edge between \a m1 and \a m2
-        UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
+        UEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
 
         /// Construct from DEdge
 
         /// Construct from DEdge
-        UEdge( const DEdge &e ) : n1(e.n1), n2(e.n2) {}
+        UEdge( const DEdge &e ) : first(e.first), second(e.second) {}
 
         /// Tests for inequality (disregarding the ordering of the nodes)
         bool operator==( const UEdge &x ) {
 
         /// Tests for inequality (disregarding the ordering of the nodes)
         bool operator==( const UEdge &x ) {
-            return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
+            return ((first == x.first) && (second == x.second)) || ((first == x.second) && (second == x.first));
         }
 
         /// Smaller-than operator
         bool operator<( const UEdge &x ) const {
         }
 
         /// Smaller-than operator
         bool operator<( const UEdge &x ) const {
-            size_t s = n1, l = n2;
-            if( s > l )
-                std::swap( s, l );
-            size_t xs = x.n1, xl = x.n2;
-            if( xs > xl )
-                std::swap( xs, xl );
+            size_t s = std::min( first, second );
+            size_t l = std::max( first, second );
+            size_t xs = std::min( x.first, x.second );
+            size_t xl = std::max( x.first, x.second );
             return( (s < xs) || ((s == xs) && (l < xl)) );
         }
 
         /// Writes an undirected edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
             return( (s < xs) || ((s == xs) && (l < xl)) );
         }
 
         /// Writes an undirected edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
-            if( e.n1 < e.n2 )
-                os << "{" << e.n1 << "--" << e.n2 << "}";
+            if( e.first < e.second )
+                os << "{" << e.first << "--" << e.second << "}";
             else
             else
-                os << "{" << e.n2 << "--" << e.n1 << "}";
+                os << "{" << e.second << "--" << e.first << "}";
             return os;
         }
 };
             return os;
         }
 };
@@ -134,6 +119,14 @@ class GraphEL : public std::set<UEdge> {
         GraphEL( InputIterator begin, InputIterator end ) {
             insert( begin, end );
         }
         GraphEL( InputIterator begin, InputIterator end ) {
             insert( begin, end );
         }
+
+        /// Construct from GraphAL
+        GraphEL( const GraphAL& G ) {
+            for( size_t n1 = 0; n1 < G.nrNodes(); n1++ )
+                foreach( const Neighbor n2, G.nb(n1) )
+                    if( n1 < n2 )
+                        insert( UEdge( n1, n2 ) );
+        }
 };
 
 
 };
 
 
@@ -159,7 +152,8 @@ class RootedTree : public std::vector<DEdge> {
 
 
 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
 
 
 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
-/** \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E)))
+/** \param G Weighted graph that should have non-negative weights.
+ *  \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E))).
  *  \note Uses implementation from Boost Graph Library.
  *  \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
  */
  *  \note Uses implementation from Boost Graph Library.
  *  \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
  */
@@ -168,7 +162,7 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
     if( G.size() > 0 ) {
         using namespace boost;
         using namespace std;
     if( G.size() > 0 ) {
         using namespace boost;
         using namespace std;
-        typedef adjacency_list< listS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
+        typedef adjacency_list< vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
 
         set<size_t> nodes;
         vector<UEdge> edges;
 
         set<size_t> nodes;
         vector<UEdge> edges;
@@ -178,8 +172,8 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
         for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
             weights.push_back( e->second );
             edges.push_back( e->first );
         for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
             weights.push_back( e->second );
             edges.push_back( e->first );
-            nodes.insert( e->first.n1 );
-            nodes.insert( e->first.n2 );
+            nodes.insert( e->first.first );
+            nodes.insert( e->first.second );
         }
 
         size_t N = nodes.size();
         }
 
         size_t N = nodes.size();
@@ -192,7 +186,7 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
         GraphEL tree;
         if( usePrim ) {
             // Prim's algorithm
         GraphEL tree;
         if( usePrim ) {
             // Prim's algorithm
-            vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
+            vector< graph_traits< boostGraph >::vertex_descriptor > p(N);
             prim_minimum_spanning_tree( g, &(p[0]) );
 
             // Store tree edges in result
             prim_minimum_spanning_tree( g, &(p[0]) );
 
             // Store tree edges in result
@@ -202,13 +196,14 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
             }
         } else {
             // Kruskal's algorithm
             }
         } else {
             // Kruskal's algorithm
-            vector< graph_traits< boostGraph >::edge_descriptor > p( num_vertices(g) );
-            kruskal_minimum_spanning_tree( g, &(p[0]) );
+            vector< graph_traits< boostGraph >::edge_descriptor > t;
+            t.reserve(  N - 1 );
+            kruskal_minimum_spanning_tree( g, std::back_inserter(t) );
 
             // Store tree edges in result
 
             // Store tree edges in result
-            for( size_t i = 0; i != p.size(); i++ ) {
-                size_t v1 = source( p[i], g );
-                size_t v2 = target( p[i], g );
+            for( size_t i = 0; i != t.size(); i++ ) {
+                size_t v1 = source( t[i], g );
+                size_t v2 = target( t[i], g );
                 if( v1 != v2 )
                     tree.insert( UEdge( v1, v2 ) );
             }
                 if( v1 != v2 )
                     tree.insert( UEdge( v1, v2 ) );
             }
@@ -222,7 +217,8 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
 
 
 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
 
 
 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
-/** \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E)))
+/** \param G Weighted graph that should have non-negative weights.
+ *  \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E))).
  *  \note Uses implementation from Boost Graph Library.
  *  \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
  */
  *  \note Uses implementation from Boost Graph Library.
  *  \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
  */