org.matalon.pagerankhits.dataStructures
Class WebGraph

java.lang.Object
  org.matalon.pagerankhits.dataStructures.WebGraph

All Implemented Interfaces:

Graph

public class WebGraph

extends java.lang.Object

implements Graph

This class is an implementation of a graph for representing a web structure; each vertex represents an URL while each edge represents a link between them.

Author:

Yonatan Matalon

Field Summary

private java.util.List[]	adjacencyListArray
private static int	lastGeneratedVertexId
private java.util.Map	verticesIds
private java.util.Map	verticesNames

Fields inherited from interface org.matalon.pagerankhits.dataStructures.Graph

PAGERANK_ALPHA_FACTOR_DENOMINATOR, PAGERANK_ALPHA_FACTOR_NUMERATOR

Constructor Summary

WebGraph(int maxVerticesNo)
Constructor.

Method Summary

boolean	addEdge(Vertex v1, Vertex v2) Adds the given vertices (if they don't already exist) and an edge between them (if it doesn't already exist).
boolean	addVertex(Vertex v) Adds the given vertex if it doesn't already exist.
private static long[]	correctPageRankMatrix1(int totalNumOfPages) Google's first correction to PageRank(TM) algorithm.
private static java.lang.String	correctPageRankMatrix2(long correctedCellNumerator, long correctedCellDenominator, long totalNumOfPages) Google's second correction to PageRank(TM) algorithm.
private static long	gcd(long num1, long num2)
java.lang.String[][]	getAdjacencyMatrix()
java.lang.String[][]	getAdjacencyMatrix(int rowStart, int rowEnd, int colStart, int colEnd)
java.lang.String[][]	getInnerLinkRankMatrix()
java.lang.String[][]	getInnerLinkRankMatrix(int rowStart, int rowEnd, int colStart, int colEnd)
java.lang.String[][]	getPageRankMatrix()
java.lang.String[][]	getPageRankMatrix(int rowStart, int rowEnd, int colStart, int colEnd)
java.lang.String[][]	getPageRankMatrixCorrected()
java.lang.String[][]	getPageRankMatrixCorrected(int rowStart, int rowEnd, int colStart, int colEnd)
private int	getVertexId(Vertex v)
java.util.Map	getVertexId2NameMap()
java.util.Map	getVertexName2IdMap()
java.lang.String	getVertexNameById(int vertexId)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

verticesNames

private java.util.Map verticesNames

verticesIds

private java.util.Map verticesIds

adjacencyListArray

private java.util.List[] adjacencyListArray

lastGeneratedVertexId

private static int lastGeneratedVertexId

Constructor Detail

WebGraph

public WebGraph(int maxVerticesNo)
         throws InvalidParameterException

Constructor.

Parameters:

maxVerticesNo -

Throws:

InvalidParameterException

Method Detail

addEdge

public boolean addEdge(Vertex v1,
                       Vertex v2)

Adds the given vertices (if they don't already exist) and an edge between them (if it doesn't already exist).

Specified by:

addEdge in interface Graph

Parameters:

v1 -

v2 -

Returns:

Returns true, if the edge was added to the graph, false otherwise.

See Also:

Graph.addEdge(org.matalon.pagerankhits.dataStructures.Vertex, org.matalon.pagerankhits.dataStructures.Vertex)

addVertex

public boolean addVertex(Vertex v)

Adds the given vertex if it doesn't already exist.

Specified by:

addVertex in interface Graph

Parameters:

v -

Returns:

Returns true, if the vertex was added to the graph, false otherwise.

See Also:

Graph.addVertex(org.matalon.pagerankhits.dataStructures.Vertex)

getAdjacencyMatrix

public java.lang.String[][] getAdjacencyMatrix()

Specified by:

getAdjacencyMatrix in interface Graph

Returns:

Returns the whole graph as an adjacency matrix.

See Also:

Graph.getAdjacencyMatrix()

getAdjacencyMatrix

public java.lang.String[][] getAdjacencyMatrix(int rowStart,
                                               int rowEnd,
                                               int colStart,
                                               int colEnd)
                                        throws InvalidParameterException

Specified by:

getAdjacencyMatrix in interface Graph

Parameters:

rowStart -

rowEnd -

colStart -

colEnd -

Returns:

Returns a partial graph adjacency matrix, restricted by the given row and column indexes.

Throws:

InvalidParameterException

See Also:

Graph.getAdjacencyMatrix(int, int, int, int)

getInnerLinkRankMatrix

