Examples of working with cycles and/or polyhierarchies?

[Richard Walker]

Hi, I'm investigating using Fancytree to replace an existing
implementation of a tree-based "browse" view that's being
used to display a variety of hierarchies; to be specific:
vocabularies (e.g., taxonomies and thesauruses) encoded using SKOS
(see, e.g., https://www.w3.org/TR/skos-primer/ for info about SKOS).

You can see an example of the existing implementation
of the "browse tree" in action at: https://vocabs.ands.org.au/anzsrc-for

I think I'd be fairly confident to go ahead and replace
the existing code with Fancytree.

However ... the key reason for considering replacing
the implementation in the first place is that the SKOS model
supports not only strict tree structures, but also
polyhierarchies (i.e., cases where a node has multiple
parents) and cycles, but the existing implementation
has no hope of coping with either of these situations.
Until now, we only had to "worry" about strictly tree-structured
vocabularies, but now we have users who want to display
polyhierarchies, and given that's the case, I want to
solve the problem of displaying cycles at the same time.

99% of the time, a vocabulary to display will be a strict tree,
which is why I don't want to switch to a library for
displaying graphs. It's the 1% of the time that there's
a polyhierarchy or cycle that means some sort
of special treatment will be required.

So I'm wondering if anyone has experience in using
Fancytree to display data with either polyhierarchies
or cycles, or otherwise has some pointers to help
me go about it.

I already noticed the "clones" extension and have
tried out the clones demo. This seems to address
the issue of _labelling_ nodes that are "the same",
but I couldn't see how two parts of the tree can
actually _be_ the same, i.e., how to specify a node and
its children in _one_ place, and "include" it by reference in
another place, _without_ also duplicating the entire
JSON fragment that describes it. It is quite possible
that I don't understand what the clones extension does.

I have already implemented a depth-first traversal
of the vocabulary, to identify the concepts that should go
at the top level, and that identifies
polyhierarchies and cycles. So I'd be grateful
for instructions/tips on how to structure the JSON
in the best way for Fancytree.

If I have to use lazy loading, that's fine, but I'd be
particularly interested to know of ways of avoiding
it (e.g., in the case in which there is otherwise not much
data to display, but there is a cycle).

Richard.
--
Richard Walker
Australian National Data Service (ANDS)
101 Liversidge Street
The Australian National University
Acton ACT 2601, Australia
E: Richard...@ands.org.au
T: +61 2 6125 0584
W: www.ands.org.au

[Christopher Lozinski]

On Oct 17, 2016, at 6:38 AM, Richard wrote:

Hi, I'm investigating using Fancytree to replace an existing
implementation of a tree-based "browse" view that's being
used to display a variety of hierarchies; 

Hi.  

I just released an implementation of fancytree for browsing a hierarchy. 

blogory.org <http://blogory.org/>

I am very very happy with fancytree.  

Your question about loops is a very interesting one.  I have not got there yet, but my understanding is as follows.   Look at the data model.  Clones are a good proxy model.  What do you want to have happen when someone clicks on a close.  Whatever you want to have happen, can happen.  It can jump to the original one if you want.   It can create a tree of clones, matching the original tree.

The problem is with the uplinks.  In a graph you can have multiple parents.   We will have to do something like a status node for each clone.  

Anyhow this is a very interesting problem.  Please keep us posed on what you decide to do and why. 

If you are interested in my code, I am happy to do a code walkthourgh with you. 

Maybe we need a new extension for this type of application.  

Warm Regards

Chris

[mar10]

I also used Fancytree in some use cases to provide a tree view into graph data.

Since a graph-node may have multiple parents, it will appear as multiple tree-nodes.

The tree requires unique tree-node IDs (node.key).

The clones extension mainly allows to add a new attribute node.refKey, so we can store the graph-node ID there.

ext-clones also provides methods to lookup nodes by this refKey, or to check if a node has clones.

How you handle this information is completely up to you.

Some thoughts:

Normally there is no 'master-clone', i.e. if a clone X appears under parents A and B, both instances are equal.

If X has children (Y), those children also appear twice.

You could also mark this nodes somehow, for example by adding a counter badge

ROOT
  A
    X(2)
      Y
  B
    X(2)
      Y

In this case the JSON could contain 2 X nodes (same node.refKey, but different node.key, or no node.key at all).

If you are concerned about data size, use lazy loading. A request 'send children for node X' would then be issued, when the user expands X.

If we have loops (i.e. Y has X as a child), you could stop rendering, i.e. don't offer to expand children, but show a hint

ROOT
  A
    X
      Y
        X (see other)
  B
    X'
      Y'
        X (see other)

Or you make the nodes expandable, so you user may follow indefinitely, but then you need to enable lazy loading for those nodes, since you cannot send infinite JSON data.

See also https://github.com/mar10/fancytree/wiki/ExtClones

[Richard Walker]

Thank you; this confirms what I had understood from the documentation and the demos.

My thinking would be that if I were to use lazy loading,
it would be _internally_: i.e., getting the new children by
finding them elsewhere in the tree, rather than by AJAX call.

So the initially-loaded tree would be "complete" in the sense
of containing one "canonical" instance of every possible node -- which
I can already do because I have the output of a depth-first
search. Lazy loading would expand children by copying
the children of that "canonical" node.

I might have to use lazy loading with AJAX in any case
for very large vocabularies, but many vocabularies are small
enough to justify me trying to avoid it.

I hesitate to use lazy loading of the whole tree,
because I also want to support filtering,
i.e. using the filter extension. If I understand correctly, filtering
of lazy-loaded trees is still on the "wish list".

[Christopher Lozinski]

On Oct 19, 2016, at 4:12 AM, Richard  wrote:

I hesitate to use lazy loading of the whole tree,

because I also want to support filtering,

i.e. using the filter extension. If I understand correctly, filtering

of lazy-loaded trees is still on the "wish list".

This is a topic that interests me hugely.  

Here is how I plan on eventually doing filtering on a 10K node tree. 

http://blogory.org/filtering-10k-nodes-with-fancytree

Warm Regards

Chris

[mar10]

My thinking would be that if I were to use lazy loading,

it would be _internally_: i.e., getting the new children by
finding them elsewhere in the tree, rather than by AJAX call. 

So the initially-loaded tree would be "complete" in the sense
of containing one "canonical" instance of every possible node -- which
I can already do because I have the output of a depth-first
search. Lazy loading would expand children by copying
the children of that "canonical" node.

Instead, you could either expand the 'compressed' JSON in the `postProcess` event, or you  copy the duplicate nodes in the `init` event.

Both ways will leave you with a complete tree, so ext-filter will work.

I might have to use lazy loading with AJAX in any case
for very large vocabularies, but many vocabularies are small
enough to justify me trying to avoid it.

Makes sense :)

 

