Jcg.graph.arraybased

Class ArrayBasedAdjacencyListGraph

java.lang.Object

Jcg.graph.arraybased.ArrayBasedAdjacencyListGraph

All Implemented Interfaces:

ArrayBasedGraph

public class ArrayBasedAdjacencyListGraph
extends java.lang.Object
implements ArrayBasedGraph

Array based implementation of an Adjacency List Representation of a graph. The graph is simple (no multiple edges), and there are not weights.

Version:

feb 2014

Author:

Luca Castelli Aleardi (Ecole Polytechnique, INF562)

Constructor Summary

Constructors

Constructor and Description
ArrayBasedAdjacencyListGraph(java.util.Collection<java.lang.Integer>[] nodes) Create a graph from the adjacency lists Each vertex stores the list of its neighbors (vertex indices) Remarks: -) the graph is assumed to be undirected, and each edge appears twice: (u,v) and (v,u) -) vertex indices range from 0 to n-1
ArrayBasedAdjacencyListGraph(int n) Create a graph with n vertices (with a given maximum vertex degree)

Method Summary

Modifier and Type	Method and Description
void	addEdge(int u, int v) Add an edge from vertex u to vertex v
boolean	adjacent(int u, int v) Check whether there is an edge from u to v
boolean	checkCombinatorics() Check whether the graph is combinatorially consistent
int	degree(int v) Return the degree of a vertex
int[][]	getEdges() Return the list of all (undirected) edges in the graph (each edge does appear only once)
java.util.Collection<java.lang.Integer>	neighbors(int v) Return the list of neighbors of a vertex
void	removeEdge(int u, int v)
int	sizeVertices() Give the number of vertices

Methods inherited from class java.lang.Object

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

Constructor Detail

ArrayBasedAdjacencyListGraph

public ArrayBasedAdjacencyListGraph(int n)

Create a graph with n vertices (with a given maximum vertex degree)

Parameters:

n - the number of vertices

ArrayBasedAdjacencyListGraph

public ArrayBasedAdjacencyListGraph(java.util.Collection<java.lang.Integer>[] nodes)

Create a graph from the adjacency lists Each vertex stores the list of its neighbors (vertex indices) Remarks: -) the graph is assumed to be undirected, and each edge appears twice: (u,v) and (v,u) -) vertex indices range from 0 to n-1

Parameters:

nodes - an array containing (in the entry nodes[i]) the list of neighbors of vertex v_i

Method Detail

addEdge

public void addEdge(int u,
                    int v)

Add an edge from vertex u to vertex v

Specified by:

addEdge in interface ArrayBasedGraph

Parameters:

u - first extremity of an edge

v - second extremity of an edge

removeEdge

public void removeEdge(int u,
                       int v)

Specified by:

removeEdge in interface ArrayBasedGraph

adjacent

public boolean adjacent(int u,
                        int v)

Check whether there is an edge from u to v

Specified by:

adjacent in interface ArrayBasedGraph

Parameters:

u - first extremity of an edge

v - second extremity of an edge

Returns:

true whether there is an edge from u to v

degree

public int degree(int v)

Return the degree of a vertex

Specified by:

degree in interface ArrayBasedGraph

Parameters:

v - the index of a vertex

Returns:

the degree of vertex v

neighbors

public java.util.Collection<java.lang.Integer> neighbors(int v)

Return the list of neighbors of a vertex

Specified by:

neighbors in interface ArrayBasedGraph

Parameters:

v - the index of a vertex

Returns:

the list of neighbors of v

getEdges

public int[][] getEdges()

Return the list of all (undirected) edges in the graph (each edge does appear only once)

Specified by:

getEdges in interface ArrayBasedGraph

Returns:

the list of all edges

sizeVertices

public int sizeVertices()

Give the number of vertices

Specified by:

sizeVertices in interface ArrayBasedGraph

Returns:

the number of vertices

checkCombinatorics

public boolean checkCombinatorics()

Check whether the graph is combinatorially consistent