CODEWITHSUNDEEP
functional-programmingocaml
mf87
mf87

Reputation: 75

Represent a "graph" like a list of successor

I have a list that represent the connection between nodes (edges) in a ipotetically graph; the list is structured like that:

val def_graph : ((int * int) * (int * int)) list =
[((0, 0), (2, 1)); ((0, 0), (1, 2)); ((0, 1), (2, 0)); ((0, 1), (2, 2));
((0, 1), (1, 3)); ((0, 2), (2, 1)); ((0, 2), (2, 3)); ((0, 2), (1, 0));
((0, 2), (1, 4)); ((0, 3), (2, 2)); ((0, 3), (2, 4)); ((0, 3), (1, 1));
((0, 3), (1, 5)); ((0, 4), (2, 3)); ((0, 4), (2, 5)); ((0, 4), (1, 2));
((0, 4), (1, 6)); ((0, 5), (2, 4)); ((0, 5), (2, 6)); ((0, 5), (1, 3));
((0, 5), (1, 7)); ((0, 6), (2, 5)); ((0, 6), (2, 7)); ((0, 6), (1, 4));
((0, 7), (2, 6)); ((0, 7), (1, 5)); ((1, 0), (3, 1)); ((1, 0), (0, 2));
((1, 0), (2, 2)); ((1, 1), (3, 0)); ((1, 1), (3, 2)); ((1, 1), (0, 3));
((1, 1), (2, 3)); ((1, 2), (3, 1)); ((1, 2), (3, 3)); ((1, 2), (0, 0));
((1, 2), (0, 4)); ((1, 2), (2, 0)); ((1, 2), (2, 4)); ((1, 3), (3, 2));
((1, 3), (3, 4)); ((1, 3), (0, 1)); ((1, 3), (...)); ...]

where the nodes is rapresented by tuples ((0,0) is a node, (1,3) is a node and so on...) and ((0,0),(2,1)) represent a connection between node (0,0) and node (2,1);

How can I represent my "graph" by a list of successor of any node? The result must be:

val succ_graph : ((int * int) * (int * int) list) list =
[((0,0),[(2,1),(1,2)]);((0,1),[(2,0),(2,2),(1,3)]);((0,2),[(2,1),(2,3),
(1,0),(1,4)]); .... ]

a list of tuples where the first param is the node himself and the second param is a list of any successor of him;

I wrote a function that extract the list of successor giving a specific node, but i don't know how to do the rest.

let succ arcs node =
  let rec aux = function
    [] -> []
    | (x,y)::rest -> if x = node then y::aux rest
       else aux rest
  in aux arcs;;

Sorry but it's my first experience with ocaml, and sorry for the bad english!!!

Thank's.

Upvotes: 2

Views: 693

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66808

As an initial comment, your problem statement and examples are a little confusing. The example result you give is not of the type you say you want. And your function doesn't compute a part of the type either. Let's say you really do want this type:

((int * int) * ((int * int) * (int * int)) list) list

For each node of your graph you want a list of pairs of nodes. An example of this would be:

[((0, 0), [((0, 0), (2, 1)); ((0, 0), (1, 2))]); ... ]

Your example result doesn't look like this, and your function is calculating a list of nodes (not a list of pairs of nodes).

So the first thing to do might be to resolve this disagreement.

After you figure this out, the code you have now is actually pretty close to the right answer. Instead of looking for links from a particular node, you would add every link you see to your answer. Instead of putting answers at the front of a list, you need to be able to insert answers down inside the result that you're constructing.

A good place to start, then, might be to write code to add a new link to an accumulated result of type ((int * int) * ((int * int) * (int * int)) list) list.

Lists in OCaml are immutable, so the way to do this is to construct a new list. The new list will contain many parts of the old list; you don't have to build it from scratch. (This is, in fact, why immutable data is actually usable in practice.)

Update

As I say, you can use your current code if you write a function that adds a new successor in the correct place. Then you use this new function instead of the simple function :: that you're using now.

But the notion of "adding" something to an immutable structure is a bit tricky at first.

Here's a function that "adds" an int to a list while keeping the list sorted. I.e., it returns a new list with the desired property. The old list is unchanged (being immutable, this is a given).

let rec insert l x = match l with
| [] -> [x]
| h :: t -> if x <= h then x :: l else h :: insert t x

It looks like this:

# insert [1; 1; 3; 4; 5; 9] 2;;
- : int list = [1; 1; 2; 3; 4; 5; 9]

You can use this insert function to sort a list (inefficiently):

let rec sort = function
| [] -> []
| h :: t -> insert (sort t) h

It looks like this:

# sort [3; 1; 4; 1; 5; 9; 2];;
- : int list = [1; 1; 2; 3; 4; 5; 9]

This is essentially what you want to do, except you have pairs instead of ints, and your structure is a little more complicated than a sorted list.

Upvotes: 1

Related Questions