topological sort returns reversed list

[megpay]

Repository commit

03a4251

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

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

[maitreepatel1110]

Hi , I would like to take on this task. Could you please assign it to me?

[megpay]

@maitreepatel1110 go ahead and create a PR with a fix

[Abdullah00110]

can i do?