We introduce P-graphs, which are generalisations of directed graphs in which
paths have a degree in a semigroup P rather than a length in N. We focus on
semigroups P arising as part of a quasi-lattice ordered group (G,P) in the
sense of Nica, and on P-graphs which are finitely aligned in the sense of
Raeburn and Sims. We show that each finitely aligned P-graph admits a
C*-algebra C*_{min}(Lambda) which is co-universal for partial-isometric
representations of Lambda which admit a coaction of G compatible with the
P-valued length function. We also characterise when a homomorphism induced by
the co-universal property is injective. Our results combined with those of
Spielberg show that every Kirchberg algebra is Morita equivalent
C*_{min}(Lambda) for some (N^2 * N)-graph Lambda.