TheAlgorithms
topological sort returns reversed list
Repository commit
03a42510b01c574292ca9c6525cbf0572ff5a2a5
Python version (python --version)
Python 3.10.12
Dependencies version (pip freeze)
affine==2.4.0 anyio==4.0.0 appdirs==1.4.4 apturl==0.5.2 argon2-cffi==23.1.0 argon2-cffi-bindings==21.2.0 arrow==1.3.0 asttokens==2.4.0 async-lru==2.0.4 attrs==23.1.0 Babel==2.13.0 backcall==0.2.0 bcrypt==3.2.0 beautifulsoup4==4.12.2 beniget==0.4.1 bleach==6.1.0 blinker==1.4 Brlapi==0.8.3 Brotli==1.0.9 certifi==2020.6.20 cffi==1.16.0 chardet==4.0.0 charset-normalizer==3.3.0 click==8.0.3 click-plugins==1.1.1 cligj==0.7.2 colorama==0.4.4 comm==0.1.4 command-not-found==0.3 cryptography==3.4.8 cupshelpers==1.0 cycler==0.11.0 dbus-python==1.2.18 debugpy==1.8.0 decorator==5.1.1 defer==1.0.6 defusedxml==0.7.1 distro==1.7.0 distro-info==1.1+ubuntu0.2 docopt==0.6.2 duplicity==0.8.21 earthpy==0.9.4 exceptiongroup==1.1.3 executing==2.0.0 fasteners==0.14.1 fastjsonschema==2.18.1 fiona==1.9.5 fonttools==4.29.1 fqdn==1.5.1 fs==2.4.12 future==0.18.2 gast==0.5.2 GDAL==3.4.1 geopandas==0.14.1 html5lib==1.1 httplib2==0.20.2 idna==3.3 imageio==2.32.0 importlib-metadata==4.6.4 ipykernel==6.25.2 ipython==8.16.1 ipython-genutils==0.2.0 ipywidgets==8.1.1 isoduration==20.11.0 jedi==0.19.1 jeepney==0.7.1 Jinja2==3.1.2 joblib==1.3.2 json5==0.9.14 jsonpointer==2.4 jsonschema==4.19.1 jsonschema-specifications==2023.7.1 jupyter==1.0.0 jupyter-console==6.6.3 jupyter-events==0.7.0 jupyter-lsp==2.2.0 jupyter_client==8.3.1 jupyter_core==5.3.2 jupyter_server==2.7.3 jupyter_server_terminals==0.4.4 jupyterlab==4.0.6 jupyterlab-pygments==0.2.2 jupyterlab-widgets==3.0.9 jupyterlab_server==2.25.0 keyring==23.5.0 kiwisolver==1.3.2 language-selector==0.1 launchpadlib==1.10.16 lazr.restfulclient==0.14.4 lazr.uri==1.0.6 lazy_loader==0.3 Levenshtein==0.23.0 lockfile==0.12.2 louis==3.20.0 lxml==4.8.0 lz4==3.1.3+dfsg macaroonbakery==1.3.1 Mako==1.1.3 MarkupSafe==2.0.1 matplotlib==3.5.1 matplotlib-inline==0.1.6 mistune==3.0.2 monotonic==1.6 more-itertools==8.10.0 mpmath==0.0.0 mypy==0.942 mypy-extensions==0.4.3 nbclient==0.8.0 nbconvert==7.9.2 nbformat==5.9.2 nest-asyncio==1.5.8 netifaces==0.11.0 networkx==3.2.1 notebook==7.0.4 notebook_shim==0.2.3 num2words==0.5.13 numpy==1.26.1 oauthlib==3.2.0 olefile==0.46 overrides==7.4.0 OWSLib==0.25.0 packaging==23.2 pandas==2.0.3 pandocfilters==1.5.0 paramiko==2.9.3 parso==0.8.3 pbr==5.8.0 pexpect==4.8.0 pickleshare==0.7.5 Pillow==9.0.1 pip==22.0.2 platformdirs==3.11.0 plotly==5.4.0 ply==3.11 prometheus-client==0.17.1 prompt-toolkit==3.0.39 protobuf==3.12.4 psutil==5.9.5 psycopg2==2.9.2 ptyprocess==0.7.0 pure-eval==0.2.2 pycairo==1.20.1 pycparser==2.21 pycups==2.0.1 Pygments==2.16.1 PyGObject==3.42.1 PyJWT==2.3.0 pymacaroons==0.13.0 PyNaCl==1.5.0 pyparsing==2.4.7 pyproj==3.3.0 PyQt5==5.15.6 PyQt5-sip==12.9.1 pyRFC3339==1.1 pyrsistent==0.18.1 python-apt==2.4.0+ubuntu4 python-dateutil==2.8.2 python-debian==0.1.43+ubuntu1.1 python-json-logger==2.0.7 python-Levenshtein==0.23.0 pythran==0.10.0 pytz==2022.1 pyxdg==0.27 PyYAML==5.4.1 pyzmq==25.1.1 QScintilla==2.11.6 qtconsole==5.4.4 QtPy==2.4.0 rapidfuzz==3.5.2 rasterio==1.3.9 referencing==0.30.2 reportlab==3.6.8 requests==2.31.0 rfc3339-validator==0.1.4 rfc3986-validator==0.1.1 rioxarray==0.15.0 rpds-py==0.10.4 ruff==0.1.1 scikit-image==0.22.0 scikit-learn==1.3.2 scipy==1.11.3 seaborn==0.13.0 SecretStorage==3.3.1 Send2Trash==1.8.2 setuptools==59.6.0 shapely==2.0.2 six==1.16.0 sniffio==1.3.0 snuggs==1.4.7 soupsieve==2.5 stack-data==0.6.3 sympy==1.9 systemd-python==234 tenacity==6.3.1 terminado==0.17.1 thefuzz==0.20.0 threadpoolctl==3.2.0 tifffile==2023.9.26 tinycss2==1.2.1 tomli==2.0.1 tornado==6.3.3 traitlets==5.11.2 typed-ast==1.4.3 types-aiofiles==0.1 types-annoy==1.17 types-appdirs==1.4 types-atomicwrites==1.4 types-aws-xray-sdk==2.8 types-babel==2.9 types-backports-abc==0.5 types-backports.ssl-match-hostname==3.7 types-beautifulsoup4==4.10 types-bleach==4.1 types-boto==2.49 types-braintree==4.11 types-cachetools==4.2 types-caldav==0.8 types-certifi==2020.4 types-characteristic==14.3 types-chardet==4.0 types-click==7.1 types-click-spinner==0.1 types-colorama==0.4 types-commonmark==0.9 types-contextvars==0.1 types-croniter==1.0 types-cryptography==3.3 types-dataclasses==0.1 types-dateparser==1.0 types-DateTimeRange==0.1 types-decorator==0.1 types-Deprecated==1.2 types-docopt==0.6 types-docutils==0.17 types-editdistance==0.5 types-emoji==1.2 types-entrypoints==0.3 types-enum34==1.1 types-filelock==3.2 types-first==2.0 types-Flask==1.1 types-freezegun==1.1 types-frozendict==0.1 types-futures==3.3 types-html5lib==1.1 types-httplib2==0.19 types-humanfriendly==9.2 types-ipaddress==1.0 types-itsdangerous==1.1 types-JACK-Client==0.1 types-Jinja2==2.11 types-jmespath==0.10 types-jsonschema==3.2 types-Markdown==3.3 types-MarkupSafe==1.1 types-mock==4.0 types-mypy-extensions==0.4 types-mysqlclient==2.0 types-oauthlib==3.1 types-orjson==3.6 types-paramiko==2.7 types-Pillow==8.3 types-polib==1.1 types-prettytable==2.1 types-protobuf==3.17 types-psutil==5.8 types-psycopg2==2.9 types-pyaudio==0.2 types-pycurl==0.1 types-pyfarmhash==0.2 types-Pygments==2.9 types-PyMySQL==1.0 types-pyOpenSSL==20.0 types-pyRFC3339==0.1 types-pysftp==0.2 types-pytest-lazy-fixture==0.6 types-python-dateutil==2.8.19.14 types-python-gflags==3.1 types-python-nmap==0.6 types-python-slugify==5.0 types-pytz==2021.1 types-pyvmomi==7.0 types-PyYAML==5.4 types-redis==3.5 types-requests==2.25 types-retry==0.9 types-selenium==3.141 types-Send2Trash==1.8 types-setuptools==57.4 types-simplejson==3.17 types-singledispatch==3.7 types-six==1.16 types-slumber==0.7 types-stripe==2.59 types-tabulate==0.8 types-termcolor==1.1 types-toml==0.10 types-toposort==1.6 types-ttkthemes==3.2 types-typed-ast==1.4 types-tzlocal==0.1 types-ujson==0.1 types-vobject==0.9 types-waitress==0.1 types-Werkzeug==1.0 types-xxhash==2.0 typing_extensions==4.8.0 tzdata==2023.3 ubuntu-drivers-common==0.0.0 ubuntu-pro-client==8001 ufoLib2==0.13.1 ufw==0.36.1 unattended-upgrades==0.1 unicodedata2==14.0.0 uri-template==1.3.0 urllib3==1.26.5 usb-creator==0.3.7 wadllib==1.3.6 wcwidth==0.2.8 webcolors==1.13 webencodings==0.5.1 websocket-client==1.6.3 wheel==0.37.1 widgetsnbextension==4.0.9 word2num==0.1.2 xarray==2023.10.1 xdg==5 xkit==0.0.0 zipp==1.0.0
Expected behavior
Sample graph
I'd expect the top node to be the first node, and subsequent nodes to be below. A possible (but not unique) output could be ['a', 'b', 'c', 'd', 'e']. It is not 100% clear because there aren't any arrows on the diagram and topological sort is usually on a directed acyclic graph.
Actual behavior
Output is from the bottom up. ['d', 'c', 'e', 'b', 'a']
I guess this has been misunderstood, current printing is bottom up and we need the printing from top to bottom so that will be the valid printing . i.e ['a', 'b', 'e', 'd', 'c']. Can you assign this task to me, I will solve this.
The code could also use some documentation. It took me a while to figure out whether or not it was incorrect because the directedness of the tree was not explicit even though it was implied. I was not familiar with the topic of topological sort, and I don't think that the code is instructive enough for someone who is looking for how-to perform the sort.
The pre written code was correct but it is sorting in the reverse order so I just manipulated that code and nothing new in that code so what sort of documentation I have to provide
The current printing is wrong because it is changing the order. In Topo sort if u->v then u should appear before v, so currently it is giving reverse order, so it is not true. So ordering is incorrect in current implementation.
The prewritten code prints ['d', 'c', 'e', 'b', 'a'] which you guys are saying wrong. After my implementation it is printing ['a', 'c', 'b', 'd', 'e'] which is correct as expected in the issue. It also follows topological sort rules considering top to down direction as in the issue.
Hi , I would like to take on this task. Could you please assign it to me?
I reviewed all open and linked PRs and not satisfied with any of them. I believe that correct implementation can be obtained by few changes from current one. Please do not mix mass refactoring with this fix. After this fix, it will be possible to improve and refactor the implementation in separate PRs (for example, add doctests - and this may require significant refactoring)
Please take a look at my solution. I've just changed the last line of code to reverse the print(sort). It is still topologically sorted, just not in the unique solution provided in the example.
