All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class tw.edu.ncnu.im.cnclab.JGAP.Graph

java.lang.Object
   |
   +----tw.edu.ncnu.im.cnclab.JGAP.Graph

public class Graph

extends Object

implements Serializable, Cloneable

The implementation of the graph supports both adjacency matrix and adjacency list. Use enumerations as adjacency list; for loop as adjacency matrix.

Node stands for identity of vertex.

Version:

0.4 Jul 8, 1999

Author:

Ding-Yi Chen

See Also:

Enumeration, Vertex, Edge

canvasSize

The best fit canvas size of the graph

description

The description of the graph.

directed

Whether the graph is directed.

edgeList

The ListArray that store edges

IN_ADJACENCY

This constant value indicates that the getting adjacency edges as in adjacency edges.

MAX_VERTICES

The maximum number of vertices capacity;

modified

Indicate if the graph has been modified.

NUL

Indicate null item

OUT_ADJACENCY

This constant value indicates that the getting adjacency edges as out adjacency edges.

serialNo

The serial number of the graph.

showFlow

Whether the flow of the graph show at screen.

vertexDiameter

The diameter of a vertex;

vertexList

The ListArray that store vertices

vertexSerialNo

The serial number of the vertex.

vertexSpace

The space between each two vertices

Graph()

Construct a directed graph.

Graph(boolean)

Construct a graph.

Graph(boolean, Dimension)

Construct a graph.

addEdge(Edge)

Add a clone of specified edge into this graph.

addEdge(int, int, double, double)

Add an edge into this graph.

addEdge(int, int, double, double, Color)

Add an edge into this graph.

addVertex(int, int)

Add vertex at specified coordinate.

addVertex(int, int, Color)

Add vertex at specified coordinate.

addVertex(Vertex)

Add a clone of specified vertex into this graph.

allEdgesElements()

Returns an enumeration of the all edges of this graph.

clean()

Reset all special attribute the graph.

cleanAllEdges()

Clean all special attribute of Edge.

cleanAllVertices()

Clean all special attribute of Vertices.

clear()

Remove all vertices and edges.

clear(boolean)

Remove all vertices and edges.

clone()

Returns a deep-copied clone of this Graph.

closeTo(int, int)

Return the node that close to specified coordinate.

closeTo(int, int, int)

Return the node that close to specified coordinate.

copyFrom(Graph)

Copies the components from specified Graph to this Graph

deleteAllEdges()

Delete all edges

deleteAllOtherEdges(Color)

Delete all special edges.

deleteEdge(Edge)

Delete an edge of this graph.

deleteEdge(int, int)

Delete an edge of this graph.

deleteNode(int)

Delete the specified node

deleteVertex(Vertex)

Delete the specified vertex

directedAdjVerticesElements(int)

Returns an enumeration of the adjacency vertex of the node of this graph.

directedAdjVerticesElements(int, int)

Returns an enumeration of the adjacency vertex of the node of this graph.

directedAdjVerticesElements(Vertex)

Returns an enumeration of the adjacency vertex of v of this graph.

directedAdjVerticesElements(Vertex, int)

Returns an enumeration of the adjacency vertex of v of this graph.

edgesElements(int)

Returns an enumeration of the outgoing adjacency edges of the node of this graph.

edgesElements(int, int)

Returns an enumeration of the adjacency edges of the node of this graph.

edgesElements(Vertex)

Returns an enumeration of the outgoing adjacency edges of the vertex of this graph.

edgesElements(Vertex, int)

Returns an enumeration of the adjacency edges of the vertex of this graph.

getCanvasSize()

Get the size of the canvas.

getDescr()

Get the description of the graph.

getEdge(int, int)

Get the edge by both ends.

getNumOfEdges()

Return the number of edges in the graph.

getNumOfVertices()

Return the actual number of vertices in this graph.

getPredecessor(int)

Get the predecessor vertex of the specified node.

getPredecessor(Vertex)

Get the predecessor vertex of the specified vertex.

getPredecessorNode(int)

Get the predecessor node of the specified node.

getPredecessorNode(Vertex)

Get the predecessor node of the specified vertex.

getVertex(int)

Get the vertex by node (the identity of vertex)

getVertexSerialNo()

