Hacker News new | ask | show | jobs
by ErotemeObelus 2522 days ago
I am a newbie to topology, so please help me. What is a topological sort and why does it describe this?
2 comments

The "topological" in topological sort is more related to "network topology" than the mathematical topology (open sets). "Sort" is related to ordering. Topological sort thus is related to the ordering of a network graph's nodes by their edges.

You can see https://en.wikipedia.org/wiki/Topological_sorting to see what it actually is. Topological sort is good in dealing with dependency graph. It can turn a dependency graph into a linear ordering of nodes.

GP mentioned topological sort because words depend on other defining words and it's one big directed acyclic graph. Do a topological sort on it and you got a linear list of words ordered by dependency. Group the consecutive words that have no dependency together and you got the word layers. Within each layer all the words don't depend on each other. The words in one layer depend on the words in the lower layers.

I don't think mathematical topology and network topology are different concepts.

The open sets in a network topology are the subsets of nodes that happen to be connected by the edges. So if you can't get from here to there without using a node outside your set, then your set isn't an open set in the network topology.

Except unions of open sets are required to be open, so the case for topology here is not what you're describing (assuming standard definitions).

Generally, the topology on a graph will look like what you get if you draw your graph in the euclidean plane (or space, whatever) without intersections of edges.

The notion of closeness of vertices in this case isn't really well described by "point set topology", but you'd rather use the notion of distance between vertices (length of a shortest path). But even then, the distance stuff generally assumes non-directed edges, because you generally want the distance from A to B to be the same as from B to A.

In short, I don't think "point set topology" has much to say here, at least as usually done.

You're right. You can use the more general mathematical topology to describe a network topology. It's just mathematical topology speaks in sets, compactness, closeness that people not visualize well. The simpler and more specific network topology or network graph can be visualized very well.
Not sure why it's called topological sort or what it had to do with topology, but it's a graph traversal where predecessors are visited before their successors. Such a sort only exists if there are no cycles in the graph.
It's been a while since I took a Topology class, but I left it with the understanding that Topology is all about taking a set (nodes, say) and applying some notion of closeness (how many hops?).

Once you've done that, you have a topological space. The sets that you've defined as "close together" are your open sets. Loosely speaking, smaller open sets are considered closer together than larger ones.

This might seem boring in the case of directed graphs, which have an obvious notion of closeness, but there are more exotic spaces where you might not usually think to use "spacial" reasoning, but where it can be applied anyhow thanks to the formalism.

In a topological sort, you end up arranging the elements based on nearness to each other (as much as is possible for a list), so that elements in a given open set in the typical topological space over directed graphs are likely to be next to each other in the list. It's a pretty topological way to do things, which probably explains the name.