Cycle detection that handles a series of directed edges?

Asked Apr 24 '18 at 20:23

Active Apr 24 '18 at 20:23

Viewed 17 times

Is there an algorithm faster than topological sort or DFSto handle time series of edges?

(1) at time t = 0, there is one node.

(2) at each time t > 0, an edge comes along. At least one of the edge's endpoints was added into the graph before t.

I want to detect at each time t if there is a directed cycle.

I really want to take advantage of the input being a time series. But the algorithms I know all deal with static graph.

A good reference that is unlikely to be a broken link: wiki

asked Apr 24 '18 at 20:23

Leedehai

Do you know in advance the total number of nodes in the graph, or is always dynamically growing? – jdehesa Apr 24 '18 at 20:26
@jdehesa it's dynamically growing, so the total number of nodes is unkown. – Leedehai Apr 24 '18 at 20:27
@juvian Yes it's duplicate. Thx! Feel free to close. – Leedehai Apr 24 '18 at 20:30
@Leedehai: Closing works best if you do it yourself. – Prune Apr 24 '18 at 23:25

0 Answers0