Bipartite Graphs

[mehalter]

We should add Bipartitioned graphs to Catlab.Graphs. We can then use this type for both AlgebraicPetri.jl and also be able to represent presentations that would give us pushout support for combining presentations as well as graphically displaying them. I think we something like the following types:

@present BipartitionedGraph(FreeSchema) begin
  (V1, V2)::Ob
  E::Ob
  src::Hom(E,V1)
  tgt::Hom(E,V2)
end

@present BipartitionedDiGraph(FreeSchema) begin
  (V1, V2)::Ob
  (E1, E2)::Ob
  src1::Hom(E1,V1)
  tgt1::Hom(E1,V2)
  src2::Hom(E2,V1)
  tgt2::Hom(E2,V2)
end

[epatters]

This would be great. You're right that it's technically more correct to call these "bipartitioned graphs," but I'd also be fine with calling them "bipartite graphs." In CT we don't always strictly follow the graph theory terminology, e.g., what we call a "graph" a graph theorist would call a "directed multigraph."

Micah, do you want to implement this? I think a new submodule Catlab.Graphs.BipartiteGraphs would make sense.

[mehalter]

Yeah I can start implementing this! It might be a couple days, I'm also working on implementing symmetric monoidal double categories as well that will be useful in double category of wiring diagrams for defining program transformations

[epatters]

I'll take this one over since I need it now.

It turns out that the (co)limit diagrams derived from UWDs have exactly the form of an undirected bipartite graph, with one vertex set corresponding to boxes and the other to junctions. This class of (co)limits is important enough, encompassing both conjunctive queries and structured cospan composites, that it makes sense to have special support for the diagrams.