Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!munnari.oz.au!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: Representing graphs? Message-ID: <6505@goanna.cs.rmit.oz.au> Date: 25 Jun 91 11:48:49 GMT References: Distribution: comp Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 25 In article , Ari.Huttunen@hut.fi (Ari Juhani Huttunen) writes: > I would like to know if this is a good way to represent graphs > or an ugly hack. The idea is to have fast access to the current > location in the graph and its near neighbours. > graph(X) :- > X = vertice(x,[A,B,C]), > A = vertice(a,[D,X]), .... It's an ugly hack. It is going to get you into big trouble is some Prologs. The file GRAPHS.PL in the DEC-10 Prolog library provides several representations for graphs, including list of edges -- sorted! list of node-(list of neighbours) -- sorted! These representations appear to be adequate for a great many tasks, allowing the graph algorithms I was interested in to be coded in Prolog with the same asymptotic cost as in Pascal or C (admittedly with higher constant factors). Another representation would be the adjacency matrix, represented as a quad-tree, which works rather nicely. I would be interested to know which graph algorithms you are implementing. By the way, it's "vertEX", not "vertICE". -- I agree with Jim Giles about many of the deficiencies of present UNIX.