Browse Prior Art Database

A Fast Insertion Sorting Algorithm for a Directed Acyclic Graph (DAG)

IP.com Disclosure Number: IPCOM000198620D
Publication Date: 2010-Aug-10
Document File: 4 page(s) / 40K

Publishing Venue

The IP.com Prior Art Database

Abstract

A program is disclosed in which a fast insertion sorting algorithm for a Directed Asyclic Graph is introduced. This algorithm doesn't require the edge information to be pre-build before the sorting starts. Instead, it sorts the list of nodes in the graph by using a boolean function to decide whether the edge exists between any two nodes.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 38% of the total text.

Page 1 of 4

A Fast Insertion Sorting Algorithm for a Directed Acyclic Graph (DAG)

Disclosed is a process for an insertion sorting algorithm that does not require edge information to be pre-built before sorting the directed acyclic graph (DAG). The edge information is determined dynamically during the sorting algorithm by calling a Boolean function F(u, v). The disclosed process of an insertion sorting algorithm is typically faster than the usual depth first search (DFS) sorting algorithm when the usual sorting algorithm includes the time to build the edge se

t.

Every DAG has at least one topological sort or topological ordering. Many applications require the DAG to be sorted in topological order [1]. For example, when data are to be flushed to a list of database tables, the data are flushed to the parent tables first before the data are flushed to the children tables due to foreign key constraints. A list of database tables with the foreign key relationship forms a DAG. The database tables are sorted based on the foreign key constraints such that parent tables are always before child tables [2].

Many sorting algorithms exist for a DAG. For example, a depth first search (DFS) for a DAG is a very fast sorting algorithm. Typically existing DAG sorting algorithms require building a graph (for example, the edge information is built) before performing the sort. However in many applications, the edge information is defined by a Boolean function F(u, v

).

That is, [u, v

]

                                                              returns true. The edge set can be built based on the Boolean function but building the edge set takes time. Typically building the edge information is usually more expensive than the sorting operation. For example, in a typical sorting algorithm, the sorting algorithm has a complexity defined by O(N

)

represents an edge if and only if F(u, v

)

, but

building the edge information has the complexity defined by O(N2

).

In one example, a directed acyclic graph G consists of a set V and a set E where V contains a set of vertices and E contains a set of edges. If e is an edge and e = [u, v

]

                                            , uis called the parent node (or source node) and v is called a child node (or target node). A topological sort for a DAG sorts the set V into a list S = {v1,v2, … , vn

}

, such that the parent node is positioned before the child node for every

edge.

A directed graph G can be defined by a set V and a Boolean function F(u, v

).

The function F(u, v

)

returns either true or false for any u and v in the V . The edge set E can be determined as [u, v

]

is an

edge if and only if the function F(u, v

)

returns true.

For a given directed graph G which is defined by a set V and a Boolean function F(u, v

)

the set V can be

written as a list S = {v1, v2, …, vn

},

the list S is sorted when the following condition never holds:

F(vk, v

)

= true, for any

j

                   < k
In this case the child node is never before the parent node. The DAG sorting problem may be described as when a DAG is defined by a set V and a Boolean func...