For management and security purposes, cloud providers should know the connectivity graph between virtual machines. Since traditional methods used in physical networks produce incomplete results and are hardly usable in the Cloud, we propose to use information provided by a Cloud Management Software and an SDN controller, to compute the connectivity graph in those environments. Our approach shows an exact, complete and up-to-date connectivity graphs computation on a representative infrastructure, in reasonable time.