Documentation

What Is a Graph?

A graph is a collection of nodes and edges that represents relationships:

• Nodes are vertices that correspond to objects.

• Edges are the connections between objects.

• The graph edges sometimes have Weights, which indicate the strength (or some other attribute) of each connection between the nodes.

These definitions are general, as the exact meaning of the nodes and edges in a graph depends on the specific application. For instance, you can model the friendships in a social network using a graph. The graph nodes are people, and the edges represent friendships. The natural correspondence of graphs to physical objects and situations means that you can use graphs to model a wide variety of systems. For example:

• The Internet — The graph nodes are computers, and the edges are network connections between computers.

• A brain — The graph nodes are neurons, and the edges represent neuron connections.

• Web page linking — The graph nodes are web pages, and the edges represent links between pages.

• Airports — The graph nodes are airports, and the edges represent flights between airports.

In MATLAB^®, the graph and digraph functions construct objects that represent undirected and directed graphs.

• Undirected graphs have edges that do not have a direction. The edges indicate a two-way relationship, in that each edge can be traversed in both directions. The figure below shows a simple undirected graph with three nodes and three edges.

  

• Directed graphs have edges with direction. The edges indicate a one-way relationship, in that each edge can only be traversed in a single direction. The figure below shows a simple directed graph with three nodes and two edges.

  

The exact position, length, or orientation of the edges in a graph illustration typically do not have meaning. In other words, the same graph can be visualized in several different ways by rearranging the nodes and/or distorting the edges, as long as the underlying structure does not change.

Graphs created using graph and digraph can have self-loops (an edge connecting a node to itself). However, graphs cannot have multiple edges with the same source and target nodes.

Creating Graphs

The primary ways to create a graph are to use an adjacency matrix or an edge list.

Adjacency Matrix

One way to represent the information in a graph is with a square adjacency matrix. The nonzero entries in an adjacency matrix indicate an edge between two nodes, and the value of the entry indicates the weight of the edge. The diagonal elements of an adjacency matrix are typically zero, but a nonzero diagonal element indicates a self-loop, or a node that is connected to itself by an edge.

• The adjacency matrix for undirected graphs created by graph must be symmetric. Although, in practice the matrices are frequently triangular to avoid repetition. Use graph(A,'upper') or graph(A,'lower') to construct an undirected graph using only the upper or lower triangle of the adjacency matrix.

• The adjacency matrix for a directed graph created by digraph does not need to be symmetric.

• For large graphs, the adjacency matrix contains many zeros and is typically a sparse matrix.

For example, consider this undirected graph.

You can represent the graph with this adjacency matrix.

To construct the graph in MATLAB, input:

A = [0 1 2; 1 0 3; 2 3 0];
node_names = {'A','B','C'};
G = graph(A,node_names)

You can use adjacency matrices to create a graph using the graph or digraph functions, or you can use the adjacency function to find the unweighted sparse adjacency matrix of a pre-existing graph.

Edge List

Another way to represent the information in a graph is by listing all of the edges. For connected graphs, the graph nodes are implied by the list of the graph edges. However, some graphs have disconnected nodes that need to be listed separately.

For example, consider the same undirected graph.

Now represent the graph by the edge list

From the edge list it is easy to conclude that the graph has three unique nodes, A, B, and C, which are connected by the three listed edges.

In MATLAB, the list of edges is separated by column into source nodes and target nodes. For directed graphs the edge direction (from source to target) is important, but for undirected graphs the source and target node are interchangeable. One way to construct this graph using the edge list is to use separate inputs for the source nodes, target nodes, and edge weights:

source_nodes = {'A','A','B'};
target_nodes = {'B','C','C'};
edge_weights = [1 2 3];
G = graph(source_nodes, target_nodes, edge_weights)

Another way to construct a graph from the edge list is by creating a table with the appropriate variables. When using this method, the first variable in the table must be a two column matrix or cell array of character vectors named EndNodes. To construct this graph using a table, input:

EdgeTable = table({'A' 'B'; 'A' 'C'; 'B' 'C'},[1 2 3]', ...
    'VariableNames',{'EndNodes','Weight'});
G = graph(EdgeTable)

Both graph and digraph permit construction of a graph from the edge list. After constructing a graph, G, you can look at the edges (and any properties they might have) with G.Edges. The order of the edges in G.Edges is sorted by source node (first column) and secondarily by target node (second column).

Since the underlying implementation of graph and digraph depends on sparse matrices, many of the same indexing costs apply. Ultimately, it is quickest to construct a graph all at once from the triplet pairs (source,target,weight) using one of the aforementioned methods, instead of creating an empty graph and iteratively adding more nodes and edges. Performance is best when you minimize the number of calls to graph, digraph, addedge, addnode, rmedge, and rmnode.

Graph Node IDs

By default, all of the nodes in a graph created using graph or digraph are numbered. Thus, it's always an option to refer to the nodes in a graph by their numeric node index.

If the graph has node names (that is, G.Nodes contains a variable Name), then you also can refer to the nodes in a graph using their names. Thus, named nodes in a graph can be referred to by either their node indices or node names. For example, node 1 can be called, 'A'.

The term node ID encompasses both aspects of node identification. The node ID of a node refers to both the node index and the node name.

For convenience, MATLAB remembers which type of node ID you use in calling most graph functions. So if you refer to the nodes in a graph by their node indices, most graph functions return a numeric answer that also refers to the nodes by their indices.

A = [0 1 1 0; 1 0 1 0; 1 1 0 1; 0 0 1 0];
G = graph(A,{'a','b','c','d'});
p = shortestpath(G,1,4)

p =

     1     3     4

However, if you refer to the nodes by their names, then most graph functions return an answer that also refers to the nodes by their names (contained in a cell array of character vectors).

p1 = shortestpath(G,'a','d')

p1 = 

    'a'    'c'    'd'

Use findnode to find the numeric node ID for a given node name. Conversely, for a given numeric node ID, index into G.Nodes.Name to determine the corresponding node name.

Modify an Existing Graph

After you construct a graph or digraph object, you can use a variety of functions to modify the graph structure. The table lists the available graph manipulation functions, which modify the nodes and edges of either graph or digraph objects.

See Modify Nodes and Edges of Existing Graph for some common graph modification examples.