The need to provide customers with the ability to configure the network in current cloud computing environments has motivated the Networking-as-a-Service (NaaS) systems designed for the cloud. Such systems can provide cloud customers access to virtual network functions, such as network-aware VM placement, real time network monitoring, diagnostics and management, all while supporting multiple device management protocols. These network management functionalities depend on a set of underlying graph primitives. In this paper, we present the design and implementation of the software architecture including a shared graph library that can support network management operations. Using the illustrative case of all pair shortest path algorithm, we demonstrate how scalable lightweight dynamic graph query mechanisms can be implemented to enable practical computation times, in presence of network dynamism. © 2012 ACM.