com.lexonics.edsel
Class Graph

java.lang.Object
  com.lexonics.edsel.Graph

public final class Graph

extends Object

An Edsel graph. A Graph has a node set and an edge set. The node set is a non-null Set of Nodes; no two Nodes in the node set have equal names. The edge set is a non-null Set of Edges; no two Edges in the edge set have the same sources and equal names, the source of every Edge in the edge set is in the node set, and every destination in the destination list of every Edge in the edge set is in the node set. Graphs are immutable.

A Graph may be constructed explicitly, or implicitly by parsing.

Structure

At times, it is desirable to guarantee that a node in a graph has a certain structure, that is, that its attributes and outgoing edges match a certain pattern.

To this end, we may associate a structure node with a node. A structure node specifies a pattern that the attributes and outgoing edges of a node must match. Equivalently, we say that a structure node specifies a structure that a node must have. If a structure node S is associated with a node N, we say that N has structure S.

A node with an associated structure node is called a structured node. Construction of a graph will fail if any structured node in the graph does not have the structure specified by its structure node.

A node without an associated structure node is called an unstructured node.

A structure node is associated with a node by giving the node a single-destination -structure edge; the destination of the edge is the structure node. For example,

        John
        {
                first-name 'John';
                last-name 'Smith';
        |
                -structure Husband;
                wife Mary;
        }

        Mary
        {
                first-name 'Mary';
                last-name 'Smith';
        |
                -structure Wife;
                husband John;
        }

Structure nodes are themselves structured nodes; structure nodes have the predefined structure -Structure, which we will define presently. Note that it follows from this that -Structure must have the structure that it itself specifies.

How do we define a structure node? For the above example, we want to specify that a node having the structure Husband has a single-value first-name attribute, a single-value last-name attribute, and a single-destination wife edge to a node having the structure Wife:

        Husband
        {
                -attribute 'first-name' 'last-name';
        |
                -structure -Structure;
                -edge WifeEdge
                {
                        -name 'wife';
                |
                        -structure -Edge;
                        -destination Wife;
                };
        }

where the predefined structure node -Edge can be defined as

        -Edge
        {
                -attribute '-name';
        |
                -structure -Structure;
                -edge -DestinationEdge
                {
                        -name '-destination';
                |
                        -structure -Edge;
                        -destination -Structure;
                };
        }

The definition of Wife is similar.

To take a more complicated example, consider defining Parent to specify that a node must have a single-value name attribute and a multi-destination child edge to nodes having the structure Child:

        Parent
        {
                -attribute 'name';
        |
                -structure -Structure;
                -multi-edge ChildMultiEdge
                {
                        -name 'child';
                |
                        -structure -MultiEdge;
                        -destination Child;
                };
        }

Here we defined ChildMultiEdge as having the predefined structure -MultiEdge. A -MultiEdge may have a single-value -at-least attribute (default value zero) and a single-value -at-most attribute (default value Integer.MAX_VALUE). It must have a single-value -name attribute and a single-destination -destination edge. We may define -MultiEdge as follows:

        -MultiEdge
        {
                -attribute '-name';
        |
                -structure -Structure;
                -multi-attribute
                        -AtLeastMultiAttribute
                        {
                                -at-most '1';
                                -name '-at-least';
                        |
                                -structure -MultiAttribute;
                        }
                        -AtMostMultiAttribute
                        {
                                -at-most '1';
                                -name '-at-most';
                        |
                                -structure -MultiAttribute;
                        };
                -edge -DestinationEdge;
        }

These definitions use the predefined structure node -MultiAttribute. A -MultiAttribute, like a -MultiEdge, may have a single-value -at-least attribute (default value zero) and a single-value -at-most attribute (default value Integer.MAX_VALUE), and it must have a single-value -name attribute. We may define -MultiAttribute as follows:

        -MultiAttribute
        {
                -attribute '-name';
        |
                -structure -Structure;
                -multi-attribute -AtLeastMultiAttribute -AtMostMultiAttribute;
        }

Note that the singleton specifications -attribute and -edge are logically unnecessary, given the multiple specifications -multi-attribute and -multi-edge; they are provided for notational convenience only. A singleton specification is equivalent to the corresponding multiple specification with the -at-least and -at-most attributes both set to '1'.

We may now define -Structure:

        -Structure
        {
        |
                -structure -Structure;
                -multi-attribute -AttributeMultiAttribute
                {
                        -name '-attribute';
                |
                        -structure -MultiAttribute;
                };
                -multi-edge
                        -MultiAttributeMultiEdge
                        {
                                -name '-multi-attribute';
                        |
                                -structure -MultiEdge;
                                -destination -MultiAttribute;
                        }
                        -EdgeMultiEdge
                        {
                                -name '-edge';
                        |
                                -structure -MultiEdge;
                                -destination -Edge;
                        }
                        -MultiEdgeMultiEdge
                        {
                                -name '-multi-edge';
                        |
                                -structure -MultiEdge;
                                -destination -MultiEdge;
                        };
        }

