Skip to content

topological sort returns reversed list #12192

@megpay

Description

@megpay
Contributor

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
Screenshot from 2024-10-19 14-00-00

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

Activity

Davda-James

Davda-James commented on Oct 20, 2024

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

linked a pull request that will close this issue on Oct 20, 2024
megpay

megpay commented on Oct 20, 2024

@megpay
ContributorAuthor

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

megpay commented on Oct 20, 2024

@megpay
ContributorAuthor

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

vedprakash226

vedprakash226 commented on Oct 20, 2024

@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

Davda-James commented on Oct 20, 2024

@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

megpay commented on Oct 20, 2024

@megpay
ContributorAuthor

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

vedprakash226

vedprakash226 commented on Oct 20, 2024

@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

LEO-LI-88 commented on Oct 22, 2024

@LEO-LI-88

I'm testing.

maitreepatel1110

maitreepatel1110 commented on Oct 22, 2024

@maitreepatel1110

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

megpay

megpay commented on Oct 25, 2024

@megpay
ContributorAuthor

@maitreepatel1110 go ahead and create a PR with a fix

linked a pull request that will close this issue on Oct 27, 2024
linked a pull request that will close this issue on Oct 27, 2024
Abdullah00110

Abdullah00110 commented on Nov 1, 2024

@Abdullah00110

can i do?

Aditya-A-Chavan

Aditya-A-Chavan commented on Jan 19, 2025

@Aditya-A-Chavan

Issue still open? mind if i give it a try?

Sh950

Sh950 commented on Jan 22, 2025

@Sh950

Can I be assigned to this?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Participants

      @megpay@vedprakash226@Sh950@Aditya-A-Chavan@maitreepatel1110

      Issue actions

        topological sort returns reversed list · Issue #12192 · TheAlgorithms/Python