Question about implementing a graph ADT in Java

[Eric IsWhoIAm]

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]

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

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]

I will check it out, then. I should have thought of that! Thank you for
your reply.

 

[Stefan Ram]

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.)

 

[Robert Klemme]

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]

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.)

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]

Jeff Higgins wrote:>

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

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]

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]

Yes, but the following situation also is allowed:

A
|
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
this already would be

A
^
|
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:

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

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]

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:

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

{ (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]

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]

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]

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:


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


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



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.

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]

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]

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]

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

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.

 

[Daniel Pitts]

[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.

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".

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.

 

[Jeff Higgins]

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.)

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]

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]

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.)

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