topological sort returns reversed list

[megpay]

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']

[Jenniferab5]

@[]()

[Davda-James]

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.

[megpay]

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.

[megpay]

If @Davda-James isn't planning on fixing, I will do it.

[vedprakash226]

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

[Davda-James]

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.

[megpay]

@vedprakash226 Docstrings/comments would be nice and doctests as well.

[vedprakash226]

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.

[LEO-LI-88]

I'm testing.