vezy/multiscaletreegraph.jl

Read, analyse, compute, write and convert MTG files

multiscaletreegraph.jl's Issues

Helper function for scales

We could provide functions to get stats for scales:

• nb scales
• min/max scale
• nb nodes in total per scale, for a given scale

Add node "type" as a parameter in the Node (as a field of type T)

Add possibility to add a node "type" as a parametric type so we can dispatch on this ? E.g. Internode, Leaf... It would be a field of node with default value of e.g. AnyNode

Change writing format

Our printing of the MTG when we write back to disk takes too many columns e.g.:

^+A1									
^/GU1									
	/N1								
		<N2							
			+A2						
			^/GU1						
				/N1					
				^<N2					
					<N3				
						<N4			
							<N5		
								<N6	
									<N7
									^+Leaf1
								^+Leaf1	
							^+Leaf1		
						^+Leaf1			
					^+Leaf1				
				^+Leaf1					
			<N3						
				<N4					
					0				
					^/GU1				
						/N1			
						^<N2			
							<N3		
								<N4	
									<N5
									^+Leaf1
								^+Leaf1	
							^+Leaf1		
						^+Leaf1			
					<N5				
						<N6			
							<N7		
								<N8	
								^+Leaf1	
							^+Leaf1		
						^+Leaf1			
					^+Leaf1				
				^+Leaf1					
			^+Leaf1						
		^+Leaf1							
	^+Leaf1								

This one can be reduced to the following just by changing the rules that decide when we create new columns, and how we order the nodes:

^+A1		
^/GU1		
^/N1		
	+Leaf1	
^<N2		
	+Leaf1	
	+A2	
	^/GU1	
	^/N1	
	^<N2	
		+Leaf1
	^<N3	
		+Leaf1
	^<N4	
		+Leaf1
	^<N5	
		+Leaf1
	^<N6	
		+Leaf1
	^<N7	
		+Leaf1
^<N3		
	+Leaf1	
^<N4		
	+Leaf1	
	+A2	
	^/GU1	
	^/N1	
	^<N2	
		+Leaf1
	^<N3	
		+Leaf1
	^<N4	
		+Leaf1
	^<N5	
		+Leaf1
^<N5		
	+Leaf1	
^<N6		
	+Leaf1	
^<N7		
	+Leaf1	
^<N8		
	+Leaf1	

Check the rules, but I think that (rapid analysis):

