Magnetic order in graphene-related structures can arise from size effects or from topological frustration. We introduce a rigorous classification scheme for the types of finite graphene structures (nanoflakes) which lead to large net spin or to antiferromagnetic coupling between groups of electron spins. Based on this scheme, we propose specific examples of structures that can serve as the fundamental (NOR and NAND) logic gates for the design of high-density ultrafast spintronic devices. We demonstrate, using ab initio electronic structure calculations, that these gates can in principle operate at room temperature with very low and correctable error rates.