1

I'm developing a node/edges graph using the d3 JavaScript library (the language isn't that important—this is a conceptual/approach question). My graph has the ability for nodes to be dynamically filtered on the basis of various criteria, including type and specific attributes. As an example, let's assume I have the following objects in my data set:

nodes = [
  {"type": "fruit", "name": "banana", "length": 5},
  {"type": "fruit", "name": "banana", "length": 6},
  {"type": "fruit", "name": "banana", "length": 4},
  {"type": "fruit", "name": "apple", "length": 3},
  {"type": "fruit", "name": "apple", "length": 2},
  {"type": "fruit", "name": "cherry", "length": 1},
  {"type": "animal", "species": "monkey", "name": "kong", "eats": "banana"},
  {"type": "animal", "species": "monkey", "name": "george", "eats": "banana"},
  {"type": "animal", "species": "rabbit", "name": "harvey", "eats": "apple"},
  {"type": "animal", "species": "bird", "name": "bluebird", "eats": "cherry"},
  {"type": "location", "name": "zoo", "residents": ["monkey", "rabbit", "bird"]},
  {"type": "location", "name": "tree", "residents": ["apple", "banana", "cherry"]}
]

Links (edges) are dynamically generated for the items based on their relationships. The following filters are available:

  • Type[fruit, animal, location]
  • Name — filters based on whether name string contains specific text
  • Length — not all types have this property, but those that do can be filtered by length
  • Species — not all types have this property, but those that do can be filtered by species

Assume also that a property has been dynamically added to every node indicating whether or not it is currently filtered out (i.e. a Boolean value). By default the value is false (all nodes are visible).

Let's suppose a user applies the following filters:

  1. The user applies a filter to the data to show only nodes where type == "fruit" (all other nodes' filter values are now set to true except for those of type "fruit")

  2. The user then applies a filter to the data to show only nodes where name does not contain the character 'a' (only "cherry" is currently unfiltered, all other nodes' filter values are now set to true)

  3. The user removes the filter applied in #1 (now only nodes whose name value does not contain the character 'a' should be showing)

How do I deal with multiple filters to ensure they don't "undo" one another, yet not have logical issues if they are applied (and unapplied) in different orders?

In my current situation, step #3 will result in all nodes being shown again, but this is not right.

Is there a logical way to check before applying filters (e.g. if (node.filtered) {// only apply new filters to unfiltered data}, or must the filter from #2 must be "re-applied" to the data set after removing the filter from #1 (I'm thinking the latter). Do I need to store all of the filters applied in an ordered list (or other data structure) and then reapply them in order any time a filter is removed (unapplied)? Or am I over-complicating this?

3

If I understand your system, filters are conjunctive, which is to say that they AND together. The AND operation is commutative, so the order the filters are applied does not matter. You should always be able to capture filters that at the ground level stand alone. (However, you may choose to express or capture filters that cannot stand alone and are dependent on other filters -- if that's the case things are more complicated and you will have to accommodate.)

If you are caching what is filtered based on the current conjunction of filters, then when you add a new filter you don't need to check the nodes that are already filtered out, since no matter the order of filters, and even if you re-filter, those nodes already removed will be removed again. Thus, given your caching of current filters, you can perform an optimization on the filtering and only apply the new filter to the remaining unfiltered items.

However, given only the current conjunction of filters and the (cached) state of filtration for each node re: the current total conjuction, when you remove a filter, you will have to reverse that logic and apply removal filtration to all currently filtered nodes, though you can leave currently unfiltered nodes alone. However, since you don't know why an item is in the filtered (removed) set, you will have to apply all the filters to each filtered nodes to redetermine. (One advantage is for the user, of course, that filters can be removed in any order.)

If you had a count of how many times an item was filtered out, you could reason that one less filter for that item should decrement the filter count, and then that at a filter count of zero the node should be unfiltered. However, you would also have to maintain that filter count more broadly than described above (apply the count to all items not just the currently unfiltered items).

Note that I'm describing your filter state as a cache, as this is copied state that is derived from existing other state, basically the definition of caching.

When we do caching, the idea is that hopefully it helps us, but it does take work to maintain the cache, and, what we cache is not always useful for all scenarios. However, by definition of derived state, you can always throw away a cache and regenerate from scratch.

Caching is generally considered an optimization, which we should not take on too lightly. First, it takes work to maintain the cache, and when our code is under development, this is sometimes an unnecessary maintenance burden. Second, we don't know for a fact that the caching optimization, even if 100% correct, makes things slower or faster. This is why best practise says we don't apply optimizations that increase code complexity without measurement justification.

  • Thanks, this solved it. It was tricky because technically it was a map() problem, not a true filter problem, because I change the opacity of my elements to filter them "out", but they actually remain in the data set. I ended up dynamically building a list of conjunctive (AND) conditions with "pointers" to functions that returned Boolean values as to whether or not a node met the filter criteria. I'm taking a minor performance hit because I reset and reapply all filters any time a filter value is changed (binded to onchange event) and don't want to track the toggled state -- but it works! – Dan Sep 22 '16 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.