## Directed and Undirected Graphs

### What Is a Graph?

A graph is a collection of *nodes* and *edges* thatrepresents relationships:

**Nodes**are verticesthat correspond to objects.**Edges**are the connectionsbetween objects.The graph edges sometimes have

**Weights**,which indicate the strength (or some other attribute) of each connectionbetween the nodes.

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

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

Airports — The graph nodes are airports, andthe 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. This figure 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. This figure shows a simple directed graph with three nodes and two edges.

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

#### Self-loops and Multigraphs

Graphs created using `graph`

and `digraph`

can have one or more *self-loops*, which are edges connecting a node to itself. Additionally, graphs can have multiple edges with the same source and target nodes, and the graph is then known as a *multigraph*. A multigraph may or may not contain self-loops.

For the purposes of graph algorithm functions in MATLAB, a graph containing a node with a single self-loop is not a multigraph. However, if the graph contains a node with *multiple* self-loops, it is a multigraph.

For example, the following figure shows an undirected multigraph with self-loops. Node A has three self-loops, while node C has one. The graph contains these three conditions, any one of which makes it a multigraph.

Node A has three self-loops.

Nodes A and B have five edges between them.

Nodes A and C have two edges between them.

To determine whether a given graph is a multigraph, use the ismultigraph function.

### Creating Graphs

The primary ways to create a graph include using an adjacency matrix or an edge list.

#### Adjacency Matrix

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

When you use

`graph`

to create an undirected graph, the adjacency matrix must be symmetric. In practice, the matrices are frequently triangular to avoid repetition. To construct an undirected graph using only the upper or lower triangle of the adjacency matrix, use`graph(A,'upper')`

or`graph(A,'lower')`

.When you use

`digraph`

to create a directed graph, the adjacency matrix does not need to be symmetric.For large graphs, the adjacency matrix contains manyzeros and is typically a sparse matrix.

You cannot create a multigraph from an adjacency matrix.

For example, consider this undirected graph.

You can represent the graph with this adjacency matrix:

$$\left(\begin{array}{ccc}0& 1& 2\\ 1& 0& 3\\ 2& 3& 0\end{array}\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}.$$

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)

G = graph with properties: Edges: [3×2 table] Nodes: [3×1 table]

You can use the `graph`

or `digraph`

functions to create a graph using an adjacency matrix, or you can use the adjacency function to find the weighted or unweighted sparse adjacency matrix of a preexisting graph.

#### Edge List

Another way to represent the information in a graph is by listing all of the edges.

For example, consider the same undirected graph.

Now represent the graph by the edge list

$$\begin{array}{l}\text{EdgeWeight}\\ \begin{array}{cc}\begin{array}{c}(A,B)\\ (A,C)\end{array}& \begin{array}{c}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}& 1\end{array}& \end{array}& \end{array}\\ \begin{array}{cc}\begin{array}{cc}\begin{array}{cc}& 2\end{array}& \end{array}& \end{array}\end{array}\\ (B,C)& \begin{array}{cc}\begin{array}{cc}\begin{array}{cc}& 3\end{array}& \end{array}& \end{array}\end{array}\end{array}$$

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. If the graph had disconnected nodes, they would not be found in the edge list, and would have to be specified separately.

In MATLAB, the list of edges is separated by column into *source* nodesand *target* nodes. For directed graphs the edgedirection (from source to target) is important, but for undirectedgraphs the source and target node are interchangeable. One way toconstruct this graph using the edge list is to use separate inputsfor 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);

Both `graph`

and `digraph`

permit construction of a simple graph or multigraph from an edge list. After constructing a graph, `G`

, you can look at the edges (and their properties) with the command `G.Edges`

. The order of the edges in `G.Edges`

is sorted by source node (first column) and secondarily by target node (second column). For undirected graphs, the node with the smaller index is listed as the source node, and the node with the larger index is listed as the target node.

Since the underlying implementation of `graph`

and `digraph`

depends on sparse matrices, many of the same indexing costs apply. Using one of the previous methods to construct a graph all at once from the triplet pairs `(source,target,weight)`

is quicker than creating an empty graph and iteratively adding more nodes and edges. For best performance, 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. Therefore, you always can refer to them by their numeric *node index*.

If the graph has node names (that is, `G.Nodes`

containsa variable `Name`

), then you also can refer to thenodes in a graph using their names. Thus, named nodes in a graph canbe 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 refers to both the node index and the node name.

For convenience, MATLAB remembers which type of node ID you use when you call 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 or string array).

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

p1 = 1×3 cell array {'a'} {'c'} {'d'}

Use `findnode`

to find the numeric node IDfor a given node name. Conversely, for a given numeric node ID, indexinto `G.Nodes.Name`

to determine the correspondingnode name.

### Modify or Query Existing Graph

After you construct a `graph`

or `digraph`

object, you can use a variety of functions to modify the graph structure or to determine how many nodes or edges the graph has. This table lists some available functions for modifying or querying `graph`

and `digraph`

objects.

addedge | Add one or more edges to a graph |

rmedge | Remove one or more edges from a graph |

addnode | Add one or more nodes to a graph |

rmnode | Remove one or more nodes from a graph |

findnode | Locate a specific node in a graph |

findedge | Locate a specific edge in a graph |

numnodes | Find the number of nodes in a graph |

numedges | Find the number of edges in a graph |

edgecount | Number of edges between specified nodes |

flipedge | Reverse the direction of directed graph edges |

reordernodes | Permute the order of the nodes in a graph |

subgraph | Extract subgraph |

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

## See Also

graph | digraph

## Related Topics

- Modify Nodes and Edges of Existing Graph
- Add Graph Node Names, Edge Weights, and Other Attributes
- Graph Plotting and Customization

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- Deutsch
- English
- Français

- United Kingdom (English)

Contact your local office