graph: find subgraphs using list of nodes including wildcards

Question

Has the following problem got a name and is there an algorithm to solve it? : Given a graph, either directed or not, find all the paths which satisfy the specification given by

1. a list of exact nodes, or
2. '*?' which denotes just 'any node or no node at all', or
3. '*{n}' which denote 'any n consecutively connected nodes'

e.g.

A -> B -> *? -> D which results in ABXD and ABYD and ABD etc.

or

A -> *{1} -> D -> *? -> E which results in ABXDZE and ABYDZE and ABDZE etc. etc.

thanks

p.s. Does anyone know a graph library doing this either in R or perl or C?

Answer 1

I dunno any library for that, but you have to separate this in two part :

• the user query parsing
• The algorithm to find what you are looking for

For the parsing, i let you find what you need to do (using parsing library or by your self)

Concerning the algorithm part i suggest you to define a special structure (like a linked list) for representing you query, in which each element can either denote a real node, x number of node, or unlimited number of nodes.

The only problem on your algorithm is to find all path from a node A to a node B, using an unlimited number or a limited number of intermediate nodes. You can do this by using dynamic programming, or a search algorithm such as DFS or BFS.