|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||
See:
Description
| Interface Summary | |
|---|---|
| ColorableGraph | ColorableGraph extends
GraphColoring.Graph with methods
that are useful for a graph-coloring system. |
| DirectedGraph | DirectedGraph is an extension of the
Graph interface that tracks the direction of the edges
that have been added to the graph. |
| Graph | Abstractly, a Graph is a pair (V, E), where V is a set
of nodes and E is collection of edges between those nodes. |
| Class Summary | |
|---|---|
| AbstractGraph | AbstractGraph is a skeletal implementation of the
Graph interface, to minimize the effort required to
implement this interface. |
| Color | Color is a placeholder for specific graph colorers. |
| ColorableGraph.IllegalColor | IllegalColor will be thrown on an attempt to color a node with a color that for some reason is not legal for that node in this graph. |
| ColorableNode | ColorableNode |
| ColorFactory | ColorFactory |
| DefaultSparseNode | DefaultSparseNode |
| GraphColorer | GraphColorer is a class for describing a graph coloring
algorithm. |
| GraphVisualizer | |
| Node | Node is an abstract representation of a node for use
with the Graph object. |
| OptimisticGraphColorer | OptimisticGraphColorer uses a strategy similar to that
of SimpleGraphColorer, except after removing
all nodes with degree < K (where K is the number of colors
provided), it begins optimistically removing nodes in the hopes
that they will not actually need to be spilled. |
| OptimisticGraphColorer.NodeSelector | |
| OptimisticGraphColorer.SimpleSelector | |
| SimpleGraphColorer | SimpleGraphColorer uses the simple but effective graph
coloring strategy of progressively removing nodes with degree less
than K, (where K is the number of colors provided). |
| SparseGraph | SparseGraph is an implementation of a
ColorableGraph object. |
| SparseNode | SparseNode is an extension of a ColorableNode for
use with the SparseGraph object. |
| UnableToColorGraph | UnableToColorGraph is a control-flow construct for
indicating the provided Graph Coloring algorithm failed to color a
given graph. |
| UnboundedGraphColorer | UnboundedGraphColorer uses the graph coloring strategy
provided by another GraphColorer to search for a near
minimum number of colors required. |
| Exception Summary | |
|---|---|
| ColorableGraph.AlreadyColoredException | AlreadyColoredException will be thrown on attempt to call
g.setColor(node,color) when n is present in the
node -> color mapping. |
| ColorableGraph.AlreadyHiddenException | AlreadyHiddenException will be thrown on attempt to call
g.addNode(n) while n is a member of the set of
hidden nodes in g. |
| EdgeNotPresentException | EdgeNotPresentException |
| IllegalEdgeException | IllegalEdgeException |
| NodeAlreadyColoredException | NodeAlreadyColoredException |
| NodeNotColoredException | NodeNotColoredException |
| NodeNotPresentInGraphException | NodeNotPresentInGraphException |
| NodeNotRemovedException | NodeNotRemovedException |
| NoFactorySetException | NoFactorySetException |
| ObjectNotModifiableException | ObjectNotModifiableException |
| WrongNodeTypeException | WrongNodeTypeException |
Provides the classes for coloring generic Graphs.
The purpose of Graph Coloring is to detect potential Interferences
(Resource Conflicts), and then use that knowledge to allow resource
consumers to share resources. Graph coloring problems derive from
the old mapmakers' rule that adjacent countries on a map should be
colored with different colors
. So in that case, colors are the
resource, countries are the consumers, and borders between countries
are the interferences.
The design of the GraphColoring package implements graph coloring analysis in terms of four parts: Graphs to represent resource consumers and the interferences between them, Colors to represent the resources, ColorFactories to represent resource generators (to allow for unbounded resources to be represented, like Stack Offsets), and GraphColorers to assign a mapping from consumers to resources.
Usually graph coloring is used for Register Allocation problems, although other problems can often be reduced to graph coloring (such as interface method table layout).
|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||