﻿ Untitled Document

# Graph

Class

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 using namespace std; using namespace HKUAL; int main(){ Graph g; g.addVertex("A"); g.addVertex("B"); g.addVertex("C"); g.addVertex("D"); g.addEdge("A","B"); g.addEdge("A","C"); g.addEdge("B","D"); 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 - hkual@cs.hku.hk