The Data-Driven Computational Mechanics approach (Kirchdoerfer et al. 2016) aims to bypass the constitutive modelling step traditionally used in continuum mechanics. On the contrary, the discrete data containing relevant information on the material, the material database, is directly enforced into the simulation, avoiding the bias inherent in material laws such as the a priori choice of the model by the user, the approximation of the experimentally observed material response or the difficulty to identify the parameters of the mathematical law. Originally written for elastic behaviours, the mathematical foundation of the method for the general case of inelastic behaviours was developed a few years later (Eggersmann et al. 2019). For this type of materials, the dependence on the past history of strain and stress and the way to consider it in the simulation is the main challenge for future developments. Our work addresses this problem for elastoplastic behaviours, which are characterised by the time-independent irreversibility of strains. We use concepts of graph theory to handle the material database and represent the past history: the observed material states and the transitions between them are symbolised by the vertices of a directed graph and its arcs. The transitions must be admissible from a thermomechanical point of view and the cost of the corresponding arcs is determined by their dissipation. In other words, a non-dissipative elastic transition is symmetric while a plastic and thus irreversible transition is asymmetric with strictly positive cost. During the data-driven simulation, as time goes by, the material database at a specific integration point reduces given the local past history. This translates in terms of graphs into a tree built from the last obtained local material state by searching for all admissible vertices in the graph. In this way, the physical phenomenology of elastoplastic behaviours is encoded in a graph whose structure is used for the data-driven simulation, allowing to predict the material response, as will be illustrated by numerical examples.