public java.lang.String[][] getInnerLinkRankMatrix()

Specified by:

getInnerLinkRankMatrix in interface Graph

Returns:

Returns the whole graph as a matrix, which contains relative variables (built by InnerLinkRank algorithm).

See Also:

Graph.getInnerLinkRankMatrix()

getInnerLinkRankMatrix

public java.lang.String[][] getInnerLinkRankMatrix(int rowStart,
                                                   int rowEnd,
                                                   int colStart,
                                                   int colEnd)
                                            throws InvalidParameterException

Specified by:

getInnerLinkRankMatrix in interface Graph

Parameters:

rowStart -

rowEnd -

colStart -

colEnd -

Returns:

Returns a partial graph matrix, which contains relative variables (built by InnerLinkRank algorithm). The matrix is restricted by the given row and column indexes.

Throws:

InvalidParameterException

See Also:

Graph.getInnerLinkRankMatrix(int, int, int, int)

getPageRankMatrix

public java.lang.String[][] getPageRankMatrix()

Specified by:

getPageRankMatrix in interface Graph

Returns:

Returns the whole graph as a matrix built by Google's PageRank algorithm.

See Also:

Graph.getPageRankMatrix()

getPageRankMatrix

public java.lang.String[][] getPageRankMatrix(int rowStart,
                                              int rowEnd,
                                              int colStart,
                                              int colEnd)
                                       throws InvalidParameterException

Specified by:

getPageRankMatrix in interface Graph

Parameters:

rowStart -

rowEnd -

colStart -

colEnd -

Returns:

Returns a partial PageRank matrix, restricted by the given row and column indexes.

Throws:

InvalidParameterException

See Also:

Graph.getPageRankMatrix(int, int, int, int)

getPageRankMatrixCorrected

public java.lang.String[][] getPageRankMatrixCorrected()

Specified by:

getPageRankMatrixCorrected in interface Graph

Returns:

Returns the whole graph as a matrix built by the corrected Google's PageRank algorithm.

See Also:

Graph.getPageRankMatrixCorrected()

getPageRankMatrixCorrected

public java.lang.String[][] getPageRankMatrixCorrected(int rowStart,
                                                       int rowEnd,
                                                       int colStart,
                                                       int colEnd)
                                                throws InvalidParameterException

Specified by:

getPageRankMatrixCorrected in interface Graph

Parameters:

rowStart -

rowEnd -

colStart -

colEnd -

Returns:

Returns a partial corrected PageRank matrix, restricted by the given row and column indexes.

Throws:

InvalidParameterException

See Also:

Graph.getPageRankMatrixCorrected(int, int, int, int)

getVertexId

private final int getVertexId(Vertex v)
                       throws VertexDoesNotExistException

Parameters:

v -

Returns:

Vertex's ID.

Throws:

VertexDoesNotExistException

getVertexNameById

public final java.lang.String getVertexNameById(int vertexId)
                                         throws VertexDoesNotExistException

Specified by:

getVertexNameById in interface Graph

Parameters:

vertexId -

Returns:

The name of the vertex having the given ID.

Throws:

VertexDoesNotExistException

correctPageRankMatrix1

private static final long[] correctPageRankMatrix1(int totalNumOfPages)

Google's first correction to PageRank(TM) algorithm.

Parameters:

totalNumOfPages -

Returns:

Returns the corrected result.

correctPageRankMatrix2

private static final java.lang.String correctPageRankMatrix2(long correctedCellNumerator,
                                                             long correctedCellDenominator,
                                                             long totalNumOfPages)

Google's second correction to PageRank(TM) algorithm.

Parameters:

correctedCellNumerator - - numerator of the value of the cell, which was corrected by Google's first correction.

correctedCellDenominator - - denominator of the value of the cell, which was corrected by Google's first correction.

totalNumOfPages -

Returns:

Returns the corrected result.

gcd

private static final long gcd(long num1,
                              long num2)

Parameters:

num1 -

num2 -

Returns:

Returns the greatest common divisor of the given numbers.

getVertexId2NameMap

public java.util.Map getVertexId2NameMap()

Specified by:

getVertexId2NameMap in interface Graph

Returns:

Returns a mapping between vertex ID (key) and its name in the graph (value).

See Also:

Graph.getVertexId2NameMap()

getVertexName2IdMap

public java.util.Map getVertexName2IdMap()

Specified by:

getVertexName2IdMap in interface Graph

Returns:

Returns a mapping between vertex name (key) and its ID in the graph (value).

See Also:

Graph.getVertexName2IdMap()