Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / October 2007

Tip: Looking for answers? Try searching our database.

Question about implementing a graph ADT in Java

Thread view: 
Eric IsWhoIAm - 20 Oct 2007 17:38 GMT
I am attempting to implement a graph ADT in Java. First, I need some idea of
a newsgroup that would be good for posting questions regarding data
structures. I am programming in Java, but what I really need is a more
abstract answer, I think. Can I post those kinds of questions here, or would
I need to post them elsewhere?

Thanks,
Eric
Christian - 20 Oct 2007 17:50 GMT
Eric IsWhoIAm schrieb:
> I am attempting to implement a graph ADT in Java. First, I need some idea of
> a newsgroup that would be good for posting questions regarding data
[quoted text clipped - 4 lines]
> Thanks,
> Eric

for abstract questions a newsgroup about computer science may help you
more and would be more appropriate.

though I think you may also get some answers here.
Eric IsWhoIAm - 20 Oct 2007 17:54 GMT
I will check it out, then. I should have thought of that! :)  Thank you for
your reply.

> Eric IsWhoIAm schrieb:
>> I am attempting to implement a graph ADT in Java. First, I need some idea
[quoted text clipped - 12 lines]
>
> though I think you may also get some answers here.
Daniel Pitts - 21 Oct 2007 03:15 GMT
[Top posting corrected]
Reply to post follows.

Please refrain from top posting, especially in this newsgroup (also in
most others).  Its considered better to post your contribution either
beneath the quote, or interspersed to address each point of a longer post.

>> Eric IsWhoIAm schrieb:
>>> I am attempting to implement a graph ADT in Java. First, I need some idea
[quoted text clipped - 10 lines]
>> for abstract questions a newsgroup about computer science may help you
>> more and would be more appropriate.
Like I mentioned in my other post, comp.object has a more abstract
tendency, but this group will help you with caveats of the Java
programming language, as well as point out existing tools to help you so
you don't need to "reinvent the wheel".

>> though I think you may also get some answers here.
> I will check it out, then. I should have thought of that! :)  Thank you for
> your reply.
>  
You can also do something called Cross Post. Generally, you should keep
the number of cross-posts to a minimum, and NEVER multi-post (sending
several posts with the same content to different groups).  If you feel
that a conversation really belongs to a wider audience, cross post
(specify more than one group in the to line), its often a good idea to
set a follow-up to a specific group.

Good luck,
Daniel.

Signature

Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Stefan Ram - 20 Oct 2007 18:04 GMT
>I am attempting to implement a graph ADT in Java.

 I have written a simple graph class for my own use.

 A small tutorial for the simple »space« graph class:

http://www.purl.org/stefan_ram/pub/de.dclj.ram.system.space

 The implementation is part of the GPLd library »ram.jar«:

http://www.purl.org/stefan_ram/pub/ram-jar

 OT: A question not related to Java:

 I also would like to ask my favorite graph question here.
 I have not yet found an answer to this question -
 even though I have asked it in several groups:

 My graph system allows points and arrows between them,
 such as:

             A --------------> B

 But it also considers arrows to be points as well, so
 that an arrow might start or end at another arrow. E.g.,

             A --------------> B
                      |
                      |
                      | This arrow starts at the arrow AB
                      | and ends at the point C.
                      |
                      v
                      C

 How is such a graph called? (»metagraph« or »hypergraph« or
 other notions that come to my mind already mean something else.)
Jeff Higgins - 20 Oct 2007 19:03 GMT
[snip]
>  OT: A question not related to Java:
>
[quoted text clipped - 21 lines]
>  How is such a graph called? (»metagraph« or »hypergraph« or
>  other notions that come to my mind already mean something else.)

Perhaps a directed labelled vertex graph?
Directed because the arrows (presumably) indicate the direction
of the edges, and labelled vertex because the vertices may be labelled
arrow or node.
JH
Jeff Higgins - 20 Oct 2007 19:09 GMT
Jeff Higgins wrote:>
> [snip]
>>  OT: A question not related to Java:
[quoted text clipped - 28 lines]
> arrow or node.
> JH

