1

So I'm looking forward to pick a lets say a triangle/square/../hexagon from a graph.

What do i mean by that:

input from keybord: a-b b-c c-a

and

output m-n-o, x-y-z, s-t-u
(where each of this subgraphs respect that relation ship pattern of the vertex)

How to solve this: It has to be a raw version not with optimisations or other stuff, but without backtracking / recursion.

Solution: transpose the vertexes to a matrix and do combinations in for loops.

The problem i have: for instance if i want my graph to accept up to octogns, do I need to make 8 for in for's ?!

4

1 回答 1

0

自己的解决方案不是最好的，但足以完成休闲。用组合学 jar 完成。有帮助的洞

    @SuppressWarnings("unchecked")
    public static void drawMatrix(Graph g, int tempMatrixSize){
        System.out.println(" ");
        System.out.println("Matrix:");
        ArrayList<Node> nodesSet = new ArrayList<>();
        nodesSet = (ArrayList<Node>) g.getNodes().clone();

        int size = nodesSet.size();

        int[][] matrix = new int[size][size];

        System.out.print("  ");
        for (Node node : nodesSet){
            System.out.print(" " + node.getName()+ " ");
        }
        System.out.println();


        for (int i=0; i<size; i++) {
            System.out.print(nodesSet.get(i).getName()+ " ");
            for (int j=0; j<size; j++){
                if (i == j) {
                    System.out.print(" 1 ");
                    matrix[i][j] = 1;

                }
                else{
                    if (nodesSet.get(i).isFriend(nodesSet.get(j))) {
                        System.out.print(" X ");
                        matrix[i][j] = 1;
                    }
                    else {
                        System.out.print(" 0 ");
                        matrix[i][j] = 0;
                    }
                }
            }
            System.out.println();
        }
        System.out.println();

        // temp matrix
        int[][] tempMatrix = new int[tempMatrixSize][tempMatrixSize];

        // Find combinations
        ArrayList<Integer> al= new ArrayList<>();
        for (int i = 0; i<size; i++ ){
            al.add(i);
        }

        ICombinatoricsVector<Integer> initialVector = Factory.createVector(al);
        Generator<Integer> gen = Factory.createSimpleCombinationGenerator(initialVector, tempMatrixSize);
        int index = 0;
        for (ICombinatoricsVector<Integer> combination : gen) {
            boolean isConnected = true;
            System.out.println(combination);
            List<Integer> comb = combination.getVector();
            for(int i=0; i<tempMatrixSize; i++){
                for(int j=0; j<tempMatrixSize; j++){
                    tempMatrix[i][j] = matrix[comb.get(i)][comb.get(j)];
//                  System.out.print(tempMatrix[i][j]+ " ");
                }
                System.out.println();


            }
            // main matrix coordinations
            System.out.println("main matrix used coords: ");
            for(int i=0; i<tempMatrixSize; i++){
                for(int j=0; j<tempMatrixSize; j++){
                    tempMatrix[i][j] = matrix[comb.get(i)][comb.get(j)];
                    System.out.print("["+comb.get(i)+","+comb.get(j)+"] ");
                }
                System.out.println();
            }
            System.out.println();

            for(int i=0; i<tempMatrixSize; i++){
                for(int j=0; j<tempMatrixSize; j++){
                    if (tempMatrix[i][j] == 0){
                        isConnected = false;
                    }
                }
            }
            if (isConnected) {
                System.out.println("Is connected by >" + tempMatrixSize);
                for (int i=0; i<tempMatrixSize; i++) {
                    System.out.println(" >" +nodesSet.get(comb.get(i)).getName());
                }           
            }
        }
于 2013-04-19T15:24:14.140 回答