Added GraphAL unit tests, fixed 6 bugs in GraphAL and added functionality:
[libdai.git] / src / weightedgraph.cpp
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 #include <algorithm>
13 #include <dai/weightedgraph.h>
14 #include <dai/util.h>
15 #include <dai/exceptions.h>
16
17
18 namespace dai {
19
20
21 using namespace std;
22
23
24 RootedTree::RootedTree( const GraphEL &T, size_t Root ) {
25 if( T.size() != 0 ) {
26 // Make a copy
27 GraphEL Gr = T;
28
29 // Nodes in the tree
30 set<size_t> nodes;
31
32 // Start with the root
33 nodes.insert( Root );
34
35 // Keep adding edges until done
36 while( !(Gr.empty()) )
37 for( GraphEL::iterator e = Gr.begin(); e != Gr.end(); ) {
38 bool e1_in_nodes = nodes.count( e->n1 );
39 bool e2_in_nodes = nodes.count( e->n2 );
40 DAI_ASSERT( !(e1_in_nodes && e2_in_nodes) );
41 if( e1_in_nodes ) {
42 // Add directed edge, pointing away from the root
43 push_back( DEdge( e->n1, e->n2 ) );
44 nodes.insert( e->n2 );
45 // Erase the edge
46 Gr.erase( e++ );
47 } else if( e2_in_nodes ) {
48 // Add directed edge, pointing away from the root
49 push_back( DEdge( e->n2, e->n1 ) );
50 nodes.insert( e->n1 );
51 // Erase the edge
52 Gr.erase( e++ );
53 } else
54 e++;
55 }
56 }
57 }
58
59
60 } // end of namespace dai