4.2 graph

8.18

4.2 graph🔗ℹ

(require karp/lib/graph)

package: Karp

type-descriptor
(graph directedness)

directedness = #:undirected
| #:directed

type-descriptor
(subgraph-of a-graph)

a-graph : value-descriptor? Graph?

value-descriptor / procedure
(edges-of a-graph)
(edges-of g)

a-graph : value-descriptor? Graph?
g : graph?

Get the set of edges of the graph g when used outside decision-problem.

value-descriptor / procedure
(vertices-of a-graph)
(vertices-of g)

a-graph : value-descriptor? Graph?
g : graph?

Get the set of vertices of the graph g when used outside decision-problem.

procedure
(endpoints e) → (setof? any)
e : edge?

Get the set of endpoints of a given edge e.

procedure
(-e- u v) → undirected-edge?
u : any
v : any

Create an undirected edge with endpoints u and v.

NOT available inside verifier definitions

procedure
(-e-> u v) → directed-edge?
u : any
v : any

Create an directed edge from u and v.

NOT available inside verifier definitions

procedure
(has-edge? u v g) → boolean?
  u : any
  v : any
  g : graph?

Check if there is an edge from u to v in graph g.

procedure
(e-u e) → any
e : edge

Get one endpoint of the edge e. If e is a directed edge, the result is the starting vertex.

procedure
(e-v e) → any
e : edge?

Get the other endpoint of the edge e, guaranteed to be different than the result of (e-u e). If e is a directed edge, the result is the ending vertex.

procedure
(incident? e v) → boolean?
e : edge?
v : any

Check if there is v is an endpoint of edge e.

procedure
(subgraph-of? g1 g2) → boolean?
g1 : graph?
g2 : graph?

Check if g1 is a subgraph of g2.

procedure
(neighbors g u) → (setof any)
g : graph?
u : any

Get the set of (out-)neighbors of vertex u in graph g. If g is a directed graph, the result is the set of vertices that u directs to.

procedure
(in-neighbors g u) → (setof any)
g : graph?
u : any

Get the set of in-neighbors of vertex u in graph g. The result is the same as (neighbors g u) when g is undirected. If g is a directed graph, the result is the set of vertices that direct to u.

procedure
(create-graph V E [#:directed? directed]) → graph?
  V : (setof any)
  E : (setof edge?)
  directed : boolean? = #f

Create a graph with vertex set V and edge set E. directed specifies whether the graph is directed or not.

procedure
(create-graph-from-edges E
[ #:directed? directed]) → graph?
E : (setof edge?)
directed : boolean? = #f

Create a graph from the edge set E. The vertex set of the resulting graph is the set of edgepoints of all edges in E. directed specifies whether the graph is directed or not.

procedure
(remove-edges g es) → graph?
g : graph?
es : (setof edge)

Produce a new graph by removing the set of edges es from graph g. The vertices of the resulting graph will be the same as g.

procedure
(remove-vertices g vs) → graph?
g : graph?
vs : (setof any)

Produce a new graph by removing the set of vertices vs from graph g. All edges with at least one endpoint in vs are also removed in the resulting graph.

procedure
(connected? g) → boolean?
g : graph?

Test if graph g is connected. When g is directed, weak connectivity is tested

procedure
(acyclic? g) → boolean?
g : graph?

Test if graph g is acyclic.

procedure
(st-path? g s t) → boolean?
  g : graph?
  s : any
  t : any

Test if graph g is an s-t path.

1	Getting Started with Karp, by Example
2	Problem Definition
3	Reduction
4	Structure Libraries

4.1	cnf
4.2	graph
4.3	mapping