The Graph ADT

The Königsberg bridge problem (HSM Ch.6.1.1, Fig.6.1)
Graphs (HSM Ch.6.1)
- Definition (HSM Ch.6.1.2, Fig.6.2-3)
- Applications
  - Mimimal cost communication networks
  - Project planning
  - The travelling salesman
  - Natural language processing (Check out Altavista'a translation page)
  - Circuit layouts
- Terminology (HSM Ch.6.1.2, Fig.6.2-5)
  - Graphs and digraphs (HSM Fig.6.2)
  - Complete graphs (HSM Fig.6.2a)
    - Edges in a complete graph = n(n-1)/2
  - Incidence, adjacency, degree
    - Edges = Sum(degree) / 2
  - Subgraphs (HSM Fig.6.4)
  - Paths, cycles, and trees
- Other types of graphs
  - Hypergraphs have edges with multiple ends
  - Loops
  - Multigraphs
The Graph ADT (HSM ADT.6.1)
Graph Representation (HSM Ch.6.1.3)
- Adjacency matrices (HSM Ch.6.1.3.1, Fig.6.7)
  - Space is O(n²), even taking advantage of symmetry
  - Some simple algorithms are O(n), most algorithms are O(n²)
  - Sparse graph algorithms should take at most O(n+e)
- Adjacency lists (HSM Ch.6.1.3.2, Fig. 6.8)
  - Space is O(n+e)
  - Some simple algorithms are O(vertex degree), most algorithms are O(n+e)
  - For directed graphs, some simple algorithms become O(n+e) instead of O(vertex degree)
- Inverted adjacency lists (HSM Fig.6.10)
  - For directed graphs, edges incident to are needed
- Adjacency multilists (HSM Ch.6.1.3.3, Fig.6.12)
  - For undirected graphs
  - Solve the problem of multiple edge representation
  - Space is O(n+e)
  - Some simple algorithms are O(vertex degree), most algorithms are O(n+e)
- Orthogonal adjacency lists (HSM Fig.6.11)
  - For directed graphs
  - Space is O(n+e)
  - Some simple algorithms are O(vertex degree), most algorithms are O(n+e)
- Weighted edges (HSM Ch.6.1.3.4)
  - Adjacency matrices
  - Adjacency lists and variants
- Edge threads

The LEDA Library

The LEDA manual

Compilation is sensitive. Use this pattern:

g++ YourCode.cpp -I/mnt/disk1/LEDA-3.8a/incl -L/mnt/disk1/LEDA-3.8a -lG -lL

Exercises

Graphs: HSM Ch.6.1, exercise 1-2.
Graph Representation: HSM Ch.6.1, exercise 5-6.

Lab Tasks

Exam Style Questions

Draw the {adjacency matrix,adjacency list,Inverted adjacency list, adjacency multilist,orthogonal adjacency list,weighted adjacency matrix} representation of this graph.
[Picture of some graph, make up your own :-]