# How can I partition a graph with two types of vertices?

I have a graph where the vertices represent latches and the edges represent whether there is a path from one latch to another (through combinational logic). The edges are undirected.

I would like to partition these latches into groups that tend to share neighbors. My problem is that there are two types of latches, positive and negative, and a group can only contain latches of the same type. Also, each latch can only be a member of one group.

Edges only exist between latches of different types.

Does METIS support what I'm trying to do? Could someone give me a little direction on how to accomplish this?

Thanks,
Matt

### RE: Matt, This is an interesting

Matt,

This is an interesting problem. Here is an approach that you may want to explore.
Let A and B be the two types of latches that you have.
Since the edges connect only type A and type B vertices, create two graphs. The first
will contain the type A vertices only and the second will contain the type B vertices.
Two vertices (u,v) in A will be connected via an edge if there is a (u,x), (x,v) edge
where x is a vertex in B. Set the weight of that edge to the different x vertices that
satisfy the above condition. Use a similar approach for creating edges in the graph
that contains the B vertices. Then, go ahead and partition those two graphs independently
of each other.

george