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 <iostream>
using namespace std;
using namespace HKUAL;

int main(){
    Graph<string> 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.