From 8070dc963753142bb86c4ed698d91fd623ed28e7 Mon Sep 17 00:00:00 2001
From: ziejd2
Date: Thu, 28 Sep 2017 15:04:40 -0500
Subject: BNW using Octave instead of Matlab.

This version of BNW should perform the same as the original version. The only difference is that it uses Octave instead of Matlab when running BayesNet Toolbox during parameter learning.

I am calling this BNW_1.02. It can be accessed at:
compbio.uthsc.edu/BNW_1.02
---
 sourcecodes/bnt-master/graph/Old/dfs.m | 84 ++++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)
 create mode 100644 sourcecodes/bnt-master/graph/Old/dfs.m

(limited to 'sourcecodes/bnt-master/graph/Old/dfs.m')

diff --git a/sourcecodes/bnt-master/graph/Old/dfs.m b/sourcecodes/bnt-master/graph/Old/dfs.m
new file mode 100644
index 00000000..0c7f46ab
--- /dev/null
+++ b/sourcecodes/bnt-master/graph/Old/dfs.m
@@ -0,0 +1,84 @@
+function [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed)
+% DFS Perform a depth-first search of the graph starting from 'start'.
+% [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed)
+%
+% d(i) is the time at which node i is first discovered.
+% pre is a listing of the nodes in the order in which they are first encountered (opened).
+% post is a listing of the nodes in the order in which they are last encountered (closed).
+% A node is last encountered once we have explored all of its neighbors.
+% If the graph is directed, i's neighbors are its children.
+% If the graph is a tree, preorder is parents before children, and
+% postorder is children before parents.
+% For a DAG, topological order = reverse(postorder).
+% height(i) is the height (distance) of node i from the start.
+% 'cycle' is true iff a (directed) cycle is found.
+% pred(i) is the parent of i in the dfs tree rooted at start.
+% See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478.
+
+% We can detect undirected cycles by checking if we are about to visit a node n which we have
+% already visited. To detect *directed* cycles, we need to know if n has been closed or is still open.
+% For example (where arcs are directed down)
+%   1    2
+%   \   /
+%     3
+% Assume we visit 1, 3 and then 2 in order. The fact that a child of 2 (namely, 3) has
+% already been visited is okay, because 3 has been closed.
+% The algorithms in Aho, Hopcroft and Ullman, and Sedgewick, do not detect directed cycles.
+
+n = length(adj_mat);
+
+global white gray black
+white = 0; gray = 1; black = 2;
+
+color = white*ones(1,n);
+d = zeros(1,n);
+height = zeros(1,n);
+pred = zeros(1,n);
+pre = [];
+post = [];
+cycle = 0;
+global count
+count = 0;
+h = 0;
+[d, pre, post, height, cycle, color, pred] = ...
+    dfs2(adj_mat, start, directed, h, d, pre, post, height, cycle, color, pred);
+
+
+
+%%%%%%%%%%
+
+function [d, pre, post, height, cycle, color, pred] = ...
+    dfs2(adj_mat, i, directed, h, d, pre, post, height, cycle, color, pred)
+
+global count
+global white gray black
+
+color(i) = gray;
+count = count + 1;
+d(i) = count;
+pre = [pre i];
+height(i) = h;
+if directed
+  ns = children(adj_mat, i);
+else
+  ns = neighbors(adj_mat, i);
+end
+for j=1:length(ns)
+  n=ns(j);
+  if ~directed & n==pred(i) % don't go back up the edge you just came down
+    % continue
+  else
+    if color(n) == gray % going back to a non-closed vertex via a new edge
+      %fprintf(1, 'cycle from %d to %d\n', i, n);
+      cycle = 1;
+    end
+    if color(n) == white % not visited n before
+      pred(n)=i;
+      [d, pre, post, height, cycle, color, pred] = ...
+	  dfs2(adj_mat, n, directed, h+1, d, pre, post, height, cycle, color, pred);
+    end
+  end
+end
+color(i) = black;
+post = [post i];
+
-- 
cgit 1.4.1