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
Submitted by mfojtik on Tue, 2010-04-27 07:13
»
- Login to post comments
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