Which tree or graph structure to solve this problem?

Question

I have the following interface, it defines a loadable resource that depends on other resources that should be loaded first so it can load itself:

It does its job, the Find method allowing to search for a particular dependency for Load method.

Now I have another problem for which I haven't found an elegant solution for, so far.

Here is an example of what I am trying to model along explanations:

(click to enlarge)

Legend of elements, starting from top:

• Level represents a game level, it has an abritrary amount of content
• Sky, Scene and Track are some of the content
  • these can consist of multiple content, e.g. for Scene it is Scene 1 and Scene N
• the next items represent different file types each content needs
• the last level, Storage, is where these are to be loaded from

Note: the direction of arrows tells what an object depends on so it can load itself

Here is the implementation I am currently using:

using System;
using System.Collections.Generic;
using System.Linq;
using JetBrains.Annotations;
using Random = UnityEngine.Random;

namespace ZeroAG.WorkInProgress.Resources
{
    public interface IResource
    {
        /// <summary>
        ///     Gets direct dependencies of this instance.
        /// </summary>
        [NotNull]
        IEnumerable<IResource> Dependencies { get; }

        /// <summary>
        ///     Gets the name of this instance.
        /// </summary>
        [NotNull]
        string Name { get; }

        /// <summary>
        ///     Gets any dependencies of this instance that matches a predicate.
        /// </summary>
        [NotNull]
        IEnumerable<T> Find<T>([NotNull] Predicate<T> predicate) where T : IResource;

        /// <summary>
        ///     Loads this instance.
        /// </summary>
        void Load<T>(IResourceProgress<T> progress) where T : IResourceProgressInfo, new();
    }

    public abstract class Resource : IResource
    {
        protected Resource([NotNull] string name, [NotNull] params IResource[] dependencies)
        {
            Name = name ?? throw new ArgumentNullException(nameof(name));
            Dependencies = dependencies ?? throw new ArgumentNullException(nameof(dependencies));
        }

        public IEnumerable<IResource> Dependencies { get; }

        public string Name { get; }

        public IEnumerable<T> Find<T>(Predicate<T> predicate) where T : IResource
        {
            if (predicate == null)
                throw new ArgumentNullException(nameof(predicate));

            var queue = new Queue<IResource>(new[] {this});

            while (queue.Any())
            {
                var dequeue = queue.Dequeue();

                foreach (var dependency in dequeue.Dependencies)
                {
                    queue.Enqueue(dependency);
                }

                if (dequeue is T item && predicate(item))
                {
                    yield return item;
                }
            }
        }

        public virtual void Load<T>(IResourceProgress<T> progress) where T : IResourceProgressInfo, new()
        {
            // just a demo for all derived types

            var count = Random.Range(3, 5);

            for (var i = 0; i < count; i++)
            {
                var value = new T
                {
                    Sender = this,
                    Percentage = 1.0f / (count - 1) * i,
                    Message = $"{GetType().Name}: {i + 1} of {count}"
                };

                progress.Report(value);
            }
        }
    }
}

Problem:

While IResource.Find allows me to find a child dependency, it does not allow me to query for an IResource on same hierachy level or above it, e.g. I need at some point to be able to make queries such as the one depicted in red color, i.e. query about anything from anywhere.

Now, while it is very tempting to add a IResource Parent property to IResource it doesn't really makes sense as there might be multiple parents such as for Scene Atlas.

It seems that I am drifting from a typical tree structure to whatever but I can't identify this structure.

Question:

What am looking for and/or how could IResource be refactored in order to solve this problem?

Answer 1

If a node may have multiple parents, it is not a tree structure, it is a directed graph. By introducing the red arrows you now have cycles in the graph, which means you cant really talk of parent-child relationships or hierarchy levels anymore.

Cycles also means you can't just traverse the graph until you find the node matching a predicate, since you might get stuck in an infinite loop.

The simplest solution is to have a collection of all the nodes in the graph, and then iterate through the collection until you find a node which match the predicate.