OTOH, the vertex labelling is probably redundant.
If a vertex has a directed edged coming in and another
going out then it is an arrow node.
Stefan Ram - 20 Oct 2007 19:20 GMT
>Perhaps a directed labelled vertex graph?
>Directed because the arrows (presumably) indicate the direction
>of the edges, and labelled vertex because the vertices may be labelled
>arrow or node.

 Yes, but the following situation also is allowed:

                        A
                        |
                        V
                    B------>C

 In this case, BC usually is not considered to be a
 »label« of A. A is not a label of BC either, because
 this already would be

                        A
                        ^
                        |
                    B------>C

 Or another possibility:

                    A------>B
                        \   ^
                         \  |
                          \ |
                           x|
                            |
                            |
                            C

 Here the arrow from AB to CB also would not be called
 a »label«, because CB is no text.
Jeff Higgins - 20 Oct 2007 20:19 GMT
>>Perhaps a directed labelled vertex graph?
>>Directed because the arrows (presumably) indicate the direction
[quoted text clipped - 7 lines]
>                         V
>                     B------>C

May be that our concepts of the term graph do not coincide.
My concept is that of vertices(or nodes) connected by edges.
In the above the vertices are named A, B, and C.  The edges
are named BC and either of AB or AC ( or AD or AA ).
The edge connected at one end to vertex A must be connected to either
of vertex B, or vertex C, or left unconnected to either of vertex
A or B. In the case that the edge connected to vertex A is not connected
at the other end to vertex B or C, then it must be terminated by
another (forth) vertex (possibly called D) or must connect back to
A itself.  There are no edges with more than or less than one vertex
connected to either end.  Edges may not connect to other edges.
Edges may be directed or not , vertices have no sense of direction
(in the graph) - (well, maybe not strictly true).

>  In this case, BC usually is not considered to be a
>  »label« of A. A is not a label of BC either, because
[quoted text clipped - 4 lines]
>                         |
>                     B------>C

Correct.
BC is not the name of vertex A.
BC is the name of edge BC.
A is not the name of edge BC.
A is the name of vertex A.

>  Or another possibility:
>
[quoted text clipped - 8 lines]
>
>  Here the arrow from AB to CB also would not be called

Here edges may not connect to edges, per my concept of graph.

>  a »label«, because CB is no text.

May be that this last statement will lead to some understanding on
my part. I'm not sure how "text" fits into the concept?

JH
Stefan Ram - 20 Oct 2007 20:33 GMT
>May be that our concepts of the term graph do not coincide.
>My concept is that of vertices(or nodes) connected by edges.
>In the above the vertices are named A, B, and C.  The edges
>are named BC and either of AB or AC ( or AD or AA ).

 In this special kind of graph I use, all edges are considered
 to be vertices (possible vertices of edges), too.

 Possibly, you do not want to call this a »graph« at all.

 Ok, then it is a »set of pairs« (which might be depicted with
 points and arrows) or a »generalized graph« - and my question
 would be, if there already is a term for such a set.

 To clarify, I will write the set of pairs (»generalized
 edges«) below the pictures:

>>                         A
>>                         ^
>>                         |
>>                     B------>C

 { (B,C), ((B,C),A) }

>>                     A------>B
>>                         \   ^
[quoted text clipped - 4 lines]
>>                             |
>>                             C

 { (A,B), (C,B), ((A,B),(C,B)) }

>May be that this last statement will lead to some understanding on
>my part. I'm not sure how "text" fits into the concept?

 A »text« was supposed to be a vertex that is not a pair,
 it might also be called »atom«. I called it »text«, because
 it usually is identified by a text.
Jeff Higgins - 20 Oct 2007 20:50 GMT
>>May be that our concepts of the term graph do not coincide.
>>My concept is that of vertices(or nodes) connected by edges.
[quoted text clipped - 37 lines]
>  it might also be called »atom«. I called it »text«, because
>  it usually is identified by a text.

Well, it may take me some time to digest this;  there is a
Mountaineers game on the TV at the moment.

Is there an algebra associated with this 'generalized graph'?

JH
Stefan Ram - 20 Oct 2007 21:08 GMT
>Is there an algebra associated with this 'generalized graph'?

 I am not aware of this.

 A formal definition would be:

   axiom 0 - If something is a string, then it is called an »atom«.
   axiom 1 - There are not other atoms than those given
             by the axiom 0.
   axiom 2 - If something is an atom, then it is called a »point«.
   axiom 3 - If something is a pair of points, then it is
             also called a »point«.
   axiom 4 - There are not other points than those given
             by the axiom 2 and the axiom 3.
   axiom 5 - A set of points that also contains the first
             and second component of each of its pair elements
             is called a »generalized graph«.
   axiom 6 - There are not other generalized graphs than those
             given by axiom 5.

 Then my question can be rephrased as
 »is there already a common term for "generalized graph"?«

 PS: By axiom 5, the actual sets from my previous posting
 should be

     { (B,C), ((B,C),A), A, B, C }
     { (A,B), (C,B), ((A,B),(C,B)), A, B, C }

 (»A, B, C« were omitted as they were considered to be implied
 by the other elements of the set.)
