Re: [Caml-list] Initial port of ocaml for mingw (long)

Re: [Caml-list] Initial port of ocaml for mingw (long)

[CaptnJamesKirk]

In a message dated 9/25/2001 3:29:34 PM Central Daylight Time, 
ayerkes@gmvnetwork.com writes:

> Actually, my thought was to build with cygwin itself at least in the
>  short term.  The important thing (to me) is the ability to write nice
>  software and distribute it without the cygwin dll.  It's a bonus too
>  that ocaml.exe works properly without it too, but the main thing was
>  the ability to run ocamlopt and get an exe out that you can pass
>  around easily.  I built with cygwin's gcc (-mno-cygwin), tho.  I think
>  that it may not be realistic to build ocaml otherwise given that it
>  uses unix tools to create the prims list, however it can easily be
>  used without cygwin.
>  
>  I should've made it more clear that you need cygwin gcc as yet to build.
>  The important point was that it's possible to get it away from
>  dependence on cygwin1.dll...  

After I fired off my last message, I started to wonder if that's what you 
did, so I tried it myself under cygwin. Copying libncurses.a to libpdcurses.a 
still works (though this may need to be changed to use the regular ncurses 
which is part of the standard cygwin distro). I ran into some other problems, 
and here's what happened.

(first untarring the ocaml source, then patching, then untarring the boot 
stuff...)

1) make
First break is at utils/misc.mli, where it says cannot open pervasives.cmi. 
The only thing that worked for me here was to...
2) make world
which exits shortly with a cryptic (at least for me) error at [coldstart], 
but then
3) make
seems to be happy until it gets to bigarray. It needs bigarray.cmi but 
doesn't have it since it doesn't have big_int.cmi.  Making the 3 cmis you 
mention in otherlibs/num (int_misc.cmi, string_misc.cmi, and arith_flags.cmi) 
may be the first step, but it doesn't fix it. The only way I could build 
big_int.cmi was to cd to "otherlibs/num" and type "make big_int.cmi" there, 
after building nat.cmi as well.  Two more tries indicated that "ratio.cmi" 
and "num.cmi" also have to be built in the "otherlibs/num" directory. THEN, 
we have to cd to "otherlibs/bigarray" and do "make bigarray.cmi" there. Then,
4) make
goes all the way to ocamldebugger where it exits with "Uncaught exception: 
Not_found." I can't figure out how to fix it, so I do your next steps of "rm 
byterun/io.h", "make -C asmrun depend", and "make -C byterun depend". These 
last two have many warnings, most of which seem tied to redefinitions in 
fail.h.
5) make opt
then says I need arith_status.cmi in otherlibs/num, but once that's built it 
finishes without further error.

However, after doing "make install" and "make installopt" and trying to run 
ocaml.exe, I get "Cannot exec /usr/local/ocamlrun". In fact, all of the 
executables return that error.

And now I don't know how to fix that...

Oh, and as long as we're working on it, it would be VERY nice if we could get 
labltk to build as well.

/John



  
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Looking for Graph Operations-library

[Mattias Waldau]

I am converting some code from SICStus Prolog, and need a directed graph
library for Ocaml. Any pointers?

I found Markus Mottl's POMAP, and I can probably redesign in order to use
that instead.

/mattias



>From the SICStus manual:

Unweighted Graph Operations

Directed and undirected graphs are fundamental data structures representing
arbitrary relationships between data objects. This package provides a Prolog
implementation of directed graphs, undirected graphs being a special case of
directed graphs.

An unweighted directed graph (ugraph) is represented as a list of
(vertex-neighbors) pairs, where the pairs are in standard order (as produced
by keysort with unique keys) and the neighbors of each vertex are also in
standard order (as produced by sort), every neighbor appears as a vertex
even if it has no neighbors itself, and no vertex is a neighbor to itself.

An undirected graph is represented as a directed graph where for each edge
(U,V) there is a symmetric edge (V,U).


