A GPL Package

A Graph Product Line (GPL) package is a customized set of graph algorithms written in Java.  This particular package implements a weighted, directedundirected graph with the following algorithms:

• Breadth First Search (BFS)
• Depth First Search (DFS)
• Vertex Numbering (Vertex)
• Connected Graphs (Connected)
• Strongly Connected Graphs (StronglyConnected)
• Cycle Checking (Cycle)
• Prim's Minimum Spanning Tree (MSTPrim)
• Kruskal's Minimum Spanning Tree (MSTKruskal)
• Shortest Path (Shortest)

Click on the above algorithm names for more detail about them and how to invoke them.  This document also contains sections on the following topics:

• Programmatic Invocation
• Command Line Invocation
• Implementation Notes
• Algorithm Descriptions

The following code snippet illustrates how a graph object is defined.  First a Graph object is created, and then each edge is added with its corresponding weight:

Graph g = new Graph();

for ( i=0; i<num_edges; i++ ) {
   Vertex v1 = ( Vertex ) V[ startVertices[ i ] ];
   Vertex v2 = ( Vertex ) V[ endVertices[ i ] ];
   EdgeIfc edge = g.addEdge( v1, v2 );
   edge.setWeight( weights[ i ] );
}

Once a graph object is created, you can invoke a graph algorithm.   Let algName be the name of an algorithm (look below to find the exact name and parameter list).  A typical invocation looks like:

g.algName();

Your package contains a Main class that has 2 command line parameters: the name of a data file and the number of a vertex:

> java <your package name>.Main <data file name> <vertex#>

A data file is a text file with the following sequence of numbers:

• the number of vertices in the graph (v)
• the number of edges in the graph (e)
• 3 numbers that are presently ignored (claimed for future use)
• a sequence of e pairs of positive numbers (start-vertex#, end-vertex#) to define each vertex
• a sequence of e positive numbers to indicate the weight of each vertex

Vertex numbers begin with 0..(v-1).

The vertex# parameter of the command line indicates the root vertex of the graph.

Implementation Notes

The OnlyVertices data structure follows a legacy design where graphs are encoded in two classes: Graph and Vertex. A Graph object defines a list of Vertex objects. Each Vertex object encapsulates two lists (or really containers): an adjacency list of other vertices and a "parallel" Weights list that maintains weight information for the corresponding adjacent vertex (i.e., the length of the adjacency list and the weights list is always the same). The advantage of this data structure is its simplicity; its disadvantage is when edges must be explicitly manipulated.

The WithEdges data structure has a class for every major graph abstraction: Graph, Vertex, Neighbor, and Edge. A Graph object maintains a list (or container) of Vertex objects, and a list (container) of Edge objects. Each Vertex contains a list of adjacent edges, and each Edge object references both Vertex objects with the weight of the edge. The advantage of this data structure is that it cleanly supports the implementation of all graph algorithms; its disadvantage is a larger overhead for graph creation.

The WithNeighbors data structure uses three classes: Graph, Vertex, and Neighbor. A Graph object contains a list (or container) of Vertex objects. Each Vertex object maintains a list (container) of Neighbor objects, which includes the weight of the associated edge. The advantage of this data structure is a simple design, but its disadvantage is when edges must be explicitly manipulated.

Breadth First Search (BFS)

The standard breadth first search algorithm.

Depth First Search (DFS)

The standard depth-first search algorithm.

Vertex Numbering (Vertex)

Assigns a unique number to each vertex.

G.NumberVertices(); // numbers vertices
V.VertexNumber // number of vertex

Connected Graphs (Connected)

Computes equivalence classes in undirected graph of nodes under the reachability relationship. Each vertex is assigned a component number (starting with number 0).

G.ConnectedComponents(); // finds components
V.ComponentNumber // number of component

Strongly Connected Graphs (StronglyConnected)

Computes equivalence classes for directed graphs. Each vertex is assigned a component number (starting with number 0).

G.StrongComponents(); // finds components
V.strongComponentNumber; // number of component

Cycle Checking (Cycle)

Returns true if there is a cycle in a graph, false otherwise. A cycle in directed graphs is at least 2 edges; in a directed graph it is at least 3.

boolean b = G.CycleCheck(); // are there cycles?

Prim's Minimum Spanning Tree (MSTPrim)

Contains all vertices such that sum of the weights of edges is minimal. Returns a weighted graph.

Graph g = G.Prim(); // finds min spanning tree

Kruskal's Minimum Spanning Tree (MSTKruskal)

Contains all vertices such that sum of the weights of edges is minimal. Returns a weighted graph.

Graph g = G.Kruskal(); // finds min spanning tree

Shortest Path (Shortest)

No Description yet.