The DirectedGraph class can represent a weighted undirected graph. A user specifies the graph by providing the labels of the vertices and the directed edges in the graph. The template type specifies the type of the labels. For example, the following program defines a graph with string label and then find the shortest distance between vertex “A” and “B”.

#include "HKUAL_graph.h"
#include <iostream>
using namespace std;
using namespace HKUAL;

int main(){
    DirectedGraph<string> g;

cout << g.shortestDistance("A","D") << endl;
return 0; }

Member Function

Specifying the Graph
(constructor) Construct DirectedGraph.
addVertex Insert vertex.
addEdge Insert edge.
Graph property
size Return number of vertices in the graph.
getVertices get all vertices.
getEdges get all edges.
isAcyclic Test is the graph acyclic or not.
Vertex Property
inDegree Return in degree of a vertex.
outDegree Return out degree of a vertex.
parent Return all parent of a vertex.
children Return all children of vertex.
Distance information
shortestPath Return the shortest path between two vertices.
shortestDistance Return the shortest distance between two vertices.
allPairsShortestDistances Calculate shortest distances between all pairs of vertices.
Subgraph selection
topologicalSort Return the topological order of the graph.
eulerianPath Return the eulerian path.
stronglyConnectedComponets Return the strong connected components.
© The University of Hong Kong Algorithms Library -