Graph and Network Algorithms

Directed and undirected graphs, network analysis

Graphs model the connections in a network and are widely applicable to a variety of physical, biological, and information systems. You can use graphs to model the neurons in a brain, the flight patterns of an airline, and much more. The structure of a graph is comprised of “nodes” and “edges”. Each node represents an entity, and each edge represents a connection between two nodes. For more information, see Directed and Undirected Graphs.

Functions

expand all

 graph Graph with undirected edges digraph Graph with directed edges
 addnode Add new node to graph rmnode Remove node from graph addedge Add new edge to graph rmedge Remove edge from graph flipedge Reverse edge directions numnodes Number of nodes in graph numedges Number of edges in graph findnode Locate node in graph findedge Locate edge in graph edgecount Number of edges between two nodes reordernodes Reorder graph nodes subgraph Extract subgraph
 centrality Measure node importance conncomp Connected graph components biconncomp Biconnected graph components condensation Graph condensation bctree Block-cut tree graph toposort Topological order of directed acyclic graph isdag Determine if graph is acyclic transreduction Transitive reduction transclosure Transitive closure isisomorphic Determine whether two graphs are isomorphic isomorphism Compute isomorphism between two graphs ismultigraph Determine whether graph has multiple edges simplify Reduce multigraph to simple graph
 bfsearch Breadth-first graph search dfsearch Depth-first graph search shortestpath Shortest path between two single nodes shortestpathtree Shortest path tree from node distances Shortest path distances of all node pairs allpaths Find all paths between two graph nodes maxflow Maximum flow in graph minspantree Minimum spanning tree of graph hascycles Determine whether graph contains cycles allcycles Find all cycles in graph cyclebasis Fundamental cycle basis of graph
 adjacency Graph adjacency matrix incidence Graph incidence matrix laplacian Graph Laplacian matrix
 degree Degree of graph nodes neighbors Neighbors of graph node nearest Nearest neighbors within radius indegree In-degree of nodes outdegree Out-degree of nodes predecessors Node predecessors successors Node successors inedges Incoming edges to node outedges Outgoing edges from node
 plot Plot graph nodes and edges labeledge Label graph edges labelnode Label graph nodes layout Change layout of graph plot highlight Highlight nodes and edges in plotted graph

Objects

 GraphPlot Graph plot for directed and undirected graphs

Properties

 GraphPlot Properties Graph plot appearance and behavior

Topics

Directed and Undirected Graphs

Introduction to directed and undirected graphs.

Graphs and Matrices

This example shows an application of sparse matrices and explains the relationship between graphs and matrices.

Modify Nodes and Edges of Existing Graph

This example shows how to access and modify the nodes and/or edges in a graph or digraph object using the addedge, rmedge, addnode, rmnode, findedge, findnode, and subgraph functions.

Add Graph Node Names, Edge Weights, and Other Attributes

This example shows how to add attributes to the nodes and edges in graphs created using graph and digraph.

Graph Plotting and Customization

This example shows how to plot graphs, and then customize the display to add labels or highlighting to the graph nodes and edges.

Label Graph Nodes and Edges

This example shows how to add and customize labels on graph nodes and edges.

Add Node Properties to Graph Plot Data Tips

This example shows how to customize GraphPlot data tips to display extra node properties of a graph.