I agree with your suggestion about adding a new type of data structure.
Graphs are topological, not cartesian, so I see this as fundamentally
different from the other types.
We should assume that the data structure needs to support very large
sparse graphs. But we should also build in the flexibility to provide
alternative implementations that adhere to the same api. For example, in
some dense cases an adjacency matrix is far more efficient because it can
indicate edges using bits in a 2d matrix of words instead of full
machine-sized words. Someone should probably review what the open-source
"Leda" graph system does to accomodate these differences.
-- Oscar
***The contents of this email message are confidential and proprietary***
On Thu, 24 Jan 2002, Steven Smith wrote:
>
>
>
> > Oscar,
> >
> > > Have you chosen a graph data structure yet? I assume you will use some
> > > kind of adjacency list representation to support sparse directed graphs,
> >
> > I am currently testing with hand-made *positional* data, and do not have an
> > underlying graph structure yet. I feel that the underlying structure in any
> > case will go thru a heavy adaption process to visad math and display types,
> > so this is not a problem.
> >
> > > but I am curious if you have chosen the data types for the node and edge
> > > labels,
> >
> > If you are talking about a visad MathType structure for them, no. I have
> > tried out two today, but both had problems. If you have suggestions, let me
> > know.
> >
> > > and if you will be using primitives or objects.
> >
> > What primitives and objects do you mean?
> >
> > Manuel
>
> Most of the graphs I work with are sparse enough to be most effeciently
> represented as time varying vertex/edge lists.... I have considered using
> irregular grids to represent these intrinsically to Visad. While ultimately I
> want to render nodes and edges, I also want to be able to take advantage of
> interpolation off the graph to define continuous fields, etc.
>
> Some of the graphs (especially if I take them over time) are dense enough to
> suggest connectivity matrix representations and especially if I use a "sparse
> matrix" package. Does anyone here have anything to suggest in that realm?
>
> I'll try to remember to report when I find good graph layout algorithms
> implemented in Java that might be a good addition or complement to Visad.
>
> I'm looking at openmap (www.openmap.org) for the geospatially referenced
> aspect
> of my problem but haven't had much time yet. My current work is taking a
> twist
> toward focusing on internet infrastructure more than transportation and energy
> distribution networks so the cybergeography folke (www.cybergeography.org) are
> most interesting at the moment.
>
> CAIDA (www.caida.org) has built an interesting layout/manipulation tool known
> as Walrus (www.caida.org/tools/visualization/walrus) which implements a 3D
> hyperbolic metric for layout and investigation which maintains excellent
> scaling properties. The early work was by Tamara Munzner but this is the best
> example to date, that I know of for handling the "detail in context" problem
> around graphs.
>
> It is also a Java App and I imagine they are likely to be cooperative if
> someone wanted to "marry" this capability with Visad in an interesting way.
>
> If all goes well, I may have the suite of INCCA graph analysis algorithms to
> make available to this community but first I need to understand how best to
> relate them to the Visad data structures.
>
> It seems possible that we need a whole new base data structure that is
> parallel
> to the ones already in Visad along with some conversion methods... it might
> be too wishful thinking to imagine that what are essentially point sets or
> continuous fields in visad are close enough to graphs to be appropriate for
> the
> kinds of manipulations done by graph theoretic algorithms.
>
> - Steve
>
>
