Hi all,
i currently try to develop an interface to the graphviz toolset
(http://www.research.att.com/sw/tools/graphviz). For that i need a good
idea how to represent graphs in lisp. There is no concrete application
behind that. It's just to have a handy lisp interface to graphviz so i
can't rely on a given structure.
My first idea was to use
(a b c) for a->b->c but on the other side it would better to use
it for a->b, a->c.
CMU's psgraph use a total other interface by using functions that
returns
the childs of a given parent.
What do you thing is the best solution for that problem ?
Best regards
AHz
Andy <···@smi.de> writes:
> Hi all,
> i currently try to develop an interface to the graphviz toolset
> (http://www.research.att.com/sw/tools/graphviz). For that i need a good
> idea how to represent graphs in lisp. There is no concrete application
> behind that. It's just to have a handy lisp interface to graphviz so i
> can't rely on a given structure.
>
> My first idea was to use
>
> (a b c) for a->b->c but on the other side it would better to use
> it for a->b, a->c.
>
> CMU's psgraph use a total other interface by using functions that
> returns
> the childs of a given parent.
>
> What do you thing is the best solution for that problem ?
If you are doing a general interface to a graph layout engine, then
following psgraph's example is IMHO the way to go: The user of your
interface (even if it is you) will already have their own
representation of their graphs, so having to cons up a mirror image
just to pass it to the interface is suboptimal.
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
On Tue, 21 May 2002 16:17:22 -0300, Andy wrote:
> Hi all,
> i currently try to develop an interface to the graphviz toolset
> (http://www.research.att.com/sw/tools/graphviz). For that i need a good
> idea how to represent graphs in lisp. There is no concrete application
> behind that. It's just to have a handy lisp interface to graphviz so i
> can't rely on a given structure.
>
> My first idea was to use
>
> (a b c) for a->b->c but on the other side it would better to use it for
> a->b, a->c.
>
> CMU's psgraph use a total other interface by using functions that
> returns
> the childs of a given parent.
>
> What do you thing is the best solution for that problem ?
>
> Best regards
> AHz
This is just and idea: write a parser for GraphML (Graph Mark-up
Language).
<http://graphdrawing.org/graphml/index.html>
Easier said than done, I know!
(But if you *do*, then *post here*)
Cheers
Henry
_________________________________________________________________
Micro$oft-Free Human 100% Debian GNU/Linux
KMFMS "Bring the genome to the people!
···········@debian-rs.org
www.debian.org - www.debian-br.cipsga.org.br - www.debian-rs.org
Andy <···@smi.de> wrote in message news:<·················@smi.de>...
> i currently try to develop an interface to the graphviz toolset
> (http://www.research.att.com/sw/tools/graphviz). For that i need a good
> idea how to represent graphs in lisp. There is no concrete application
> behind that. It's just to have a handy lisp interface to graphviz so i
> can't rely on a given structure.
Before you can get a good answer, you have to ask the right question,
which requires you state what kinds of information you wish to represent
and what kinds of operations you want to be efficient.
If you just want a set of featureless vertices, each with a different name,
and a set of featureles links between pairs of them, with no names at all
associated with any particular link (except for the names of the vertices
within each), and you don't care about anything being efficient,
so you want just the simplest thing possible, just make a list of dotted
pairs of strings, for example (("a" . "b") ("b" . "c")). Why strings
instead of identifiers (symbols)? Because a symbol implies the efficiency
of the hash table plus a value and/or a function definition and/or
some other properties associated with that symbol and also a package
associated with each symbol (presumably all your nodes would be in the
same package but that's not necessarily true, maybe each different graph
in a different package if you want to go to the other extreme). By comparison
with strings you just have the raw names with no extra overhead setting
up things to be efficient and no overkill. If you want the strings to
be EQ whenever the same name, register them in a hash table and keep
the first such entry whenever you read in a new copy.
But if pairs of strings don't give you all the functionality you need,
then you have to say what functionality you need before deciding what
alternate representation to use. Do you need onscreen or mathematical
locations in Euclidean space associated with each vertex? Do you need
labels on the links? Do you need other properties such as color on
the vertices and/or links? Do you need to distinguish between directed
and undirected edges? Do you need multiple links between the same pair
of vertices? Do you need a link to take other than a straight-line path
from first vertex to second? Do you need search and/or update operations
to be efficient?
Robert Maas wrote:
>
> Before you can get a good answer, you have to ask the right question,
> which requires you state what kinds of information you wish to represent
> and what kinds of operations you want to be efficient.
>
GraphViz itself can represent directed and undirected graphs. Nodes and
edges
can have attributes like color, font and labels. The graphs my be
cyclic. There
can be more than one graph in a diagram.
Nodes can also be records (structs) and referencing a field in a record
as
source or sink is possible.
Output is generated for a lot of formats including PS & EPS.
All that should be covered by the interface.
Since all what the interface does is transfer the lisp representation to
the dot representation of graphviz it will have only a small amount of
the
total calculation time. So performance is only a nice-to-have.
The current responses to my mail (from Piere and Tim) prefer to have a
function
interface like psgraph. I think about how to build this but keep the
various
features of graphviz handy. My current idea is to use the property lists
of
the symbols to store the information (since the features are typically
0-5/node).
Your notes about the hashing was very interesting for me. But i fear
that i have
to store the symbols if i can't find an other way to represent the
features of
the nodes/edges.
Best regards
AHz