edu.wwu.tobikley.acgc.graphcoloring
Class ColoredGraph

java.lang.Object
  edu.wwu.tobikley.acgc.graphcoloring.ColoredGraph

All Implemented Interfaces:

ArchetypeGraph, Graph, UserDataContainer, Cloneable

public class ColoredGraph
extends Object
implements Graph

Extends any Graph-Implementation with a node- and an edge-coloring.

Version:

1.0

Author:

Tobias Kley

Nested Class Summary

Nested classes/interfaces inherited from interface edu.uci.ics.jung.utils.UserDataContainer

UserDataContainer.CopyAction

Field Summary

protected int[]	edgeColoring The current edge coloring.
protected HashMap<Edge,Integer>	edgeIds Mapping the graphs edges to Integer ids.
protected HashMap<Integer,Edge>	edgesById Mapping the edge ids to the corresponding edges.
protected Graph	graph Graph object all method calls are delegated to.
protected int[]	vertexColoring The current vertex coloring.
protected HashMap<Vertex,Integer>	vertexIds Mapping the graphs vertices to Integer ids.
protected HashMap<Integer,Vertex>	verticesById Mapping the vertice ids to the corresponding vertices.

Fields inherited from interface edu.uci.ics.jung.graph.Graph

DIRECTED_EDGE, NOT_PARALLEL_EDGE, SIMPLE_EDGE, UNDIRECTED_EDGE

Fields inherited from interface edu.uci.ics.jung.graph.ArchetypeGraph

SUBSET_MANAGER

Constructor Summary

ColoredGraph(Graph g)
Creates a new instance of a colored graph.

Method Summary

Edge	addEdge(Edge e)
void	addListener(GraphEventListener gel, GraphEventType get)
void	addUserDatum(Object key, Object datum, UserDataContainer.CopyAction copyAct)
Vertex	addVertex(Vertex v)
Object	clone()
boolean	containsUserDatumKey(Object key)
ColoredGraph	copy()
int	getColor(Edge edge) Returns the color of an edge.
int	getColor(Vertex vertex) Returns the color of a vertex.
Edge	getEdge(int id) Returns the edge that corresponds to the given id.
int	getEdgeColor(int id) Returns the color of an edge by its identifier.
int[]	getEdgeColoring()
Collection	getEdgeConstraints()
int	getEdgeId(Edge edge) Returns the edge's identifier.
Set	getEdges()
Graph	getGraph()
int	getMaxDegree() Determines the maximum degree of the graph and returns it.
Object	getUserDatum(Object key)
UserDataContainer.CopyAction	getUserDatumCopyAction(Object key)
Iterator	getUserDatumKeyIterator()
Vertex	getVertex(int id) Returns the vertex that corresponds to the given id.
int	getVertexColor(int id) Returns the color of a vertex by its identifier.
int[]	getVertexColoring()
Collection	getVertexConstraints()
int	getVertexId(Vertex vertex) Returns the vertex's identifier.
Set	getVertices()
void	importUserData(UserDataContainer udc)
boolean	isDirected() Deprecated.
boolean	isProperVertexColoring() Determines if the current vertex coloring is proper.
boolean	isRegular() Determines if the graph is Delta-regular.
ArchetypeGraph	newInstance()
int	numEdges()
int	numVertices()
void	removeAllEdges()
void	removeAllVertices()
void	removeEdge(Edge e)
void	removeEdges(Set edges) Deprecated.
void	removeListener(GraphEventListener gel, GraphEventType get)
Object	removeUserDatum(Object key)
void	removeVertex(Vertex v)
void	removeVertices(Set vertices) Deprecated.
void	setColor(Edge edge, int color) Sets the color of an edge.
void	setColor(Vertex vertex, int color) Sets the color of a vertex.
void	setEdgeColor(int id, int color) Sets the color of an edge by its identifier.
void	setEdgeColoring(int[] edgeColoring)
void	setUserDatum(Object key, Object datum, UserDataContainer.CopyAction copyAct)
void	setVertexColor(int id, int color) Sets the color of a vertex by its identifier.
void	setVertexColoring(int[] vertexColoring)

Methods inherited from class java.lang.Object

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

Field Detail

graph

protected Graph graph

Graph object all method calls are delegated to.

vertexIds

protected HashMap<Vertex,Integer> vertexIds

Mapping the graphs vertices to Integer ids.

edgeIds

protected HashMap<Edge,Integer> edgeIds

Mapping the graphs edges to Integer ids.

verticesById

protected HashMap<Integer,Vertex> verticesById

Mapping the vertice ids to the corresponding vertices.

edgesById

protected HashMap<Integer,Edge> edgesById

Mapping the edge ids to the corresponding edges.

vertexColoring

protected int[] vertexColoring

The current vertex coloring.

edgeColoring

protected int[] edgeColoring

The current edge coloring.

Constructor Detail

ColoredGraph

public ColoredGraph(Graph g)

