1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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 */
12 #include <algorithm>
13 #include <dai/weightedgraph.h>
14 #include <dai/util.h>
15 #include <dai/exceptions.h>
18 namespace dai {
21 using namespace std;
24 RootedTree::RootedTree( const GraphEL &T, size_t Root ) {
25 if( T.size() != 0 ) {
26 // Make a copy
27 GraphEL Gr = T;
29 // Nodes in the tree
30 set<size_t> nodes;
32 // Check whether the root is in the tree
33 bool valid = false;
34 for( GraphEL::iterator e = Gr.begin(); e != Gr.end() && !valid; e++ )
35 if( e->first == Root || e->second == Root )
36 valid = true;
37 if( !valid )
38 DAI_THROWE(RUNTIME_ERROR,"Graph does not contain specified root.");
41 nodes.insert( Root );
43 // Keep adding edges until done
44 bool done = false;
45 while( !done ) {
46 bool changed = false;
47 for( GraphEL::iterator e = Gr.begin(); e != Gr.end(); ) {
48 bool e1_in_nodes = nodes.count( e->first );
49 bool e2_in_nodes = nodes.count( e->second );
50 if( e1_in_nodes && e2_in_nodes )
51 DAI_THROWE(RUNTIME_ERROR,"Graph is not acyclic.");
52 if( e1_in_nodes ) {
53 // Add directed edge, pointing away from the root
54 push_back( DEdge( e->first, e->second ) );
55 nodes.insert( e->second );
56 // Erase the edge
57 Gr.erase( e++ );
58 changed = true;
59 } else if( e2_in_nodes ) {
60 // Add directed edge, pointing away from the root
61 push_back( DEdge( e->second, e->first ) );
62 nodes.insert( e->first );
63 // Erase the edge
64 Gr.erase( e++ );
65 changed = true;
66 } else
67 e++;
68 }
69 if( Gr.empty() )
70 done = true;
71 if( !changed && !done )
72 DAI_THROWE(RUNTIME_ERROR,"Graph is not connected.");
73 }
74 }
75 }
78 GraphEL RandomDRegularGraph( size_t N, size_t d ) {
79 return GraphEL( createGraphRegular( N, d ) );
80 }
83 } // end of namespace dai