adding nodeID functionality to support various needs

[paciorek]

I've been brainstorming some new functionality to support getConditionallyIndependentSets and setupMargNodes.

Basically, we need unique IDs for the nodes in a nodeRange in order to be able to collect them into conditionally independent (CI) sets and for handling "touching". At the same time we'd like to avoid an explosion of unique IDs, one per node, as much as possible.

Note that at present there is no notion of nodeIDs in nimbleModel. There are unique IDs, but they are at the calcRule level for use in walking the graph to determine calculation sortID. Every calcRule (which can relate to many (or all) nodes from a given declaration) has the same ID. Hence we can't just use them with the current nimbleGraph functionality (unlike my original lazy/punting proposal about getConditionallyIndependentSets last week).

I think it makes most sense to have unique nodeIDs at the declaration level. In part this is because a nodeRange knows its declaration, so from any nodeRange we could go back to the declaration and get the nodeIDs. So here are the pieces:

• declRuleClass would have a function for determining nodeIDs from a nodeRange - this would involve using the originalIndexingRules to get the indices and then converting those to unique IDs, 1,...,n. E.g., for(i in 3:5); for(j in 1:2) y[i,j+2] would have y[4,3] have indices 4,1 and that would correspond with nodeID of (4-3)*2+1=3 via straightforward flattening (and adjusting for indexing not starting at 1). We'd also need to deal with for(i in 2,3,5) as a special case.
• declRuleClass would have a new reverseOriginalIndexingRule that maps from indices to nodeRanges. I think this just involves reversing the order of the LHS and RHS from when we create and originalIndexingRule. Using that plus the reverse of the bullet item above allows one to go from IDs to indices to nodeRanges.
• we could potentially cache the nodeIDs for a given nodeRange in the nodeRange so we don't need to continually look them up. And provide a method to clear them out to reduce memory use. Down the road we could consider compact representation of these using simple 1-d varRanges (or just an indexRange), plus possibly the ability to smartly combine these (e.g, 1:5 + 6:10 = 1:10 and 1,2,4 + 3 = 1:4)
• the declRules would also have a boolean vector touched corresponding to the nodeIDs. During getConditionallyIndepSets we would instantiate this and modify it by indexing into it using the nodeIDs, presumably by writing a new method. We would have methods to reset "touched" and to set to NULL.
• to handle intersect and setDiff, as needed for getConditionallyIndependentSets and setupMargNodes, we make use of the nodeIDs, but note that we only need to do any work when two nodeRanges share a declaration. These would be used a lot in the setup steps for those two methods when we are sorting out the various sets of nodes.
• getConditionallyIndependentSets would proceed (roughly) as follows, relying on the new functionality as well as current graph traversal in getParents and getDependents
  • For a given untouched candidate node, find dependents, convert from varRanges to nodeRanges, set to touched in declRule if stoch and get nodeIDs and add them to the current set.
  • For each dependent, if not already touched, find parents and dependents and convert from varRanges to nodeRanges.
  • Intersect with current nodeIDs and only follow those not already in the set nor touched. In some cases this will involve fracturing a nodeRange which we can do using the nodeIDs and then converting back to nodeRange.
  • Continue recursing.
  • This would be in R so could be slow if there are a lot of CI sets, but hopefully fast enough to leave efficiency work for down the road and recognizing that if one has a ton of CI sets, setting up Laplace would be slow and potentially as much of a bottleneck as this.
  • For sequential dependence cases with contiguous sortIDs, I think we could short-cut having to iterate through all the nodes. For interwoven cases with two variables/declarations, things would be slow, as is the case in issue tricky cases and inefficient instructionList setup for calculate with time series/state space structures #25 .

I think this would also:

1. readily allow deduplication in sets of nodeRanges (see issue to discuss: duplicated nodeRanges with getNodes and calculate #36) and
2. (with a bit more work) allowing omit in getParents and getDependencies (which is not currently provided in nimbleModel, unlike in nimble; see issue getParents and getDependencies do not have an omit argument #39).

@perrydv I think I have a good path forward, though it would be good to touch base soon. One specific issue is that in what I'm imagining, it wouldn't handle using a split node in omit in getConditionallyIndependentSets. It's hard for me to see the use case for that, and I think that in all cases if a user needed to do it, they could manually insert a node that represents the split node and then use that in omit as an actual node. But let's discuss before I go too far down the path.

[paciorek]

One other note: we might be able to use this for back compatibility with `returnType='ids'. However we'd need to either use characters and append the decl ID in some fashion, e.g., "1.35" for decl 1, ID 35, or create unique IDs across all declarations. This would be easy but could be confusing to have to separate IDs. I'm not sure what use cases there are for this, so not sure what would be best.

We could conceivably have the IDs within a declaration be unique across declarations, but that prevents simple lookup into touched; which instead would involve dealing with subtracting an offset from the ID.

At the moment, my thought is that this seems simple enough that we could add the functionality in the future if need arose.