Lists for graphs

next up previous contents
Next: The two ways to represent graphs
Up: Introduction to Prolog for Mathematicians
Previous: Lists for parse trees

Lists for graphs

By putting ``labels'' inside lists, we can represent cyclic graphs:

[ label(1,a), b, c, ref(1) ].

It may be more convenient though, to represent the edge-set:

[ edge(a,b), edge(b,c), edge(c,a) ].

Doing this, we can associate weights and other information with the edges:

[ edge(a,b,0.3), edge(b,c,0.4),
  edge(c,a,27) ].

This is useful in handling finite-state automata:

[ arc(s1,s2,i1), arc(s1,s3,i2),
  arc(s3,s1,i3), arc(s3,s3,i4) ].
We could use a similar representation for diagrams in category theory.

Jocelyn Ireson-Ireson-Paine
Mon Jul 17 22:27:41 BST 1995