spiglet.translate.graph
Class Graph

java.lang.Object
  spiglet.translate.graph.Graph

Direct Known Subclasses:

FlowGraph, InterferenceGraph

public abstract class Graph
extends java.lang.Object

This abstract class defines the public API and default implementation of the primitive functions of both types of graphs (control flow and interference graphs) we are going to use in this module.

Author:

Santoso Wijaya

See Also:

Node

Field Summary

protected java.util.List<Node>

nodes The list of all nodes in the graph.

Constructor Summary

Graph()

Method Summary

boolean	addEdge(Node from, Node to) Adds a directed edge between the two given nodes.
boolean	addNode(Node n) Adds the given node to the graph.
protected void	check(Node node) Helper function that simply checks if the given node belongs to this graph.
Node	createNode() Creates a node that is associated to this graph, then return it.
java.util.List<Node>	getNodes() Returns the (unmodifiable) list of all the nodes defined in this graph.
boolean	removeEdge(Node from, Node to) Removes a directed edge from the two given nodes.
java.lang.String	toString() Returns the string representation of this graph, for debugging dump.

Methods inherited from class java.lang.Object

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

Field Detail

nodes

protected java.util.List<Node> nodes

The list of all nodes in the graph. Represented by a linked list.

Constructor Detail

Graph

public Graph()

Method Detail

getNodes

public java.util.List<Node> getNodes()

Returns the (unmodifiable) list of all the nodes defined in this graph.

Returns:

the (unmodifiable) list of all the nodes defined in this graph

createNode

public Node createNode()

Creates a node that is associated to this graph, then return it. Note that the newly created node is not yet added to the graph that instantiates it. Add the node to the graph using addNode(spiglet.translate.graph.Node).

Returns:

a newly instantiated node that is associated to this graph

addNode

public boolean addNode(Node n)

Adds the given node to the graph.

Parameters:

n - the node to add

Returns:

true if the operation succeeds, false otherwise (the node already exists).

addEdge

public boolean addEdge(Node from,
                       Node to)

Adds a directed edge between the two given nodes. Throws an error if the two nodes do not belong to the same graph. This abstract class defines a default implementation that adds edges by adding reference to this Node in the neighbor Nodes' "neighbor" fields.

Parameters:

from - the node whence the edge comes

to - the node where to the edge arrive

Returns:

true if the operation succeeds, false otherwise (the edge already exists)

removeEdge

public boolean removeEdge(Node from,
                          Node to)

Removes a directed edge from the two given nodes. Throws an error if the two nodes do not belong to the same graph. Returns false if no such edge exists to begin with. This abstract class defines a default implementation that assumes edges are represented by references to neighbor nodes in each Node.

Parameters:

from - the node whence the edge comes

to - the node where to the edge arrive

Returns:

true if the operation succeeds, false otherwise (the edge does not exist)

check

protected void check(Node node)

Helper function that simply checks if the given node belongs to this graph. Throws an error if it doesn't.

Parameters:

node - the node to check

toString

public java.lang.String toString()

Returns the string representation of this graph, for debugging dump. The string is in one line, in the form of ({#,#,...,#,}, {(#,#),(#,#),...,(#,#),}), which represents the set of nodes and edges in the graph, where each node is represented by its key number. This default implementation relies on the information from Node.getPredecessors() and Node.getSuccessors(). Override the method if edges are represented differently.

Overrides:

toString in class java.lang.Object

Returns:

the string representation of this graph