New git HEAD version
[libdai.git] / src / weightedgraph.cpp
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
7
8
9 #include <algorithm>
10 #include <dai/weightedgraph.h>
11 #include <dai/util.h>
12 #include <dai/exceptions.h>
13
14
15 namespace dai {
16
17
18 using namespace std;
19
20
21 RootedTree::RootedTree( const GraphEL &T, size_t Root ) {
22 if( T.size() != 0 ) {
23 // Make a copy
24 GraphEL Gr = T;
25
26 // Nodes in the tree
27 set<size_t> nodes;
28
29 // Check whether the root is in the tree
30 bool valid = false;
31 for( GraphEL::iterator e = Gr.begin(); e != Gr.end() && !valid; e++ )
32 if( e->first == Root || e->second == Root )
33 valid = true;
34 if( !valid )
35 DAI_THROWE(RUNTIME_ERROR,"Graph does not contain specified root.");
36
37 // Start with the root
38 nodes.insert( Root );
39
40 // Keep adding edges until done
41 bool done = false;
42 while( !done ) {
43 bool changed = false;
44 for( GraphEL::iterator e = Gr.begin(); e != Gr.end(); ) {
45 bool e1_in_nodes = nodes.count( e->first );
46 bool e2_in_nodes = nodes.count( e->second );
47 if( e1_in_nodes && e2_in_nodes )
48 DAI_THROWE(RUNTIME_ERROR,"Graph is not acyclic.");
49 if( e1_in_nodes ) {
50 // Add directed edge, pointing away from the root
51 push_back( DEdge( e->first, e->second ) );
52 nodes.insert( e->second );
53 // Erase the edge
54 Gr.erase( e++ );
55 changed = true;
56 } else if( e2_in_nodes ) {
57 // Add directed edge, pointing away from the root
58 push_back( DEdge( e->second, e->first ) );
59 nodes.insert( e->first );
60 // Erase the edge
61 Gr.erase( e++ );
62 changed = true;
63 } else
64 e++;
65 }
66 if( Gr.empty() )
67 done = true;
68 if( !changed && !done )
69 DAI_THROWE(RUNTIME_ERROR,"Graph is not connected.");
70 }
71 }
72 }
73
74
75 } // end of namespace dai