Return the next serial number of vertices, as well as the total number of vertices, including deleted vertices.

inAVertex(int, int)

Return the node that contains the specified coordinate.

isDirected()

Whether the graph is directed.

isEdge(int, int)

Return whether the edge exist specified indexes.

isEdgeUndir(int, int)

Return whether the edge exist specified indexes.

isModified()

Whether the graph has been modified.

isShowFlow()

Whether the graph algorithms need to consider the flow of the graph.

isVertexExist(int)

Return whether the vertex exist at the index (node)

makeVertex(int, int)

If there is a canvas space for vertex, then add vertex at specified coordinate.

purgeDeletedVertex()

Purge the deleted vertex.

reset()

Reset special attribute of the graph.

setCanvasSize(Dimension)

Set the size of the canvas.

setDescr(String)

Set the description of the graph.

setDirected(boolean)

Specified whether the graph has been modified.

setEdge(int, int, double, double)

Set edge attribute.

setEdge(int, int, double, double, Color)

Set edge attribute.

setModified(boolean)

Specified whether the graph has been modified.

setPredecessor(int, int)

Set the predecessor node of the specified node.

setPredecessor(int, Vertex)

Set the predecessor vertex of the specified node.

setPredecessor(Vertex, int)

Set the predecessor node of the specified vertex.

setPredecessor(Vertex, Vertex)

Set the predecessor vertex of the specified vertex.

setShowFlow(boolean)

Whether the graph algorithms need to consider the flow of the graph.

symmetricDifference(Graph)

Symmetric Difference edges (Excludsive OR) with other graph.

undirectedAdjVerticesElements(int)

Returns an enumeration of the adjacency vertex of the node of this graph.

undirectedAdjVerticesElements(Vertex)

Returns an enumeration of the adjacency vertex of v of this graph.

union(Graph)

Union edges with other graph.

verticesElements()

Returns an enumeration of the vertices of this graph.

 public static final int NUL

Indicate null item

 public static final int OUT_ADJACENCY

This constant value indicates that the getting adjacency edges as out adjacency edges.

 public static final int IN_ADJACENCY

This constant value indicates that the getting adjacency edges as in adjacency edges.

 public int serialNo

The serial number of the graph.

 protected int vertexSerialNo

The serial number of the vertex.

 protected boolean modified

Indicate if the graph has been modified.

 protected ListArray vertexList

The ListArray that store vertices

 protected ListArray2 edgeList

The ListArray that store edges

 protected boolean directed

Whether the graph is directed.

 protected boolean showFlow

Whether the flow of the graph show at screen.

 public static final int MAX_VERTICES

The maximum number of vertices capacity;

 public static int vertexDiameter

The diameter of a vertex;

 public static int vertexSpace

The space between each two vertices

 protected Dimension canvasSize

The best fit canvas size of the graph

 protected String description

The description of the graph.

 public Graph()

Construct a directed graph.

 public Graph(boolean directed)

Construct a graph.

Parameters:

directed - whether the graph is directed.

 public Graph(boolean directed,
              Dimension canvasSize)

Construct a graph.

Parameters:

directed - whether the graph is directed.

canvasSize - the size of canvas.

 public String getDescr()

Get the description of the graph.

Returns:

the description of the graph.

 public void setDescr(String descr)

Set the description of the graph.

Parameters:

descr - The description of the graph.

 public Object clone()

Returns a deep-copied clone of this Graph.

Returns:

a deep-copied clone of this Graph.

Overrides:

clone in class Object

 public void copyFrom(Graph src)

Copies the components from specified Graph to this Graph

Parameters:

src - the source Graph

 public void reset()

Reset special attribute of the graph.

See Also:

reset, reset, clean

 public void clean()

Reset all special attribute the graph.

See Also:

clean, clean, reset

 public void clear()

Remove all vertices and edges.

 public void clear(boolean directed)

Remove all vertices and edges.

Parameters:

directed - set the new graph type.

 public boolean isDirected()

Whether the graph is directed.

Returns:

whether the graph is directed.

 protected void setDirected(boolean directed)

Specified whether the graph has been modified.

Parameters:

modified - whether the graph has been modified.

 public boolean isModified()

Whether the graph has been modified.

Returns:

