Any comments about JGraphT?
Hi,
I'm designing the data structures for representing simple undirected graphs in my application, and came across JGraphT http://jgrapht.sourceforge.net (it's also been mentioned in this forum).
If there's anyone here who's used JGraphT, could I get some feedback on the scalability etc? I'm dealing with graphs of 10000 vertices and approx 50 million edges, so I was wondering if JGraphT can handle something as big?
TIA,
Linda
i've not used JGraphT for anything above simple evaluation, but have used JGraph (which is what its an adapter for) a bit.
if you're needing to visualise these graphs then I think 50M edges is going to cause quite serious trouble (in terms of speed). Especially with graph drawing algorithms on the structures in question.
that said though, it may not be the limiting factor (the complexity of the algorithm itself is more likely to be the problem)
both projects being open source are likely to be quite contactable if you need definitive answers
or playing with the webstart version of JGraphPad might be of help
http://jgraph.sourceforge.net/webstart.html
it does seem pretty slow for more than hundred nodes, but compare this to any similar native tool and its not bad.. so I don't think its particularly JGraphs fault (or even that much Javas)
if you are purely after speed of processing some abstraction of a graph then a simple data-structure representation is the best bet
asjf
asjfa at 2007-7-14 22:12:58 >
You can also consider Graph foundation classes from ibm's alpha works
http://www.alphaworks.ibm.com/tech/gfc
An I agree. Agorithms in general will probably be your performance
bottle-neck. The author of the GFC seems to be quite contactable
(he posted me a fix for a bug I found within a day). But my graphs
were nowhere near as large as yours (100's of nodes in fully connected
graphs beign the most challenging) (Kruskal's Minimum Spanning Tree and
recursive minimun cuts being the algorihtms).
matfud
> if you are purely after speed of processing some
> abstraction of a graph then a simple data-structure
> representation is the best bet
Thanks, this is what I actually suspected. I don't need to display the graphs, but I am going to be writing some algorithms (namely Vertex Cover, Maximum Independent Set and Minimum Dominating Set) to process these huge graphs.
I was just hoping to get away with using JGraphT or somethig similar so that I don't need to create my own data format and I can get down to coding the algorithms ASAP :)
Also thanks for the link to GFC, I'll have a closer look later, but from the FAQs it seems that it's mainly concerned with graph visualisation.
Linda
A big chunk of the GFC is for visualisation but is is seperate from
the data structures used to represent the graphs (a different package).
But as a previous poster said general graph representaion structures
are likely to be significantly less efficient then rolling your own
specialised structures for performing algoithms on
matfud
> A big chunk of the GFC is for visualisation but is is
> seperate from
> the data structures used to represent the graphs (a
> different package).
>
> But as a previous poster said general graph
> representaion structures
> are likely to be significantly less efficient then
> rolling your own
> specialised structures for performing algoithms on
matfud - i've never used GFC, whats it like in general? how does it compare to JGraph?
thanks,
asjf
asjfa at 2007-7-14 22:12:58 >
I'm afraid I've never used JGraph so I can't make the comparison.
GFC is very flexible (so not stunningly easy to use). In general though
it allows you to attach as much arbitrary data as you wish to Graphs,
vertices and edges (via dictionaries). And to find elements based on
their additional data. (I haven't used it for a while but it was
based on java 1.1 which can be useful for some people (Enumerations
rather then Iterators (not really a problem) not sure what the display
stuff uses though). GFC is split into three packages: The basics for
creation and manipulation of graph structures, a package for graphical
layout algorithms (independent of actual drawing), and a package for display
(probably dependent on awt but maybe updated for swing).
The basic graph bit has a large number of classes to represent different graph
structures (directed, undirected, paths, nets, trees, forests etc.). Into these graphs you can insert vertices and edges. In fact a vertex
or edge can exist in multiple graphs at the same time (again this can
be useful to save memory space. The graph structures have a variety of
utility methods that allow things like tree traversals (on Trees of course)
tests for completeness (is the graph fully connected), connected-ness
(are these two nodes connected to each other or is one reachable from
the other via the graph (directed or undirected graphs) etc.
While probably not being the most efficient thing in the world for
writing algorihtms on top of, it can save a huge amount of programming
time when comapred to rolling your own.
matfud
Hi Linda,
Accidently came accross this post...
Did a little benchmark on my home PC with 1/10th of the size you are talking about, that is, graph with 10,000 vertices and 5,000,000 edges.
The following figures were obtained using JGraphT 0.5.0:
- memory consuption: ~300MB (costs a little less than 60 bytes for every edge)
- depth first traversal: 4 secs
- breadth first traversal: 10 secs
If you want I can email you the program to play and test on your machine - just let me know at barak_naveh@sourceforge.net.
All the best,
Barak
Barak,
I tried to reply you but your e-mail address keeps bouncing back (see below).
It would be great if you could send me the test program, my address is linda_bu@dodo.com.au
Thanks!
Linda
-- The following addresses had permanent fatal errors --
<barak_naveh@sourceforge.net>
(reason: 550 Unrouteable address)
-- Transcript of session follows --
... while talking to mail.sourceforge.net.:
>>> RCPT To:<barak_naveh@sourceforge.net>
<<< 550 Unrouteable address
550 5.1.1 <barak_naveh@sourceforge.net>... User unknown
> Hi Linda,
>
> Accidently came accross this post...
>
> Did a little benchmark on my home PC with 1/10th of
> the size you are talking about, that is, graph with
> 10,000 vertices and 5,000,000 edges.
>
> The following figures were obtained using JGraphT
> 0.5.0:
>
> - memory consuption: ~300MB (costs a little less
> than 60 bytes for every edge)
> - depth first traversal: 4 secs
> - breadth first traversal: 10 secs
>
> If you want I can email you the program to play and
> test on your machine - just let me know at
> barak_naveh@sourceforge.net.
>
> All the best,
> Barak
Hi Linda,
Processing huge graphs with "some algorithms" like the ones you mentioned is quite hard, as Vertex Cover, Maximimum Independent Set and Minimum Dominating Set are all NP-Complete AFAIK. This means it might take quite some (life-) time of yours ;-) computing
Looking at the numbers:
N = 10.000 M = 50.000.000 looks like a rather complete graph so that makes things in most cases (especially in yours) way easier -> see the literature for some O(1) solutions to these problems.
But if you are really looking for a library, you might want to take a look at yFiles, our Java Graph Drawing and Algorithms Library.
http://www.yworks.com/products/yfiles
I ran the same tests as the OP and got the following results:
Memory consumption about 350 megs,
DFS time: 4 seconds
BFS time: 5 seconds
each using standard algorithms. Using your own version (customized to your exact problem) might make things speed up a little more....
BTW if you want to do some experiments using normal size graphs, you should try our free Java Graph Editor yEd which is available as a WebStart application from http://www.yworks.com/products/yed
Greetings and have fun!
Sebastian
Sebastian,
> Processing huge graphs with "some algorithms" like the
> ones you mentioned is quite hard, as Vertex Cover,
> Maximimum Independent Set and Minimum Dominating Set
> are all NP-Complete AFAIK. This means it might take
> quite some (life-) time of yours ;-) computing
Yes, I know these are all NPC problems. We're not actually looking for optimal solutions here, just some sort of heuristic or approximation.
> Looking at the numbers:
> N = 10.000 M = 50.000.000 looks like a rather
> complete graph so that makes things in most cases
> (especially in yours) way easier -> see the literature
> for some O(1) solutions to these problems.
The numbers I gave have exactly half the edges of a complete graph (that is, if my calculations are correct).
However, most of the time we'll be dealing with 'normal' graphs, it was just required that we should be able to handle huge graphs, at the expense of a lot longer computation time, so my main concern was that the graph library is physically able to create and traverse a graph of the given size, not the time it takes. We are planning to supply several algorithms to solve a given problem, so based on the size of the graph either a more accurate algorithm (for a small graph) or a fast heuristic (for a big graph) can be chosen.
Anyway, I've ran Barak's test program and confirmed that JGraphT will do what we need to do, so that's the one we'll be using.
Thanks Sebastian for the info.
Linda
Hi Sebastian,
yFiles is indeed a lovely library, and I would have definitely used it myself unless it had a "dark" side: http://www.yworks.com/en/products_yfiles_commercialinfo_prices.htm
Anyway, cool to know that free JGraphT matches yFiles in DFS and beats yFiles on memory consumption (15% less)!!
Will improve the known BFS performance issue so that next JGraphT version will run like the wind...
Thanks for making my day,
Barak Naveh
http://jgrapht.sourceforge.net/
> yFiles is indeed a lovely library, and I would have
> definitely used it myself unless it had a "dark" side:
> http://www.yworks.com/en/products_yfiles_commercialinfo
> prices.htm
Yes, I think I forgot to mention that this is a university project for me, so that's why I was looking for a free library.
And indeed, Barak, well done with JGraphT!
> BTW if you want to do some experiments using normal
> size graphs, you should try our free Java Graph Editor
> yEd which is available as a WebStart application from
> http://www.yworks.com/products/yed
this is impressive :)
do you intend to start charging at some point? (or is there a difference between the priced and free versions?) also what do you make of the JGraph project?
thanks,
asjf
asjfa at 2007-7-14 22:12:58 >
> > yEd which is available as a WebStart application
> from
> > http://www.yworks.com/products/yed
>
> this is impressive :)
thank you!
> do you intend to start charging at some point?
Good news: currently not, yed is free of charge and probably will stay free in the current form.
> (or is
> there a difference between the priced and free
> versions?)
You should have taken a closer look at what you get when you or your company purchases *yFiles*, which indeed is a library. yEd is using yFiles and demonstrates *some* of the capabilities of the library.
Paying the price for a yFiles license, means you get the right to use the API of the library (which by the way is online on our site, if you are interested). Also you get the right to create your own applications that use the yFiles library and distribute them in almost any way you like and you do *not* have to pay any royalties, i.e. the price is a one time cost and you can develop as many programs as you like.
yEd on the other hand offers no API and you are not allowed to reuse, modify, disassemble, redistribute (and so on) the application.
> also what do you make of the JGraph
> project?
nothing ;-) JGraph is a well done Graph Viewer with editing capabilities. The strength of the yFiles library is the automatic layout feature for diagrams and graphs. These are highly sophisticated algorithm which produce impressive layouts very quickly (see our site, there is a gallery or try the editor). JGraph(Pad) has very rudimentary automatic layout support.
Also I would say yFiles' view component performs better than JGraph's. And last but not least since it is a commercial library you get high class support, warranties and the usual things you might miss with Open Source projects, but I really don't want to start any flame wars ;-)
Gaudenz did a great job and JGraph is good if you want to create your own application that has basic support for editing graph structures, but if your company wants to create an application I would definitely recommend using yFiles. You could even use the JGraph component to display and edit graph structures and use yFiles to do the algorithms and the layout, but why should you use two different libraries if one offers both?
greetings, Sebastian
> > Looking at the numbers:
> > N = 10.000 M = 50.000.000 looks like a rather
> > complete graph so that makes things in most cases
> > (especially in yours) way easier -> see the
> literature
> > for some O(1) solutions to these problems.
>
> The numbers I gave have exactly half the edges of a
> complete graph (that is, if my calculations are
> correct).
The problems you stated use undirected graphs. A complete undirected graph has N*(N-1)/2 edges, e.g. K3 has 3*2/2 = 2 edges, K5 has 5*4/2 = 10 edges.
In your case this is M = 49.995.000 which is an even smaller number, hence an undirected graph with 10.000 vertices/nodes and 50.000.000 edges is complete and has an additional 5.000 multiple edges (multiple edges between two nodes) if you do not allow self-loops (edges, where both end points are at the same node).
> However, most of the time we'll be dealing with
> 'normal' graphs, it was just required that we should
> be able to handle huge graphs, at the expense of a lot
> longer computation time, so my main concern was that
> the graph library is physically able to create and
> traverse a graph of the given size, not the time it
> takes. We are planning to supply several algorithms to
> solve a given problem, so based on the size of the
> graph either a more accurate algorithm (for a small
> graph) or a fast heuristic (for a big graph) can be
> chosen.
ok, that's what I thought you were intending to do.
greetings, Sebastian
> > > Looking at the numbers:
> > > N = 10.000 M = 50.000.000 looks like a rather
> > > complete graph so that makes things in most cases
> > > (especially in yours) way easier -> see the
> > literature
> > > for some O(1) solutions to these problems.
> >
> > The numbers I gave have exactly half the edges of a
> > complete graph (that is, if my calculations are
> > correct).
>
> The problems you stated use undirected graphs. A
> complete undirected graph has N*(N-1)/2 edges, e.g. K3
> has 3*2/2 = 2 edges, K5 has 5*4/2 = 10 edges.
> In your case this is M = 49.995.000 which is an even
> smaller number, hence an undirected graph with 10.000
> vertices/nodes and 50.000.000 edges is complete
Yes, you're right, of course. I must have forgot to divide 50 M by 2 again, since we definitely want half the complete graph. That brings it down to 25M :) (24997500 to be exact)
Linda
I did some memory testing using the com.graphbuilder.struc.Graph.
What I found was that for a complete graph on 3163 nodes (that is 5000703 edges) the total memory used was 220 MB.
The specs are:
create node : O(1)
create edge : O(1)
delete node : O(deg(n))
delete edge : O(1)
are adjacent : O(min(deg(n1),deg(n2)))
Here is the code I used to test it:
import com.graphbuilder.struc.Graph;
public class GraphTest {
public static void main(String[] args) throws Throwable {
Runtime rt = Runtime.getRuntime();
// amount of memory used by JVM (usually about 0.25 MB on my machine)
long javaMem = rt.totalMemory() - rt.freeMemory();
int n = Integer.parseInt(args[0]);
int m = n * (n - 1) / 2;
System.out.println("Num nodes: " + n);
System.out.println("Num edges: " + m);
System.out.println();
System.out.println("java memory: " + javaMem);
Graph g = new Graph(n, m, n-1, false);
long graphMem = (rt.totalMemory() - rt.freeMemory()) - javaMem;
System.out.println("graphMem: " + graphMem);
for (int i = 0; i < n; i++)
g.createNode();
long nodeMem = ((rt.totalMemory() - rt.freeMemory()) - (javaMem + graphMem));
System.out.println("nodeMem: " + nodeMem);
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
g.createEdge(i, j);
long edgeMem = (rt.totalMemory() - rt.freeMemory()) - (javaMem + graphMem + nodeMem);
System.out.println("edgeMem: " + edgeMem);
System.out.println();
System.out.println("" + (1.0 * nodeMem / n) + " bytes / node");
System.out.println("" + (1.0 * edgeMem / m) + " bytes / edge");
System.out.println();
System.out.println("graphMem + nodeMem + edgeMem = " + (graphMem + nodeMem + edgeMem));
long totalMem = (rt.totalMemory() - rt.freeMemory()) - javaMem;
System.out.println("total: " + totalMem + " (" + (1.0 * totalMem / (1024 * 1024)) + "MB)");
System.out.println();
System.out.println(graphMem);
System.out.println(nodeMem);
System.out.println(edgeMem);
System.out.println(totalMem);
}
}
Hi,
> I did some memory testing using the
> com.graphbuilder.struc.Graph.
Interesting... could you point me to the API or give us any links where to hava a look at this API, project or product? I had no success googleing for graphbuilder :-(
> What I found was that for a complete graph on 3163
> nodes (that is 5000703 edges) the total memory used
> was 220 MB.
This sounds ok, but I would definitely want to see the API, since I don't think you can compare these figures with the ones of JGraphT or yFiles (actually you cannot really compare the figures of the latter two implementations, but that's another point).
> The specs are:
>
> create node : O(1)
> create edge : O(1)
> delete node : O(deg(n))
> delete edge : O(1)
> are adjacent : O(min(deg(n1),deg(n2)))
This is ok, anything else would have been inefficient (well, you can tune "are adjacent" to O(1) without using an adjancy matrix - different story). What about memory consumption and O() specs for edge and node traversals? For algorithms, these specs often are of a much greater importance.
> Graph g = new Graph(n, m, n-1, false);
This line seems to make the big difference, why would you want to tell the graph in advance how big it is going to be. Maybe you cannot... so are there any restrictions concerning graph modifications after you specified any initial sizes?
> for (int i = 0; i < n; i++)
> g.createNode();
> for (int i = 0; i < n; i++)
> for (int j = i+1; j < n; j++)
> g.createEdge(i, j);
You structure does not seem to support Object identifiers, this is truely an advantage concerning memory consumption, but this is awful for programmers. How would you do the following:
g.createNode(); // remember index 0
g.createNode(); // remember index 1
g.createEdge(1,2);
g.createNode(); // remember index 2
g.removeNode(1);
how do i create an edge between the first and third node now? do i have to call:
g.createEdge(0,2);
or
g.createEdge(0,1);
?
what about memory consumption if I remove lots of elements from the graph structure? Does the wasted space get GCed or is it "lost forever"?
Thanks for your answers and greetings,
Sebastian
it can give an estimate, but should really measure memory externaly using the operating system. The rt.totalMemory() - rt.freeMemory() does not count all the used memory. big difference.
>
> Interesting... could you point me to the API or give
> us any links where to hava a look at this API, project
> or product? I had no success googleing for
> graphbuilder :-(
>
http://graphbuilder.hypermart.net/Graph.html
> What about
> memory consumption and O() specs for edge and node
> traversals? For algorithms, these specs often are of a
> much greater importance.
>
I will look into it...
> > Graph g = new Graph(n, m, n-1, false);
>
> This line seems to make the big difference, why would
> you want to tell the graph in advance how big it is
> going to be. Maybe you cannot... so are there any
> restrictions concerning graph modifications after you
> specified any initial sizes?
>
For efficiency purposes you can specify the initial sizes for node, edge and incident edge arrays. The graph is not restricted unless there is a GraphManager present.
> You structure does not seem to support Object
> identifiers, this is truely an advantage concerning
> memory consumption, but this is awful for programmers.
> How would you do the following:
> g.createNode(); // remember index 0
> g.createNode(); // remember index 1
> g.createEdge(1,2);
> g.createNode(); // remember index 2
> g.removeNode(1);
>
Actually, the API is very OO.
> how do i create an edge between the first and third
> node now? do i have to call:
> g.createEdge(0,2);
> or
> g.createEdge(0,1);
> ?
The first way would create an edge between the first and third node.
> what about memory consumption if I remove lots of
> elements from the graph structure? Does the wasted
> space get GCed or is it "lost forever"?
>
It gets GCed, unless an UndoManager is present. The com.graphbuilder.undo API hasn't been made available online. There are two methods that relate to memory consumption for the UndoManager, which are setSizeLimit(int) and discardAllEdits(). If there is no UndoManager, then once an element is deleted it is forever removed from the graph.
Test results for DFS and BFS using com.graphbuilder.struc.Graph:
Structure was a complete graph on 3163 nodes (that is 5000703 edges).
DFS time: 2.08 seconds
BFS time: 2.0 seconds
DFS code:
Stack s = new Stack();
boolean[] visited = new boolean[g.order()];
s.push(g.getNode(0));
while (!s.isEmpty()) {
Graph.Node cn = (Graph.Node) s.peek(); // current node
visited[cn.indexOf()] = true;
int i = 0;
for (; i < cn.degree(); i++) {
Graph.Node nbor = cn.node(i);
if (!visited[nbor.indexOf()]) {
s.push(nbor);
break;
}
}
if (i == cn.degree()) // no unvisited nbors found
s.pop();
}
//
BFS code:
Queue q = new Queue();
boolean[] visited = new boolean[g.order()];
boolean[] inq = new boolean[g.order()]; // in queue
q.add(g.getNode(0));
while (!q.isEmpty()) {
Graph.Node cn = (Graph.Node) q.next(); // current node
if (!visited[cn.indexOf()])
visited[cn.indexOf()] = true;
for (int i = 0; i < cn.degree(); i++) {
Graph.Node nbor = cn.node(i);
if (!visited[nbor.indexOf()] && !inq[nbor.indexOf()]) {
inq[nbor.indexOf()] = true;
q.add(nbor);
}
}
}
Hi
> http://graphbuilder.hypermart.net/Graph.html
Thanks, although there is very little additional information there ;-)
> Actually, the API is very OO.
I agree, there *are* methods that work on objects.
> > how do i create an edge between the first and third
> > node now? do i have to call:
> > g.createEdge(0,2);
> > or
> > g.createEdge(0,1);
> > ?
> The first way would create an edge between the first
> and third node.
The API says:
When an element is removed from an array, the last element in the array is moved to the index location of the deleted element, its index value is updated, the size counter is decreased and the last index is set to null.
So it should be the second way, since node index 2 became node index 1 after I removed node index 1.
> > what about memory consumption if I remove lots of
> > elements from the graph structure? Does the wasted
> > space get GCed or is it "lost forever"?
> >
> It gets GCed, unless an UndoManager is present. The
> com.graphbuilder.undo API hasn't been made available
> online.
Has anything else been made available online except for the things stated in this forum?
Regards, Sebastian
> Hi
> > http://graphbuilder.hypermart.net/Graph.html
> Thanks, although there is very little additional
> information there ;-)
>
True, true. I suppose you are wondering what is graphbuilder.com?
> > Actually, the API is very OO.
>
> I agree, there *are* methods that work on objects.
>
Example of why "very": "Node what is your degree?" instead of "Graph, what is the degree of this node?"
> > > how do i create an edge between the first and
> third
> > > node now? do i have to call:
> > > g.createEdge(0,2);
> > > or
> > > g.createEdge(0,1);
> > > ?
> > The first way would create an edge between the
> first
> > and third node.
>
> The API says:
> When an element is removed from an array, the last
> element in the array is moved to the index location of
> the deleted element, its index value is updated, the
> size counter is decreased and the last index is set to
> null.
>
> So it should be the second way, since node index 2
> became node index 1 after I removed node index 1.
>
Sorry, I didn't realize the code above your question related to the same question. Yes, you are correct.
> >
> > It gets GCed, unless an UndoManager is present.
> The
> > com.graphbuilder.undo API hasn't been made
> available
> > online.
> Has anything else been made available online except
> for the things stated in this forum?
>
I will see what I can do about making some class files available. Is there anything else you are looking for?
> > Hi
> > > http://graphbuilder.hypermart.net/Graph.html
> > Thanks, although there is very little additional
> > information there ;-)
> >
> True, true. I suppose you are wondering what is
> graphbuilder.com?
Yes, I have been wondering that. Is it some big secret or something? I went to http://graphbuilder.hypermart.net/, but that just shows "This is a default template, indicating that the webmaster has not yet uploaded a Web site to the server."
Graphbuilder is a project started by a group of Queen's University (Kingston, Ontario, Canada) students. It is a research tool for graph theory and computational geometry.
> it can give an estimate, but should really measure
> memory externaly using the operating system. The
> rt.totalMemory() - rt.freeMemory() does not count all
> the used memory. big difference.
You are probably right. The following is a break down of the memory used by each node and edge:
Each Node uses the following # of bytes:
8 : reference to host graph
8 : reference from host graph
8 : int (index in graph)
8 : reference to an edge array
8 : int (degree)
Total: 40 bytes
Each Edge uses the following # of bytes:
8 : reference to host graph
8 : reference from host graph
8 : int (index in graph)
8 : int (index in node1)
8 : int (index in node2)
8 : reference to node1
8 : reference to node2
8 : reference from node1
8 : reference from node2
Total: 72 bytes
If there are 5,000,000 edges, that is about 343 MB. However, it is possible to remove the reference to the host graph, which would give a total usage of 305 MB.
But I was wondering if Java perhaps does some optimizations. If so, how do I monitor the total memory used?
> If so, how do I monitor the total
> memory used?
afaik,
maxMem = the hard limit (ie the value passed to -Xmx)
totalMem = amount of maxMem claimed (but not. nec. in allocation)
freeMem = amount of totalMem free
so why can (totalMemory - freeMemory) not be used?
asjf
asjfa at 2007-7-19 4:59:09 >
Hi again
I just wanted to put some things right, since your post makes the other libraries look bad.
Your calculation seems a bit naive:
> The following is a break down
> of the memory used by each node and edge:
>
> Each Node uses the following # of bytes:
>
> 8 : reference to host graph
> 8 : reference from host graph
> 8 : int (index in graph)
> 8 : reference to an edge array
> 8 : int (degree)
>
> Total: 40 bytes
I do not know exactly what you mean by "reference from", maybe that is the mistake, but If I understand you right, you say that the memory an object uses depends on the sum of the instance variables only. This is somehow correct, but you forgot some of the less obvious instance variables: Each instance object has at least a reference to it's Class, that's why an instance of java.lang.Object, although carrying not much useful information uses at least somewhat around 12 bytes heap size.
On the other hand an array of size 0 for example uses somewhat around 20 bytes, even though it stores no useful information. Therefore "reference to an edge array" may be 8 bytes, but the edge array itself will take up at least say 16 bytes (I think it is even 20 bytes, but that's not the point). So your list should say:
"24: an edge array"
and an additional:
"ca. 12: the instance object itself"
and the total would then be something like 68 bytes.
>
>
> Each Edge uses the following # of bytes:
>
> 8 : reference to host graph
> 8 : reference from host graph
> 8 : int (index in graph)
> 8 : int (index in node1)
> 8 : int (index in node2)
> 8 : reference to node1
> 8 : reference to node2
> 8 : reference from node1
> 8 : reference from node2
>
> Total: 72 bytes
while there seems to be some redundancy in this data structure (the index of the node and the node itself) which could save you some space, again you forgot the ca. 12 bytes for the instance object itself.
Nevertheless this isn't too much space so this is actually quite good, but there is a huge disadvantage in using this kind of graph structure (as I pointed out in an earlier post):
You cannot efficiently traverse the graph structure, especially if your graph is dynamic or used directed edges. This is because you are using simple arrays (at least that's what you say) to store adjacency information and all of the graph's nodes. E.g. if you create a complete graph, remove half of its edges and try to do you algorithms on the resulting structure, you will:
1. need to skip the empty array slots
2. still have the memory reserved for elements which could have otherwise been gc'ed already (not the instances but the empty array slots).
3. have to skip all outgoing edges if you want to iterate through all incoming edges and vice versa (which affects the running time of your algorithms)
if not, you would have to "compress" and copy your arrays from time to time, which would still alter your indices.
All in all I would say for most scenarios your graph structure isn't that superior over yFiles' or JGraphT's implementations I would say.
Think about it....
regards - Sebastian
>your post makes the other libraries look bad
(some libraries do this on their own, I can't take all the blame =)
Thanks for pointing out some of my assumptions. I assumed that a reference to an array only requires 8 bytes. Because the # of nodes was insignificant, I did not notice this.
Do you have a reference to Java memory allocation on the other issues you mentioned? You seem to be very knowledgeable!
But, you have made some assumptions that I would like to correct ;)
1. There are no gaps. The indices are all updated behind the scenes. This was accomplished by using public inner static classes, Graph.Node, Graph.Edge.
2. Traversals won't be slow because there are no gaps in the arrays. I am a little surprised you said this (maybe you thought this because you thought deleting would leave gaps). In an earlier post of mine, I stated the DFS and BFS times, which were equally fast as the other two graph libraries in this thread. Actually, they were a little faster (but maybe my computer is faster).
3. There is no wasted space. If half the edges are deleted, the API gives has the capability to trim the arrays. I can see if you thought there were gaps, this would not be possible.
Very soon graphbuilder.com is going to be officially online, then you can see for yourself :-)
Hi again!
> Do you have a reference to Java memory allocation on
> the other issues you mentioned? You seem to be very
> knowledgeable!
For one thing we did a lot of investigations ourselves: we wrote little test programs, we are using a profiler (JProfiler) which includes memory profiling and we googled the web a lot:
http://www.javaworld.com/javaworld/javatips/jw-javatip130.html has very valuable information.
BTW: I am one of the developers of the yFiles graph library (http://www.yworks.com/products/yfiles) , so it is my job to be knowledgable :D
>
> But, you have made some assumptions that I would like
> to correct ;)
>
> 1. There are no gaps. The indices are all updated
> behind the scenes. This was accomplished by using
> public inner static classes, Graph.Node, Graph.Edge.
That's ok in part, but this has absolutely nothing to do with inner classes, especially static inner classes.
> 2. Traversals won't be slow because there are no gaps
> in the arrays. I am a little surprised you said this
> (maybe you thought this because you thought deleting
> would leave gaps).
This is not true for directed graphs. All of your edges (incoming and outgoing) are stored in no particular order in a single array, so there *are* "gaps" during traversals of incoming respectively outgoing edges only.
You told me in an earlier post that indices stay the same, this can only be efficiently accomplished by keeping the arrays (thereby producing gaps in a dynamic scenario).
Compressing arrays is a workaround, which has an enourmous disadvantage:
-it takes quite a lot of time
-it modifies indices
-during compression you need to have an awful lot of memory (the new array and the old array will have to exist in parallel for a short period of time, this may actually double your memory consumptions!
> In an earlier post of mine, I
> stated the DFS and BFS times, which were equally fast
> as the other two graph libraries in this thread.
> Actually, they were a little faster (but maybe my
> computer is faster).
Your library is especially crafted to perform well with these sort of algorithms and static graph structures, this is true.
>
> 3. There is no wasted space. If half the edges are
> deleted, the API gives has the capability to trim the
> arrays. I can see if you thought there were gaps,
> this would not be possible.
>
>
> Very soon graphbuilder.com is going to be officially
> online, then you can see for yourself :-)
>
I am truly looking forward to that, thanks for your response!
Regards, Sebastian
>That's ok in part, but this has absolutely nothing to do with inner classes, especially static inner classes.
Here is the rough idea:
public class Graph {
public static class Node {
private int index = 0; // there is no mutator method
public int indexOf() { return index; }
}
public void deleteNode(Graph.Node n) {
// swap last into node[n.index];
node[n.index].index = n.index; // look here
}
}
In order to be able to [bold]reassign[/bold] the index variable, and keep it private, the class has to be static and inner.
>That's ok in part, but this has absolutely nothing to do with inner classes, especially static inner classes.
Here is the rough idea:
In order to be able to reassign the index variable, and keep it private, the class has to be static and inner.
public class Graph {
public static class Node {
private int index = 0; // there is no mutator method
public int indexOf() { return index; }
}
public void deleteNode(Graph.Node n) {
// swap last into node[n.index];
node[n.index].index = n.index; // look here
}
}
>
> In order to be able to reassign the index
> variable, and keep it private, the class has to be
> static and inner.
>
I should have said, in order to keep the index private, but be able to change it, the class has to be inner. In order to be able to access the Node class, it has to be public and static.
> Compressing arrays is a workaround, which has an enourmous disadvantage:
>-it takes quite a lot of time
>-it modifies indices
>-during compression you need to have an awful lot of memory (the new >array and the old array will have to exist in parallel for a short period of time, this may actually double your memory consumptions!
The role of the index is not to provide a unique identifier, but to provide quick reference to the location in the array so that a removal can be accomplished in O(1) time. This is required because an array based implementation is used.
You are correct that to trim the arrays, a new array must be created. A more important problem with using arrays is that increasing the array length, a new array is required. That is why the initial capacities of the graph can be specified.
However, when increasing the time is amortized, but you are correct that time is an issue when trimming (limitation of arrays).
> Compressing arrays is a workaround, which has an enourmous disadvantage:
Can you clarify this. Are you in favor of a linked list implementation ? In what sense is it a workaround? This is how arrays work in Java.
> I am truly looking forward to that, thanks for your response!Thanks for your repsonses too!
Hi again,
> > In order to be able to reassign the index
> > variable, and keep it private, the class has to be
> > static and inner.
> >
>
> I should have said, in order to keep the index private, but
> be able to
> change it, the class has to be inner. In order to be able to
> access the Node class, it has to be public and static.
You could have made it package private or introduce package private setters (in fact this is exactly what the compiler does for each private inner classes field) - so it is not a requirement to create an inner class. But the solution is nevertheless a good one, I wasn't trying to say the solution is bad, only it had nothing to do with running time or memory requirements.
> The role of the index is not to provide a unique identifier, but to
> provide quick reference to the location in the array so that a
> removal can be accomplished in O(1) time. This is required because an
> array based implementation is used.
Your API consists of a couple of methods that use the indices like identifiers. So they are used as identifiers - at least temporal ones.
> You are correct that to trim the arrays, a new array must be created.
> A more important problem with using arrays is that increasing the
> array length, a new array is required. That is why the initial
> capacities of the graph can be specified.
That's why I said, your implementation is good for static scenarios, but may need a lot more memory in dynamic scenarios.
> However, when increasing the time is amortized, but you are correct
> that time is an issue when trimming (limitation of arrays).
Even when decreasing time *can* be amortized, but temporal space requirements may be high (both during increasing and decreasing).
> > Compressing arrays is a workaround, which has an enourmous disadvantage:
> Can you clarify this. Are you in favor of a linked list
> implementation ?
I should have said "using arrays" has lots of disadvantages, and compression is a way to get rid of a couple of problems.
I absolutely do favor linked list implementations, as long as you are dealing with dynamic graph structures. The yFiles Graph structure implementation uses linked lists, which is a bit more complicated in implementation, but provides the best possible running-time complexities, while requiring only very little memory per entity.
Best of all, at no time there is wasted memory (garbage collection of large arrays).
yFiles' graph structure provides O(1) (non-amortized) operations where possible *and* best possible performance for iterations over
all nodes O(n), all edges O(e) , inedges O(indegree) outedges O(outdegree) and all edges of a node O(degree) at all times. memory requirements is O(n+e) *at any time*.
You may take a look at the (complete) API for details:
http://www.yworks.com/products/yfiles/doc/api-gif/y/base/Graph.html
Therefore:
"use linked list for dynamic graph structures"
"use arrays for static structures and simplicity *only*"
would be my advice.
Regards - Sebastian
Hi Sebastian,What tool do you use to create the lovely UML embedded in the javadoc?Thanks,Barak
Hi,
> What tool do you use to create the lovely UML embedded
> in the javadoc?
:-) This is our (yWorks') own tool "yDoc". yDoc is like a plugin for the jdk1.4.x generic javadoc tool. You may have a look at it, evaluate it and possibly purchase it :D for a small fee (it's shareware) at http://www.yworks.com/products/ydoc/
For an unbiased source :-) :
Sun also mentions it on
http://java.sun.com/j2se/javadoc/faq/
regards, Sebastian
PS: BTW we have also a very cool *free* java obfuscation tool called "yGuard" on our site - before someone asks how this lovely UML tool has been obfuscated so perfectly :D
hmm... any chance for a free community version?
>I should have said "using arrays" has lots of disadvantages
Linked list or array based implementations both carry the same functionality. So in terms of functionality, there are no disadvantages. In terms of memory, an array based implementation will have amortized equal performance to that of a linked list implementation.
An advantage of using an array based implementation is the ability to access the i'th node, edge or neighbor in constant time. Since each node and edge has an index value, this makes it easy to associate external data with each node or edge. As as example, see the DFS code I posted earlier. It is possible to accomplish this with a linked list implementation using a hash table (slightly less efficient).
In terms of bytes used per node, a linked list implementation is slightly better.
In terms of bytes used per edge, the linked list implementation and array based implementations are equal.
> memory requirements is O(n+e) *at any time*.
The same is true for an array based implementation. This would only not be true if a large number of nodes or edges were deleted.
>You may take a look at the (complete) API for details:
>http://www.yworks.com/products/yfiles/doc/api-gif/y/base/Graph.html
Yes, very nice UML diagrams! =)
The y.base.Graph allows edge reinsertions. What happens when a node is
removed, and one of the removed incident edges is reinserted?
Hi, once again!
> >I should have said "using arrays" has lots of
> disadvantages
>
> Linked list or array based implementations both carry
> the same functionality. So in terms of functionality,
> there are no disadvantages. In terms of memory, an
> array based implementation will have amortized equal
> performance to that of a linked list implementation.
This is all true. Only in practice it is far more important what the real amount of memory in use is. In practice people will give a **** if the memory is amortized the same when they receive an OutOfMemoryError ;-)
> An advantage of using an array based implementation is
> the ability to access the i'th node, edge or neighbor
> in constant time.
This is absolutely true, although I am not aware of any important algorithm that really *needs* this feature.
> Since each node and edge has an
> index value, this makes it easy to associate external
> data with each node or edge. As as example, see the
> DFS code I posted earlier. It is possible to
> accomplish this with a linked list implementation
> using a hash table (slightly less efficient).
This is true. Actually this is the reason, why yFiles' memory requirements for graph entities is a few bytes greater than the absolute minimum needed: we have a facility included that makes it possible to associate arbitrary data with those entities in an easy and efficient (perfect O(1) ) way:
NodeMap map = graph.createNodeMap();
map.set(node, myObject); // no hashing O(1) access, will stay consistent if graph structure is changed
Also, I would say we have the best of both worlds, since the yFiles library *allows* the use of something similiar to array indices. Especially for algorithms that work on static graph structures one can do the following:
Node node1 = graph.createNode();
int[] data = new int[graph.N()]; // best possible space allocation, just as you stated
data[node1.index()] = 5;
...
.index() will return the *current* position in the linked list, those will only be updated or calculated if the .index() methods are called. This will take O(n) time the first time the method is called, but amortized running time will be O(1) even in this case, if the algorithm calls the index() method for all or most of the entities.
> In terms of bytes used per node, a linked list
> implementation is slightly better.
No, actually your implementation can be slightly better :-(
> In terms of bytes used per edge, the linked list
> implementation and array based implementations are
> equal.
Again, in terms of used bytes, array based implementations *can* be slightly better (8 bytes or so)
> > memory requirements is O(n+e) *at any time*.
>
> The same is true for an array based implementation.
> This would only not be true if a large number of
> nodes or edges were deleted.
Ok, my fault, I should have said "memory requirements is exactly k*n + j*e *at any time* for certain optimal k an j, even *without* amortization, so you will never get an OutOfMemoryError unless there is absolutely no more room for a single edge or node.l
> >You may take a look at the (complete) API for
> details:
> >http://www.yworks.com/products/yfiles/doc/api-gif/y/ba
> e/Graph.html
>
> Yes, very nice UML diagrams! =)
Thank you - as a said: take a look at yDoc !BTW yDoc uses a linked list implementation :D
>
> The y.base.Graph allows edge reinsertions. What
> happens when a node is
> removed, and one of the removed incident edges is
> reinserted?
Since this operation requires the nodes to be in the graph as a postcondition, it will throw a RunTimeException, most likely an IllegalArgumentException or IllegalStateException, I don't no which exactly.
I could ask you the same question:
what happens if is say graph.createEdge(-1, Integer.MAX_VALUE); with *your* API. I would guess it either throws an IndexOutOfBoundsException (most likely ArrayIndexOutOfBoundsException :D ) or an IllegalArgumentException, or a subclassed version of one of these. Am I right?!
Greetings,
Sebastian
> > An advantage of using an array based implementation
> is
> > the ability to access the i'th node, edge or
> neighbor
> > in constant time.
>
> This is absolutely true, although I am not aware of
> any important algorithm that really *needs* this
> feature.
>
Having index locations makes it easy to create parallel
arrays, which makes it easy to separate the model and view.
Doing so means that the model and view are coupled using
an index location.
Ideally a coupling should be possible that:
1. does not make a subclass of Node dependent on the view.
For example, making a class called ShapeNode, that contains
a reference to a java.awt.Shape would not be desirable
because that node could only be used in a view that uses Java2D.
Instead, the view component should store that information.
2. The coupling does not depend on the graph implementation
used. Coupling the model and view using the index location
(although easy) is not desirable.
3. The model (the graph) should be able to be placed in any
view. (Should the model be able to exist in multiple views
at the same time?)
>
> NodeMap map = graph.createNodeMap();
> map.set(node, myObject); // no hashing O(1) access,
> will stay consistent if graph structure is changed
>
For a single NodeMap, how many objects be associated with a node?
Can multiple NodeMaps exist at the same time for the same graph?
If multiple NodeMaps are created, does this mean multiple objects can
be associated with a single node?
When a large number of nodes are created, what happens to the NodeMap in
terms of memory allocation?
>
> Node node1 = graph.createNode();
> int[] data = new int[graph.N()]; // best possible
> space allocation, just as you stated
> data[node1.index()] = 5;
> ...
It appears that the data array is not required, since each
node already stores the index information.
> (most likely ArrayIndexOutOfBoundsException :D )
Funny. And true.
Hi,
> Having index locations makes it easy to create
> parallel
> arrays, which makes it easy to separate the model and
> view.
> Doing so means that the model and view are coupled
> using
> an index location.
Don't you agree, that this sounds not very OO, but more like old c-style programming?! In fact, doing things this way requires you to do the array compression on each and every "synched" array, doesn't it?
>
> Ideally a coupling should be possible that:
> 1. does not make a subclass of Node dependent on the
> view.
I totally agree.
> For example, making a class called ShapeNode, that
> contains
> a reference to a java.awt.Shape would not be desirable
ACK
>
> because that node could only be used in a view that
> uses Java2D.
> Instead, the view component should store that
> information.
ACK. yFiles has the concept of "realizers". These are the visual attributes for nodes. This ressembles Swing's "Renderer" Design Pattern.
Each node can be associated (through a NodeMap for example) with a NodeRealizer, which depends on the type of the view. The view could use the NodeMap to get access to its own realizer and use the information to render the Node (although this is possible, we use a more tightly coupled (subclassing) and more optimized variant of this approach).
>
> 2. The coupling does not depend on the graph
> implementation
> used. Coupling the model and view using the index
> location
> (although easy) is not desirable.
totally agree.
>
> 3. The model (the graph) should be able to be placed
> in any
> view. (Should the model be able to exist in multiple
> views
> at the same time?)
Of course it should! That's the basic idea of the MVC design pattern!
>
> >
> > NodeMap map = graph.createNodeMap();
> > map.set(node, myObject); // no hashing O(1) access,
> > will stay consistent if graph structure is changed
> >
>
> For a single NodeMap, how many objects be associated
> with a node?
One, although you can associate arrays containing mutliple objects or helper classes ("structs").
>
> Can multiple NodeMaps exist at the same time for the
> same graph?
Any number.... - well a hard upper limit would be Integer.MAX_VALUE :D
>
> If multiple NodeMaps are created, does this mean
> multiple objects can
> be associated with a single node?
yes
>
> When a large number of nodes are created, what happens
> to the NodeMap in
> terms of memory allocation?
NodeMap is an interface in yFiles and you can have different implementations, each suitable for different requirements:
graph.createNodeMap();
will reserve memory (4 byte) for each and every node in the graph, regardless of whether actual data is associated with the node or not
Maps.createNodeMap(java.util.Map);
will take any map implementation, preferrably java.util.HashMap() and return a wrapping NodeMap implementation. In this case the memory requirement (and access time) is the same as for the map implementation, i.e. it doesn't matter how many nodes you have in the graph structure, all that matters is the data that is associated with the nodes.
Object[] data = new Object[graph.N()];
NodeMap map = Maps.createIndexedNodeMap(data);
will create a wrapping view on the array, this is perfect for static scenarios, since the indices stay the same, as I mentioned in a previous post.
The big advantage of having these different options of creating different instances of NodeMap is that one can exchange the implementation after the implementation of the algorithms so that an optimal space/time performance can be achieved.
>
> >
> > Node node1 = graph.createNode();
> > int[] data = new int[graph.N()]; // best possible
> > space allocation, just as you stated
> > data[node1.index()] = 5;
> > ...
>
> It appears that the data array is not required, since
> each
> node already stores the index information.
well, I should have written:
Node node1 = graph.createNode();
Object[] data = new Object[graph.N()]; // best possible
space allocation, just as you stated
data[node1.index()] = "hello";
data[node2.index()] = new FooObject();
it does not need to be a simple integer index....
maybe you would like to have a look at some demos (source code)
http://www.yworks.com/products/yfiles/doc/demo/index.html
The features I just tried to explain (and many many more) can be found there.
Also take a look at the complete API:
http://www.yworks.com/products/yfiles/doc/api-gif
or (svg version, you need a plugin: on Windows boxes normally having a recent version of Adobe Acrobat Reader installed suffices)
http://www.yworks.com/products/yfiles/doc/api-svg
Of course I encourage everyone to request a free evaluation version of yFiles on our site (email and company/institution required).
BTW quite a number of universities in the states and all around the world own a "Site License" of yFiles for academic purposes (very affordable). I am sure your university would agree to purchase such a license if you asked them to do so (and give reasons, of course).
Last but not least make sure you have checked out yEd which demonstrates many of the features of yFiles as I mentioned somewhere in a previous post:
http://www.yworks.com/products/yed/ - absolutely free and fully functional java graph editor application (webstartable and downloadable)
Have fun and 'hope to hear more from you ...
Sebastian
SebastianM,
Reading through these posts got me interested in yDoc. Yesterday, I downloaded the evaluation version and documented my classes.
I have a few questions:
1.) Where can I find documentation on what the shapes and lines mean? I can figure out that white arrow is equivalent to extends, but some of the other relationships aren't as straight forward to me.
2.) Why is it that the private member variables appear in the UML diagram? Are the diagrams exposing too much information about the implementation or is that part of UML?
(i.e. Why does class Cache appear in this example?)
http://www.bacman.net/doc/javadoc/net/bacman/thumbnailer/Thumbnailer.html
yDoc is very cool!
Thanks,
BacMan
Hi,
> SebastianM,
> Reading through these posts got me interested in yDoc.
> Yesterday, I downloaded the evaluation version and
> documented my classes.
>
> I have a few questions:
> 1.) Where can I find documentation on what the shapes
> and lines mean? I can figure out that white arrow is
> equivalent to extends, but some of the other
> relationships aren't as straight forward to me.
First I must say, that using this forum is not the best way to get these questions answered, please send your questions to ydoc "at" yworks.com (yes, I think you will get an response!). Secondly I am a developer of the yFiles library which yDoc uses but I haven't had very much to do with the development, design let alone implementation of yDoc. Therefore my answer might not be very accurate:
>
> 2.) Why is it that the private member variables
> appear in the UML diagram? Are the diagrams exposing
> too much information about the implementation or is
> that part of UML?
AFAIK you can configure yDoc what kind of relationships shall be displayed in the diagrams. The style you are using also displays compile time dependencies, which is not normally displayed in UML diagrams. Since there is a dependency to your "Cache" class, it is visible in the diagram.
There is an editor, which lets you easily modify the style of your diagrams (fonts, colors, sizes, shapes and *what* exactly is displayed)
The program is called StyleEd (style editor) it is part of the distribution - see the README files on how to execute it. I think the editor will make it clear which elements are displayed in your diagram (Is there really no description in the README files?!).
> yDoc is very cool!
>
> Thanks,
> BacMan
Thank YOU!
Regards, Sebastian
Sebastian, Barak,
I was hoping I could solicit your opinions on something since you both have experience implementing graph data structures.
What is your interpretation of a directed edge?
The (non-exhaustive) possibilities are:
public class DEdge0 extends Edge {
// this would override the isDirected method of Edge
public final boolean isDirected() {
return true;
}
}
public class DEdge1 implements DirectedEdge {
// the tag indicates that edge is directed
}
public class DEdge2 extends Edge implements Directable {
private boolean directed = false;
public void setDirected(boolean b) {
directed = b;
}
public boolean isDirected() {
return directed;
}
}
DEdge0 and DEdge1 are both always directed. Classes DEdge0 and DEdge2 would override the isDirected() method of Edge, but DEdge2 provides more flexibility by allowing this variable to be set. The default isDirected() method would return false.
There is also the opinion that there is no such thing as a directed edge, only a directed graph.
The reason for wanting to have an isDirected method is that some algorithms may want to make use of the directed status, but not change it.
Regards.
I will avoid the directedness of edges altogether - it caused problems and inconsistencies in JGraphT and is now (almost) completely removed.
The directedness is a property of the graph, not of the edge. Although it appears convenient to be able to ask edge.isDirected(), it's causing troubles. take for example a graph that is an undirected view based on a directed graph (e.g. http://cvs.sourceforge.net/viewcvs.py/jgrapht/src/org/_3pq/jgrapht/graph/AsUndirectedGraph.java). You end up with an undirected graph that has directed edges -- that ain't pretty.
In some other cases, one might end up with graph that has both, directed and undirected edges in the same graph - not my idea of fun.
bottom line of my suggestion: avoid directedness in edges altogether.
--
ps: such matters were already discussed and peer reviews in JGraphT. Why not just take JGraphT as a basis and extend it?!
Hi,
the yFiles graph library does not even have anything like undirected edges. When working with the graph's structure each edge has a source node and a target node, i.e. it is somehow directed (you must provide convenient accessor methods for both adjacent nodes at least, and during edge creation you will always have to give two nodes as an argument in order, so there will always be some kind of direction). Whether an edge is *treated* as a directed edge depends on the algorithm. Therefor one could say the graph has the property of being directed, although there is no such actual property in our implementation. As I said, it depends on the algorithm you are using. Some of them treat edges as directed (max-flow algorithms for example), some of them treat them as undirected (connectedness algorithms for example) and some of them can be configured to treat edges as either directed or undirected (bfs, dfs, cycledetection and many many more, see http://www.yworks.com/products/yfiles/doc/api-gif/y/algo/Paths.html for an example). In some very rare cases, people like to have "directed *and* undirected edges" in the same graph structure (certain custom reachability algorithms for example). In those cases we advise our users to use the directed modes for those algorithms and for each "undirected edge", we tell them to insert a "reverse edge" parallel to the former, so that the directed algorithm will be able to traverse and edge in both directions.
Therefor I would suggest not to have anything like "undirected edges".
Regards, Sebastian
> --
> ps: such matters were already discussed and peer
> reviews in JGraphT. Why not just take JGraphT as a
> basis and extend it?!
JGraphT is designed to be a general purpose graph library that can be tailored quite significantly, correct?
The goal of Graph Builder is to provide a specific graph implementation that is easy to learn, flexible and has good overall performance. Here, flexible means that the implementation could be used in a variety of applications, but it cannot be tailored.
So there are 2 reasons, the need for a specific implementation and a smaller learning curve.
> JGraphT is designed to be a general purpose graph
> library that can be tailored quite significantly,
> correct?
yes, and it can also be used as is. tailoring is optional.
> The goal of Graph Builder is to provide a specific
> graph implementation that is easy to learn, flexible
> and has good overall performance.
sounds like a subset of what JGraphT is trying to do :)
see http://jgrapht.sourceforge.net/
JGraphT has proved to be high performance and it managed to remain quite simple. If you think you can simplify it further, or improve its performance, you can do it -- its a free software...
however, if you WANT to develop your own package for, say, the sheer fun of it, that is something... completely different :)
> There is also the opinion that there is no such thing
> as a directed edge, only a directed graph.
Speaking from the point of view of a mathematician, I
would say that's correct. However, an undirected graph
is a special case of a directed graph in which "edges"
are pairs of edges going in opposite directions. In that
sense, in a directed graph there could be some edges
that are members of such pairs, and some that aren't.
There's no harm in calling a pair of edges of the
first kind an undirected edge, and the second kind a
directed edge.
This suggests implementing a graph of this mixed kind
as a directed graph.
Terry,As you may have noticed, this is exactly the way the graph structure is implemented in yFiles. Seems to me, that you have found better words to describe it accurately ;-)Regards, Sebastian
