The Graph class can represent a weighted undirected graph. A user specifies the graph by providing the labels of the vertices and the 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 path between vertex “A” and “B”.

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

int main(){
    Graph<string> g;
    cout << g.shortestDistance("C","D") << endl;
    return 0;

Member Functions

Specifying the Graph
(constructor) Construct Graph.
addVertex Insert a vertex.
addEdge Insert an edge.
Graph property
size Return number of vertices in the graph.
getVertices get all vertices.
getEdges get all edges.
isConnected Test is the graph connected or not.
isTree Test is the graph is a tree or not.
isComplete Test is the graph is complete graph or not.
isBipartite Test is the graph is a Bipartite graph or not.
isContainCycle Return the graph contain cycle or not.
Vertex Property
degree Return degree of a vertex.
neighbours Return neighbours of a vertex.
eccentricity Return eccentricity of a specified 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
bipartiteMatching Return the maximum matching of a bipartite graph.
cutVertex Return all cut vertices in the graph.
bridge Return all bridges in the graph.
spanningTree Return all edges that use to construct a spanning tree
eulerianPath Return the eulerian path.
© The University of Hong Kong Algorithms Library -