DirectedGraph

Class

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;
    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("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.