Selection / Inspection Policies

[bryevdv]

cc @bokeh/dev

• ref: Add policy to highlight Linked Edges and Adjacent Nodes by selecting node. #11899

Summary

The above PR adds a new policy NodesAndLinkedEdgesAndAdjacentNodes. Under the current design, the extremely long name fits in perfectly, but its verboseness prompted me to think about some of the deficiencies of the current design that lead to awkward naming like that as the natural outcome.

More or less, the issue boils down to too much coupling. Specifically, it is not possible to specify policies for hits on nodes and edges separately. It's also not possible to parameterize the "distance" to include. These limitations prevent expressing different policies as compositions of simple building blocks, and mandates an entire new named Model any time any new combination is desired.

I'd like to propose a new design that affords a flexible mechanism for composing these policies. First some motivating examples:

Examples

clicked nodes and nothing else

graph_renderer.selection_policy = GraphSelectionPolicy(
    node_hit=[AdjacentNodes()]
)

nodes of clicked edges, and nothing else

graph_renderer.selection_policy = GraphSelectionPolicy(
    edge_hit=[AdjacentNodes()]
)

clicked edges and nothing else

graph_renderer.selection_policy = GraphSelectionPolicy(
    edge_hit=[AdjacentEdges()]
)

clicked edges and clicked nodes and nothing else

graph_renderer.selection_policy = GraphSelectionPolicy(
    node_hit=[AdjacentNodes()],
    edge_hit=[AdjacentEdges()]
)

clicked nodes, their edges, and nodes 1 hop away

graph_renderer.selection_policy = GraphSelectionPolicy(
    node_hit=[AdjacentNodes(hops=[0, 1]), AdjacentEdges()]
)

nodes that are 2 hops away from clicked nodes, and all edges leading to them

graph_renderer.selection_policy = GraphSelectionPolicy(
    node_hit=[AdjacentNodes(hops=[2]), AdjacentEdges(hops=[1, 2])]
)

clicked nodes and custom edges and nodes away

graph_renderer.selection_policy = GraphSelectionPolicy(
    node_hit=[AdjacentNodes(), CustomJSNodeSelection(...), CustomJSEdgeSelection(...)]
)

Design Sketch

class NodeSelectionPolicy:
    pass

class AdjacentNodes(NodeSelectionPolicy):
    """ Compute which nodes in a graph report selected/inspected after a hit test """

    hops = List(Int, default=[0], help="""
    What hop distances to include in selected results.

    For a node renderer hit-test, hop 0 nodes are the nodes that were clicked or tapped. 

    For an edge renderer hit-test, hop 0 nodes are the nodes that are on either end of an 
    edge that was clicked or tapped.  
    
    Hop 1 nodes are all the nodes nodes that are one edge traversal away from any hop 0 
    node (but not including  hop 0 nodes). Hop 2 nodes are all the nodes that are two edge 
    traversals away, etc. 
    """)

class EdgeSelectionPolicy:
    pass

class AdjacentEdges(EdgeSelectionPolicy):
    """ Compute which edges in a graph report selected/inspected after a hit test """

    hops = List(Int, default=[0], help="""
    What hop distances to include in selected results.

    For an edge renderer hit-test, hop 0 edges are the edges that were clicked or tapped. 

    For a node renderer hit-test, hop 0 edges are the edges that touch the node that was
    clicked or tapped.
    
    Hop 1 edges are all the nodes edges that are one node traversal away from any hop 0 
    edge (but not including  hop 0 edges). Hop 2 edges are all the nodes that are two node 
    traversals away, etc. 
    """)

class GraphSelectionPolicy:
    """ Specify how selections occur when nodes or edges are 'hit' """

    node_hit = List[Instance(NodeSelectionPolicy), help="""
    A series of node selection policies to apply when a node or edge is clicked or tapped. 
    Each policy is applied in order and the computed results of each are unioned together. 
    """)

    edge_hit = List[Instance(EdgeSelectionPolicy), help="""
    A series of edge selection policies to apply when a node or edge is clicked or tapped. 
    Each policy is applied in order and the computed results of each are unioned together. 
    """)

Migration

Existing policies e.g. NodesAndLinkedEdges should become functions that return an appropriately configured GraphSelectionPolicy and also issues a deprecation warning. Suggest that any recent policies added only to branch-3.0 before release simply be removed altogether.

