Consistent representation of trees through "parent vectors"

[szhorvat]

There are several functions in igraph which effectively return a tree through a "parent vector", sometimes called "predecessors" or "father". We should make sure that functions that use this format are consistent with each other. We should also use a consistent and neutral naming (such as "parent").

Here is an incomplete list of relevant functions:

• igraph_bfs, igraph_bfs_simple, igraph_dfs. @ntamas proposed to overhaul the interface of these functions.
• igraph_get_shortest_paths, igraph_get_shortest_paths_dijkstra, igraph_get_shortest_paths_bellman_ford return the shortest path tree in a similar format. (fixed in Use parent vector of #1880 for get_shortest_paths #2070 and 9fddebf)
• igraph_dominator_tree returns a tree like this as well
• igraph_cohesive_blocks can return the block tree this way
• There is a proposal in Create tree or forest from list of parents #1840 for a function to create a tree from this format.
• Any other functions that are not yet mentioned? Please edit the issue and complete this list.

There are small differences in the representation:

• DFS/BFS functions used NaN to represent the lack of a parent, but this was switched to -1 after the integer transition
• Shortest path functions use -1 for unvisited vertices, but they use the same index as the vertex itself for the root vertex. According to the current proposal in Create tree or forest from list of parents #1840 such a vector would be rejected by the tree creation function. edit: shortest path functions now confirm to this proposal.

We need to make everything consistent, and since this is API-breaking, ideally do this before 0.10.

Other related issues to consider:

• Do we want other functions to optionally return data in the same format? How about spanning tree functions—is it useful at all for them?
• Do we want to introduce a format which can encode not just a spanning tree, but a complete edge traversal? This relates to modifying DFS/BFS which currently just record nodes, but not the edges. For some applications, the edges are necessary (e.g. cycle basis). It also relates to weighted shortest path functions, which also return the predecessor edge ID of each vertex—this is necessary to identify the weight of the incoming edge. But it is not sufficient for a complete representation of an edge traversal: for that we additionally need the predecessor vertex of each edge (thus two vectors: predecessor edge of each vertex and predecessor vertex of each edge). Finally, it also related to igraph_unfold_tree().

[szhorvat]

Let me make a concrete suggestion about what restrictions parent vectors must have and what their interpretations should be. These rules would be followed for all uses of parent vectors throughout igraph, whether the parent vector is an input or output parameter. Also, functions that produce trees will strive to provide a parent representation as well, whenever feasible.

• Values are either negative or a valid vertex ID.

• parent[i] is the vertex ID of the parent/predecessor of vertex i.

• No cycles are allowed, not even self-loops, meaning that parent[i] == i is forbidden as well. This promise makes it easier to work with these vectors. There will be a function that verifies this in linear time.

• If parent[i] < 0, then vertex i has no parent/predecessor.

• There can be multiple reasons for a vertex having no parent, and some applications require distinguishing between these different reasons. For example, when a (partially) spanning tree is constructed by traversing the graph, one vertex has no parent because it is the starting point (explicitly a root). Others have no parent because they could not be reached.

  In these cases, explicit roots are marked by -1, while vertices that have no parent for other reasons (e.g. unreachable) get a value < -1, e.g. -2. This is precisely what igraph_dominator_tree() does right now.

• High-level interfaces which prefer to use other values here will translate the negative values appropriately. For example, if R wants to have NA for unreachable, it can perform this translation at the same time as converting 0-based indices to 1-based ones.

• Same rules apply for edge-predecessor vectors, i.e. where the value is not the vertex ID of the parent vertex, but the edge ID of the incoming edge. Such vectors are used by shortest path functions.

Additionally, for parent vectors which contain vertex IDs (not edge IDs), there will be functions to:

• Validate them (verify that there are no cycles)
• Convert a parent vector to a graph object (a tree), see [WIP] tree from parents #1891
• Convert a tree to a parent vector. This is accomplished by either BFS/DFS so we do not need a separate function. We just need to make sure that the BFS/DFS functions are easy enough to use for this purpose.

Is everyone in agreement with this solution?

[GroteGnoom]

In https://github.com/igraph/igraph/pull/1893/files#diff-fa3e203d81d47d7b83d76476e402790e4e3895e3da139d016be7b35d6e0e3052R76 there's a predecessor vector with self-loops. Do you think we should prevent that? This is of course similar to the shortest path functions.

[szhorvat]

Can you summarize why it appears there, and what is the intended meaning? Is the root again having itself as a predecessor, i.e. is it just a choice of representation?

[GroteGnoom]

I think it's just a choice of representation, and it's possible to make a different choice that confirms to this proposal that will work fine. It just takes a lot of work on the PR, so it's nice to know for sure if the work is necessary.

[szhorvat]

My proposal is above, i.e. use -1 for roots and -2 for unreachable. There hasn't been any feedback yet, except from you.

@ntamas @vtraag Are you happy with this proposal? If not, can you make a counterproposal?

[ntamas]

For some reason I thought I'd already answered this, but apparently not. I'm okay with this proposal.