Some operations:
================

transitive_closure(+Graph, -Closure)
Computes Closure as the transitive closure of Graph in O(N^3) time.

symmetric_closure(+Graph, -Closure)
Computes Closure as the symmetric closure of Graph, i.e. for each edge (u,v)
in Graph, add its symmetric edge (v,u). Takes O(N^2) time. This is useful
for making a directed graph undirected.

top_sort(+Graph, -Sorted)
Finds a topological ordering of a Graph and returns the ordering as a list
of Sorted vertices. Fails iff no ordering exists, i.e. iff the graph
contains cycles. Takes O(N^2) time.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Looking for Graph Operations-library

[Mattias Waldau]

I am converting some code from SICStus Prolog, and need a directed graph
library for Ocaml. Any pointers?

I found Markus Mottl's POMAP, and I can probably redesign in order to use
that instead.

/mattias



>From the SICStus manual:

Unweighted Graph Operations

Directed and undirected graphs are fundamental data structures representing
arbitrary relationships between data objects. This package provides a Prolog
implementation of directed graphs, undirected graphs being a special case of
directed graphs.

An unweighted directed graph (ugraph) is represented as a list of
(vertex-neighbors) pairs, where the pairs are in standard order (as produced
by keysort with unique keys) and the neighbors of each vertex are also in
standard order (as produced by sort), every neighbor appears as a vertex
even if it has no neighbors itself, and no vertex is a neighbor to itself.

An undirected graph is represented as a directed graph where for each edge
(U,V) there is a symmetric edge (V,U).


Some operations:
================

transitive_closure(+Graph, -Closure)
Computes Closure as the transitive closure of Graph in O(N^3) time.

symmetric_closure(+Graph, -Closure)
Computes Closure as the symmetric closure of Graph, i.e. for each edge (u,v)
in Graph, add its symmetric edge (v,u). Takes O(N^2) time. This is useful
for making a directed graph undirected.

top_sort(+Graph, -Sorted)
Finds a topological ordering of a Graph and returns the ordering as a list
of Sorted vertices. Fails iff no ordering exists, i.e. iff the graph
contains cycles. Takes O(N^2) time.

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Looking for Graph Operations-library

[Markus Mottl]

On Wed, 26 Sep 2001, Mattias Waldau wrote:
> I am converting some code from SICStus Prolog, and need a directed graph
> library for Ocaml. Any pointers?
> 
> I found Markus Mottl's POMAP, and I can probably redesign in order to use
> that instead.

Yes, this should be possible. The internal datastructure used to
represent partially ordered maps is actually a (purely functional)
directed graph. Maybe not optimal for all purposes, but fast enough
for many and additionally allows persistent sharing of datastructures,
which is also a nice feature.

> transitive_closure(+Graph, -Closure)
> Computes Closure as the transitive closure of Graph in O(N^3) time.
>
> symmetric_closure(+Graph, -Closure)
> Computes Closure as the symmetric closure of Graph, i.e. for each edge (u,v)
> in Graph, add its symmetric edge (v,u). Takes O(N^2) time. This is useful
> for making a directed graph undirected.

Should be straightforward.

> top_sort(+Graph, -Sorted)
> Finds a topological ordering of a Graph and returns the ordering as a list
> of Sorted vertices. Fails iff no ordering exists, i.e. iff the graph
> contains cycles. Takes O(N^2) time.

A similar function is already implemented (topo_fold). Because the
partially ordered map represents a Hasse-diagram, this function is
really fast. Of course, you are likely to spend the O(N^2) computation
time elsewhere, namely during the creation of the Hasse-diagram.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Looking for Graph Operations-library

[Brian Rogoff]

On Wed, 26 Sep 2001, Mattias Waldau wrote:
> I am converting some code from SICStus Prolog, and need a directed graph
> library for Ocaml. Any pointers?

