1 2 Previous Next 19 Replies Latest reply: Jun 4, 2007 2:20 AM by 807600 Go to original post RSS
      • 15. Re: Graph Search Algorithm
        807600
        List < List < Integer > > prints List<List><Integer>> in this reply
        That's the forum's "self closing angle bracket" bug. If you want to write something like:
        List<List<Integer>> setOfSet = new ArrayList<List<Integer>>();
        then you have to use &lt; instead of <. This applies to every instance of < both inside the[code] tags and outside.

        I thought of quite a different approach to this problem: building a forest (I think that's the term) from the adjacency entries. The forest is built from the bottom up. First the original graphs nodes are added (they constitute the leaves of the forest). Then each adjacency entry is added from the smallest to the biggest in the following fashion.

        ? * The "top" ancestors (so far) of the leaves being connected are determined.
        ? * If they are the same, the adjacency entry is added as the parent of this node
        ? * If they are different, the adjacency entry is added as the common parent of both nodes.

        While it is being built the forest keeps track of the currently parentless nodes.

        Once the forest has been built it is an easy matter to determine the components for any given threshold: for each of the parentless nodes you work down its tree until you encounter a node whose value is less than or equal to the threshold. The leaves under this node constitute one of the components being sought.

        The resulting code is more verbose than yours. (Not polished, and not even thoroughly checked). But such an approach might be useful if the components have to be determined for a large number of different thresholds: the forest only has to be constructed once.

        [Edit] The middle step of the three listed is not necessary. In that case the adjacency infomation contributes nothing and can be discarded. This greatly reduces the size of the resulting data structure and allows for graphs with thousands of nodes to be analysed.
        • 16. Re: Graph Search Algorithm
          807600
          Hello,

          Thanks for your efforts. I am sorry that I was not precise enough in my last reply.
          The answer for the adjacency matrix should be [[ABEC]] which is a set or any of the permutation (the order of the char do not matter) , and not [[ABEC], [BAEC]] which are two sets. The Set [ABEC] and [BAEC] are the same subgraph, so, it will be either the later or the former.

          I will work hard to see if I can correct the problem, but If you have a better idea on how to do it that will be fine.

          Jona_T
          • 17. Re: Graph Search Algorithm
            807600
            see 14th reply and remove '>' at every List<List<Integer>> to List<List<Integer>>.
            This forum automatically add '>' when it meet with another '<'
            • 18. Re: Graph Search Algorithm
              807600
              Hello,

              I removed the additional "<" and ran the program before my last reply. It still gave me 2 similar sets of different permutations instead of 1. Is there any way we can check if a permutation of a set already exits?
              // check if source already in setOfSet
                          boolean alreadyExists = false;
                          for (List<Integer> e : setOfSet) {
                              if (e.contains(src)) {  // Can we check for different permutations of the set, eg, [A,B,E,C] = [A,B,C,E] = [B,C,E,A] etc. ???? 
                                  alreadyExists = true;
                                  break;
                              }
                          }
              Thanks a lot,

              Jona_T
              • 19. Re: Graph Search Algorithm
                807600
                Hello Shadinata,

                Your program actually works. The problem was on my side and I have corrected it. By now you must have received your dukes.

                Thanks for the time spent.

                Jona_T
                1 2 Previous Next