قم بتنفيذ اختبار اتصال غير مباشر لفئة الرسم البياني Java

Question

أنا أكتب فصلًا في Java لتمثيل بنية بيانات الرسم البياني. هذا خاص برسم بياني غير موجه غير مرغوب فيه والغرض منه بشكل أساسي لاختبار الحافة (هل العقدة A متصلة بالعقدة B ، سواء بشكل مباشر أو غير مباشر).

أحتاج إلى مساعدة في تنفيذ أفضل طريقة. في الكود أدناه ، علقت فقط هذه الطريقة وأنا أعيد خطأ حتى يتم تجميع الكود كما هو.

لقد وضعت بعض الوقت في الخروج بخوارزمية ، لكن لا يمكنني العثور على أي شيء أكثر بساطة من هذا ، وأخشى أن أجعله أكثر تعقيدًا مما يجب أن يكون:

• اختبار أولاً للاتصال المباشر
• إذا لم يكن هناك اتصال مباشر من العقدة A إلى العقدة B:
  • لكل حافة قمت بتوصيلها بالعقدة أ:
    • قم بإنشاء رسم بياني جديد لا يحتوي على Edge A -> i
    • اختبار رسم بياني جديد للاتصال غير المباشر بين العقد I و B.

إما رمز كاذب أو رمز Java الفعلي موضع ترحيب في إجاباتك. هذا هو الرمز الذي لدي:

class Graph {

    // This is for an undirected, unweighted graph
    // This implementation uses an adjacency matrix for speed in edge testing 

    private boolean[][] edge;
    private int numberOfNodes;

    public Graph(int numNodes) {

        // The indices of the matrix will not be zero-based, for clarity,
        // so the size of the array will be increased by 1.

           edge = new boolean[numNodes + 1][numNodes + 1];
           numberOfNodes = numNodes;
    }

    public void addEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = true;
                edge[b][a] = true;
            }
        }
    }

    public void removeEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = false;
                edge[b][a] = false;
            }
        }
    }

    public boolean directEdgeTest(int a, int b) {

        // if node a and node b are directly connected, return true 

        boolean result = false;
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                if (edge[a][b] == true) {
                    result = true;
                }
            }
        }
        return result;
    }

    public boolean indirectEdgeTest(int a, int b) {

        // if there exists a path from node a to node b, return true 

            // implement indirectEdgeTest algorithm here.

            return false;
    }
}

Answer 1

أنا أقدر Meriton لإجابته ، لكنني قمت بترميز الفكرة في فصول Java العاملة واختبار الوحدة ، لذلك أقوم بتوفير إجابة منفصلة هنا في حال كان أي شخص يبحث عن رمز قابل لإعادة الاستخدام.

شكرا ميريتون. أوافق على أنه من المهم التمييز بين اختبار الحافة المباشرة واختبار المسار ، وأن هناك تطبيقات مختلفة من الرسوم البيانية المناسبة لنوع معين من الاختبارات. في حالة اختبار المسار ، يبدو أن قوائم المجاورة أكثر كفاءة من تمثيل مصفوفة مجاور.

ربما لا يكون الكود أدناه فعالًا كما يمكن أن يكون ، ولكنه في الوقت الحالي يحل مشكلتي. إذا كان لدى أي شخص تحسينات لاقتراحه ، فلا تتردد.

للترجمة: Javac Graph.java

للتنفيذ: Java GraphTest

class Graph {

    private java.util.ArrayList<Node> nodeList;
    private int numberOfNodes;

    public Graph(int size) {
        nodeList = new java.util.ArrayList<Node>(size + 1);
        numberOfNodes = size;

        for (int i = 0; i <= numberOfNodes; i++) {
            nodeList.add(new Node());
        }
    }

    public void addEdge(int a, int b) {
        if (a >= 1 && a <= numberOfNodes) {
            if (b >= 1 && b <= numberOfNodes) {
                nodeList.get(a).addNeighbour(nodeList.get(b));
                nodeList.get(b).addNeighbour(nodeList.get(a));
            }
         }
    }

