Paths, Cycles, and Flows

One of the key problems in graphs is navigation. In particular, the problem is finding the shortest path between two vertices, whether that is finding the way out of a maze or navigating a road network. The lengths of the shortest paths give rise to a whole collection of natural measures such as the diameter of a graph. If instead of navigating from one vertex to another you would like to traverse the whole graph in some way, you are looking for cycles. Eulerian and Hamiltonian cycles provide paths that traverse every edge or vertex of graph.

Shortest Paths

(RefLink[FindShortestPath, paclet:ref/FindShortestPath]) — find the shortest path from the source to a target

(RefLink[ShortestPathFunction, paclet:ref/ShortestPathFunction]) — represent a function that gives the shortest path in a graph

(RefLink[FindHamiltonianPath, paclet:ref/FindHamiltonianPath]) — find the shortest path that traverses every vertex once

Flows

(RefLink[FindMaximumFlow, paclet:ref/FindMaximumFlow]) — find the maximum flow between two vertices

(RefLink[FindMinimumCostFlow, paclet:ref/FindMinimumCostFlow]) — find minimum cost flows

(RefLink[OptimumFlowData, paclet:ref/OptimumFlowData]) — represent optimum flow data

Distances

(RefLink[GraphDistance, paclet:ref/GraphDistance]) — the length of the shortest path between two vertices

(RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix]) — the matrix of graph distances between all pairs of vertices

Longest Shortest Paths

(RefLink[VertexEccentricity, paclet:ref/VertexEccentricity]) — length of the longest shortest path to every other vertex

(RefLink[GraphRadius, paclet:ref/GraphRadius]) — minimum vertex eccentricity

(RefLink[GraphDiameter, paclet:ref/GraphDiameter]) — maximum vertex eccentricity

(RefLink[GraphCenter, paclet:ref/GraphCenter]) — vertices with minimum eccentricity

(RefLink[GraphPeriphery, paclet:ref/GraphPeriphery]) — vertices with maximum eccentricity

Topological Paths

(RefLink[TopologicalSort, paclet:ref/TopologicalSort]) — gives vertices in an order compatible with graph topology

Cycles and Tours

(RefLink[FindShortestTour, paclet:ref/FindShortestTour]) — find the shortest tour that traverses every vertex once

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour]) — find a tour that traverses every edge at least once

(RefLink[FindEulerianCycle, paclet:ref/FindEulerianCycle]) — find a cycle that traverses every edge exactly once

(RefLink[FindHamiltonianCycle, paclet:ref/FindHamiltonianCycle]) — find a cycle that traverses every vertex exactly once

(RefLink[FindCycle, paclet:ref/FindCycle]) — find all cycles of specified length

Independent Paths

(RefLink[FindEdgeIndependentPaths, paclet:ref/FindEdgeIndependentPaths]) — find edge-independent paths between two vertices

(RefLink[FindVertexIndependentPaths, paclet:ref/FindVertexIndependentPaths]) — find vertex-independent paths between two vertices

(RefLink[FindPath, paclet:ref/FindPath]) — find all paths between two vertices