graphlab
Class SparseGraph

java.lang.Object
  graphlab.SparseGraph

All Implemented Interfaces:

Graph

Direct Known Subclasses:

DenseGraph, PythonGraph

public class SparseGraph
extends java.lang.Object
implements Graph

Efficient representation for sparse graphs. Default Graph class to be used.

Author:

akyrola

Field Summary

protected Vertex[]

vertices

Constructor Summary

SparseGraph()
Constructor.

SparseGraph(int n)
Creates a new graph with estimated number of vertices.

Method Summary

void	addEdge(Edge e, int fromVertex, int toVertex) Add a directed edge
protected Vertex	addVertex(int vertexId, Vertex vertex)
Vertex	addVertex(Vertex vertex) Add a vertex to the graph.
protected void	checksize(int vertexId) Grows the data structures if needed
int[]	children(int vertex) Returns list of outbound neighbors of a vertex.
void	finalizeGraph()
Edge	getEdge(int sourceVertexId, int targetVertexId) Returns an edge from source vertex to target vertex.
int	getNumOfVertices() Returns the number of vertices in graph.
Vertex	getVertex(int vid) Returns Vertex object of given id.
Vertex[]	getVertices() Returns a copy of vertex-array of the graph.
boolean	isColoringEnabled() Whether this graph is a "colored" graph.
int[]	parents(int vertex) Returns list of inbound neighbors of a vertex.
void	setVertexColor(int vertex, int vertex_color) Set vertex color.
java.lang.String	toString()
int[]	vertices() Returns a copy of vertex ids of a graph.

Methods inherited from class java.lang.Object

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

Field Detail

vertices

protected Vertex[] vertices

Constructor Detail

SparseGraph

public SparseGraph()

Constructor.

SparseGraph

public SparseGraph(int n)

Creates a new graph with estimated number of vertices. Internal data structures will grow if the estimate is exceeded.

Parameters:

n - estimated number of vertices

Method Detail

getVertex

public Vertex getVertex(int vid)

Returns Vertex object of given id.

Specified by:

getVertex in interface Graph

Parameters:

vid - vertex id (>=0)

Returns:

vertex object

Throws:

java.lang.ArrayIndexOutOfBoundsException

addVertex

public Vertex addVertex(Vertex vertex)

Add a vertex to the graph.

Specified by:

addVertex in interface Graph

Parameters:

vertex -

Returns:

the vertex object. Now id-field is set

addVertex

protected Vertex addVertex(int vertexId,
                           Vertex vertex)

setVertexColor

public void setVertexColor(int vertex,
                           int vertex_color)

Set vertex color. Graph coloring can be used for scheduling with the "colored_scheduler" scheduler.

Specified by:

setVertexColor in interface Graph

Parameters:

vertex - vertex id

vertex_color - color id. Color must be integer between 0 and 255.

addEdge

public void addEdge(Edge e,
                    int fromVertex,
                    int toVertex)

Add a directed edge

Specified by:

addEdge in interface Graph

Parameters:

e - edge object encapsulating edge data

fromVertex - vertex id of the source vertex

toVertex - vertex id of the target vertex

vertices

public int[] vertices()

Returns a copy of vertex ids of a graph.

Returns:

children

public int[] children(int vertex)

Returns list of outbound neighbors of a vertex. Do not modify.

Specified by:

children in interface Graph

Parameters:

vertex - id of vertex

Returns:

array of outbound neighbors of a vertex

parents

public int[] parents(int vertex)

Returns list of inbound neighbors of a vertex. Do not modify.

Specified by:

parents in interface Graph

Parameters:

vertex - id of vertex

Returns:

array of inbound neighbors of a vertex

checksize

protected void checksize(int vertexId)

Grows the data structures if needed

Parameters:

vertexId -

getVertices

public Vertex[] getVertices()

Returns a copy of vertex-array of the graph.

Specified by:

getVertices in interface Graph

Returns:

array of vertex objects.

getEdge

public Edge getEdge(int sourceVertexId,
                    int targetVertexId)

Returns an edge from source vertex to target vertex. Note: this is a slow operation (O(degree)) since edges are not sorted. You are usually best of using iterators from getVertex(vid).getInboundEdges()

Specified by:

getEdge in interface Graph

Parameters:

sourceVertexId - vertex id of the origin vertex

targetVertexId - vertex id of the destination vertex

Returns:

edge spanning source to target vertex

isColoringEnabled

public boolean isColoringEnabled()

Whether this graph is a "colored" graph. Graph coloring can be used for scheduling.

Specified by:

isColoringEnabled in interface Graph

Returns:

true if vertices have color

getNumOfVertices

public int getNumOfVertices()

Returns the number of vertices in graph.

Specified by:

getNumOfVertices in interface Graph

Returns:

finalizeGraph

public void finalizeGraph()

Specified by:

finalizeGraph in interface Graph

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object