Jeff Higgins - 21 Oct 2007 12:18 GMT
>>Is there an algebra associated with this 'generalized graph'?
>
[quoted text clipped - 27 lines]
>  (»A, B, C« were omitted as they were considered to be implied
>  by the other elements of the set.)

Well, the game's won, I've had some sleep and in the hope of
gaining some common terminology, I wonder if you could look
at this page and say how it might relate.
<http://en.wikipedia.org/wiki/Binary_relation>

JH
Stefan Ram - 21 Oct 2007 12:37 GMT
>I wonder if you could look at this page and say how it might relate.
><http://en.wikipedia.org/wiki/Binary_relation>

 The set of edges of a graph is a (binary) relation.

 (But this is not the term I am looking for, because it is too
 general, and I am looking for a specific term for a graph with
 the specific property that edges are vertices.)
Jeff Higgins - 21 Oct 2007 14:10 GMT
>>I wonder if you could look at this page and say how it might relate.
>><http://en.wikipedia.org/wiki/Binary_relation>
[quoted text clipped - 4 lines]
>  general, and I am looking for a specific term for a graph with
>  the specific property that edges are vertices.)

Stephan, you've taken me out of my depth.  I can't fathom the idea.
I'll have to defer to others more knowledgable for further suggestions.

But, a couple questions still remain.

Does the following Graph display the specific property
that edges are vertices?  How would I use it?

interface V extends Iterable{}

interface E extends V{}

class VertexPair{
 Vertex left;
 Vertex right;
}

class Vertex implements V{
 Set<V> vertices;
 Iterator<V> iterator(){};
}

class Edge implements E{
 Set<VertexPair> pairs;
 Iterator<VertexPair> iterator(){};
}

class Graph{
 Set<Vertex> v;
 Set<Edges> e;
}

What is an de.dclj.ram.system.iteration.Iteration?
I've looked at Combinations, Permutations, and TupleNesting
but still can't get it.

I've built your ram.jar but get 4 errors.

The field BigFloatNumber.value is not visible
ram/src/de/dclj/ram/type/number BigIntNumber.java
line 43 1192961619340 60729
The field BigIntNumber.value is not visible
ram/src/de/dclj/ram/type/number BigFloatNumber.java
line 53 1192961621723 60824
The method clone() is undefined for the type Cloneable
ram/src/de/dclj/ram/system/iteration
TupleNesting.java
line 57 1192961814430 61109
The type IntegralRange must implement the
inherited abstract method Cloneable.Clone()
ram/src/de/dclj/ram/system/iteration
IntegralRange.java
line 25 1192961936736 61110
Jeff Higgins - 21 Oct 2007 14:39 GMT
Oops!

interface V extends Iterable{}

interface E extends V{}

class VertexPair{
 Vertex left;
 Vertex right;
}

class Vertex implements V{
 Set<E> edges;
 Iterator<E> iterator(){};
}

class Edge extends Vertex implements E{
 Set<VertexPair> pairs;
 Iterator<VertexPair> iterator(){};
}

class Graph{
 Set<Vertex> v;
 Set<Edges> e;
}
Stefan Ram - 21 Oct 2007 15:23 GMT
>Does the following Graph display the specific property
>that edges are vertices?

>class VertexPair{
>  Vertex left;
>  Vertex right;
>}

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

>How would I use it?

 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.

>What is an de.dclj.ram.system.iteration.Iteration?

 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.

>I've looked at Combinations, Permutations, and TupleNesting
>but still can't get it.

 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

>The field BigFloatNumber.value is not visible
>ram/src/de/dclj/ram/type/number BigIntNumber.java
>The field BigIntNumber.value is not visible
>ram/src/de/dclj/ram/type/number BigFloatNumber.java

 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.

>line 53 1192961621723 60824
>The method clone() is undefined for the type Cloneable
>ram/src/de/dclj/ram/system/iteration
>TupleNesting.java
>line 57 1192961814430 61109

 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?

