**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Topological sorting

Summary

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications especially in ranking problems such as feedback arc set. Topological sorting is possible

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (21)

Related people (5)

Loading

Loading

Loading

Related concepts (13)

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ar

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

Related courses (6)

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

DH-405: Foundations of digital humanities

This course gives an introduction to the fundamental concepts and methods of the Digital Humanities, both from a theoretical and applied point of view. The course introduces the Digital Humanities circle of processing and interpretation, from data acquisition to new understandings.

Related units (3)

Related lectures (14)

The goal of this work is to study Alexander-Whitney coalgebras (first defined in [HPST06]) from a topological point of view. An Alexander-Whitney coalgebra is a coassociative chain coalgebra over Z with an extra algebraic structure : the comultiplication must respect the coalgebra structure up to an infinite sequence of homotopies (this sequence is part of the data of the Alexander-Whitney coalgebra structure). Alexander-Whitney coalgebras are interesting for topologists because the normalized chain complex C(K) of a simplicial set K is endowed with an Alexander-Whitney coalgebra structure. This theorem is proved for the first time here (generalising a result proven in [HPST06]). This theorem gives the hope that the Alexander-Whitney coalgebra structure of C(K) contains interesting information that can be used to solve topological problems. This hope is strengthened by the success already obtained in the work of several topologists. Among others, [HPST06], [HL07], [Boy08], and [HR] use the Alexander-Whitney coalgebra structure of the normalized chains of a simplicial set in an essential way to solve topological problems. This thesis begins with some background material. In particular, the definition of a DCSH morphism between two coassociative chain coalgebras is recalled in complete detail. For example, signs are determined with great precision. Next we devote a chapter to the definition of Alexander-Whitney coalgebras and to their importance in topology. In the following chapter we begin the conceptual study of Alexander-Whitney coalgebras. A global study of these objects had not yet been carried out even if the Alexander-Whitney coalgebra structure has been studied and used in order to answer some specific questions. With the aim of studying Alexander-Whitney coalgebras in a nice setting, we develop an operadic description of these coalgebras in the following chapter. More precisely, we show that there is an explicit operad AW such that the coalgebras over this operad are exactly the Alexander-Whitney coalgebras. Furthermore, AW is shown to be a Hopf operad, so that the category formed by the Alexander-Whitney coalgebras is actually a monoidal category. These results are proven in a reasonably general framework. In fact, we associate an operad to each bimodule (over the associative operad) of a certain type, such that we get AW if this bimodule is well chosen. In particular, these results enable us to study Alexander-Whitney coalgebras from the standpoint of operads. This strategy is recognised to be successful in various mathematical situations, and especially in algebraic topology. Moreover, we develop a minimal model notion in the setting of right module over a chosen operad (which has to satisfy some reasonable conditions), with the aim of applying this result to the special case of the Alexander-Whitney coalgebras. This is possible because coalgebras over some fixed operad P can be seen as right modules over P. And the category of right modules over P has some nice features which do not appear to hold in the category of P-coalgebras. The inspiration for this part of our work comes from the notion of minimal model developed in the framework of rational homotopy theory. The two following facts show that it is reasonable to try to adapt some ideas of rational homotopy theory to the category of Alexander-Whitney coalgebras. A. There is a theorem that says that studying topological spaces up to rational equivalences is, essentially, equivalent to studying cocommutative chain coalgebras over the field of rational numbers. This is false if the ring of integers replaces the field of rational numbers, but Alexander-Whitney coalgebras are "almost" cocommutative in the sense which is explained in this thesis. B. It could be that the Alexander-Whitney coalgebra structure of the normalized chains of a simplicial set is weak enough to allow explicit computations. At least, it is clear that the Alexander-Whitney coalgebra structure on the normalized chains is far from being an E∞-structure (such a structure determines the homotopy type of the considered simplicial set, at least under some conditions). The chapter about minimal models in the framework of right modules over an operad includes an existence theorem and a discussion of the unicity of this model. In the second part of this chapter, we construct an explicit path-object in the model category of right modules over an operad. This path-object is then used to investigate the topologically relevant information that could stem from the minimal model in the case of the operad AW. Finally, we present and examine some interesting open questions about Alexander-Whitney coalgebras. These questions give a nice outlook on future research in this area.

Samy Bengio, Hervé Bourlard, Hamed Ketabdar

In this paper, we present initial results towards boosting posterior based speech recognition systems by estimating more informative posteriors using multiple streams of features and taking into account acoustic context (e.g., as available in the whole utterance), as well as possible prior information (such as topological constraints). These posteriors are estimated based on ``state gamma posterior'' definition (typically used in standard HMMs training) extended to the case of multi-stream HMMs.%, resulting in new features. This approach provides a new, principled, theoretical framework for hierarchical estimation/use of posteriors, multi-stream feature combination, and integrating appropriate context and prior knowledge in posterior estimates. In the present work, we used the resulting gamma posteriors as features for a standard HMM/GMM layer. On the OGI Digits database and on a reduced vocabulary version (1000 words) of the DARPA Conversational Telephone Speech-to-text (CTS) task, this resulted in significant performance improvement, compared to the state-of-the-art Tandem systems.

2005