Re: library(graph_algorithms)

From: Andrew Eremin <a.eremin_at_icparc.ic.ac.uk>
Date: Tue 11 Nov 2003 11:39:50 AM GMT
Message-ID: <3FB0CA86.DB2BA8FA@icparc.ic.ac.uk>
Andrew John Sadler wrote:
> 
> If you only want to add/remove edges you can try these predicates.
> They're reasonably efficient, though in no way supported by the
> ECLiPSe team, nor are they guaranteed to work in any future (or past)
> versions of ECLiPSe.
> 
> Also note, that some operations may take longer once a graph has been
> modified (get_incoming_edges/3).  Also note that tools like the
> Visualisation Client will NOT be notified of such changes to the graph
> structure.
> 
> % add an edge
> graph_add_edge(G, Edge):-
>         Edge=e(S,_T,_Info),
>         arg(2,G,Adj),
>         SEdgesOld is Adj[S],
>         SEdgesNew = [Edge|SEdgesOld],
>         setarg(S,Adj,SEdgesNew),
>         setarg(3,G,_),   % remove the optional incoming edges array
>         true.
> 
> % remove an edge
> graph_remove_edge(G, Edge):-
>         Edge=e(S,_T,_Info),
>         arg(2,G,Adj),
>         SEdgesOld is Adj[S],
>         once(delete(Edge, SEdgesOld, SEdgesNew)),
>         setarg(S,Adj,SEdgesNew),
>         setarg(3,G,_),   % remove the optional incoming edges array
>         true.
> 
> PS. It is probably not a good idea to modify the graph in this way
> whilst any resatisfiable predicates are running on the graph.
> 
> Andrew Sadler

Is there a good reason for deleting the incoming edges array in these
operations, rather than doing say:

% add an edge
graph_add_edge(G, Edge):-
        Edge=e(S,_T,_Info),
        arg(2,G,Adj),
        SEdgesOld is Adj[S],
        SEdgesNew = [Edge|SEdgesOld],
        setarg(S,Adj,SEdgesNew),
        arg(3,G,In),
	( nonvar(In) ->
	    TEdgesOld is In[T],
	    TEdgesNew = [Edge|TEdgesOld],
	    setarg(T,In,TEdgesNew)
	;
	    true
	).

% remove an edge
graph_remove_edge(G, Edge):-
        Edge=e(S,_T,_Info),
        arg(2,G,Adj),
        SEdgesOld is Adj[S],
        once(delete(Edge, SEdgesOld, SEdgesNew)),
        setarg(S,Adj,SEdgesNew),
	arg(3,G,In),
	( nonvar(In) ->
	    TEdgesOld is In[T],
	    once(delete(Edge, TEdgesOld, TEdgesNew)),
	    setarg(T,In,TEdgesNew)
	;
	    true
	).

-- 
Andrew Eremin
Research Assistant                   Tel: +44 (0)20 7594 8299
IC-Parc, Imperial College London     Fax: +44 (0)20 7594 8432
London SW7 2AZ                       Email: a.eremin@icparc.ic.ac.uk
Received on Tue Nov 11 11:41:19 2003

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:26 PM GMT GMT