Re: graphs

• To: steve smith <sas@xxxxxxxx>
• Subject: Re: graphs
• From: Oscar Stiffelman <oscar@xxxxxxxxxxxx>
• Date: Mon, 28 Jan 2002 09:44:26 -0800 (PST)

A great article on a related approach is:

Proceedings of the Working Conference on Advanced Visual Interfaces
2000 , Palermo, Italy
A fast multi-scale method for drawing large graphs
Authors
  David Harel
  Yehuda Koren


Publisher
 ACM Press   New York, NY, USA






***The contents of this email message are confidential and proprietary***


On Mon, 28 Jan 2002, steve smith wrote:

> I agree with Oscar's assessment here with one caveat.  The graphs I deal
> with are so large that it is often a serious issue to maintain duplicate
> data structures.  Hundreds of thousands each of nodes and edges are not
> uncommon, often saturating the physical memory of a 512M or even 1G
> machine.
>
>  I am seeking ways to mitigate this in Java by doing "memory mapping" on
> the original structure since most of the algorithms I am considering
> depend on multiple passes through the data where the first pass is/can
> be linear.  By recognizing various "intermediate" forms that might be
> useful, I can hopefully push them into data structures which are also
> "memory mapped".   I have not determined if the mechanisms Bill
> mentioned within VISAD are the ones I want to use or if I have to wait
> for Java proper to provide them.
>
> I am also looking at "level of detail" graph decompositions which
> promise to reduce the "view" of the graph to a fraction of the whole
> graph.  One of the techniques I am considering would involve deriving a
> continuous field from a registered (layed out in some metric space)
> graph and either displaying the field using conventional methods or
> using the value of the field at different locations to determine how or
> if I draw the graph elements themselves (for example, deriving a "node
> density" field and drawing only a single "aggregate node" where many
> nodes are too close to eachother to distinguish at a given magnification).
>
> I think there is precedent in Visad for maintaining complex data
> structures which are not neccesarily ever rendered directly and the
> Graph Structures are a likely candidate for extension once more work has
> been done to make sense of/with them.
>
> - Steve
>
> >I am not a visad expert, but I recommend not coupling the graph (adjacency
> >matrix or adjacency list) data structure to the existing VisAD data
> >structures, until it comes time for the embedding in R^2 or R^3 (which is
> >the function performed by the layout algorithm).  It will be easier for
> >people to import graph data into whatever you design if you keep the
> >topology encoding and the cartesian embedding conceptually orthogonal to
> >each other.  It is also a natural interface boundary to make it easier to
> >plug in layout algorithms that can work with arbitrary underlying topology
> >encodings.
> >
> >I am curious if the rest of the visad community (especially those more
> >familiar with the visad themes and design) agrees with this assessment.
> >I am also curious if this is the sort of datatype that the main visad team
> >feels is appropriate to integrate into the overall framework.
> >
> >-- Oscar Stiffelman
> >
>
>
>
>
>