November 19, 2008

Java Graph Analyzer

Written in 2001 for CS-344 Design and Analysis of Algorithms at Rutgers University.

Introduction

This program will perform various graph searching functions on an input dataset representing a graph G = (E,V).

It works on directed and undirected graphs, and detects cycles.

Theory of Operation

The stand-alone Java Graph Analyzer, will correctly do the following:

  • Read the name of the input file as a command line argument.
  • Open a GUI for the user to select the function they wish to perform.
  • Create an adjacentcy matrix from the input file
  • Perform Prims search
  • Perform DFS search
  • Perform BFS search
  • Perform Topsort
Each of these tasks was implemented entirely in Java, and can be run on any machine which supports Java.

Implementation

  • Class Graphframe

    sets up the GUI and does most of the important required functions. A number of global data structures are used which store the TreeEdges, Backedges, CutPoints, dfsNumbers, backnumbers, and finishing numbers.

    • void BrowseButton_actionPerformed(ActionEvent e)

      this function creates the adjacency list for the Graph. It handles both directed and undirected graphs. Arrays of Linked Lists are used to store the edges and edge weights associated with each edge. Arrays that will be used to store the dfsnumbers and back numbers are allocated.

    • void CycleButton_actionPerformed(ActionEvent e)

      this function calls DFS() and outputs the tree and backedges. The existence of backedges indicates that a cycle exists.

    • void BiconnButton_actionPerformed(ActionEvent e)

      this function calls DFS() on undirected graphs and outputs the cutpoints. If there are no cutpoints the graph is biconnected.

    • void ConnButton_actionPerformed(ActionEvent e)

      checks whether the graph is connected. If it is, it calls Prims() and outputs the MST and it's total weight.

    • void TopSortButton_actionPerformed(ActionEvent e)

      calls DFS(). It outputs the topsorted ordering of vertices for acyclic graphs.

    • void DFS()

      recursive function that does a Depth First Search on an input Graph. This method is used to create a topological ordering on a directed graph and to find the biconnected components of an undirected graph. Calls DFSFrom(vertex) to perform these calculations.

    • void DFSFrom(Vertex index)

      Computes cutpoints, topsorted ordering of vertices, and dfs tree. ParentOf[] keeps track of parents, avals[] keeps track of the place in the linked list(each vertice's edge list) that we leave off at when pushing a vertex on the stack, Stack[] keeps track of which vertices are on the stack, backnum[] and dfsnum[] keep track of those numbers for each vertex.

    • Prims()

      Computes the MST of a connected, undirected graph. status[] keeps track of status for each vertex, marked[] keeps track of which vertices are marked, parent[] keeps track of parents, count is the number of unmarked vertices, tempweight keeps track of lowest weight, and tempvertex keeps track of which vertex has the lowest weight.

    • public void ClearAll()

      clears the corresponding data structures that hold backEdges, treeEdges, and FinishingNums.

  • Class Edge

    Global variables he and she are used to hold the first and second vertices of an edge.

    • public Edge()

      null constructor

    • public Edge(Vertex y, Vertex z)

      contructor that creates an edge with 2 given vertices

    • public Vertex getShe()

      extracts the second vertex of an edge pair

    • public Vertex getHe()

      extracts the first vertex of an edge pair

  • Class Vertex

    Global variable num is used to give each vertex a label. Global variable numD is used to hold the weight of each edge. Weights are stored in vertices to make the implementation if the adjacency list more efficient. (In the adjacency list every other node is a vertex and every other node is a weight).

    • public Vertex()

      null constructor

    • public Vertex(int x)

      constructor with vertex label x

    • public Vertex(double y)

      constructor for a node that holds weight information for an edge. The weight is specified by y.

    • public int getNum()

      returns the num for this Vertex

    • public double getNumD

      returns the numD for this Vertex. (returns the weight associated with the edge that this Vertex is a part of).

  • Class mainclass

    constructs the application, frames, and runs the main program

Source