Блог

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

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

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

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

У меня есть 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) amp;amp; segment3.Includes(segment2))
                            isDirectChild = false;
                        break;
                    }
                    if (isDirectChild)
                        segment.Childs.Add(segment2);
                }
            }
            if (isRoot)
            {
                result.Root = segment;
            }
        }

        return resu<
    }
}
  

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

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

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

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