Questions

Is there any reason to have a separate but very similar GraphInspectionPolicy? If these models simply compute the lists of indices, and don't actually perform selection or inspection (i.e. they are used by something else that actually does that step). Then I don't think any distinction is necessary. But in that case is there any better (more generic) terminology to indicate that the policies can apply equally to selections or inspections?

Also/alternatively: should these rebrand as "hit testing policy" or something? There is already a separate, different notion of Selection.selection_policy that is for controlling how selections across different renderers are combined together, and that is completely unrelated to this.

What is the best way to expose "CustomJS" policies? The user will need to provide JS code for what to do when nodes are hit an/or when edges are hit.

How onerous will cycle detection be?

[g-parki]

This is nice! Thanks for preparing this @bryevdv

Is there any reason to have a separate but very similar GraphInspectionPolicy?

My vote's 👎 since they're so similar. I think the benefit of combining them outweighs the burden of maintaining both + trying to convey the nuance in the docs.

any better (more generic) terminology to indicate that the policies can apply equally to selections or inspections?

I don't think GraphSelectionPolicy is bad. If I were a fresh user I wouldn't think twice about it.
At the expense of clashing with existing model names, GraphHitTestPolicy or GraphHitTest may be more neutral while getting the message across.
I considered GraphInteractionPolicy, but I think that's too generic to be useful.

[bryevdv]

My vote's 👎 since they're so similar. I think the benefit of combining them outweighs the burden of maintaining both + trying to convey the nuance in the docs.

It's definitely also my preference, but I would also like to keep deprecated compatibility with the existing policies rather that drop them immediately, so it will take a little more actual investigation / experimentation to see if those are reconcilable goals (an if not, which to compromise).

Re: naming, perhaps it would be instructive to consider the most verbose, descriptive name possible, to think about other synonyms or directions to trim. I guess truly this is the "Policy for Extending Selections for Hit Tests on Graph Renderers". I think the thing that clicks there for me is that these are for taking an initial selection and extending/modifying them. So what about ExtendedGraphSelection ?

[bryevdv]

cc @p-himik would love your thoughts if you have time for a quick look

[bryevdv]

I guess most of the answer above comes down to e.g. adding OnlyNodes() or OnlyEdges() to the filters. I guess that leaves users open the possibility to do non-sensical things like add both.

I'm more unsure about e.g. FilterEdgesByAttr In my mind it would be common to want to "look at all nodes a distance of 10 away" but then this policy needs to filter nodes, but according to edges Would you propose a separate FilterNodesbByEdgeAttr ? Or have FilterEdgesByAttr also implicitly cull nodes? That seems like it might become hard to reason about.

[bryevdv]

In any event I will try to reformulate a proposal that enumerates common cases, with this different filtering POV in mind.

[p-himik]

that leaves users open the possibility to do non-sensical things like add both.

Yep, an intersection of all nodes and all edges is an empty set. Nothing would be highlighted. Or it would be an error - depends on implementation.

In my mind it would be common to want to "look at all nodes a distance of 10 away" but then this policy needs to filter nodes, but according to edges

I'm afraid I don't follow. Looking at nodes 10 hops away is just expanding the working set 10 times, or by 10 hops - there's no filtering involved.
FilterEdgesByAttr removes edges and all connected nodes. In other words, if filters out paths in graph - my whole approach is about paths, not nodes or edges specifically. It makes things with divergent paths like "selected red edges but forget about their nodes and select nodes connected by blue edges, but forget the blue edges themselves" impossible without either inventing some nasty classes specifically for that or turning that flat path-expanding-and-filtering list into a proper tree. Which is not that bad - it's just nested lists - but it might get confusing.

[bryevdv]

I'm afraid I don't follow. Looking at nodes 10 hops away is just expanding the working set 10 times, or by 10 hops - there's no filtering involved.

Sorry, by distance I did not mean hops, I meant a path distance according so some edge attr that provides "distance". In any case like I said I will try to come up with ~10 scenarios that seems like they would be the most common, and hopefully we can start from there and see how things would be spelled explicitly.

[p-himik]

Ah, that is handled by my second code block in the initial proposal, with FilterNodesByPathLength. Seems like I forgot to add a number there, so it should be FilterNodesByPathLength(attr='weight', value=10, op='le').

Indeed, looking forward!