Creates a new instance of a colored graph. A copy of the given graph will be create and extended with the coloring properties.

Parameters:

g - Master graph to create a colored copy from.

Method Detail

getEdge

public Edge getEdge(int id)

Returns the edge that corresponds to the given id.

Parameters:

id - Edge identifier.

Returns:

Edge by identifier id.

getVertex

public Vertex getVertex(int id)

Returns the vertex that corresponds to the given id.

Parameters:

id - Vertex identifier.

Returns:

Vertex by identifier id.

getEdgeId

public int getEdgeId(Edge edge)

Returns the edge's identifier.

Parameters:

edge - Edge.

Returns:

Identifier of edge.

getVertexId

public int getVertexId(Vertex vertex)

Returns the vertex's identifier.

Parameters:

vertex - Vertex.

Returns:

Identifier of vertex.

getColor

public int getColor(Vertex vertex)

Returns the color of a vertex.

Parameters:

vertex - Vertex.

Returns:

Color of vertex.

getColor

public int getColor(Edge edge)

Returns the color of an edge.

Parameters:

edge - Edge.

Returns:

Color of edge.

getVertexColor

public int getVertexColor(int id)

Returns the color of a vertex by its identifier.

Parameters:

id - Vertex's identifier.

Returns:

Color of vertex.

getEdgeColor

public int getEdgeColor(int id)

Returns the color of an edge by its identifier.

Parameters:

id - Edge's identifier.

Returns:

Color of vertex.

setColor

public void setColor(Vertex vertex,
                     int color)

Sets the color of a vertex.

Parameters:

vertex - Vertex.

color - Color to set.

setColor

public void setColor(Edge edge,
                     int color)

Sets the color of an edge.

Parameters:

edge - Edge.

color - Color to set.

setVertexColor

public void setVertexColor(int id,
                           int color)

Sets the color of a vertex by its identifier.

Parameters:

id - Vertex's identifier.

color - Color to set.

setEdgeColor

public void setEdgeColor(int id,
                         int color)

Sets the color of an edge by its identifier.

Parameters:

id - Edge's identifier.

color - Color to set.

isProperVertexColoring

public boolean isProperVertexColoring()

Determines if the current vertex coloring is proper. To determine if it is a proper colorings, each edge in the graph is examined. A coloring is proper if the endnodes of all edges are of different colors.

Returns:

true if the current vertex coloring is proper, and false if it is not.

getMaxDegree

public int getMaxDegree()

Determines the maximum degree of the graph and returns it.

Returns:

Maximum degree of the graph.

isRegular

public boolean isRegular()

Determines if the graph is Delta-regular.

Returns:

true if the graph is regular, and false if it is not.

getGraph

public Graph getGraph()

Returns:

the graph

getEdgeColoring

public int[] getEdgeColoring()

Returns:

the edgeColoring

setEdgeColoring

public void setEdgeColoring(int[] edgeColoring)

Parameters:

edgeColoring - the edgeColoring to set

getVertexColoring

public int[] getVertexColoring()

Returns:

the vertexColoring

setVertexColoring

public void setVertexColoring(int[] vertexColoring)

Parameters:

vertexColoring - the vertexColoring to set

addEdge

public Edge addEdge(Edge e)

Specified by:

addEdge in interface Graph

Parameters:

e -

Returns:

the edge

See Also:

Graph.addEdge(edu.uci.ics.jung.graph.Edge)

addListener

public void addListener(GraphEventListener gel,
                        GraphEventType get)

Specified by:

addListener in interface ArchetypeGraph

Parameters:

gel -

get -

See Also:

ArchetypeGraph.addListener(edu.uci.ics.jung.graph.event.GraphEventListener, edu.uci.ics.jung.graph.event.GraphEventType)

addUserDatum

public void addUserDatum(Object key,
                         Object datum,
                         UserDataContainer.CopyAction copyAct)

Specified by:

addUserDatum in interface UserDataContainer

Parameters:

key -

datum -

copyAct -

See Also:

UserDataContainer.addUserDatum(java.lang.Object, java.lang.Object, edu.uci.ics.jung.utils.UserDataContainer.CopyAction)

addVertex

public Vertex addVertex(Vertex v)

Specified by:

addVertex in interface Graph

Parameters:

v -

Returns:

the vertex

See Also:

Graph.addVertex(edu.uci.ics.jung.graph.Vertex)

clone

public Object clone()
             throws CloneNotSupportedException

Specified by:

clone in interface UserDataContainer

Overrides:

clone in class Object

Returns:

the object

Throws:

CloneNotSupportedException

See Also:

UserDataContainer.clone()

containsUserDatumKey

public boolean containsUserDatumKey(Object key)

Specified by:

containsUserDatumKey in interface UserDataContainer

Parameters:

key -

Returns:

???

See Also:

UserDataContainer.containsUserDatumKey(java.lang.Object)

copy

public ColoredGraph copy()