If I understand correctly, filtering
of lazy-loaded trees is still on the "wish list".

 

That's true, but it doesn't mean that you can't implement it using the existing API.

(Any solution will require ajax calls and special logic in the backend.)

You could start an approach and open an issue for discussion, so we might add support for it. See also https://github.com/mar10/fancytree/wiki/SpecFilter

p.s.

If you like, could add your project to the gallery.

[mar10]

See my comment above: we could discuss this in a new issue and collect some ideas there

[Richard Walker]

I wrote:

Hi, I'm investigating using Fancytree to replace an existing
implementation of a tree-based "browse" view that's being
used to display a variety of hierarchies; to be specific:
vocabularies (e.g., taxonomies and thesauruses) encoded using SKOS
(see, e.g., https://www.w3.org/TR/skos-primer/ for info about SKOS).

You can see an example of the existing implementation
of the "browse tree" in action at: https://vocabs.ands.org.au/anzsrc-for

I think I'd be fairly confident to go ahead and replace
the existing code with Fancytree.

However ... the key reason for considering replacing
the implementation in the first place is that the SKOS model
supports not only strict tree structures, but also
polyhierarchies (i.e., cases where a node has multiple
parents) and cycles, but the existing implementation
has no hope of coping with either of these situations.
Until now, we only had to "worry" about strictly tree-structured
vocabularies, but now we have users who want to display
polyhierarchies, and given that's the case, I want to
solve the problem of displaying cycles at the same time.

I can now report that we now have a new implementation

of our browse "tree" using Fancytree, and we support

polyhierarchies (but not cycles).

The sample URL I already gave (https://vocabs.ands.org.au/anzsrc-for)

shows one straightforward example of the

re-implementation.

Here's a simple polyhierarchy:

https://vocabs.ands.org.au/viewById/124

To see how clones are handled, click on

"core drilling" to open child nodes, then hover

over "vibrocore" to bring up the tooltip.

Then click the link "Filter to all instances."

(Use the "X" button to reset filtering.)

And here's a simple example of

how we handle SKOS notations:

https://vocabs.ands.org.au/viewById/193

Click the "Show notations" toggle to show

notation values. And try the different values

of the "Sort by" dropdown. (The dropdown

and toggle settings may be adjusted

independently.)

Last, here's an example with many thousands

of nodes, where performance of filtering is

degraded, and we say so:

https://vocabs.ands.org.au/viewById/246

Here's the "back end" Java code to produce the

JSON describing the tree structure:

https://github.com/au-research/ANDS-ResearchVocabularies-Registry/blob/master/src/main/java/au/org/ands/vocabs/registry/workflow/provider/transform/ConceptTreeTransformProvider.java

And here's the "front end" JavaScript (AngularJS)

that uses Fancytree:

https://github.com/au-research/ANDS-ResearchVocabularies-Portal/blob/master/applications/portal/vocabs/assets/js/visualiseCtrl.js

("It's not pretty.")