Computing limits and colimits in the Category of Graphs and Morphisms

Question

I would like to compute limits (e.g., pullbacks, etc.) and colimits (e.g., pushouts, etc) of the finite diagrams in the category of finite Graphs and Morphisms.

Question:

1. Is there any algorithm (or tool) out there that I can use for this purpose?
2. If for a given diagram, its limit/colimit does not exist, I would like the algorithm tells me so (I think this should be decidable, isn't it?)

p.s.: by Graph above, I mean directed multi-graph; that is, edges are directed, and it is possible to have more than one edge between two nodes.

Answer 1

Products and coproducts of graphs are gotten in the same way as in sets. Similarly, the equalizer of two graph morphisms looks just like that in sets: its points and edges are those identified by the two morphisms. As for coequalizers, just identify the images under the two maps of the same vertices or edges from the domain. The final graph is a point with a single edge and the initial graph is the empty set with no edges.

As is well known, the existence of finite (co)products and (co)equalizers suffices to show the existence of all finite limits and colimits, so this settles your second question. If you're unaware of this fact, look in MacLane, Awodey, Julia Goedecke's online notes, or any other introduction to category theory. The proof of the fact also suggests an algorithm to compute arbitrary finite (co)limits in terms of two (co)products and a single (co)equalizer. The exact construction is either already known to you or will be found in any of the above references, which you'll need anyway, so I won't reproduce it here.

To understand why it was so straightforward to construct all finite limits and colimits as it's done it finite sets, it suffices to observe that the category of finite graphs is a functor category, that is the category of diagrams of shape $\bullet \stackrel{\to}{\to}\bullet$ with values in the category of finite sets. It's a general fact, then, that functor categories are just as complete or cocomplete as their codomains, and this would have yielded the calculations from the special case above.

If by "algorithm" you were hoping more for a "computer program," then I realize this may not be so helpful-but a finite graph is such a simple data structure that you should be able to implement it yourself in any language once you've understood the theory.