The Graph Traversal Programming Pattern (Part 1) - Graph Structures

In his presentation at WindyCityDB, Marko Rodriguez, discusses graph traversal patterns. This is the first part of a multi-part series that will discuss this presentation. Specifically in this posting we are going to discuss the various types of graph structures. We will be discussing graph databases and graph traversals in a following posts.

So what types of graph structures are there? It's an interesting question and one I did not know the answer to until this presentation. Before we can begin discussing the various graph structures we need a small primer.

Graph Primer

• Dots are vertices
• Lines are edges
• Dots and Lines make a Graph

Undirected Graph

• Vertices
  • All denote the same type of object
• Edges
  • All edges denote the same type of relationship
  • All edges denote a symmetric relationship
• Examples
  • Collaborator graph
  • Road graph

Directed Graph

• Vertices
  • All denote the same type of object
• Edges
  • All edges denote the same type of relationship
  • All edges denote a asymmetric relationship
• Primer
  • Directed edge is a line with an arrow
• Examples
  • Twitter follow graph
  • Web href-citation graph

Single-Relational Graphs

Both undirected and directed graphs are considered single relational graphs.

• All edges have the same meaning/type
• Perhaps the most common type of graph type

Limitations of a single relational graph:

• Only can express a single type of vertex
• Only can express a single type of edge
• In general are very limiting graph types

Multi-Relational Graphs

Obviously the opposite of a single-relational graph.

What are the gains with multi-relational graphs?

• Allows for explicit typing of edges
• Explicit typing allows for
  • edges to have different meanings
  • vertices to have different types

Property Graph

• Specialized graph which extends a multi-relational graph by adding key/value map to both edges and vertices
• Properties useful for expressing non-relational data
• Allows further refinement of the meaning of an edge
• Property graphs are the basis for other types of graphs

The entire presentation is shown below. We'll discuss graph databases on Monday.