-3

I have data like

Key  Value
---  -----
A     B
B     E
B     C
C     E
E     D
D     G
F     e

Now when user enters A I want the output like 

A-B-C-E-D-G

If user Enters F then F-E-D-G

I have recursive function which is working for small no of key value say 100 if combination and count gets increase it is taking too much time for execution

How to achieve this using C#?

wonea
  • 4,783
  • 17
  • 86
  • 139
user466722
  • 15
  • 4
  • Are you asking how to throw out the duplicates? – Robert Harvey Jun 09 '14 at 17:16
  • 1
    Is `A-B-E-D-G` for `A` also valid, given that `B` has a link directly to `E`? If not, what makes you pick one link above another? – Bernhard Barker Jun 09 '14 at 17:20
  • Why implement this as a dictionary, why not an actual graph? It would serve you much better (even if you have to roll your own). – BradleyDotNET Jun 09 '14 at 17:22
  • 2
    You tagged this [tag:graph-algorithm], so presumably you know you should construct a graph (the parts of which should be fairly obvious), at which point the algorithm becomes somewhat trivial. Have you tried doing this? Where are you stuck? – Bernhard Barker Jun 09 '14 at 17:22
  • "I have recursive function which is working..." - can you elaborate a bit on your algorithm? Perhaps provide a high-level description or some pseudo-code. This should also give us a better idea of how your data is currently stored, and it tends to help in case your examples aren't entirely clear. – Bernhard Barker Jun 09 '14 at 17:26
  • @BradleyDotNET A dictionary representing the edges is an entirely sensible way of representing a graph in code. Another is through a number of objects each with references to each other. Each representation makes certain operations easier, and certain ones harder. Personally I'd rather implement this particular problem with a dictionary of edges than with a root note that has references to a bunch of other nodes, although both are capable of doing the job. – Servy Jun 09 '14 at 17:39
  • [Here](http://blogs.msdn.com/b/ericlippert/archive/2010/02/08/making-the-code-read-like-the-spec.aspx) is an amazing blog article on how to build the proper mindset for solving programming problems that incidentally uses your exact problem as its example (which it solves). – Servy Jun 09 '14 at 17:43
  • @Dukeling A-B-E-D-G is not valid event though there is link btween B and E we need to ignore as B is connected to C amd C to E – user466722 Jun 10 '14 at 08:35

2 Answers2

2

The data that you have defines a Directed Graph (DG). A more traditional representation would be an Adjacency List:

A -> { B }
B -> { C, E }
C -> { E }
D -> { G }
E -> { D }
F -> { E }
G -> { }

You can find cycles in DGs by running a Depth-First Search (DFS) algorithm on them. A cycle exists if, and only if, there is a back edge. You can retrieve the cycle easier if your recursive implementation of DFS passes down the list of vertexes visited on the path from the initial node to the current one. Once your algorithm detects a back edge, it traverses the current path from the source, finds the destination vertex of the back edge, and takes the edges from that vertex to the end as the part of a cycle.

You can find good implementations of DFS among answers to this question.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
0

In case your data is not changing much you can try performing your calculations in background and maintain the set of ready sequences for each possible entry - in some sort of dictionary. This way you will gain maximum performance. Once your data has been changed, you can update relevant paths in your result dictionary. This way you will prevent unneeded calculations on each and every request. Another strategy you can use is trying to cache already calculated results just on demand, so the first request will take some time, but the next time for already computed entry you will not perform same calculation, but return already computed result. Again, all this will improve the performance with relatively static initial data. In case your initial set is changing rapidly, you should think of some sort of data structure that will help you avoid recursion, or at least minimize the depth of recursion stack.

gelmanet
  • 89
  • 2