►Compilers – 2023/  24
▼3 CPSC 411 Infrastructure Package
On this page:
graph?
new-graph
add-vertex
remove-vertex
add-directed-edge
add-edge
add-directed-edges
add-edges
get-neighbors
8.10
    contents  ← prev  up  next → 

3.6 Functional Graphs

 (require cpsc411/graph-lib) package: cpsc411-lib
This library defines a functional graph library, where graphs are represented as lists of proper association lists for simple serialization.

procedure

(graph? v) → boolean?

  v : any/c
A predicates that returns #t if v is a graph.

A graph is an proper association list from a vertex to a list of vertexes. A directed edge exists between a vertex V1 to V2 if V2 is in the list associated with V1.

Examples:
> (graph? '())

#t

> (graph? '((x ())))

#t

> (graph? '((x (y))))

#t

> (graph? '((x    y)))

#f

> (graph? '((x (y)) (y (x))))

#t

procedure

(new-graph [vs]) → graph?

  vs : (listof any/c) = '()
Returns a new graph, initialized to include each element of vs as a vertex in the graph.

Examples:
> (new-graph)

'()

> (new-graph '(a b c))

'((c ()) (b ()) (a ()))

procedure

(add-vertex g v) → graph?

  g : graph?
  v : any/c
Returns a new graph equivalent to g with v added a vertex.

Example:
> (add-vertex (new-graph) 'a)

'((a ()))

procedure

(remove-vertex g v) → graph?

  g : graph?
  v : any/c
Returns a new graph equivalent to g twith the vertex v removed from the graph.

Examples:
> (add-vertex (new-graph) 'a)

'((a ()))

> (remove-vertex (add-vertex (new-graph) 'a) 'a)

'()

> (add-directed-edge (new-graph '(a b)) 'a 'b)

'((b ()) (a (b)))

> (remove-vertex (add-directed-edge (new-graph '(a b)) 'a 'b) 'b)

'((a ()))

procedure

(add-directed-edge g v u) → graph?

  g : graph?
  v : any/c
  u : any/c
Returns a new graph equivalent to g with a directed edge from v to u. Assumes both v and u are already vertexes in the graph.

Example:
> (add-directed-edge (new-graph '(a b)) 'a 'b)

'((b ()) (a (b)))

procedure

(add-edge g v u) → graph?

  g : graph?
  v : any/c
  u : any/c
Returns a new graph equivalent to g with a directed edge from v to u, and a directed edge from u to v. Assumes both v and u are already vertexes in the graph.

Example:
> (add-edge (new-graph '(a b)) 'a 'b)

'((b (a)) (a (b)))

procedure

(add-directed-edges g v us) → graph?

  g : graph?
  v : any/c
  us : (listof any/c)
Returns a new graph equivalent to g with a directed edge from v to every element of us. Assumes all vertexes are already in g.

Example:
> (add-directed-edges (new-graph '(a b c d)) 'a '(b c))

'((d ()) (c ()) (b ()) (a (c b)))

procedure

(add-edges g v us) → graph?

  g : graph?
  v : any/c
  us : (listof any/c)
Returns a new graph equivalent to g with a directed edge from v to every element of us, and from every element of us to v. Assumes all vertexes are already in g.

Example:
> (add-edges (new-graph '(a b c d)) 'a '(b c))

'((d ()) (c (a)) (b (a)) (a (c b)))

procedure

(get-neighbors g v) → graph?

  g : graph?
  v : any/c
Returns a list of each vertex with an edge coming from v in the graph g. Returns the empty set if v isn’t in the graph.

Examples:
> (add-edges (new-graph '(a b c d)) 'a '(b c))

'((d ()) (c (a)) (b (a)) (a (c b)))

> (get-neighbors (add-edges (new-graph '(a b c d)) 'a '(b c)) 'a)

'(c b)

    contents  ← prev  up  next →