1
$\begingroup$

I am having trouble transforming a maximum weighted spanning tree into a directed tree such that each node is allowed at most one parent node. Taken from page 141 Friedman et. al (1997), the outline of the algorithm is as follows:

1) Compute $I_{\hat{P}_{D}}(X_{i};X_{j})$ between each pair of variables $i \neq j$ where $$I_{\hat{P}_{D}}(X_{i};X_{j}) = \sum_{x,y} P(x,y) log\left(\frac{P(x,y)}{P(x)P(y)}\right)$$ 2) Build a complete undirected graph in which the vertices are the variables in $X$. Annotate the weight of an edge connecting $X_{i}$ to $X_{j}$ by $$I_{\hat{P}_{D}}(X_{i};X_{j})$$ 3) Build a maximum weighted spanning tree

4) Transform the resulting undirected tree to a directed one by choosing a root variable and setting the direction of all edges to be outward from it.

I have done steps 1-3, my trouble is on step 4. As of right now I have a set of names of continuous variables $X = \{x_{1}, x_{2}, \ldots, x_{n} \}$ and a $(from , to)$ matrix of the form $$ \begin{bmatrix} x_{1}&x_{10}\\x_{3}&x_{7}\\ \vdots& \vdots \end{bmatrix} $$ For example in the undirected maximum weighted tree, there's an edge going from $x_{1}$ to $x_{10}$ and so forth (note that this could have easily been read as an edge from $x_{10}$ to $x_{1}$ because as of right now the graph is undirected). I understand exactly what's going on I'm just unsure how to actually program it. If somebody could give me a pesduocode-type overview of how I should go about implementing step 4 it would be much appreciated. If someone could provide a link to a detailed implementation of this algorithm that would be fine as well. This is my first post on stackexchange, please forgive me if I have not provided enough information or posted this question in the incorrect location.

$\endgroup$
0
$\begingroup$

Given an undirected tree, pick any node (it doesn't matter which one). Call that the root. Now do depth-first search (or breadth-first search, or any other kind of search) starting from the root, traversing only the edges of the tree. That will visit all the vertices and edges. When you visit an edge for the first time, it will always be in an "outward" direction, so now you know how to orient it (how to set its direction).

Work through a small example if this is still unclear.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.