Visualize graph homomorphisms using Graphviz

[epatters]

The Graphs module has built-in support for Graphviz drawing of graphs. It should also support visualizing graph homomorphisms.

A starting point is in #555, which visualizes the codomain graph using colors.

[jpfairbanks]

Here is the code from #555 that you can start with, the only changes I think it needs are

function GraphvizGraphs.to_graphviz_property_graph(f::ACSetTransformation; kw...)
  pg = GraphvizGraphs.to_graphviz_property_graph(dom(f); kw...)
  vcolors = hex.(range(colorant"#0021A5", stop=colorant"#FA4616", length=nparts(codom(f), :V)))
  ecolors = hex.(range(colorant"#6C9AC3", stop=colorant"#E28F41", length=nparts(codom(f), :E)))
  hex.(colormap("Oranges", nparts(codom(f), :V)))
  for v in vertices(dom(f))
    fv = f[:V](v)
    set_vprops!(pg, v, Dict(:color => "#$(vcolors[fv])"))
  end
  for e in edges(dom(f))
    fe = f[:E](e)
    set_eprops!(pg, e, Dict(:color => "#$(ecolors[fe])"))
  end
  pg
end

1. Type parameters should be slightly more constrained so that we don't pirate ourselves.
2. Color scale should be passed as a keyword argument.

@olynch, do you see a way to generalize this approach for Semagrams? Color coding a Semagram via a homomorphism seems useful.

[slwu89]

@jpfairbanks I was playing around with this code, it has a problem setting up the color range when multiple edges/nodes get mapped to a single edge or node in the codomain. Minimal ex:

G = Graph(2)
add_edges!(G, [1], [2])

H = Graph(1)
add_edges!(H, [1], [1])

f = ACSetTransformation(G, H; V = [1,1], E = [1])

GraphvizGraphs.to_graphviz_property_graph(f)

[jpfairbanks]

Is the problem that multiple vertices are getting sent to 1 in the codomain? Or is it that there is only one vertex in the codomain? I think the latter because we are doing a colorant range

  vcolors = hex.(range(colorant"#0021A5", stop=colorant"#FA4616", length=nparts(codom(f), :V)))
  ecolors = hex.(range(colorant"#6C9AC3", stop=colorant"#E28F41", length=nparts(codom(f), :E)))

That call to range needs to handle the case that if nparts(codom(f), :V) == 1 just use a default color like black or a dark grey and the same for :E.

Something like this would work

  nv = nparts(codom(f), :V)
  vcolors = nv < 2 ? [hex(colorant”000000”)] : hex.(range(colorant"#0021A5", stop=colorant"#FA4616", length=nv))

[slwu89]

@epatters I decided to play around with Graphviz after being inspired by the Petri net homomorphisms, basically simplifying the approach from AlgPetri. I came up with something like this:

Is this still of interest to include in catlab? I could clean things up and open a PR if so (including figuring out how to get rid of my ad-hoc labeling in the vertices). It also seems that I cannot create edges between edges but hopefully the coloring combined with the edges between vertices will be clear enough.

[epatters]

@slwu89, absolutely, it would be wonderful to get a cleaned up version of this in Catlab!

[slwu89]

@epatters I cleaned up my code a bit but I'm yet unsure what changes need to be made to make it live more harmoniously with the existing graph visualization code (I was looking at this file in particular https://github.com/AlgebraicJulia/Catlab.jl/blob/master/src/graphics/GraphvizGraphs.jl). Do you have any advice for what you'd like to see changed before I open a PR?

Here's a minimal example:

using Catlab.CategoricalAlgebra
using Catlab.Graphics.Graphviz
using Colors
using Catlab.Graphs.BasicGraphs
using Graphviz_jll # needed on my machine

make_tagged_subgraph = function(g; pre="")
  stmts = map(g.stmts) do st
    add_label(st, pre)
  end
  Graphviz.Subgraph(g.name, stmts, g.graph_attrs, g.node_attrs, g.edge_attrs)
end

add_label(n::Graphviz.Node, pre) = Node("$pre$(n.name)", n.attrs)
add_label(e::Graphviz.Edge, pre) = begin
  path = map(e.path) do n_id
    Graphviz.NodeID("$pre$(n_id.name)", n_id.port, n_id.anchor)
  end
  Graphviz.Edge(path, e.attrs)