>The type IntegralRange must implement the
>inherited abstract method Cloneable.Clone()
>ram/src/de/dclj/ram/system/iteration
>IntegralRange.java
>line 25 1192961936736 61110

 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.
Jeff Higgins - 21 Oct 2007 15:41 GMT
[snip]

Thank you Stephan.  This will give me much to think about
as I digest beer, pepperoni rolls, and football over the next several hours.

>  The type
>  »de.dclj.ram.java.lang.Cloneable« has a single method

There seems to be no de.dclj.ram.java.lang.Cloneable.java
included with the distribution.

>  This is strange as it requests the implementation of a method
>  »Clone()« with an uppercase »C«, and nowhere ...

I apologise. This results from my attempt at a fix.
Stefan Ram - 21 Oct 2007 15:48 GMT
>There seems to be no de.dclj.ram.java.lang.Cloneable.java
>included with the distribution.

  Sorry! This just should be de/dclj/ram/java/Cloneable.java =

package de.dclj.ram.java.lang;
public interface Cloneable
{ public java.lang.Object clone(); }
Patricia Shanahan - 21 Oct 2007 14:53 GMT
>> I wonder if you could look at this page and say how it might relate.
>> <http://en.wikipedia.org/wiki/Binary_relation>
[quoted text clipped - 4 lines]
>   general, and I am looking for a specific term for a graph with
>   the specific property that edges are vertices.)

A binary relation is just a set of ordered pairs. You could have a
Vertex interface, with two implementing classes:

Point - the ultimate, non-edge, vertex.

Edge - has two Vertex elements.

Patricia
Robert Klemme - 20 Oct 2007 19:01 GMT
> I am attempting to implement a graph ADT in Java. First, I need some idea of
> a newsgroup that would be good for posting questions regarding data
> structures. I am programming in Java, but what I really need is a more
> abstract answer, I think. Can I post those kinds of questions here, or would
> I need to post them elsewhere?

It sounds as if a book on data structures and algorithms would be
helpful - at least for answering general questions about graph
implementations and algorithms (for example Sedgewick's book on the matter).

Kind regards

    robert
Jeff Higgins - 20 Oct 2007 20:41 GMT
Eric wrote:
>I am attempting to implement a graph ADT in Java. First, I need some idea
>of a newsgroup that would be good for posting questions regarding data
>structures. I am programming in Java, but what I really need is a more
>abstract answer, I think. Can I post those kinds of questions here, or
>would I need to post them elsewhere?

Professor Bruno R. Preiss has made a text available online.
"Data Structures and Algorithms
with Object-Oriented Design Patterns in Java"
I found it helpful and easy to read. There is a chapter on graphs.
You may view it here:
<http://www.brpreiss.com/books/opus5/html/book.html>
Also see:
<http://www.jgraph.com/>
<http://jgrapht.sourceforge.net/>

JH
Stefan Ram - 20 Oct 2007 20:50 GMT
>Professor Bruno R. Preiss has made a text available online.
>"Data Structures and Algorithms
>with Object-Oriented Design Patterns in Java"
>I found it helpful and easy to read. There is a chapter on graphs.
>You may view it here:
><http://www.brpreiss.com/books/opus5/html/book.html>

 Fresh from the future:

     »Copyright © 19102 by Bruno R. Preiss.«

http://www.brpreiss.com/books/opus5/html/page1.html#SECTION000100000000000000000
Jeff Higgins - 20 Oct 2007 22:08 GMT
>  Fresh from the future:
>
>      »Copyright © 19102 by Bruno R. Preiss.«
>
:-o)
Wow, talk about your advance releases!
Looking at your ram page and the game just now.
Daniel Pitts - 21 Oct 2007 03:08 GMT
> I am attempting to implement a graph ADT in Java. First, I need some idea of
> a newsgroup that would be good for posting questions regarding data
[quoted text clipped - 4 lines]
> Thanks,
> Eric

comp.object will give you a good place to discuss theory of object
oriented programming not specific to (but including) Java.

This group tends to very from "how to I use a for loop" to "What is a
good 'Design Pattern' to use for this problem".  This group gets far
more traffic than comp.object, and I find that the people on comp.object
are somewhat less pragmatic.

This is a great place to get answers, and a good place to have a
discussion. comp.object is an okay place to get answers, but a great
place to have a discussion.

I would start here, and if you're questions aren't answered, ask in
another newsgroup more specific.

Hope this helps,
Daniel.

Signature

Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>



Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.