I ported part of Martin Erwig's Functional Graph Library to OCaml, the
part that uses functional maps as arrays. I used a hacked version of
Jean-Christophe Filliatre's Patricia tree implementation for that. I
haven't yet written the version tree code. If you don't mind its
incomplete state and would like to help complete the port I can wrap it
up and e-mail it to you.

See http://www.cs.orst.edu/~erwig/fgl/ for the original.

You might also consider porting a more imperative library, like the one in
SML for MLRISC, if you are comfortable with SML too. FGL is cool but I'm
not confident that the performance will match a tuned imperative
implementation :-).

-- Brian

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] Looking for Graph Operations-library

[Mattias Waldau]

I looked thru the documentation, but FGL doesn't seem to be any operations
like closures and topological sorting in fgl, it mostly seems to be about
traversing the structure. Have I missed something?

When I look at one of the papers, you get the impression that an imperative
implementation is one to two magnitudes faster, is that right?
(Speed is irrelevant right now for me.)

/mattias


-----Original Message-----
From: owner-caml-list@pauillac.inria.fr
[mailto:owner-caml-list@pauillac.inria.fr]On Behalf Of Brian Rogoff
Sent: Wednesday, September 26, 2001 7:14 PM
To: Mattias Waldau
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Looking for Graph Operations-library


On Wed, 26 Sep 2001, Mattias Waldau wrote:
> I am converting some code from SICStus Prolog, and need a directed graph
> library for Ocaml. Any pointers?

I ported part of Martin Erwig's Functional Graph Library to OCaml, the
part that uses functional maps as arrays. I used a hacked version of
Jean-Christophe Filliatre's Patricia tree implementation for that. I
haven't yet written the version tree code. If you don't mind its
incomplete state and would like to help complete the port I can wrap it
up and e-mail it to you.

See http://www.cs.orst.edu/~erwig/fgl/ for the original.

You might also consider porting a more imperative library, like the one in
SML for MLRISC, if you are comfortable with SML too. FGL is cool but I'm
not confident that the performance will match a tuned imperative
implementation :-).

-- Brian

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] Looking for Graph Operations-library

[Brian Rogoff]

On Wed, 26 Sep 2001, Mattias Waldau wrote:
> I looked thru the documentation, but FGL doesn't seem to be any operations
> like closures and topological sorting in fgl, it mostly seems to be about
> traversing the structure. Have I missed something?

The interfaces don't have, say, topsort as a builtin function, but the
papers describe how to implement it using the provided functions.

> When I look at one of the papers, you get the impression that an imperative
> implementation is one to two magnitudes faster, is that right?
> (Speed is irrelevant right now for me.)

I don't think the papers measured against an imperative implementation,
but rather a functional array based on binary trees versus a functional
array based on version arrays. But I could be wrong and I don't have them
handy at the moment. Anyways, I'd like to do a version array version :-)
too in the future. It would be nice if there was a version array library
around; I've written some quick ones but I don't know how they compare
against some of the better ones. Lots of SML implementations around.

Beware of surmising too much based on some quick benchmarks.

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Looking for Graph Operations-library

[Markus Mottl]

On Wed, 26 Sep 2001, Mattias Waldau wrote:
> When I look at one of the papers, you get the impression that an
> imperative implementation is one to two magnitudes faster, is that
> right?  (Speed is irrelevant right now for me.)

This depends on the operation and the size of your graph. Some operations
should be nearly as fast (e.g. in the POMAP-case, insertion of elements),
others might run slower by this considerable amount (e.g. traversing
nodes - requires traversal and lookups in both edge sets and the node
set). I don't have any direct comparison to an imperative version so
this is just an estimate. It would be really interesting to have an
efficient imperative graph library in OCaml, too.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Looking for Graph Operations-library

[Jean-Christophe Filliatre]

Mattias Waldau writes:
 > I am converting some code from SICStus Prolog, and need a directed graph
 > library for Ocaml. Any pointers?

