O'Reilly logo

Graph Algorithms by Amy E. Hodler, Mark Needham

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 2. Graph Theory and Concepts

In this chapter, we set the framework and cover terminology for graph algorithms. The basics of graph theory are explained, with a focus on the concepts that are most relevant to a practitioner.

We’ll describe how graphs are represented, and then explain the different types of graphs and their attributes. This will be important later, as our graph’s characteristics will inform our algorithm choices and help us interpret results. We’ll finish the chapter with an overview of the types of graph algorithms detailed in this book.

Terminology

The labeled property graph is one of the most popular ways of modeling graph data.

A label marks a node as part of a group. In Figure 2-1, we have two groups of nodes: Person and Car. (Although in classic graph theory a label applies to a single node, it’s now commonly used to mean a node group.) Relationships are classified based on relationship type. Our example includes the relationship types of DRIVES, OWNS, LIVES_WITH, and MARRIED_TO.

Properties are synonymous with attributes and can contain a variety of data types, from numbers and strings to spatial and temporal data. In Figure 2-1 we assigned the properties as name-value pairs, where the name of the property comes first and then its value. For example, the Person node on the left has a property name: "Dan", and the MARRIED_TO relationship has a property of on: Jan 1, 2013.

A subgraph is a graph within a larger graph. Subgraphs are useful as a filters ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required