Adjacency List Based Graph Tutorial
How does the GraphAdjList<K,E> work?
A graph is a set of vertices connected by edges. Unlike tree structures, a
vertex can be an ancestor or a child and can have multiple emanating edges.
In fact, a tree structure is just a special case of a graph.
Bridges represents graph structures in one of two ways: either using an
adjacency list representation or an adjacency matrix representation.
Access to the vertices is similar to indexing into an array (O(1) complexity).
The main difference in our implementation is that vertex ids can be
numerical values or strings;
BRIDGES implements constant access to vertices using maps (in Java, C++
and Python).
In the adjacency list representation, the GraphAdjList is holding a Map
of vertices, each of which is associated with a linked list of Edges.
These Edge vertices
are of type SLElement<E> with the generic object E used to hold edge information (terminating vertex, edge weight, etc). Finally, graph
vertices and edges can have application specific data objects associated
with them.
The graph class provides some convenient methods to add vertices
and edges
(GraphAdjList::addVertex(), GraphAdjList::addEdge()) to build the graph,
and to access or set visual attributes. There are also methods to
iterate through the outgoing edges of a vertex, iterators, all of which
will be demonstrated in this tutorial.
See also
This tutorial gives an introduction to the usage of adjacendy list. You can find the complete documentation of the features in the Doxygen documentation of the following classes and functions:
- GraphAdjList [Java] [C++] [Python]
- Edge [Java] [C++] [Python]
- SLelement [Java] [C++] [Python]
- Element [Java] [C++] [Python]
- ElementVisualizer [Java] [C++] [Python]
- LinkVisualizer [Java] [C++] [Python]
- Color [Java] [C++] [Python]
1. Getting Started: Build a Barebones Adjacency List Based Graph
In the first part of the tutorial, we will create a graph with nodes containing string labels, add some edges between nodes, provide BRIDGES a handle to the data structure and visualize the graph.
If you follow the URL given to you when the application runs, it will get to to the Bridges webpage that shows your output. You do not need to be logged into your BRIDGES account to see the output. If you are logged into your account, the output will show up in your gallery.
Make sure that you can run the basic tutorial. Here is the code for this tutorial. The visualization follows that. Hit the 'l' button to turn on the labels.
2. What Visual Attributes are supported for Graphs?
The graph you created in the first part of the tutorial uses default attributes and is pretty boring, but it gives you the basic structure of a BRIDGES program.
Next, we will style the graph we just created. For graphs, you can set the shape, color, opacity and label of the nodes (vertices), and for the links, color, opacity, thickness and label. Check out the links to the classes (listed above) that supports these attributes and also details the possible colors and shapes you can use and how to specify them.
The following code styles the graph we created in part 1 and adds visual attributes. The visualization follows that.
3. Advanced Features.
In the last part of this tutorial, we show some advanced features with graphs. An operation that is frequently required in graph algorithms is to traverse through the edges from a given vertex. The convenience method outgoingEdgeSetOf() combined with iterators makes it easy to perform this operation. We demonstrate multiple ways of doing the traversal in this tutorial. These features make it more intuitive and convenient to traverse the data structure. A similar feature is provided to list the vertices in the graph, using the keySet() method.
The following code illustrates these advanced features of graphs. The visualization follows that. Hit the 'l' button to turn on the labels.
Well done! You’ve just created your first Bridges Graph!
Going Further
Check Bridges assignment page for graph based assignments