File Dependency graph and RGL
RGL provides easy manipulation of graph:
require 'rgl/adjacency' g = RGL::DirectedAdjacencyGraph.new IO.foreach(ARGV.shift) {|line| if line =~ /\s*([^\"]+)[\"\s]*->[\"\s]*([^\"\[\;]+)/ g.add_edge $1, $2 end } p "vertices: #{g.num_vertices}, edges: #{g.num_edges}" p g.vertices, g.edges.sort.to_s require 'rgl/topsort' p "topological sort:", g.topsort_iterator.to_a require 'rgl/traversal' v = "c.h" gb = g.bfs_search_tree_from(v) p "tree from #{v}: vertices: #{gb.num_vertices}, edges #{gb.num_edges}" p gb.vertices, gb.edges.sort.to_s require 'rgl/dot' p gb.write_to_graphic_file('gif', 'ctree') p "dfs: distance_to_root==2" dv = RGL::DFSVisitor.new(g) dv.attach_distance_map g.depth_first_search(dv) {|u| print "#{u} " if dv.distance_to_root(u) == 2 }
Then its output:
"vertices: 8, edges: 13" ["a.c", "b.h", "m.h", "x.h", "c.h", "n.h", "y.h", "z.h"] "(a.c-b.h)(a.c-c.h)(a.c-x.h)(b.h-m.h)(b.h-n.h)(b.h-x.h)(c.h-x.h)(c.h-y.h)(m.h-z.h)(n.h-y.h)(x.h-y.h)(x.h-z.h)(y.h-z.h)" "topological sort:" ["a.c", "c.h", "b.h", "n.h", "m.h", "x.h", "y.h", "z.h"] "tree from c.h: vertices: 4, edges 3" ["x.h", "c.h", "y.h", "z.h"] "(c.h-x.h)(c.h-y.h)(x.h-z.h)" "ctree.gif" "dfs: distance_to_root==2" x.h m.h n.h
Source Graphviz "dot" file: ------ Subtree "c.h" and below: