[ENH] Add the ability to convert a DAG to an MAG

[aryan26roy]

Closes #95

Changes proposed in this pull request:

• function to that takes a DAG as an argument and outputs a valid MAG.

The algorithm is described in Zhang et al. 2008 on page number 1877.

Before submitting

• [ ] I've read and followed all steps in the Making a pull request section of the CONTRIBUTING docs.
• [ ] I've updated or added any relevant docstrings following the syntax described in the Writing docstrings section of the CONTRIBUTING docs.
• [ ] If this PR fixes a bug, I've added a test that will fail without my fix.
• [ ] If this PR adds a new feature, I've added tests that sufficiently cover my new functionality.

After submitting

• [ ] All GitHub Actions jobs for my pull request have passed.

[codecov[bot]]

Codecov Report

Merging #96 (6cf1edf) into main (2d6f1d3) will decrease coverage by 2.67%. Report is 9 commits behind head on main. The diff coverage is 60.22%.

@@            Coverage Diff             @@
##             main      #96      +/-   ##
==========================================
- Coverage   80.02%   77.35%   -2.67%     
==========================================
  Files          39       42       +3     
  Lines        2838     3413     +575     
  Branches      759      984     +225     
==========================================
+ Hits         2271     2640     +369     
- Misses        408      570     +162     
- Partials      159      203      +44     

Files	Coverage Δ
pywhy_graphs/classes/augmented.py	78.04% <100.00%> (+8.62%)	:arrow_up:
pywhy_graphs/functional/additive.py	83.33% <100.00%> (+6.86%)	:arrow_up:
pywhy_graphs/functional/linear.py	70.27% <90.00%> (+3.60%)	:arrow_up:
pywhy_graphs/viz/draw.py	76.00% <77.77%> (-0.93%)	:arrow_down:
pywhy_graphs/algorithms/multidomain.py	59.09% <22.22%> (+9.09%)	:arrow_up:
pywhy_graphs/functional/multidomain.py	11.88% <7.69%> (+0.30%)	:arrow_up:
pywhy_graphs/algorithms/generic.py	89.59% <92.16%> (+4.01%)	:arrow_up:
pywhy_graphs/functional/discrete.py	60.37% <60.37%> (ø)
pywhy_graphs/functional/sampling.py	0.00% <0.00%> (ø)
pywhy_graphs/functional/base.py	57.44% <57.44%> (ø)
... and 1 more

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

[adam2392]

Can you rebase this? The GH files changed tab is showing a lot of files for some reason.

[aryan26roy]

Sure.

[aryan26roy]

@adam2392 I think it's fine now.

[aryan26roy]

@adam2392 I think I figured out how to implement the algorithm. Can you look over the comments and tell me if that is correct or not?

[aryan26roy]

Hey @adam2392 , how do I get/generate valid DAG, MAG pairs? The implementation is complete and I need to test it now.

[adam2392]

Nice!

Perhaps peruse papers or come up with your own and draw them in tetrad

[aryan26roy]

@adam2392 I found a pair on the internet and just wanted to confirm, is this a correct DAG and MAG pair? H is a latent variable.

[adam2392]

Seems right walking thru each condition of the DAG to MAG algo.

[aryan26roy]

I don't see how the bidirected edge from E to R came about. Isn't E present in the ancestral graph of R U S ?

[adam2392]

Oh yeah sorry. It should be E -> R right?

See the definition on pg 1877 and the last paragraph on section 2.3.

Maybe it would help if you explicitly wrote the algorithm into the docstring too.

[aryan26roy]

@adam2392 If two nodes are adjacent in a graph, can we say an inducing path exists between the two of them given all the conditions for an inducing path are satisfied?

[adam2392]

I believe the definition states this is trivially true. IIRC

[aryan26roy]

Ah! I found a bug in my inducing paths implementation. I never check to see if either X or Y are members of L or S (which would immediately make it impossible for them to have an inducing path between them, according to what I understood.) Since this is a small thing to fix, can I just do it in this PR?

[aryan26roy]

@adam2392 in the MAG shouldn't A -> E be A - E? My implementation seems to be working correctly.

[adam2392]

What's the reasoning?

[aryan26roy]

What's the reasoning?

A is an ancestor of E union S and E is an ancestor of A union S. When both are present in the ancestor sets its a undirected edge, right?

[aryan26roy]

@adam2392 I added two more tests, one of them is from a zhang paper and the method worked on it on the first try! I think the implementation is correct. Is the number of tests ok?

[aryan26roy]

Using frozenset was a better solution!

[aryan26roy]

@adam2392 Incorporated all the suggestions you made.