If you  ever consider  writing such a  library from scratch,  there at
least two  books describing graphs  data structures and  algorithms in
very details:

The Stanford GraphBase
    http://www-cs-staff.Stanford.EDU/~knuth/sgb.html

The LEDA Platform
    http://www.mpi-sb.mpg.de/~mehlhorn/LEDAbook.html

Hope this helps,
-- 
Jean-Christophe Filliatre (http://www.lri.fr/~filliatr)

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Looking for Graph Operations-library

[Francois Pottier]

[-- Attachment #1: Type: text/plain, Size: 1286 bytes --]


> I am converting some code from SICStus Prolog, and need a directed graph
> library for Ocaml. Any pointers?

It is difficult to design a `universal' graph library, i.e. one that will suit
most users' needs, because different applications often require different
concrete representations of graphs.

Perhaps (as suggested by Chris Tilt in an earlier message) the best route is
to write a functorized library of graph algorithms, where each algorithm is
written independently of the actual data structure used to represent the
graph.

Yet, even then, it is not easy to determine which set of basic operations
should be supported by the structure. For instance, some algorithms are easily
expressed if graph nodes are numbered sequentially, but this is a rather
undesirable requirement if nodes are to be dynamically added and deleted.  As
another example, some algorithms can be written more efficiently if they are
allowed to store data directly within every graph node, but this causes them
to be non-reentrant and can also be a problem in some applications.

As an example of this functorized style of programming, attached is an
abstract implementation of a topological-order iterator for graphs.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/

[-- Attachment #2: topological.mli --]
[-- Type: text/plain, Size: 1017 bytes --]

(* $Header: /home/pauillac/formel1/fpottier/cvs/typo/topological.mli,v 1.1 2001/08/17 17:04:35 fpottier Exp $ *)

module type Graph = sig

  type node

  (* The client must allow associating an integer degree with every graph node. *)

  val get: node -> int
  val set: int -> node -> unit

  (* The client must allow enumerating all nodes. *)

  val iter: (node -> unit) -> unit

  (* The client must allow enumerating all successors of a given node. *)

  val successors: (node -> unit) -> node -> unit

end

(* Given an acyclic graph $G$, this functor provides functions which allow iterating over the graph in topological
   order. Each graph traversal has complexity $O(V+E)$, where $V$ is the number of vertices in the graph, and $E$ is
   the number of its edges. The graph must be acyclic; otherwise, [Cycle] will be raised at some point during every
   traversal. *)

module Sort (G : Graph) : sig

  exception Cycle
  
  val iter: (G.node -> unit) -> unit
  val fold: (G.node -> 'a -> 'a) -> 'a -> 'a

end


[-- Attachment #3: topological.ml --]
[-- Type: text/plain, Size: 1958 bytes --]

(* $Header: /home/pauillac/formel1/fpottier/cvs/typo/topological.ml,v 1.1 2001/08/17 17:04:35 fpottier Exp $ *)

module type Graph = sig

  type node

  (* The client must allow associating an integer degree with every graph node. *)

  val get: node -> int
  val set: int -> node -> unit

  (* The client must allow enumerating all nodes. *)

  val iter: (node -> unit) -> unit

  (* The client must allow enumerating all successors of a given node. *)

  val successors: (node -> unit) -> node -> unit

end

(* Given an acyclic graph $G$, this functor provides functions which allow iterating over the graph in topological
   order. Each graph traversal has complexity $O(V+E)$, where $V$ is the number of vertices in the graph, and $E$ is
   the number of its edges. The graph must be acyclic; otherwise, [Cycle] will be raised at some point during every
   traversal. *)

module Sort (G : Graph) = struct

  (* Auxiliary function. *)

  let increment node =
    G.set (G.get node + 1) node

  (* The main iterator. *)

  exception Cycle

  let fold action accu =

    (* Compute each node's in degree. *)

    G.iter (G.set 0);
    G.iter (G.successors increment);

    (* Create a queue and fill it with all nodes of in-degree 0. At the same time, count all nodes in the graph. *)

    let count = ref 0 in
    let queue = Queue.create() in
    G.iter (fun node ->
      incr count;
      if G.get node = 0 then
	Queue.add node queue
    );

    (* Walk the graph, in topological order. *)

    let rec walk accu =
      if Queue.length queue = 0 then
	if !count > 0 then
	  raise Cycle
	else
	  accu
      else
	let node = Queue.take queue in
	let accu = action node accu in
	decr count;
	G.successors (fun successor ->
	  let degree = G.get successor - 1 in
	  G.set degree successor;
	  if degree = 0 then
	    Queue.add successor queue
        ) node;
	walk accu in

    walk accu

  let iter action =
    fold (fun node () -> action node) ()

end

RE: [Caml-list] Looking for Graph Operations-library

[Chris Tilt]

Although I am not an accomplished functional programmer,
I would be happy to share a parameterized (functor-based)
graph module that provides basic directed graph data
structures and itterators. It allows arbitrary vertex
and edge types with the use of a functor interface. There
is also an accompanying algorithm module that currently
only implements shortest path and a skeleton function.
Let me know it sounds useful. I included the signature
below (sorry for the extra length). Performance is good
even though the vertex and edge maps are purely functional.
A pretty printer uses the graphviz "dot" format. Sorry
there is no parser :-(

Cheers, Chris
mailto:cet@webcriteria.com

(* Module [Pgraph]: graphs over ordered vertex identifiers with
   parameterized vertex, and edge types *)

module type ParameterizedGraphType =
  sig
    type t
      (* type of the vertex identifier *)
    type edge
      (* edge attributes *)
    type vertex
      (* vertex attributes *)
    val compare: t -> t -> int
	(* compare is used to order vid *)
    val formatEdge: t -> t -> edge -> string
    val formatVertex: t -> vertex -> string
  end


module type S =
  sig
    type vid
    type pVertex
    type pEdge
    type vertex = Vertex of vid * pVertex
    type edge = Edge of vid * vid * pEdge
    type t
    type graph = t

    module GraphAttributes : ParameterizedGraphType
    module VertexMap : Map.S with type key = vid

    val empty: t
    val isEmpty: t -> bool
    val numVertices: t -> int
    val numEdges: t -> int
    val vidOf: vertex -> vid
	(* find a vertex by name, throws Not_found if vid not in graph *)
    val vertexOf: vid -> t -> vertex
    val numEdgeDuplicates: vid -> vid -> t -> int
    val firstChildOf: vid -> t -> vid
    val vertexAttributeOf: vid -> t -> pVertex
    val hasVertex: vid -> t -> bool
    val removeAllEdges: t -> t
    val hasEdge: vid -> vid -> t -> bool
    val addVertex: vertex -> t -> t
    val addEdge: edge -> t -> t
	(* addEdgeAccumulate adds/updates an edge where the edge value
	   is the result of applying the supplied accumulator function
	   to the old edge value and supplied edge value *)
    val addEdgeAccumulate: edge -> (edge -> edge -> edge) -> t -> t
    val edges: t -> edge list
    val vertices: t -> vertex list
    val edgesFrom: vid -> t -> edge list
    val edgesTo: vid -> t -> edge list
    val mapVertices: (vertex -> vertex) -> t -> t
	(* applies a mapping function to all vertices in the graph,
	   replacing each vertex in the graph with the result of the
	   function application. Careful if you change the vid *)
    val iterVertices: (vertex -> unit) -> t -> unit
    val iterEdges: (edge -> unit) -> t -> unit
    val formatEdge: edge -> string
    val formatVertex: vertex -> string
    val printDotGraph: string -> out_channel -> t -> unit

  end
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr