Abstract: Given a finite directed graph G with n vertices, the metric m(G) is naturally defined over F q n , where the weight of a word which has its nonzero entries in positions i 1 ,..., i r , is equal to the number of vertices in all the directed paths starting in the vertices v i1 ,..., v ir . Two canonical forms, which do not affect the metric, are given to each graph. Based on these canonical forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield two different metrics. Efficient algorithms to check if a given set of metric weights define a metric based on a graph are given. We provide tight bounds on the number of metric weights required to reconstruct the whole metric. Finally, we discuss the group of linear isometries of the graph metrics and the connection of the work to coding theory Ver menos