|
wolffd@0
|
1
|
|
wolffd@0
|
2 function [eg] = dag_to_essential_graph(dag)
|
|
wolffd@0
|
3 cpdag = dag_to_cpdag(dag);
|
|
wolffd@0
|
4 eg = dag + dag .* (cpdag + cpdag');
|
|
wolffd@0
|
5
|
|
wolffd@0
|
6 return;
|
|
wolffd@0
|
7
|
|
wolffd@0
|
8
|
|
wolffd@0
|
9
|
|
wolffd@0
|
10
|
|
wolffd@0
|
11 % Coverts a DAG into Essential Graph where edges are coded by 2 and 3, 2 is
|
|
wolffd@0
|
12 % directed edge and 3 is bidirected edge and is at one (the same as the original DAG) of the two
|
|
wolffd@0
|
13 % symetrical places.
|
|
wolffd@0
|
14
|
|
wolffd@0
|
15 % Is implemented by the algorithm of Max Chickering in D.M.Chickering (1995).
|
|
wolffd@0
|
16 % A transformational characterization of equivalent Bayesian network structures.
|
|
wolffd@0
|
17 % In Proceedings of Eleventh Conference on Uncertainty in Artificial Intelligence, Montreal, QU,
|
|
wolffd@0
|
18 % pages 87-98. Morgan Kaufmann
|
|
wolffd@0
|
19 % http://research.microsoft.com/~dmax/publications/uai95.pdf
|
|
wolffd@0
|
20
|
|
wolffd@0
|
21 % Implemented by Tomas Kocka, AAU.
|
|
wolffd@0
|
22
|
|
wolffd@0
|
23 function [eg] = dag_to_essential_graph(dagx)
|
|
wolffd@0
|
24
|
|
wolffd@0
|
25 %print_dag(dagx); % Just checking input
|
|
wolffd@0
|
26
|
|
wolffd@0
|
27 order = topological_sort(dagx); % get the topological order of nodes and their number
|
|
wolffd@0
|
28
|
|
wolffd@0
|
29 % fprintf('the topological order is: %d',order);
|
|
wolffd@0
|
30 % fprintf('\n');
|
|
wolffd@0
|
31
|
|
wolffd@0
|
32 [nx,ny] = size(dagx); % gets the number of nodes, note that nx == ny
|
|
wolffd@0
|
33 [I,J] = find(dagx); % finds all nonzero elements in the adjacency matrix, i.e. arcs in the DAG - however we will overwrite it in a special order
|
|
wolffd@0
|
34 % we will sort the arcs from lowest possible y and highest possible x, arcs are x->y
|
|
wolffd@0
|
35 e = 1;
|
|
wolffd@0
|
36 for y = 1:ny
|
|
wolffd@0
|
37 for x = nx:-1:1
|
|
wolffd@0
|
38 %fprintf('x %d ',order(x)); fprintf('y %d ',order(y));
|
|
wolffd@0
|
39 if dagx(order(x),order(y)) == 1
|
|
wolffd@0
|
40 I(e) = order(x);
|
|
wolffd@0
|
41 J(e) = order(y);
|
|
wolffd@0
|
42 e = e + 1;
|
|
wolffd@0
|
43 %fprintf('x order %d',x);
|
|
wolffd@0
|
44 %fprintf('y order %d',y);
|
|
wolffd@0
|
45 %fprintf('\n');
|
|
wolffd@0
|
46 end
|
|
wolffd@0
|
47 end
|
|
wolffd@0
|
48 end
|
|
wolffd@0
|
49
|
|
wolffd@0
|
50
|
|
wolffd@0
|
51 % fprintf('the arcs are: %d',I);
|
|
wolffd@0
|
52 % fprintf('\n');
|
|
wolffd@0
|
53 % fprintf('the arcs are: %d',J);
|
|
wolffd@0
|
54 % fprintf('\n');
|
|
wolffd@0
|
55
|
|
wolffd@0
|
56
|
|
wolffd@0
|
57 % Now we have to decide which arcs are part of the essential graph and
|
|
wolffd@0
|
58 % which are undirected edges in the essential graph.
|
|
wolffd@0
|
59 % Undecided arc in the DAG are 1, directed in EG are 2 and undirected in EG
|
|
wolffd@0
|
60 % are 3.
|
|
wolffd@0
|
61
|
|
wolffd@0
|
62
|
|
wolffd@0
|
63 for e = 1:length(I)
|
|
wolffd@0
|
64 if dagx(I(e),J(e)) == 1
|
|
wolffd@0
|
65 cont = true;
|
|
wolffd@0
|
66 for w = 1:nx
|
|
wolffd@0
|
67 if dagx(w,I(e)) == 2
|
|
wolffd@0
|
68 if dagx(w,J(e)) ~= 0
|
|
wolffd@0
|
69 dagx(w,J(e)) = 2;
|
|
wolffd@0
|
70 else
|
|
wolffd@0
|
71 for ww = 1:nx
|
|
wolffd@0
|
72 if dagx(ww,J(e)) ~= 0
|
|
wolffd@0
|
73 dagx(ww,J(e)) = 2;
|
|
wolffd@0
|
74 end
|
|
wolffd@0
|
75 end % and now skip the rest and start with another arc from the list
|
|
wolffd@0
|
76 w = nx;
|
|
wolffd@0
|
77 cont = false;
|
|
wolffd@0
|
78 end
|
|
wolffd@0
|
79 end
|
|
wolffd@0
|
80 end
|
|
wolffd@0
|
81 if cont
|
|
wolffd@0
|
82 exists = false;
|
|
wolffd@0
|
83 for z = 1:nx
|
|
wolffd@0
|
84 %fprintf('test %d',dagx(z,J(e)));
|
|
wolffd@0
|
85 if dagx(z,J(e)) ~= 0 & z ~= I(e) & dagx(z,I(e)) == 0
|
|
wolffd@0
|
86 exists = true;
|
|
wolffd@0
|
87 for ww = 1:nx
|
|
wolffd@0
|
88 if dagx(ww,J(e)) == 1
|
|
wolffd@0
|
89 dagx(ww,J(e)) = 2;
|
|
wolffd@0
|
90 end
|
|
wolffd@0
|
91 end
|
|
wolffd@0
|
92 end
|
|
wolffd@0
|
93 end
|
|
wolffd@0
|
94 if ~ exists
|
|
wolffd@0
|
95 for ww = 1:nx
|
|
wolffd@0
|
96 if dagx(ww,J(e)) == 1
|
|
wolffd@0
|
97 dagx(ww,J(e)) = 3;
|
|
wolffd@0
|
98 end
|
|
wolffd@0
|
99 end
|
|
wolffd@0
|
100 end
|
|
wolffd@0
|
101 end
|
|
wolffd@0
|
102 end
|
|
wolffd@0
|
103 end
|
|
wolffd@0
|
104
|
|
wolffd@0
|
105 %print_dag(dagx); % Just checking output
|
|
wolffd@0
|
106
|
|
wolffd@0
|
107
|
|
wolffd@0
|
108
|
|
wolffd@0
|
109
|
|
wolffd@0
|
110
|
|
wolffd@0
|
111
|
|
wolffd@0
|
112
|
