1. A method comprising: storing, by a router having a processor, a shape graph that is a compressed form of a trie that represents routing information for routing data packets in a network; storing, by the router, an update data structure that includes plural entries corresponding to nodes of the shape graph, the plural entries containing count values indicating respective numbers of nodes of the trie represented by the corresponding nodes of the shape graph; and incrementally updating, by the router, the shape graph as a portion of the routing information changes, wherein the incremental updating uses information in the update data structure.