Java Forum / General / October 2007
Question about implementing a graph ADT in Java
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 MagazinesGet 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 ...
|
|
|