Task: Creating a data structure that represents directed graphs with adjacency lists.

Input: A text file that encodes a directed graph using special format (edge list)

Output: Information about the input directed graph on the screen.

Input Format Example:

9 -max possible vertex number after which goes list of edges.

0 2 8 7 2 3 2 5 7 2 2 7 5 2 5 0 3 8 7 3 7 5

Inner representation:

index	vertex_id	rank	out degree	adjacency list
0	0	0	1	@2
1	-1	-1
2	2	0	3	@3,5,7
3	3	0	1	@8
4	-1	-1
5	5	0	2	@0,2
6	-1	-1
7	7	0	3	@2,3,5
8	8	0	1	@7
9	-1	-1

Graph Representation:

The vertices identifiers in a directed graph are integers

A directed graph is represented by a table with variable length fields where a row corresponds to a vertex and contains the following fields: vertex id-integer, 'rank' - real, out degree- integer, list of 'edges' - sorted list of integers.

list of edges is a sorted list of adjacent vertices where the i-th element of the chosen data structure represents i'th largest 'vertex id'.

All fields of the table are initialized with null values.

The choice of data structures is yours as long as the representation uses theta(|V|+|E|) space.

Structure for vertexes Example:

public static class Row {

int vertex_id = -1; double pageRank = 1.0D; int outdegree = -1; ArrayList adjacencyList = new ArrayList();

}

Graph Initialization Example:

In main: {

Row[] vertexArray = new Row[];

initArray(vertexArray);

}

initArray(vertexArray);

public static void initArray(Row[] vertexArray)

{

for (int i=0; i < vertexArray.length; i++) {

vertexArray[i] = new Row();

}

}

Example of output file(assumed to be located in same directory as program)

3 1 8

2 3 3 5 7

8 1 7

0 1 2

5 2 0 2

7 3 2 3 5

Main Steps:

1.Define structures for adjacency lists and for an array of vertices.

2. Initialize the array of vertices by assigning -1 to the id field.

3. Read the input file and enter information about the vertices:the vertex id, out-degree, and adjacency list. Assign 1 to the rank field.

4. Output information about the graph on the screen (using format in following example)

Format of output to screen:

Vertex 0: rank = -1, out-degree = 1

Edges from 0 to: 2

Vertex 2: rank = -1, out-degree = 3

Edges from 2 to: 3, 5, 7

Vertex 3: rank = -2, out-degree = 1

Edges from 3 to: 8