Найти граф включения из упорядоченного множества

Question

Допустим, у меня есть набор элементов и отношение порядка (не общее) между ними.

Для простоты, скажем, его одномерные сегменты с включением.

Из необработанного списка сегментов, как я могу построить график прямого включения (если это возможно из моего набора):

из черных сегментов, как я могу восстановить красный график?

У меня есть решение O(n^3) в C #, которое совершенно безобразно, и мне интересно, есть ли что-нибудь лучше [псевдокод]:

interface INode
{
    bool Includes(INode other);
    List<INode> Childs { get; set; }
}

class Graph
{
    public INode Root { get; set; }
}

class GraphBuilder
{
    public static Graph Build(IList<INode> nodes)
    {
        Graph result = new Graph();
        foreach (var segment in nodes) {
            segment.Childs = new List<INode>();
            bool isRoot = true;
            foreach (var segment2 in nodes)
            {
                if (segment2.Includes(segment))
                {
                    isRoot = false;
                }
                if (segment.Includes(segment2))
                {
                    bool isDirectChild = true;

                    foreach (var segment3 in nodes)
                    {
                        if (segment.Includes(segment3) && segment3.Includes(segment2))
                            isDirectChild = false;
                        break;
                    }
                    if (isDirectChild)
                        segment.Childs.Add(segment2);
                }
            }
            if (isRoot)
            {
                result.Root = segment;
            }
        }

        return result;
    }
}

Answer 1

Сначала выполните топологическую сортировку DAG, используя эффективный алгоритм, такой как Алгоритм Кана во времени O(V+E).

Для каждого элемента постройте только стрелку от самого себя до наименьшего(в топологическом порядке) вещь меньше, чем в оригинальной DAG.Для их определения также требуется время O(V+E).

Это ваш красный график во времени O(V+E).

Обратите внимание, что простое чтение DAG занимает время O(V+E), так что допостоянное, лучшее, что вы могли бы сделать.