  We develop a notion of a generalized Cuntz-Krieger family of projections and
partial isometries where the range of the partial isometries need not have
trivial intersection. We associate to these generalized Cuntz-Krieger families
a directed graph, with a coloring function on the edge set. We call such a
directed graph an edge-colored directed graph. We then study the $C^*$-algebras
and the non-selfadjoint operator algebras associated to edge-colored directed
graphs. These algebras arise as free products of directed graph algebras with
amalgamation. We then determine the $C^*$-envelopes for a large class of the
non-selfadjoint algebras. Finally, we relate properties of the edge-colored
directed graphs to properties of the associated $C^*$-algebra, including
simplicity and nuclearity. Using the free product description of these algebras
we investigate the $K$-theory of these algebras.
