Method and apparatus for routing groups of paths

A method of routing a net by identifying a set of paths between a set of source routable elements of a net and a set of target routable elements of the net, wherein the set of paths has to have a minimum acceptable number of paths, the method comprising:

• a) identifying a set of an acceptable number of at least two paths between the set of source routable elements and the set of target routable elements, said identifying comprising:
• 1) specifying a first total cost;
• 2) performing a first depth-first search to identify the set of at least two paths that each have a cost that does not exceed the first total cost, wherein each path in the set includes a set of expansions from the set of routable-element sources to the set of routable-element targets;
• 3) if the search cannot find the acceptable number of paths, incrementing the total cost and performing a second depth-first search to identify the set of paths that each have a cost that does not exceed the incremented total cost, wherein the acceptable number of paths is at least two paths;
• and
• b) when the acceptable number of paths is identified, using one of the paths to define a route for the net.