    public void walk(Node origin, java.util.Set<Node> visited) {
        for (Node n : origin.getNeighbours()) {
            if (!visited.contains(n)) {
                visited.add(n);
                walk(n, visited);
            }
        }
    }

    public boolean hasPath(Node origin, Node target) {
        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        walk(origin, reachables);
        return reachables.contains(target);
    }

    public boolean hasPath(int a, int b) {

        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        Node origin = nodeList.get(a);
        Node target = nodeList.get(b);
        walk(origin, reachables);
        return reachables.contains(target);       
    }
}

class Node {

    private java.util.Set<Node> neighbours;

    public Node() {
        neighbours = new java.util.HashSet<Node>();
    }

    public void addNeighbour(Node n) {
        neighbours.add(n);
    }

    public java.util.Set<Node> getNeighbours() {
        return neighbours;
    }
}

class GraphTest {

    private static Graph g;

    public static void main(String[] args) {

        g = new Graph(6);

        g.addEdge(1,5);
        g.addEdge(4,1);
        g.addEdge(4,3);
        g.addEdge(3,6);

        printTest(1, 2);
        printTest(1, 4); 
        printTest(6, 1);   
    }

    public static void printTest(int a, int b) {

        System.out.print("Are nodes " + a + " and " + b + " connected?");
        if (g.hasPath(a, b)) {
            System.out.println(" YES.");
        } else {
            System.out.println(" NO.");
        }
    }
}

Answer 2

ERM ، هذا النهج يبدو غير فعال بشكل فظيع. مذا عن هذه:

void walk(Node orgin, Set<Node> visited) {
    for (Node n : origin.neighbours) {
        if (!visited.contains(n)) {
            visited.add(n);
            walk(n, visited);
        }
    }
}


boolean hasPath(Node origin, Node target) {
    Set<Node> reachables = new HashSet<Node>();
    walk(origin, reachables);
    return reachables.contains(target);
}

أيضًا ، يعد استخدام مصفوفة متاخمة للاستخدام المشكوك فيه لتجاوز الرسم البياني ، حيث لا يمكنك التكرار بكفاءة على جيران العقدة في رسم بياني متناثر.

إذا تم استخدام هذه الطريقة بشكل متكرر ، ونادراً ما يتغير الرسم البياني المناطق المتصلة في المقدمة ، وتخزين لكل عقدة المنطقة التي تنتمي إليها. ثم ، يتم توصيل العقدتين إذا كانت تنتمي إلى نفس المنطقة.

تحرير: للتوضيح حول أفضل طريقة تمثيل الرسم البياني. لاختبار الحافة المباشرة ، يفضل مصفوفة مجاورة. لاختبار المسار ، يكون التحلل في المناطق. هذا الأخير ليس تافهاً للحفاظ على التيار مع تغير الرسم البياني ، ولكن قد تكون هناك خوارزميات لهذا في الأدب. بدلاً من ذلك ، تكون قوائم المجاورة قابلة للخدمة لتجاوز الرسم البياني وبالتالي اختبار المسار ، لكنها تظل أقل كفاءة من تسجيل التحلل مباشرة إلى المناطق المتصلة. يمكنك أيضًا استخدام مجموعات المجاورة لدمج تكرار الجوار الأكثر كفاءة في الرسوم البيانية المتناثرة مع اختبار حافة الوقت الثابت.

ضع في اعتبارك أنه يمكنك أيضًا تخزين المعلومات بشكل متكرر ، والحفاظ على كل نوع من أنواع الاستعلام ، وهي بنية بيانات منفصلة مخصصة.

Answer 3

سيعمل الحل الخاص بك ، ولكن الحل الأفضل هو بناء شجرة تمتد من العقدة "A". وبهذه الطريقة ، سيكون لديك في النهاية شجرة واحدة فقط يجب مراعاتها ، بدلاً من عمليات الرسم البيانية المتعددة التي تفتقد حواف معينة فقط.

بمجرد الحصول على فكرة, ، كيف تنفذ الأمر متروك لك. على افتراض أنه يمكنك تنفيذ الخوارزمية بطريقة معقولة ، يجب أن يكون لديك شجرة واحدة فقط للبحث عن الاتصال ، والتي من شأنها تسريع الأمور بشكل كبير.