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.