Graph incidence list implementation

Question

I'm considering graph data structure implementations and am looking at the "incidence list" representation. There is a brief description of it here:

Incidence list

So each vertex in the graph stores a list of those edges upon which it is incident.

Given that my graph is a directed graph, I'm not very clear from this description on a couple of points:

1. Does the graph itself also store a list of all edges?
2. Do vertices only store outgoing edges, or incoming and outgoing?
3. If both, are they in separate lists?

I'm quite familiar with the other graph representations (adjacency list, adjacency matrix, edge list, incidence matrix), so this isn't a question about graph implementations in general, just this particular one.

Any pointers would be much appreciated.

Settlement

Answer 1

Having researched and thought about it further, I've come to the conclusion that there isn't an incidence list graph data strucure. I think that the Wikipedia article was the product of some confusion in the author's mind. Thanks to everyone who read this question and spent any time on it.

Armand

Settlement

Answer 2

I know I'm perhaps raising an old question from the dead, but I felt it appropriate to comment.

You can make an incidence list graph structure, and you can also tweak it for digraphs.

Consider a LinkedList<Vertex> object and a LinkedList<Edge> object. This would let you iterate over all edges and all vertices, but contains no information about how everything is connected.

Say we add, then, several LinkedList<Connection> objects. In fact, one for each Vertex. A Connection is simply where an Edge and a Vertex Meet. Thus an Edge will have two Connection objects (For an undirected graph), and a Vertex will have one LinkedList<Connection> object, representing connections to every Edge that is connected to it. This is, in essence, an incidence list.

You can modify this to represent a digraph if you delete some of those Connection objects. More specifically, you'll have to choose where to not have those references. You might choose to delete a Connectionfrom the associated LinkedList<Connection> if you don't want to be able to see an Edge from a Vertex (for the example above, N2 would have an empty LinkedList<Connection>). You might instead choose to make the references optional on the Edge(For the example above, E1 would have one Connection pointing at N2 and one Connection null, allowing traversal from E1 to N2, but not back onto N1. Your choice of how to implement this would be entirely up to you. One is more intuitive - Edges are directed, so removing the connections on Edges to dictate which way they go seems logical. The other might seem a bit more complex at first, but will stop you needlessly hopping onto edges that lead nowhere when doing breadth first and depth first searches.

In point form:

1. In my implementations of a incidence list, I have. Do you need to for your implementation?

2. Strictly speaking, you could get by storing only outgoing edges. However, backtracking algorithms might benefit from being able to backtrack along references they traveled. You can implement around this, of course, with some sort of history, so it's probably not much of a consideration.

3. If you do both, you would probably need some way to differentiate whether it's incoming or outgoing. Whether that's by having two LinkedList<Connection> objects on the Vertex, or by having a boolean pointingToVertex primitive on Connection, or whatever. Maybe your Edge would be directed, and undirected edges would be made of two edges pointing opposite ways. Considerations to be made depending on the needs of your structure.

Eagle

Answer 3

I implemented a incidence list in the following way and couldn't find any problem for undirected graphs. I implemented several graph topology algorithms too.

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

Using a map of sets guarantee O(1) for vertices lookup and amortized O(1) complexity for edge insertion and deletions. Keeping an incidence list of edges instead of an adjacent list of vertices is just a way to carry some particular information of the edge itself. This is useful for abstract algorithms too when, for example, you associate a weight to the edges.

EDIT:

I have updated the talks on wikipedia for the "incidence list" topic.

Predicant

Answer 4

Incidence list is another name for adjacency list.

1. You may or may not store edges separately in the graph itself. It's your choice. Usually if you link the edges in the edge list using Java references, you don't need to store the edges separately. But you might prefer centralized storage of edges and link edges using edge indices instead of Java references. This way is more natural for serialization of the graph to external storage since edge indices would be written as is while the Java references need to be converted into indices first.

class Graph {
    // vertex[i] points to a list of arcs from vertex i
    private Arc[] vertex; 

    private static final class Arc {
        // whatever data you need to attach to the arc
        private int data;
        // end vertex index
        private int arcEnd;
        // a reference to the next arc in the vertex arc list
        private Arc next;
    }
}

class Graph {
    // an array of all arcs
    private Arc[] arcs;
    // the same as before, but instead of references we use indices in the arcs array
    private int[] vertex;

    private static final class Arc {
        private int data;
        private int arcEnd;
        private int next;
    }
}

2. It's as you wish. For a typical graph algorithm it's enough to store outgoing edges.

3. Yes.

Clamorous