Specified by:

copy in interface ArchetypeGraph

Returns:

copy of the graph

See Also:

ArchetypeGraph.copy()

getEdgeConstraints

public Collection getEdgeConstraints()

Specified by:

getEdgeConstraints in interface ArchetypeGraph

Returns:

the edge constraints

See Also:

ArchetypeGraph.getEdgeConstraints()

getEdges

public Set getEdges()

Specified by:

getEdges in interface ArchetypeGraph

Returns:

the set of edges

See Also:

ArchetypeGraph.getEdges()

getUserDatum

public Object getUserDatum(Object key)

Specified by:

getUserDatum in interface UserDataContainer

Parameters:

key -

Returns:

the user datum

See Also:

UserDataContainer.getUserDatum(java.lang.Object)

getUserDatumCopyAction

public UserDataContainer.CopyAction getUserDatumCopyAction(Object key)

Specified by:

getUserDatumCopyAction in interface UserDataContainer

Parameters:

key -

Returns:

the user datum copy action

See Also:

UserDataContainer.getUserDatumCopyAction(java.lang.Object)

getUserDatumKeyIterator

public Iterator getUserDatumKeyIterator()

Specified by:

getUserDatumKeyIterator in interface UserDataContainer

Returns:

the user datum key iterator

See Also:

UserDataContainer.getUserDatumKeyIterator()

getVertexConstraints

public Collection getVertexConstraints()

Specified by:

getVertexConstraints in interface ArchetypeGraph

Returns:

the vertex constraints

See Also:

ArchetypeGraph.getVertexConstraints()

getVertices

public Set getVertices()

Specified by:

getVertices in interface ArchetypeGraph

Returns:

the set of vertices

See Also:

ArchetypeGraph.getVertices()

importUserData

public void importUserData(UserDataContainer udc)

Specified by:

importUserData in interface UserDataContainer

Parameters:

udc -

See Also:

UserDataContainer.importUserData(edu.uci.ics.jung.utils.UserDataContainer)

isDirected

public boolean isDirected()

Deprecated.

Specified by:

isDirected in interface Graph

Returns:

true if it is directed

See Also:

Graph.isDirected()

newInstance

public ArchetypeGraph newInstance()

Specified by:

newInstance in interface ArchetypeGraph

Returns:

a new instance

See Also:

ArchetypeGraph.newInstance()

numEdges

public int numEdges()

Specified by:

numEdges in interface ArchetypeGraph

Returns:

the number of edges

See Also:

ArchetypeGraph.numEdges()

numVertices

public int numVertices()

Specified by:

numVertices in interface ArchetypeGraph

Returns:

the number of vertices

See Also:

ArchetypeGraph.numVertices()

removeAllEdges

public void removeAllEdges()

Specified by:

removeAllEdges in interface ArchetypeGraph

See Also:

ArchetypeGraph.removeAllEdges()

removeAllVertices

public void removeAllVertices()

Specified by:

removeAllVertices in interface ArchetypeGraph

See Also:

ArchetypeGraph.removeAllVertices()

removeEdge

public void removeEdge(Edge e)

Specified by:

removeEdge in interface Graph

Parameters:

e -

See Also:

Graph.removeEdge(edu.uci.ics.jung.graph.Edge)

removeEdges

public void removeEdges(Set edges)

Deprecated.

Specified by:

removeEdges in interface ArchetypeGraph

Parameters:

edges -

See Also:

ArchetypeGraph.removeEdges(java.util.Set)

removeListener

public void removeListener(GraphEventListener gel,
                           GraphEventType get)

Specified by:

removeListener in interface ArchetypeGraph

Parameters:

gel -

get -

See Also:

ArchetypeGraph.removeListener(edu.uci.ics.jung.graph.event.GraphEventListener, edu.uci.ics.jung.graph.event.GraphEventType)

removeUserDatum

public Object removeUserDatum(Object key)

Specified by:

removeUserDatum in interface UserDataContainer

Parameters:

key -

Returns:

the user datum removed (???)

See Also:

UserDataContainer.removeUserDatum(java.lang.Object)

removeVertex

public void removeVertex(Vertex v)

Specified by:

removeVertex in interface Graph

Parameters:

v -

See Also:

Graph.removeVertex(edu.uci.ics.jung.graph.Vertex)

removeVertices

public void removeVertices(Set vertices)

Deprecated.

Specified by:

removeVertices in interface ArchetypeGraph

Parameters:

vertices -

See Also:

ArchetypeGraph.removeVertices(java.util.Set)

setUserDatum

public void setUserDatum(Object key,
                         Object datum,
                         UserDataContainer.CopyAction copyAct)

Specified by:

setUserDatum in interface UserDataContainer

Parameters:

key -

datum -

copyAct -

See Also:

UserDataContainer.setUserDatum(java.lang.Object, java.lang.Object, edu.uci.ics.jung.utils.UserDataContainer.CopyAction)