Introduction

As I explained in this note, I often use ocamlgraph to build graphs, and the Graphviz.Dot to export them in dot format to be able to see them. But to be able to visually extract information from a large graph, it can be useful to select only a part of it.

We suppose here that the graph is a Persistent.Digraph module named G.

Compute a selection

The ocamlgraph library provide a Fixpoint module that can be used very easily to compute the reachability of nodes from some starting points, and BTW, it is precisely the example given in the documentation. The reachability module can work either forward of backward:

module Reachability (P: sig val fwd: bool end) = Graph.Fixpoint.Make(G)
(struct
  type vertex = G.E.vertex
  type edge = G.E.t
  type g = G.t
  type data = bool
  let direction
    if P.fwd then Graph.Fixpoint.Forward else Graph.Fixpoint.Backward
  let equal = (=)
  let join = (||)
  let analyze _ = (fun x -> x)
end)
module ReachabilityForward = Reachability (struct let fwd = true end)
module ReachabilityBackward = Reachability (struct let fwd = false end)

Using these modules, a selection function can be implemented:

let selected v
  let select_fwd = ReachabilityForward.analyze fwd_root_vertex g in
  let select_bwd = ReachabilityBackward.analyze bwd_root_vertex g in
  select_fwd v || select_bwd v

The fwd_root_vertex and bwd_root_vertex are supposed to be functions that return a boolean stating whether a node has to be considered as a starting point for the selection.

Build the new graph

Then to build a new graph with only the selected nodes, and the edges between selected nodes, the Gmap module can be used, and more precisely the Gmap.Edge module because we also want to select the edges, and not only the nodes. The edge selection is given by:

let select e
  if selected (G.E.src e) && selected (G.E.dst e) then Some e else None

Finally, the new graph can be build with:

let build_sub_graph g
  let module S = Graph.Gmap.Edge (G) (G) in
  S.filter_map select g

Now, you can learn here how to export it in order to see it.

Filter with ocamlgraph

Introduction

Compute a selection

Build the new graph

Voir aussi :