Maximum Adjacency Search
Dual MAS Version
CSE 7350/5350
David W. Matula

Total Points: 400

Updated: June 2000

1 Introduction

In this project, you are asked to implement an algorithm for determining a maximum adjacency search (MAS) vertex ordering of a graph along with an arc labeling. You are further asked to display associated properties of the search and arc labeling particularly related to appropriate edge connectivity pairs, cutsets, and vertex clustering. Regarding algorithm efficiency, you are asked to verify a linear time bound O (|V|+|E|) for determining the MAS and forward arc labeling, and to analyze the efficiency of your implementation of the reverse partial arc labeling. You are furthermore asked to select one of several subprojects to pursue in greater detail.

 

2 Basic Terminology

A search of a graph G = (V,E) denotes an ordering of the vertices, v1, v2, ..., vn, determined by the order in which vertices are selected to be scanned. A maximum adjacency search (MAS) is a search where vi is selected from the unscanned vertices, V - {v1,v2,..,vi-1} on the basis of having a maximum number of adjacencies with the previously scanned vertices,{v1,v2,...,vi-1}.
An ordering of the vertices, v1, v2, ..., vn, induces an ordering of the arcs associated with the edges of a graph. Each edge (vi, vj) has two associated arcs: for i < j, the arc a(i,j) is the forward arc, and a(j,i) is the reverse arc. The arc a(i,j) lexicographically precedes the arc a(k,l) if either i < k, or i = k and j < l (lexicographic order). When a(i,j) precedes a(k,l) then a(k,l) is said to lexicographically succeed a(i,j).
    For the vertex ordering v1, v2, ..., vn, a minimum acyclic arc labeling assigns a unique minimum label (color) from {1,2,...,n-1} to every forward arc such that the arc does not form a cycle with preceding forward arcs having the same label, and a unique minimum label (color) from { 1,2,...,n-1} to a subset of reverse arcs such that the arc does not form a cycle with succeeding reverse arcs having the same label. The forward arcs of the same color form a forest for each color, and similarly for the colored reverse arcs.

Given the MAS vertex ordering v1, v2,…, vn , a dual MAS (DMAS) denotes the vertex ordering v1, v2, …, vn, along with a reverse edge set ER , where ER is a maximum subset of E having the property that the reverse search vn, vn-1, …v1, is an MAS vertex ordering of the subgraph G = (V, ER).

A Dual MAS is total when | ER | = | E | . A total DMAS allows a minimum acyclic arc labeling to be efficiently determined on-the-fly for forward arcs during the forward search and for reverse arcs during the reverse search.

A Dual MAS is partial when | ER | < | E |. In this case the ratio | ER | / | E | provides an effectiveness measure for the DMAS.

3 Benchmark

You will be provided with ten benchmarks graphs with which to test your program. Five of these graphs were created using a graph generation program developed by Paul Bartholomew. Your program must find a dual maximum adjacency search and minimum acyclic arc labeling for each of the ten benchmark graphs.
The graphs are available in both adjacency list and adjacency matrix representations.

The graphs are available as ASCII files on the SEAS UNIX network in the directory: /users/project/cse/CSE5350.

 

4 Project Format

Your project submission should be equivalent to an 8-12 page word-processor-composed report for the project description and walkthrough text plus pages for summarizing and presenting the results using figures and tables. The report should be oriented towards a technical manager with a wide perspective, say in Scientific American magazine style. Grading partition:

4.1    Introduction (30 points)

Give a brief description, in layman's terms, of the project, including your major result. Consider this section to be a professionally worded marketing effort. That is, would the competent technical manager (your audience) be likely to want to read on and try to understand your claimed good results. Describe the strongest features of your implementation. State which subproject you pursued and focus on your original work in this selected area. Summarize your use of illustrations, figures, tables, or computer graphics employed that will reveal your results effortlessly to the reader. Give clear citations to your sources including downloaded programs and previous student's projects that most influenced your work.

4.2    Programming Environment Description (20 points)

