search

INCATools / obographviz

Customizable translation of OBO graphs to dot for visualization using graphviz and other tools
24 stars 6 forks source link

Visually nest equivalence cliques #5

Closed cmungall closed 5 years ago

cmungall commented 5 years ago

We want to be able to show pairs, triads etc of equivalent classes as being grouped together. This is for the output of algorithms like kboom that find most likely equivalence axioms, and for general visualization of mappings.

An example can be seen here: https://github.com/monarch-initiative/monarch-disease-ontology-RETIRED/issues/365#issue-249734436

I made a test file equivs.json

which currently renders as:

image

We would like all xs to be nested inside one box, all ys in one box, all zs in one box, based on:

https://github.com/cmungall/obographviz/blob/3ca5cd2404ac05a2d75189dd15171b8bc489c724/tests/equivs.json#L71-L89

The algorithm should be:

  1. find all equivalence cliques
    • e.g. using Tarjan's algorithm (convert each equivalence axiom to reciprocal DAG edges and find strongly connected components)
    • could also do this as a side-effect of reasoning, but that may be overkill here, but there may be other use cases for reasoning in this application
  2. for each clique, nest all members inside. This is probably easiest done by generating a new node for each clique, relating each clique member to the clique via an artificial cliqueMemberOf relation, and passing this in as a nested relation

@kltm - is the intent for bbop-graph to have algorithms such as Tarjan's implemented?

Or could just use https://www.npmjs.com/package/tarjan-graph

Or even the abandoned https://github.com/geneontology/noctua-reasoner

Or implement RETE/Arachne in node cc @balhoff

kltm commented 5 years ago

@cmungall The intent was for bbop-graph to be a general-purpose low-level graph library that people could use as the base for more complicated algorithms, e.g. bbop-graph-noctua. I believe that it is a fairly robust and fast JS implementation, but there may be better stuff out there at this point--there was not a lot when that all got started.