Partial adoption of contributions by Giuseppe:
[libdai.git] / include / dai / weightedgraph.h
1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
3
4 This file is part of libDAI.
5
6 libDAI is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 libDAI is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with libDAI; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21
22 #ifndef __defined_libdai_weightedgraph_h
23 #define __defined_libdai_weightedgraph_h
24
25
26 #include <vector>
27 #include <map>
28 #include <iostream>
29 #include <set>
30
31
32 namespace dai {
33
34
35 /// Directed edge
36 class DEdge {
37 public:
38 size_t n1, n2;
39
40 DEdge() {}
41 DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
42 bool operator==( const DEdge &x ) const {
43 return ((n1 == x.n1) && (n2 == x.n2));
44 }
45 bool operator!=( const DEdge &x ) const {
46 return !(*this == x);
47 }
48 bool operator<( const DEdge &x ) const {
49 return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
50 }
51 friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
52 os << "(" << e.n1 << "," << e.n2 << ")";
53 return os;
54 }
55 };
56
57
58 /// Undirected edge
59 class UEdge {
60 public:
61 size_t n1, n2;
62
63 UEdge() {}
64 UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
65 UEdge( const DEdge & e ) : n1(e.n1), n2(e.n2) {}
66 bool operator==( const UEdge &x ) {
67 return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
68 }
69 bool operator<( const UEdge &x ) const {
70 size_t s = n1, l = n2;
71 if( s > l )
72 std::swap( s, l );
73 size_t xs = x.n1, xl = x.n2;
74 if( xs > xl )
75 std::swap( xs, xl );
76 return( (s < xs) || ((s == xs) && (l < xl)) );
77 }
78 friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
79 if( e.n1 < e.n2 )
80 os << "{" << e.n1 << "," << e.n2 << "}";
81 else
82 os << "{" << e.n2 << "," << e.n1 << "}";
83 return os;
84 }
85 };
86
87
88 typedef std::vector<UEdge> UEdgeVec;
89 typedef std::vector<DEdge> DEdgeVec;
90 std::ostream & operator << (std::ostream & os, const DEdgeVec & rt);
91 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
92 typedef std::set<UEdge> Graph;
93
94
95 /// Use Prim's algorithm to construct a maximal spanning tree from the weighted graph Graph
96 template<typename T> DEdgeVec MaxSpanningTreePrim( const WeightedGraph<T> & Graph ) {
97 const long verbose = 0;
98
99 DEdgeVec result;
100 if( Graph.size() == 0 )
101 return result;
102 else {
103 // Make a copy
104 WeightedGraph<T> Gr = Graph;
105
106 // Nodes in the tree
107 std::set<size_t> treeV;
108
109 // Start with one node
110 treeV.insert( Gr.begin()->first.n1 );
111
112 // Perform Prim's algorithm
113 while( Gr.size() ) {
114 typename WeightedGraph<T>::iterator largest = Gr.end();
115
116 for( typename WeightedGraph<T>::iterator e = Gr.begin(); e != Gr.end(); ) {
117 if( verbose >= 1 )
118 std::cout << "considering edge " << e->first << "...";
119 bool e1_in_treeV = treeV.count( e->first.n1 );
120 bool e2_in_treeV = treeV.count( e->first.n2 );
121 if( e1_in_treeV && e2_in_treeV ) {
122 if( verbose >= 1 )
123 std::cout << "red";
124 Gr.erase( e++ ); // Nice trick!
125 } else if( e1_in_treeV || e2_in_treeV ) {
126 if( verbose >= 1 )
127 std::cout << e->second;
128 if( (largest == Gr.end()) || (e->second > largest->second) ) {
129 largest = e; // largest edge connected to the tree (until now)
130 if( verbose >= 1 )
131 std::cout << " and largest!";
132 }
133 e++;
134 } else {
135 if( verbose >= 1 )
136 std::cout << "out of reach";
137 e++;
138 }
139 if( verbose >= 1 )
140 std::cout << std::endl;
141 }
142
143 if( largest != Gr.end() ) {
144 if( verbose >= 1 )
145 std::cout << "largest = " << largest->first << std::endl;
146 // Add directed edge, pointing away from the root
147 if( treeV.count( largest->first.n1 ) ) {
148 result.push_back( DEdge( largest->first.n1, largest->first.n2 ) );
149 treeV.insert( largest->first.n2 );
150 } else {
151 result.push_back( DEdge( largest->first.n2, largest->first.n1 ) );
152 treeV.insert( largest->first.n1 );
153 }
154 Gr.erase( largest );
155 }
156 }
157
158 return result;
159 }
160 }
161
162
163 /// Calculate rooted tree from a tree T and a root
164 DEdgeVec GrowRootedTree( const Graph & T, size_t Root );
165
166
167 UEdgeVec RandomDRegularGraph( size_t N, size_t d );
168
169
170 } // end of namespace dai
171
172
173 #endif