Algorithm Suggestion/Help (buiding strings from a graph)

[Jeremy S.]

Using .NET 3.5.I need to build a collection of strings given the following
input (presented in the app as a DataTable):

NodeID --- ParentNodeID --- CultureName --- NodeText
1 --- 2 --- fr-FR --- Crepes
1 --- 2 --- en-US --- Pancakes
2 --- null --- fr-FR --- Petit-Déjeuner
2 --- null --- en-US --- Breakfast
3 --- null --- en-US --- Veggies
4 --- 3 --- en-US --- Carrots
5 --- 3 --- en-US --- Peas
6 --- 5 --- en-US --- Snow Peas
7 --- 5 --- en-US --- Snap Peas
8 --- 6 --- en-US --- Large
9 --- 10 --- fr-FR --- Pois
10 --- null --- fr-FR --- Légumes

* Each string is to represent a complete valid "path" from a root node to
each possible child node, with nodes delimited with the '/' character.
* A root node is a row with a NULL ParentNodeID value
* This is a graph, not a tree, as each "child" node can have multiple
parents, and each parent can have multiple child nodes. For example, in the
sample data set, NodeID 1 has multiple parents (nodeID 2. differentiated on
CultureName).

The output string collection given the above sample DataTable input would
include these as valid strings (the output sequence is not important)

Petit-Déjeuner
Breakfast
Veggies
Légumes
Petit-Déjeuner/Crepes
Breakfast/Pancakes
Veggies/Carrots
Veggies/Peas
Veggies/Peas/Snow Peas
Veggies/Peas/Snow Peas/Large
Veggies/Peas/Snap Peas
Légumes/Pois

This string.
Breakfast/Crepes
.. would NOT be valid because the CultureName does not match between the
parent node (Breakfast is en-US) and child node (Crepes is fr-FR).

I would very much appreciate a suggestion for an algorithm I could use or
tweak to get what I need here.

Thanks

[Fred Mellender]

Re: Algorithm Suggestion/Help (buiding strings from a graph)

You should look into "depth-first-search with backtracking", which will
calculate all paths for you. You just need to audit each to discard invalid
ones (either after the fact, or as you build up the path).


"Jeremy S." <A@B.comwrote in message
news:OMBCaIW1IH A.2384@TK2MSFTN GP04.phx.gbl...

Using .NET 3.5.I need to build a collection of strings given the following
input (presented in the app as a DataTable):
>
NodeID --- ParentNodeID --- CultureName --- NodeText
1 --- 2 --- fr-FR --- Crepes
1 --- 2 --- en-US --- Pancakes
2 --- null --- fr-FR --- Petit-Déjeuner
2 --- null --- en-US --- Breakfast
3 --- null --- en-US --- Veggies
4 --- 3 --- en-US --- Carrots
5 --- 3 --- en-US --- Peas
6 --- 5 --- en-US --- Snow Peas
7 --- 5 --- en-US --- Snap Peas
8 --- 6 --- en-US --- Large
9 --- 10 --- fr-FR --- Pois
10 --- null --- fr-FR --- Légumes
>
* Each string is to represent a complete valid "path" from a root node to
each possible child node, with nodes delimited with the '/' character.
* A root node is a row with a NULL ParentNodeID value
* This is a graph, not a tree, as each "child" node can have multiple
parents, and each parent can have multiple child nodes. For example, in
the sample data set, NodeID 1 has multiple parents (nodeID 2.
differentiated on CultureName).
>
The output string collection given the above sample DataTable input would
include these as valid strings (the output sequence is not important)
>
Petit-Déjeuner
Breakfast
Veggies
Légumes
Petit-Déjeuner/Crepes
Breakfast/Pancakes
Veggies/Carrots
Veggies/Peas
Veggies/Peas/Snow Peas
Veggies/Peas/Snow Peas/Large
Veggies/Peas/Snap Peas
Légumes/Pois
>
This string.
Breakfast/Crepes
. would NOT be valid because the CultureName does not match between the
parent node (Breakfast is en-US) and child node (Crepes is fr-FR).
>
I would very much appreciate a suggestion for an algorithm I could use or
tweak to get what I need here.
>
Thanks
>
>

[=?ISO-8859-2?Q?Micha=B3_Piaskowski?=]

Re: Algorithm Suggestion/Help (buiding strings from a graph)


Jeremy S. wrote:

* This is a graph, not a tree, as each "child" node can have multiple
parents, and each parent can have multiple child nodes. For example, in the
sample data set, NodeID 1 has multiple parents (nodeID 2. differentiated on
CultureName).

If you group the records in source table by CultureName won't that
reduce this graph to a set of trees (one tree for each culture) and
also eliminate all invalid results ( like Breakfast/Crepes )?