Re: Question about implementing a graph ADT in Java

"Jeff Higgins" <oohiggins@yahoo.com> writes:


  This should use ?V? instead of ?Vertex? to allow
  for ?left? and ?right? to also be an Edge object.


  I call this ?pair-based information storage?,
  a web page to explain it is not finished, but the
  basic ideas can be grasped from the tutorial page
  mentioned yesterday.

  Explained in a few words:

  Knowledge, i.e., a set of assertions, can be expressed as
  a set of (possibly nested) pairs, like:

((isa planet) earth)
((orbits sun) earth)
((orbits sun) venus)
((orbits sun) mars)
(is-even 2)
((has-homepage Example-Corporation) http://example.com)

  Pair-based information storage keeps a set of such pairs,
  which also can be depicted as a generalized graph of the kind
  I wrote about yesterday.

  All pairs and strings are internalized by the Java
  implementation, so that, with the Java implementation

point( "earth" )

  always returns the same reference (vertex), and

point( point( "orbits" ), point( "sun" ))

  always returns the same reference (edge)
  - If such an edge does not exist yet, it is created,
  if it already exists, it is returned.

  By this, points constructed before, can be accessed, again.

  Also, every point has an actual in-list (?rdc?) and out-list
  (?rac?), so that retrieval of information about any point is
  fast: to find what is known about a certain point (such as the
  sun), one just iterates over its in-list - one does not have
  to iterate over all assertions to find those mentioning the
  sun.

  To find out, what orbits the sun, just iterate the out-list
  of ?( orbits, sun )?.

  To find out, what is known about the earth, iterate
  the in-list of ?earth?.

  To find out, about any entities orbiting each other,
  iterate the out-list of ?orbits?

  And so on.


  First, I have to apologize for most of the classes lacking
  documentation! This library is ?work in progress? and still in
  an early state.

  When I wrote implementations of java.util.Iterator<T>, I often
  found it to be convenient to add an ?iterator()? method, so
  that the Iterator object can be used in a for loop.

  The interface ?Iteration<T>? is intended to represent this
  pattern combining Iterator with Iterable.

  Someone told me that it is ?bad style? for an iterator
  to also implement ?java.lang.Iterable<T>? - but I do not
  yet know whether this is true and why it should be bad style.


  This is my fault, because most classes still lack documentation.

  But at least I can give an example and explanation here:

public class Main
{ /** print all words (of length 1, 2, and 3) that can
  be built from the letters "T", "H", and "E" (Scramble). */
  public static void main( final java.lang.String[] args )
  { final java.lang.Object[] hand = new java.lang.Object[]{ "T", "H", "E" };
    for( int i = 1; i <= hand.length; ++i )
    for
    ( final java.lang.Object[] j :
      new de.dclj.ram.system.iteration.Combinations( i, hand ))
    for
    ( final java.lang.Object[] k :
      new de.dclj.ram.system.iteration.Permutations( j ))
    java.lang.System.out.print( java.util.Arrays.toString( k )); }}

[T][H][E][T, H][H, T][T, E][E, T][H, E][E, H][T, H, E][T, E, H][H, T, E]
[H, E, T ][E, T, H][E, H, T]

  So, for a number ?i? and an array ?hand?, ?Combinations( i, hand )?
  gives all i-Combinations from the array as an array, and for an array
  ?j?, ?Permutations( j )? gives all the Permutations of that array.

http://en.wikipedia.org/wiki/Combination
http://en.wikipedia.org/wiki/Permutation


  Oops. I actually try to enforce some quality by building
  the library myself directly before it is published.

  But recently I had added a hack that will replace some
  occurences of ?public? with ?private? before building the
  JavaDoc documentation to hide some parts that should not show
  up in the Documentation.

  This hack is not yet tested and so it seems that this
  ?private? made it into the distribution. It seems that
  you can correct it by replacing ?private? with ?public?
  for the offending field.


  I have no idea why this happens. The type
  ?de.dclj.ram.java.lang.Cloneable? has a single method ?public
  java.lang.Object clone()?, which is called there.
  Maybe it has the same cause as the next error message?


  This is strange as it requests the implementation of a method
  ?Clone()? with an uppercase ?C?, and nowhere such a method
  should be mentioned - neither in my sources nor in Sun's Java SE.
  So it is not clear how ?Clone? with an uppercase ?C? makes it
  into the error message.

  I have no fix for the last two error messages - except to try
  to remove the offending parts of the code - which might render
  some parts of the library unusable, but at least should allow
  one to compile the rest.