Titan Graph Databases with Cassandra - Beginning Apache Cassandra Development - page 169

Graph theory can be traced back to 1736. A graph is a data structure that consists of
vertices/nodes and edges. A graph can have zero or multiple edges. A graph without
edges is also referred to as an empty graph.
A vertex is a graph node that is connected to other graph nodes/vertices via edges.
Each edge is an arc or line which connects multiple vertices.
In computer science, a graph can be categorized in many ways. A few of the popu-
lar ones include:

• Simple and nonsimple graphs

• Directed and undirected graphs

• Cyclic and acyclic graphs

Simple and Nonsimple Graphs

A simple graph, as the name suggests, is a basic graph having at most one edge
between two vertices. It's a graph that has no self loops but multiple nodes (see Figure
7-1a ) . On the other hand, graphs with self loops and multiple edges are nonsimple
graphs (see Figure 7-1b ). Here, a self loop is an edge which connects to a vertex itself.
A graph having multiple edges between the same nodes is also called a multigraph or
parallel graph. The graph shown in Figure 7-1c is a multigraph and a self-loop graph. It
contains a self loop on vertex A and has multiple edges between vertex A and B.

Figure 7-1 . a) On the left, a simple graph; b) a nonsimple graph in the middle; and c) a multigraph with a self loop

Directed and Undirected Graphs

Graphs with multiple nodes and directed edges are directed graphs (see Figure 7-2a ) .
Undirected graphs are the graphs having edges without direction (see Figure 7-2b ).