Talk:Incidence list

Potentially Useful

If Incidence List / Incidence Map representations allow lookup in graph data with lower big-O algorithmic complexity they have advantages over adjacency lists. Graph Traversal algorithms are in heavy use circa 2019 at google (pagerank), facebook (friend suggestions) and in AI Knowledge Graphs this could accelerate NLP algorithms, and systems biology. Object Oriented graphs might trade space for time

Untitled

Citing "Data Structures and Algorithms in Java":

"The adjacency list structure includes all the structural components of the edge list structure plus the following: • A vertex object v holds a reference to a collection I(v), called the incidence collection of v, whose elements store references to the edges incident on v. • The edge object for an edge e with end vertices v and w holds references to the positions (or entries) associated with edge e in the incidence collections I(v)and I(w). Traditionally, the incidence collection I(v) for a vertex v is a list, which is why we call this way of representing a graph the adjacency list structure. The adjacency list structure provides direct access both from the edges to the vertices and from the vertices to their incident edges."

"edge list structure" is just the usual pair G = (V,E) where V = list/set of vertices, E = list/set of edges

The only differences with old representations here is that an edge is an object and not something abstract. This little differences, that can be conceived by everybody, not just Goodrich and Tamassia, makes the difference between an adjacency list and an incidence list. The "incidence list" term may have been coined by the wikipedia community itself. Nothing strange, IMO. I like it :)

I use the following custom representation for an undirected graph (may work for directed too):

HashMap<VertexT, HashSet<EdgeT>> incidenceMap

I call it an Incidence map. It merge the concept of an incidence list and recommendations from Guido van Rossum, cited even in the adjaceny list wikipedia page, to store vertices and adjacents in a dictionary. With respect for whom who introduced graph theory we are still speaking of adjacency lists and matrices, when in fact we should renew these concepts with more concrete integration with existent data structures.

Ceztko (talk) 15:27, 8 January 2011 (UTC)

Doesn't exist?

I can find no primary source that indicates that there is such a data structure as an "incidence list". The article claims that it was "conceived by Goodrich and Tamassia", but it does not occur in the contents page or index of their book (Data Structures and Algorithms in Java).

The only detailed description of an "incidence list" implementation I could find is on this page -Assessed Practical - but the author is quite evidently mistaken and is describing an adjacency list.

Reflecting upon the "incidence list" as it is described in the article I can see it having no advantages at all over an adjacency list, while being more complex to implement.

I would recommend deleting this article.

A Aleg (talk) 13:10, 11 October 2010 (UTC)

Initial version

I'm rather surprised that there was no article on incidence list (other than a deletion log), so I created it. It's written from the computer science perspective, hence the comp-sci-stub. If anyone has more info from the mathematics side, please edit.

Also, feel free to butcher the ugly example. An ideal example would involve a picture as well.

--LazyEditor 07:12, 19 June 2006 (UTC)

Variation

Graph theory#List structures explains a different "incidence list", which, instead of being indexed by the vertices, is indexed by the edges: {e1: (v1, v2), e2: (v3, v4)}. It makes complete sense, but I could not find any reference to it (instead, I found references to "incidence lists" which are really adjacency lists). LazyEditor 07:12, 19 June 2006 (UTC)