Search

The subgraph isomorphism problem, the goal of which is to find the occurrences of a given pattern graph in a given host graph, is, owing to the pervasiveness of large networks, becoming increasingly important. However, the problem is NP-complete, and the search efficiency may also be negatively affected by symmetries in the pattern graph. In this paper, we present an algorithm for solving the subgraph isomorphism problem using a search plan, a sequence of instructions for a systematic traversal of the pattern graph. The presented algorithm pays attention to the symmetries in the pattern graph and thus performs more efficiently than its straightforward counterpart which merely follows the search plan instructions in all possible ways. By testing our algorithm on artificial and real-world graphs, we empirically confirm its advantage over the naive approach and answer several research questions. [ABSTRACT FROM AUTHOR]

The paper introduces a concept of attributed context-sensitive graph grammars. The graph grammars are a graphical generalization of the textual grammars and can thus be used to specify the syntax of graphical programming or modeling languages. The attributed graph grammars extend the basic graph grammars with definitions of attributes and the associated attribute evaluation rules. By analogy to the attributed textual grammars, the purpose of the attributes and the rules is to define the semantic elements of a graphical language. The introduced concept is illustrated by an example of a grammar-driven conversion of flowcharts to the equivalent C code. The presented example might find its use in introductory programming courses. [ABSTRACT FROM AUTHOR]