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 ℕ. 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 (Λ) which is co-universal for partialisometric representations of Λ 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 to Cmin* (Λ) for some (ℕ2* ℕ)-graph Λ. © 2012 Hebrew University Magnes Press.