1. A method comprising: generating a second graph from (i) a first graph of multiple devices in a network and (ii) a set of one or more network compatibility rules, wherein said generating comprises dividing each device in the first graph into multiple nodes in the second graph, and wherein each node in the second graph represents a valid configuration of a device in the first graph; identifying multiple sub-graphs of two or more linked nodes in the second graph that are each isomorphic to at least a portion of the first graph, wherein the two or more linked nodes in the second graph represent two or more configurations that (i) are compatible based on the set of one or more network compatibility rules, and (ii) satisfy one or more constraints pertaining to device upgrades; identifying each of the multiple sub-graphs in the second graph that corresponds to a valid upgrade plan, wherein said identifying comprises (i) verifying that each device has only one configuration in each of the multiple sub-graphs, and (ii) filtering out each of said sub-graphs that (a) is isomorphic but (b) does not satisfy a target configuration based on said verifying; creating an upgrade plan arising from each of the remaining sub-graphs, wherein each upgrade plan is based on a determination of each of one or more changes needed to convert a current configuration in the network to said target configuration specified by the sub-graph from which the upgrade plan arises; computing a cost associated with each of the upgrade plans via a cost function comprising at least the number of devices in the network requiring at least one configuration change under each of the upgrade plans; and outputting a sub-set of the multiple upgrade plans that satisfy one or more pre-defined specifications based on the computed cost associated with each of the upgrade plans; wherein the steps are carried out by at least one computing device.