New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Edge List representation intended in place of Adjacency List. #16

Open

aroonalok opened this issue Apr 4, 2022 · 0 comments

aroonalok commented Apr 4, 2022

In the section The challenges of using graphs in machine learning, a paragraph starts with the sentence:

One elegant and memory-efficient way of representing sparse matrices is as adjacency lists.

From the representation described later, it is clear that an Edge List representation of the graph is meant.

Also from the side text:

Another way of stating this is with Big-O notation, it is preferable to have 𝑂(𝑛𝑒𝑑𝑔𝑒𝑠), rather than 𝑂(𝑛2𝑛𝑜𝑑𝑒𝑠).

It is confirmed that the Edge List representation is meant here as an Adjacency List representation takes O(V+E) space.

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