• we shouldn't create a new column if the node has only one child;
• the nodes that follow should stay in the same column, and the nodes that branches should go in a new column, unless they have no siblings
• we should visit the branching nodes first, put them in a new column (unless they have no sibling has I just said), then the nodes that follow (and keep them in the same column as we can't have two nodes that follow I think);
• nodes that decompose should stay on the same column that their parents, unless they have siblings, in that case they should be in a new column (but first, before branching nodes)

Add possibility to parse node type at parsing

The node type is often related to the symbol of the node, with potentially a parameter linked to an attribute value or the scale. It would be interesting to be able to parse the node type at parsing when needed, for example using a function that takes the information about the node in input and computes the type, or by passing a Dict of symbols => type or symboles => function.

Use `traversal_cache` for `descendants`

Everything's in the title, related to #21

Add prune! to docs

Add an example with prune! in the Add/remove nodes section.

Add test for traverse with args...

We only test to traverse the mtg with a function f that has no further arguments, except when transforming into a MetaGraph. We should add a test for e.g.

traverse!(mtg, fn, argument_to_fn)

descendants with `all=false` does not work

We tried on cacao MTG to compute something with all=false and it returned all descendants, including the ones that should be filtered-out...

Use `traverse` in `descendants`

We should use traverse or traverse!in descendants / descendants! instead of using a different implementation.
From what I see it can be quite trivial, except descendants as few more arguments:

• all
• self
• recursivity_level
• ignore_nothing
• type

Without much investigation, I would say that:

• all can be added as a new argument to traverse
• self: can stay in descendants as is
• recursivity_level: can also be added as a new argument to traverse
• ignore_nothing: can stay in descendants as is, because it is added to the filtering function
• type: can also be kept as is

Then, descendants will initialise an array as it is done now, but will add the whole "if keep then push to the array" thing inside the function applied in the tree traversal.

We have to be careful when implementing this for descendants! though, because we have to find a way to stop tree traversal if there is a cached value for the particular traversal here.

delete_nodes! gives unexpected results when deleting multiple nodes at the root

The function delete_nodes! seems to have an issue when deleting the root node as well as one or more nodes that would become its successor root node:

using MultiScaleTreeGraph
mtg = Node(MutableNodeMTG("/", "Scene", 0, 0), Dict())
insert_child!(mtg, MutableNodeMTG("/", "Plant", 0, 1))
insert_child!(mtg[1], MutableNodeMTG("/", "Internode", 0, 2))
insert_child!(mtg[1][1], MutableNodeMTG("<", "Leaf", 0, 2))
insert_child!(mtg[1][1], MutableNodeMTG("<", "Leaf", 0, 2))

new_mtg = delete_nodes!(mtg, filter_fun = node -> node_mtg(node).scale != 2)
length(new_mtg) == 3 # false

The issue seems to arise from the fact that the function only checks the root node once before starting to work recursively from leaves to root:

function delete_nodes!

...

if filtered
    node = delete_node!(node)
    # Don't go further if all == false
    !all && return
end

delete_nodes!_(node, scale, symbol, link, all, filter_fun, child_link_fun)
...

Changing the function to continue working from root to leaves until the node does not need to be deleted:

function delete_nodes!(
    node;
    scale=nothing,
    symbol=nothing,
    link=nothing,
    all::Bool=true, # like continue in the R package, but actually the opposite
    filter_fun=nothing,
    child_link_fun=new_child_link
	)

    # Check the filters once, and then compute the descendants recursively using `descendants_`
    check_filters(node, scale=scale, symbol=symbol, link=link)
    filtered = is_filtered(node, scale, symbol, link, filter_fun)

    while filtered
        node = delete_node!(node)
        filtered = is_filtered(node, scale, symbol, link, filter_fun)

        # Don't go further if all == false
        !all && return
    end

    delete_nodes!_(node, scale, symbol, link, all, filter_fun, child_link_fun)

    return node
end

fixes the issue for this example:

using MultiScaleTreeGraph
mtg = Node(MutableNodeMTG("/", "Scene", 0, 0), Dict())
insert_child!(mtg, MutableNodeMTG("/", "Plant", 0, 1))
insert_child!(mtg[1], MutableNodeMTG("/", "Internode", 0, 2))
insert_child!(mtg[1][1], MutableNodeMTG("<", "Leaf", 0, 2))
insert_child!(mtg[1][1], MutableNodeMTG("<", "Leaf", 0, 2))

new_mtg = delete_nodes!(mtg, filter_fun = node -> node_mtg(node).scale != 2)
length(new_mtg) == 3 # true

Add `hasproperty` to the node

Add hasproperty to the Nodetype, so we can safely check if an attribute exists for a node or not:

hasproperty(node, :var) # should return true if `var` exist in the attributes for that particular node.

Careful, users can still access a variable if it does not exist for that particular node, and it will return nothing. This is because the variable can exist for other scales, and we don't add the value at all scales to keep everything memory efficient.

descendants and ancestors but for nodes instead of attributes

It could be useful to have a method for descendants and ancestors with no attribute that would return the nodes selected by the different filters.

For descendants, it would simply use traverse(mtg, node -> node, filters...). For ancestors, we need a new method.

MTG with no features cannot be read

Try with this file:

palm.mtg.zip

Make the return of `traverse` optionnally type aware

When we traverse the mtg (non-mutating version), we often already now what type of data our function will return. This could be given by the user as an argument so we could create a vector with this type instead of Any[].

Define the workflow for simulation

Simulation of an MTG is already available from PlantSimEngine, but it makes a lot of copies when making a simulation.

Ideally, we would have the data in a Tables.jl compatible structure, and this structure would be given as the status of the ModelList of the node. This way it wouldn't make a copy of the data, just modify it.

Here's the specifications:

• we need a Tables.jl compatible structure for the status of the ModelList
• we need this structure to have as many time-steps as needed, e.g. according to the required meteorology. So we need a step before simulation to check that, and maybe a way to easily build the table for simulation
• we need the data to be easily accessible and changeable through the API of MultiScaleTreeGraph
• We need to avoid copies of the data as much as possible (MTGs can grow big)

But we also need a way to have the ModelList of the Node accessible. There's two solutions I can think of:

• add the ModelList to the table (this is not very memory efficient as it would be repeated many times.
• have a custom field in the MTG for the ModelList. For this solution to be efficient, we need to test if the ModelList can be given as a mutable field as is, or if we need to put it as a parameterized field. In the second case we need to know the ModelList at the creation of the MTG, which is probably not the best thing. Also, if we do this, it would be interesting to have a way to transform a regular MTG into this type of MTG.

In any case, we have to think about usability vs performance.

Performance improvements

Tree traversal can be slow sometimes. Ses how I can improve it for large MTGs.

• remove node type as it is not type stable
• remove all typeof(something) that can be replaced by the parameters of the input type
• Is isnothing faster than isdefined for parent()? Removed it completely as it was not needed (see f2a443f).
• Is default tree traversal from AbstractTrees faster? No, in an example, it did 6.192 μs (383 allocations: 8.98 KiB) against 6.938 μs (18 allocations: 1.30 KiB) with our implementation. We keep ours.

Error using `scales`

When we use scaleson an mtg, we get the following error:

ERROR: MethodError: no method matching iterate(::Nothing)

This is because we traverse the mtg with the mutating version (traverse!), but pipe the returned value into unique. We shouldn't pipe the value because this version doesn't return anything (or more precisely, it returns nothing).

write_mtg does not work with immutable structs

write_mtg does not make a copy of the mtg when writting, and modifies it in place to add temporary variables, which does not work when we have immutable attribute.

We have to change the code here:

MultiScaleTreeGraph.jl/src/write_mtg/write_mtg.jl

Lines 103 to 108 in 0940222

	transform!(
	mtg,
	(x -> get_leading_tabs(x, lead_name)) => lead_name,
	paste_mtg_node => print_name,
	get_reference => mtg_refer
	)

And make the computation outside the node attributes.

Add colors to tree printing

It would be nice to colour the nodes by , e.g. scale, for example.

Add post-order traversal

Currently, we only provide pre-order tree traversal, which applies the function from the root to the leaves. We should also provide the reverse, applying the function to the leaves first and then going to the root.

See: AbstractTrees.PreOrderDFS and AbstractTrees.PostOrderDFS.

I propose that we re-export those two and that users provide them as an argument to the tree traversal. The only thing we have to change is when we call the function in the traversal:

• before recursion on the children for PreOrderDFS
• after recursion for PostOrderDFS

Add parallel traversal

Make MTG traversal parallel. We may need to fall back to the methods from AbstractTrees.jl that also have filters now (see here).
We could use Floops.jl to do that.

Add helper functions for users

Some traversals are quite complicated to reason about. For example, users often want to traverse the nodes along an axis without visiting the branching positions. This is especially difficult when we have several scales along the axis. For example, we can visit them as follows:

descendants(axis_node, link = ["/", "<"], all = false)

What's important here is to understand what the all argument does, and not many people go read the documentation. They would rather use a function that does that instead, or at least a filter function that already exists:

descendants(axis_node, filter_fun = node -> along_axis(node, axis = "A", target = "N"))

The axis argument is used to identify the name of the nodes that are an axis, and the target argument for getting the name of the nodes we want (could be "GU" for growth units or "N" for nodes).

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Ensure type stability in the MTG traversal

Make sure that all nodes of the MTG have the same parametric types, and make sure that the compiler knows about it.

Use symbols for MTG description

We should use symbols for the symbol and link of the node, it is ~10 times faster for comparison compared to strings, and we only do that anyway. There is also no new allocation when a symbol appear more than once.

Of course we have to still support strings from the users, but convert them to symbols under the hood. And document that using symbols is preferred over strings.

Apply ExplicitImports.jl

Apply ExplicitImports.jl on the package to be sure that we explicitly import the functions of our dependencies.

Add possibility to select / drop variables at parsing

It would be nice to be able to select or drop some attributes at file parsing, this way we could import large MTGs efficiently if we are only interested on just a subset of the variables

Remove the "name" attribute of the node?

I'm not sure it is much used except for printing. We should compute it on the fly using the node id instead, no need to store it.

Add `reduce` argument to descendants and `ancestors`

Add a reduce argument to those functions, which would take a function that is used to reduce the results from the ancestors before returning the value. This is not that useful for the non-mutating functions, but could be neat to have for the mutating one (descendants!). This way the cache would only take one value instead of the full list of values, which largely reduce the memory usage.

Should `ordered_children` return nodes by their ID ?

Maybe it would be better than showing by branching first, as it would respect the order of appearance in the mtg file, and order of creation when modelling.

Look at a more efficient way to parse MTG files

See https://github.com/JuliaData/Parsers.jl

insert_generation! does not update parent

The function insert_generation! adds a new node to a graph and makes the previous children of its parent node its own children, but it does not update the parent of these child nodes:

using MultiScaleTreeGraph
mtg = Node(MutableNodeMTG("/", "foo", 0, 0), Dict())
insert_child!(mtg, MutableNodeMTG("/", "bar", 0, 0))

insert_generation!(mtg, MutableNodeMTG("/", "xyzzy", 0, 0))
parent(mtg[1][1]) == mtg[1] # false

Changing the function to include the parent update of the child nodes:

function insert_generation!(node::Node{N,A}, template, attr_fun=node -> A(), maxid=[max_id(node)]) where {N<:AbstractNodeMTG,A}

    maxid[1] += 1

    new_node = Node(
        maxid[1],
        node,
        children(node),
        new_node_MTG(node, template),
        copy(attr_fun(node)),
        Dict{String,Vector{Node{N,A}}}()
    )

    # Add the new node as the only child of the node:
    rechildren!(node, Node{N,A}[new_node])

    # Add the new node as parent of the children
    for chnode in children(new_node)
        setfield!(chnode, :parent, new_node)
    end
    
    return node
end

fixes this:

using MultiScaleTreeGraph
mtg = Node(MutableNodeMTG("/", "foo", 0, 0), Dict())
insert_child!(mtg, MutableNodeMTG("/", "bar", 0, 0))

insert_generation!(mtg, MutableNodeMTG("/", "xyzzy", 0, 0))
parent(mtg[1][1]) == mtg[1] # true

Strangely, using reparent! in the for loop instead of setfield! does not work, despite seeming to be the intended function here. I've looked into this but can't find the issue. Since I can't properly fix the issue I will not open a PR for this.

Implement several methods for `clean_cache!` and `select!` depending on the attributes type

At the moment, it uses pop! so it works only for Dicts.

Errors when parsing MTG file in MTG section

Problem:

Two problems have been identified in parse_mtg.jl:

1. some files have a blank line after the declaraiton of the MTGsection. This is not allowed with the actual parser (cf.

   MultiScaleTreeGraph.jl/src/read_MTG/parse_mtg.jl

   Lines 25 to 28 in 8b504f1

   	if length(l[1]) == 0
   	error("No header was found for MTG section `MTG`. Did you put an empty line in-between ",
   	"the section name and its header?")
   	end

   )
2. On the first line of the MTG description, 2 nodes can be defined, e.g. /P1/U1. Actual behaviour of the parser only considers the first node (/P1 in this case)

Proposed solution:

1. In parse_mtg.jl, replace:

       error("No header was found for MTG section `MTG`. Did you put an empty line in-between ",
           "the section name and its header?")

by

l[1] = next_line!(f, line)

2. Needs to be discussed. Main issue is here:

   MultiScaleTreeGraph.jl/src/read_MTG/parse_mtg.jl

   Line 61 in 8b504f1

   link, symbol, index = parse_MTG_node(node_1_node[1])

   
   where we would need to loop on node_1_node

Put children as an array of Nodes instead of a Dict

Having children in as a Dict complicates the tree traversal, and probably adds nothing interesting anyway.
We have to look the impact on doing so before changing.

Make `addchild!` return the child so we can iteratively add children

It returns nothing right now, but it would be very nice if it returned the newly created child so we can add more children without the need to traverse again.

Add `component` and `complex` to Node

This would align with MTG implementation OpenAlea and is a first step toward visit only some scales without the need to visit all nodes in-between.

This means also updating names: children become nodes of the same scale, components of a scale with higher number and complex are nodes of a scale with lower number.

delete_node! errors on root nodes

Hi

The delete_node! function returns MethodError: no method matching link(::Nothing) when using it to remove the root node.

using MultiScaleTreeGraph
mtg = Node(MutableNodeMTG("/", "foo", 0, 0), Dict())
insert_child!(mtg, MutableNodeMTG("/", "bar", 0, 0))

new_mtg = delete_node!(mtg) # errors

The problem seems to arise from the fact that the child node of the root has its parent set to nothing before applying the link! function. Changing the order as follows:

function delete_node_fixed!(node::Node{N,A}; child_link_fun=new_child_link) where {N<:AbstractNodeMTG,A}
    if isroot(node)
        if length(children(node)) == 1
            # If it has only one child, make it the new root:
            chnode = children(node)[1]
            # Add to the new root the mandatory root attributes:
            root_attrs = Dict(
                :symbols => node[:symbols],
                :scales => node[:scales],
                :description => node[:description]
            )

            append!(chnode, root_attrs)

            link!(chnode, child_link_fun(chnode))
            reparent!(chnode, nothing)

            node_return = chnode
        else
            error("Can't delete the root node if it has several children")
        end
    else
        parent_node = parent(node)

        if !isleaf(node)
            # We re-parent the children to the parent of the node.
            for chnode in children(node)
                # Updating the link of the children:
                link!(chnode, child_link_fun(chnode))
                addchild!(parent_node, chnode; force=true)
            end
        end

        # Delete the node as child of his parent:
        deleteat!(children(parent_node), findfirst(x -> node_id(x) == node_id(node), children(parent_node)))
        node_return = parent_node
    end

    node = nothing

    return node_return
end

seems to fix the issue

mtg = Node(MutableNodeMTG("/", "foo", 0, 0), Dict())
insert_child!(mtg, MutableNodeMTG("/", "bar", 0, 0))

new_mtg = delete_node_fixed!(mtg) # no error
new_mtg

Version info: Julia Version 1.10.2, MultiScaleTreeGraph v0.13.1

Make option to build `traversal_cache` at file parsing

It could be nice to be able to build the cache at parsing to avoid re-traversing the whole MTG to build the cache

Add Tables.jl interface instead of DataFrame

It would be nicer to have a Tables.jl interface instead of DataFrames.jl: it is more generic (it helps interface with any Tables-compatible package, e.g., databases), has a smaller dependency, and has fewer releases per year (less maintenance).

It would also allow us to iterate over the MTG as rows of a Table.

Add/check possibility to use `Not`

It would be useful to be able to use Not in e.g.:

DataFrame(mtg, Not(:symbol))

or:

select!(mtg, Not(:symbol))