Alternative graph data structures

Question

Are there any graph implementation data structures beyond the standard adjacency list/matrix ones? If so, what are they?

I welcome experimental ones as well as highly specialized ones.

A little background: I'm developing an algorithm that relies heavily on graph operations, so I'm doing research in graph implementation. I'm not looking for out-of-the-box solution, but rather for additional material in hope to combine my findings into something that will optimize my algorithm.

An adjacency matrix is not suitable for me in its core form, because it is costly to resize. In my environment, vertices are expected to be frequently added/removed.

An adjacency list is a bit better approach. Yet, it lacks the ability to efficiently cross-reference information from different nodes. Further, the graph is weighted, so I need immediate neighbors sorted for a fast search. However, the weights are also dynamic: they change frequently (are explicitly updated) and decay with time (change implicitly based on the type/time of the last operation).

The graph is expected to have somewhere between 50 and 100 vertices. Once a new vertex is added, it will form edges with some or all of the other vertices, depending on its life time.

I've tried using sorted lists, but still haven't found any efficient way to accommodate all the criteria listed above. I also considered hash-tables, similar to the answer below, but they don't solve the problem with sorting.

Answer 1

Here are some examples of slightly different approaches:

Hash-table

Key into hash-table is a vertex, value is a list of vertices it is connected to, the edge is thus a relation between the key and the element of the value in the hash-table. This is not so different from adjacency list except that testing for presence of the vertex will be faster, but it will take more spece to store the graph.

This, obviously, describes a directed graph. You could include the reversed edges to make it work as undirected graph.

Example (JavaScript):

function graph() {
    var vertices = {}, g = { vertices: vertices };
    g.getVertex = function (vertex) {
        return vertices[vertex];
    };
    g.getEdge = function (from, to) {
        var adjacent = vertices[from], result;
        if (adjacent.indexOf(to) > -1) result = [from, to];
        return result;
    };
    g.addEdge = function (from, to) {
        var edges = vertices[from] || [];
        edges.push(to);
        vertices[from] = edges;
    };
    [].slice.call(arguments).forEach(function (edge) {
        g.addEdge.apply(g, edge);
    });
    return g;
}
graph([1, 2], [1, 3], [2, 1], [2, 3], [3, 5], [3, 6], [3, 4],
      [4, 7], [5, 2], [5, 6], [6, 3], [6, 7]);
// { vertices: 
//    { '1': [ 2, 3 ],
//      '2': [ 1, 3 ],
//      '3': [ 5, 6, 4 ],
//      '4': [ 7 ],
//      '5': [ 2, 6 ],
//      '6': [ 3, 7 ] },
//   getVertex: [Function],
//   getEdge: [Function],
//   addEdge: [Function] }

Graph-proper data structure

We define vertex as a tuple of the value and a list of edges from this vertex to other vertices it is directly connected to. This is a little bit more compact than the hash-table, but testing whether vertex is in a graph becomes linear (just as in adjacency list / matrix). Same as before we can add edges in the opposite direction to make this graph undirected. This is different from adjacency list in that retrieving all adjacent vertices to a given vertex is a constant time operation, while in the list it is linear in time. Adjacency matrix would also give constant time for this, but will use more space, especially if a graph is sparse.

Example (Prolog):

:- use_module(library(record)).

:- record vertex(value, arcs=[_ | _]).

lookup(X, [X | _]).
lookup(X, [Y | Xs]) :- X \== Y, lookup(X, Xs).

instantiated(Goal, [X | _], []) :- \+ call(Goal, X).
instantiated(Goal, [X | Xs], [X | Ys]) :- call(Goal, X), instantiated(Goal, Xs, Ys).

vertex_instantiated(Vertex) :-
    make_vertex([], Vertex),
    vertex_value(Vertex, Value),
    ground(Value).

find_vertex_helper(Value, _, Vertex) :- vertex_value(Vertex, Value).
find_vertex_helper(V1, Cache, V2) :-
    vertex_arcs(V2, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    subtract(InstArcs, Cache, FilteredArcs),
    union(Cache, InstArcs, NewCache),
    findnsols(1, V, (member(V, FilteredArcs),
                     find_vertex_helper(V1, NewCache, V)),
              [V2]).

find_vertex(_, [], _) :- !, fail.
find_vertex(Value, [V | Graph], Vertex) :-
    vertex_value(V, Value), Vertex = V
    ;
    vertex_arcs(V, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    include(find_vertex_helper(Value, []), InstArcs, [Vertex])
    ;
    find_vertex(Value, Graph, Vertex).

find_or_create_vertex(Value, Vertex, Graph, Graph) :-
    find_vertex(Value, Graph, Vertex), !.
find_or_create_vertex(Value, Vertex, OldGraph, [Vertex | OldGraph]) :-
    make_vertex([value(Value)], Vertex).

add_arc(From, To, OldGraph, NewGraph) :-
    find_or_create_vertex(From, VertexFrom, OldGraph, Graph1),
    find_or_create_vertex(To, VertexTo, Graph1, NewGraph),
    vertex_arcs(VertexFrom, Arcs),
    lookup(VertexTo, Arcs).

make_graph_helper([], Graph, Graph).
make_graph_helper([From-To | Vs], GraphIn, GraphOut) :-
    add_arc(From, To, GraphIn, NewGraph),
    make_graph_helper(Vs, NewGraph, GraphOut).

make_graph(Vs, Graph) :- make_graph_helper(Vs, [], Graph).

make_graph([x1-x2, x1-x3, x2-x1, x2-x3, x3-x5, x3-x6, x3-x4,
            x4-x7, x5-x2, x5-x6, x6-x3, x6-x7], G).
/*    G = [vertex(x7, [_G3910|_G3911]),
           vertex(x4, [vertex(x7, [_G3910|_G3911])|_G3891]),
           _S1, _S2,
           vertex(x3, [_S2, _S1, vertex(..., ...)|...]),
           vertex(x2, [_S3, vertex(..., ...)|...]), _S3],
           % where
          _S1 = vertex(x6, [...]),
          _S2 = vertex(x5, [...]),
          _S3 = vertex(x1, [...]) */