The predefined structure nodes -Structure, -MultiAttribute, -Edge, and -MultiEdge are implicitly contained by every graph that needs them. They do not, however, have the structures shown here.

Constructor Summary

Graph(Set nodeSet, Set edgeSet)
Construct a Graph with a given node set and edge set.

Method Summary

Set	childSet(Node node, String name) Return a subset of the node set of this Graph, containing each Node that is a destination in the destination list of an Edge in the edge set whose source is a given Node and whose name equals a given name.
Set	edgeSet() Return a shallow copy of the edge set of this Graph.
Set	edgeSetIn(Node node) Return a subset of the edge set of this Graph, containing all Edges whose destination list contains a given Node.
Set	edgeSetOut(Node node) Return a subset of the edge set of this Graph, containing all Edges whose source is a given Node.
boolean	equals(Object o) Compare a given object with this Graph for equality.
int	hashCode() Return the hash code value for this Graph.
Node	node(String name) Return the Node in this Graph with a given name, or null if none.
Set	nodeSet() Return a shallow copy of the node set of this Graph.
Set	parentSet(Node node, String name) Return a subset of the node set of this Graph, containing each Node that is the source of an Edge in the edge set whose destination list contains a given Node and whose name equals a given name.
String	toString() Return a string representation of this Graph.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

Graph

public Graph(Set nodeSet,
             Set edgeSet)

Construct a Graph with a given node set and edge set.

Parameters:

nodeSet - The node set of the Graph. Must be a non-null Set of Nodes, no two of which have equal names. This set is copied by a shallow copy, to guarantee Graph immutability.

edgeSet - The edge set of the Graph. Must be a non-null Set of Edges, no two of which have the same sources and equal names, the source of each of which is in the node set, and every destination in the destination list of each of which is in the node set. This set is copied by a shallow copy, to guarantee Graph immutability.

Throws:

IllegalArgumentException - The node set is null, an element of the node set is not a Node, two Nodes in the node set have equal names, the edge set is null, an element of the edge set is not an Edge, two Edges in the edge set have the same sources and equal names, the source of an Edge in the edge set is not in the node set, a destination in the destination list of an Edge in the edge set is not in the node set, or a structured Node in the node set does not have the structure specified by its structure Node.

Method Detail

childSet

public Set childSet(Node node,
                    String name)

Return a subset of the node set of this Graph, containing each Node that is a destination in the destination list of an Edge in the edge set whose source is a given Node and whose name equals a given name.

Parameters:

node - The node.

name - The name.

Returns:

The requested subset of the node set.

edgeSet

public Set edgeSet()

Return a shallow copy of the edge set of this Graph.

Returns:

A shallow copy of the edge set of this Graph.

edgeSetIn

public Set edgeSetIn(Node node)

Return a subset of the edge set of this Graph, containing all Edges whose destination list contains a given Node.

Parameters:

node - The node.

Returns:

The requested subset of the edge set.

edgeSetOut

public Set edgeSetOut(Node node)

Return a subset of the edge set of this Graph, containing all Edges whose source is a given Node.

Parameters:

node - The node.

Returns:

The requested subset of the edge set.

equals

public boolean equals(Object o)

Compare a given object with this Graph for equality. Return true if the given object is also a Graph, and the two Graphs have equal node sets and edge sets.

Parameters:

o - The object.

Returns:

true if the object is equal to this Graph.

hashCode

public int hashCode()

Return the hash code value for this Graph. The hash code of a Graph is defined to be the sum of the hash codes of its node set and edge set.

Returns:

The hash code value for this Graph.

node

public Node node(String name)

Return the Node in this Graph with a given name, or null if none.

Parameters:

name - The name.

Returns:

The Node in this Graph with the given name, or null if none.

nodeSet

public Set nodeSet()

Return a shallow copy of the node set of this Graph.

Returns:

A shallow copy of the node set of this Graph.

parentSet

public Set parentSet(Node node,
                     String name)

Return a subset of the node set of this Graph, containing each Node that is the source of an Edge in the edge set whose destination list contains a given Node and whose name equals a given name.

Parameters:

node - The node.

name - The name.

Returns:

The requested subset of the node set.

toString

public String toString()

Return a string representation of this Graph.

Returns:

The string representation. The string representation is suitable for parsing by an Edsel parser. If a Node in the node set has the name -Edsel, it appears first in the string representation.