whether the graph has been modified.

 public void setModified(boolean modified)

Specified whether the graph has been modified.

Parameters:

modified - whether the graph has been modified.

 public boolean isShowFlow()

Whether the graph algorithms need to consider the flow of the graph.

Returns:

whether the graph algorithms need to consider the flow of the graph.

 public void setShowFlow(boolean b)

Whether the graph algorithms need to consider the flow of the graph.

Returns:

whether the graph algorithms need to consider the flow of the graph.

 public void symmetricDifference(Graph g)

Symmetric Difference edges (Excludsive OR) with other graph.

Parameters:

g - the graph to process with this graph.

 public void union(Graph g)

Union edges with other graph.

Parameters:

g - the graph to union with this graph.

 public Dimension getCanvasSize()

Get the size of the canvas.

Returns:

the size of canvas

 public void setCanvasSize(Dimension d)

Set the size of the canvas.

Parameters:

d - The new size of canvas.

 public void addVertex(int x,
                       int y)

Add vertex at specified coordinate.

Parameters:

x - the coordinate x of this vertex.

y - the coordinate y of this vertex.

 public void addVertex(int x,
                       int y,
                       Color color)

Add vertex at specified coordinate.

Parameters:

x - the coordinate x of this vertex.

y - the coordinate y of this vertex.

color - the color of this vertex.

 public void addVertex(Vertex v)

Add a clone of specified vertex into this graph.

The method use the infomation of specified vertex to create another vertex.

Parameters:

v - the vertex to add.

 public int makeVertex(int x,
                       int y)

If there is a canvas space for vertex, then add vertex at specified coordinate.

This method prevents vertices congesting in some place. If there is some vertices close to the coordinate of new vertex, makeVertex won't add vertex and return NUL , otherwise add vertex in this graph and return the vertexID of the vertex to add.

Parameters:

x - the coordinate x of this vertex.

y - the coordinate y of this vertex.

Returns:

the vertex ID if sucess; NUL if fail.

 public int inAVertex(int i,
                      int j)

Return the node that contains the specified coordinate.

Parameters:

x - the coordinate x.

y - the coordinate y.

Returns:

The node that contains the specified coordinate; NUL if none of vertices contain the corrdinate.

 public int closeTo(int x,
                    int y)

Return the node that close to specified coordinate.

Parameters:

x - the coordinate x.

y - the coordinate y.

Returns:

The node that close to specified coordinate; NUL if none of vertices close the corrdinate.

 public int closeTo(int x,
                    int y,
                    int distance)

Return the node that close to specified coordinate.

If Math.abs(vertex.x - x) < distance and Math.abs(vertex.y)-y)

Parameters:

x - the coordinate x.

y - the coordinate y.

distance - the distance.

Returns:

The node that close to specified coordinate; NUL if none of vertices close the corrdinate.

deleteVertex

 public void deleteVertex(Vertex v) throws NoSuchVertexException

Delete the specified vertex

Parameters:

v - the vertex to be delete.

Throws: NoSuchVertexException

if the v is not valid.

deleteNode

 public void deleteNode(int node) throws NoSuchVertexException

Delete the specified node

Parameters:

node - the node to be delete.

Throws: NoSuchVertexException

if the node is not valid.

getVertex

 public Vertex getVertex(int node) throws NoSuchVertexException

Get the vertex by node (the identity of vertex)

Parameters:

node - the identity of vertex

Throws: NoSuchVertexException

if the no vertex exist at index node

purgeDeletedVertex

 public void purgeDeletedVertex()

Purge the deleted vertex.

Renumbumering the vertex from 0 to number of vertices

getPredecessor

 public Vertex getPredecessor(int node) throws NoSuchVertexException

Get the predecessor vertex of the specified node.

Parameters:

node - the specified node.

Returns:

the predecessor vertex of the specified node.

Throws: NoSuchVertexException

if the no vertex exist at index node .

getPredecessor

 public Vertex getPredecessor(Vertex v) throws NoSuchVertexException

Get the predecessor vertex of the specified vertex.

Parameters:

v - the specified vertex.

Returns:

the predecessor vertex of the specified vertex.

Throws: NoSuchVertexException

if the v is null.

getPredecessorNode

 public int getPredecessorNode(int node) throws NoSuchVertexException