Give a description of the environment you used to develop the program including both hardware and software components, i.e., the specific type and brand of computer, the computer's processing speed, the amount of memory, the operating system, the language, any special libraries, etc. The description should include metrics on the program resource utilization allowing judgement of "was the total used respectable or an overkill"? The purpose of this description is to allow comparisons and facilitate reproduction. Consider: would a knowledgeable colleague be able to judge the scope of your work from this description of the environment and resource utilization. The graphics package used to present the report should also be described.

4.3    References (20 points)

Provide a list of publications, texts and programs in typical reference style at the end of the descriptive text of your report and before the collection of output tables for benchmarks and tests graphs.

4.4    Reduction to Practice (100 points)

This is the core of your report and should cover the five following topics appropriately integrated.
    • Data structure design (20 points.): Describe and illustrate the representation and organization of data employed and discuss its relation to the algorithms employed.
    • Algorithm descriptions (20 points): Provide a description of the Dual MAS algorithm sufficient for your report to be self-contained to someone familiar with other graph search algorithms. The description should clearly cover the distinctions between the forward MAS search coloring all arcs, and the reverse MAS search coloring only an appropriately described subset of reverse arcs.
    • Algorithm engineering (20 points): Describe how the algorithm implementation is engineered to achieve efficiencies in time and space and provide arguments for the efficiencies. In particular, carefully substantiate the linear time bound for the Dual MAS if your implementation realizes this bound.
    • Verification Walk through (20 points): Present a walk through of an original graph having 10 to 14 vertices and 20 to 30 edges. Choose the graph to expose challenging aspects of the algorithm and your implementation.
    • Algorithm effectiveness (20 points): Include here a summary table of results as an overview of the benchmarks and test graphs. Give your conclusion on the strengths and weaknesses of the algorithm on the one hand and your implementation on the other. Indicate applications (clustering, routing, etc) where your implementation would be strongest and what kind of input would be most difficult to handle. Your analysis and conclusions relevant to your own test graphs can be a focal point of this topic.

4.5    Benchmark Result Summary (50 points)

You should provide a standard output for each benchmark graph including the following:
    • The benchmark number and certain parameters on size and structure so the user may judge the difficulty of each benchmark instance, e.g., number of vertices, and edges, minimum, maximum, and average degree, the density (% non zero) of the adjacency matrix and length of the adjacency list representations of the graph.
    • The MAS vertex ordering, the number of edges receiving each color, the number and proportion of edges given a reverse arc color.
    •  A table of results with n-1 lines for an n vertex graph, indexed by the last-to-next vertices visited in MAS order, each line including the following:

1- Cut Vertex Pair 

2 - Cut Size

3 - Forward Cut Coloring

4 - Reverse Cut Coloring

5 - Dual Coloring

6 - Connectivity Upper Bound (determined by the minimum of the cut size, the degree of the last vertex and the degree of the next vertex of the visit pair)

7 - Connectivity Bound Gap (the difference in the colored path count and the upper bound, zero indicating a &ldquo; maximum flow&rdquo; identified between the visit pair)

    • The level Vs order graph showing forward and dual level plots, and the bound gap.

 

4.6 Verification Case Studies (40 points)

4.7 Subproject (60 points)
    • MAS on-the-fly block reordering.
    • Preprocessing adjacency list structure by smallest last vertex reordering.
    • Graph drawing and adjacency matrix plotting to expose clusters.
    • Cut tree and all pairs edge connectivity bounds.
    • Thin cuts and clusters.

4.8    Display (80 points)

These points are awarded on the basis of your use of illustrations, figures, tables, bar charts, and computer generated diagrams in your report. Hand drawn and/or computer generated figures may be utilized as appropriate.

 i) 30 points will be related to your displays associated with the algorithm and data structure explanation, including the verification walkthrough.

ii) 50 points will be related to your displays associated with output results, including the benchmark cases and the supplementary verification case studies you create.

 

Implementation Notes