end

default_edge_colors(n) = "#" .* hex.(distinguishable_colors(n, colorant"#F8766D", lchoices = [65], cchoices = [100]))
default_edge_labels(e, dom::Bool) = "$(e)"

default_vertex_colors(n) = repeat(["black"], n)
default_vertex_labels(v, dom::Bool) = "$(v)"

""" Visualize a graph homomorphism using Graphviz

Visualize an ACSetTransformation between two Graph objects. By default the edge mapping is represented by colors, and vertex mapping by edges between the domain and codomain subgraphs.

Keyword arguments are listed below:
- `edge_colors::Function`: a function which returns a `Vector{String}` giving a color for each element in the map from edges in the domain to codomain.
- `edge_labels::Function`: a function taking two arguments, the integer edge id and a boolean specifying if this edge is in the domain or codomain, and returning a string label.
- `vertex_colors::Function`: a function which returns a `Vector{String}` giving a color for each element in the map from vertices in the domain to codomain.
- `vertex_labels::Function`: a function taking two arguments, the vertex edge id and a boolean specifying if this vertex is in the domain or codomain, and returning a string label.
"""
function visualize_graph_homomorphism(f::ACSetTransformation; 
  edge_colors::Function=default_edge_colors, edge_labels::Function=default_edge_labels,
  vertex_colors::Function=default_vertex_colors, vertex_labels::Function=default_vertex_labels,
  name="G", prog="dot")

  (dom(f) isa BasicGraphs.Graph && codom(f) isa BasicGraphs.Graph) || throw(ArgumentError("f should be a homomorphism between Graphs"))

  # mapping between edges given by colors
  ecolors = edge_colors(nparts(codom(f), :E))

  # mapping between vertices given by colors
  vcolors = vertex_colors(nparts(codom(f), :V))

  # subgraph of dom(f)
  dom_nodes = [Node("$v", Attributes(:label=>vertex_labels(v, true),:shape=>"circle",:color=>vcolors[f[:V](v)])) for v in parts(dom(f), :V)]
  dom_edges = [Edge(["$(dom(f)[e,:src])", "$(dom(f)[e,:tgt])"], Attributes(:label=>edge_labels(e, true),:color=>ecolors[f[:E](e)])) for e in parts(dom(f), :E)]

  dom_stmts = vcat(dom_nodes, dom_edges)
  dom_subgraph = make_tagged_subgraph(Graphviz.Digraph("G", dom_stmts; prog=prog, name="clusterDom"), pre="dom_")

  # subgraph of codom(f)
  codom_nodes = [Node("$v", Attributes(:label=>vertex_labels(v, false),:shape=>"circle",:color=>vcolors[v])) for v in parts(codom(f), :V)]
  codom_edges = [Edge(["$(codom(f)[e,:src])", "$(codom(f)[e,:tgt])"], Attributes(:label=>edge_labels(e, false),:color=>ecolors[e])) for e in parts(codom(f), :E)]

  codom_stmts = vcat(codom_nodes, codom_edges)
  codom_subgraph = make_tagged_subgraph(Graphviz.Digraph("G", codom_stmts; prog=prog, name="clusterCodom"), pre="codom_")

  # mapping between vertices
  node_map = [Edge(["\"dom_$i\"", "\"codom_$(components(f)[:V](i))\""], Attributes(:constraint=>"false", :style=>"dotted")) for i in 1:length(dom(components(f)[:V]))]

  stmts = vcat(dom_subgraph, codom_subgraph, node_map...)
  g = Graphviz.Digraph(name, stmts)
  return g
end

A = BasicGraphs.Graph(3)
add_edges!(A, [1,1], [2,3])

B = BasicGraphs.Graph(4)
add_edges!(B, [1,3], [2,4])

f = ACSetTransformation(A, B; V = [1,2,2], E = [1,1])

visualize_graph_homomorphism(f)

[epatters]

Thanks Sean! I may make some changes but it would be great if you could start a PR.

[jpfairbanks]

Thanks Sean, this is a great feature!

[slwu89]

Thanks to Evan for his work to review the PR, which must have been at least as much work as the PR itself haha.