Get the predecessor node of the specified node.

Parameters:

node - the specified node.

Returns:

the predecessor node of the specified node.

Throws: NoSuchVertexException

if the no vertex exist at index node .

getPredecessorNode

 public int getPredecessorNode(Vertex v) throws NoSuchVertexException

Get the predecessor node of the specified vertex.

Parameters:

v - the specified vertex.

Returns:

the predecessor node of the specified vertex.

Throws: NoSuchVertexException

if the v is null.

setPredecessor

 public void setPredecessor(int node,
                            Vertex predecessor) throws NoSuchVertexException

Set the predecessor vertex of the specified node.

Parameters:

node - the node.

predecessor - the predecessor of node .

Throws: NoSuchVertexException

either code or predecessor is not valid.

setPredecessor

 public void setPredecessor(Vertex v,
                            Vertex predecessor) throws NoSuchVertexException

Set the predecessor vertex of the specified vertex.

Parameters:

v - the vertex.

predecessor - the predecessor of v .

Throws: NoSuchVertexException

either v or predecessor is not valid.

setPredecessor

 public void setPredecessor(int node,
                            int predecessorNode) throws NoSuchVertexException

Set the predecessor node of the specified node.

Parameters:

node - the node.

predecessorNode - the predecessor of node .

Throws: NoSuchVertexException

either node or predecessorNode is not valid.

setPredecessor

 public void setPredecessor(Vertex v,
                            int predecessorNode) throws NoSuchVertexException

Set the predecessor node of the specified vertex.

Parameters:

v - the vertex.

predecessorNode - the predecessor of vertex .

Throws: NoSuchVertexException

either v or predecessorNode is not valid.

isVertexExist

 public boolean isVertexExist(int node)

Return whether the vertex exist at the index (node)

Parameters:

node - the index (node).

Returns:

whether the vertex exist at the index.

getNumOfVertices

 public final int getNumOfVertices()

Return the actual number of vertices in this graph.

Deleted vertices don't count in this method. Use getVertexSerialNo instead while using for-loop or while loop

Returns:

the number of vertices in this graph.

See Also:

getVertexSerialNo

getVertexSerialNo

 public int getVertexSerialNo()

Return the next serial number of vertices, as well as the total number of vertices, including deleted vertices.

Use getNumOfVertices if you don't want to count deleted vertices.

Returns:

the next serial number of vertices.

See Also:

getNumOfVertices

verticesElements

 public final synchronized Enumeration verticesElements()

Returns an enumeration of the vertices of this graph.

Returns:

s an enumeration of the vertices of this graph.

addEdge

 public void addEdge(Edge edge)

Add a clone of specified edge into this graph.

The method use the infomation of specified edge to create another edge.

Parameters:

edge - the edge to add.

addEdge

 public void addEdge(int from,
                     int to,
                     double weight,
                     double flow)

Add an edge into this graph.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

weight - the weight of the edge.

flow - the flow of the edge.

addEdge

 public void addEdge(int from,
                     int to,
                     double weight,
                     double flow,
                     Color color)

Add an edge into this graph.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

weight - the weight of the edge.

flow - the flow of the edge.

color - the color of the edge.

deleteEdge

 public void deleteEdge(int from,
                        int to)

Delete an edge of this graph.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

deleteEdge

 public void deleteEdge(Edge edge)

Delete an edge of this graph.

Parameters:

edge - the edge to be delete.

cleanAllVertices

 public void cleanAllVertices()

Clean all special attribute of Vertices.

See Also:

clean, cleanAllEdges

cleanAllEdges

 public void cleanAllEdges()

Clean all special attribute of Edge.

See Also:

clean, cleanAllVertices

deleteAllOtherEdges

 public void deleteAllOtherEdges(Color color)

Delete all special edges.

Delete edges which color is not same as color .

For example: If you want to keep the edge with color with Edge.normalColor, but delete other, you may use deleteAllOtherEdges(Edge.normalColor) to do this.

Parameters:

color - Ths edge with this status to keep.

deleteAllEdges

 public void deleteAllEdges()

Delete all edges

isEdge

 public boolean isEdge(int from,
                       int to)

Return whether the edge exist specified indexes.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

Returns:

true if edge(from,to) exist; false otherwise.

isEdgeUndir

 public boolean isEdgeUndir(int from,
                            int to)

Return whether the edge exist specified indexes. Direction don't care.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

Returns:

true if edge(from,to) or edge(to,from) exist; false otherwise.

getEdge

 public Edge getEdge(int from,
                     int to) throws NoSuchEdgeException

Get the edge by both ends.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

Throws: NoSuchEdgeException

if the no edge exist at (from,to)

setEdge

 public void setEdge(int from,
                     int to,
                     double edgeWeight,
                     double edgeFlow)

Set edge attribute.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

edgeWeight - the weight of the edge.

edgeFlow - the flow of the edge.

setEdge

 public void setEdge(int from,
                     int to,
                     double edgeWeight,
                     double edgeFlow,
                     Color color)

Set edge attribute.

Parameters:

from - the start node of the edge.

to - the end node of the edge.

edgeWeight - the weight of the edge.

edgeFlow - the flow of the edge.

status - the status of the edge.

color - the color of the edge.

getNumOfEdges

 public int getNumOfEdges()

Return the number of edges in the graph.

edgesElements

 public final synchronized Enumeration edgesElements(int node)

Returns an enumeration of the outgoing adjacency edges of the node of this graph.

Parameters:

node - the node.

edgesElements

 public final synchronized Enumeration edgesElements(Vertex v)

Returns an enumeration of the outgoing adjacency edges of the vertex of this graph.

Parameters:

v - the vertex.

edgesElements

 public final synchronized Enumeration edgesElements(int node,
                                                     int dimension)

Returns an enumeration of the adjacency edges of the node of this graph.

Parameters:

node - the node.

dimension - Graph.OUT_ADJACENCY : return the enumeration of outgoing adjacency edges; Graph.IN_ADJACENCY return the enumeration of incoming adjacency edges.

edgesElements

 public final synchronized Enumeration edgesElements(Vertex v,
                                                     int dimension)

Returns an enumeration of the adjacency edges of the vertex of this graph.

Parameters:

v - the vertex.

dimension - Graph.OUT_ADJACENCY : return the enumeration of outgoing adjacency edges; Graph.IN_ADJACENCY return the enumeration of incoming adjacency edges.

directedAdjVerticesElements

 public final synchronized Enumeration directedAdjVerticesElements(int node)

Returns an enumeration of the adjacency vertex of the node of this graph.

Parameters:

node - the node.

directedAdjVerticesElements

 public final synchronized Enumeration directedAdjVerticesElements(int node,
                                                                   int dimension)

Returns an enumeration of the adjacency vertex of the node of this graph.

Parameters:

v - the vertex.

dimension - Graph.OUT_ADJACENCY : return the enumeration of outgoing adjacency edges; Graph.IN_ADJACENCY return the enumeration of incoming adjacency edges.

directedAdjVerticesElements

 public final synchronized Enumeration directedAdjVerticesElements(Vertex v)

Returns an enumeration of the adjacency vertex of v of this graph.

Parameters:

v - the Vertex.

directedAdjVerticesElements

 public final synchronized Enumeration directedAdjVerticesElements(Vertex v,
                                                                   int dimension)

Returns an enumeration of the adjacency vertex of v of this graph.

Parameters:

v - the Vertex.

dimension - Graph.OUT_ADJACENCY : return the enumeration of outgoing adjacency edges; Graph.IN_ADJACENCY return the enumeration of incoming adjacency edges.

undirectedAdjVerticesElements

 public final synchronized Enumeration undirectedAdjVerticesElements(int node)

Returns an enumeration of the adjacency vertex of the node of this graph. Directed graph is treat as undirected graph.

Parameters:

node - the node.

undirectedAdjVerticesElements

 public final synchronized Enumeration undirectedAdjVerticesElements(Vertex v)

Returns an enumeration of the adjacency vertex of v of this graph. Directed graph is treat as undirected graph.

Parameters:

Vertex - the vertex.

allEdgesElements

 public final synchronized Enumeration allEdgesElements()

Returns an enumeration of the all edges of this graph.

Returns:

s an enumeration of the all edges of this graph.

---

All Packages  Class Hierarchy  This Package  Previous  Next  Index