search

datavis-tech / graph-data-structure

A graph data structure with topological sort and shortest path algorithms.
MIT License
249 stars 46 forks source link

topologicalSort produces invalid results for graphs with cycles #41

Closed notmatthancock closed 3 years ago

notmatthancock commented 3 years ago

Performing a topological sort on a graph with cycles should throw an error (related: https://github.com/datavis-tech/graph-data-structure/issues/32).

Currently, you can do:

g = Graph()
g.addEdge('a', 'b').addEdge('b', 'a').topologicalSort()
// => [ 'a', 'b' ]
curran commented 3 years ago

I agree an error should be thrown.

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).

From https://en.wikipedia.org/wiki/Topological_sorting

I wonder what sort of change this would take...

notmatthancock commented 3 years ago

It seems the depth first function could be slightly modified to be in accordance with the method shown on wiki so that it throws an Error on a detected cycle -- maybe only if a errorOnCycle flag is passed to depthFirstSearch?

curran commented 3 years ago

Got it. That would be a welcome change!

notmatthancock commented 3 years ago

Cool, I'll take a whack at it.