การเพิ่มรายการโหนดลงใน Java Graph ด้วย for loop

ฉันกำลังพยายามเพิ่มวัตถุที่สร้างขึ้นใหม่ลงในตารางและกราฟ โดยเฉพาะวิธีการเพิ่มโหนดลงในกราฟอย่างมีประสิทธิภาพด้วย for loop ตารางเหล่านี้ได้รับการตั้งค่าเป็นอาร์เรย์คู่เพื่ออัปเดตมุมมองเริ่มต้น (ตารางวัตถุเป็นแบบจำลองและอัปเดตมุมมองผ่านการพุช) ฉันยังตั้งค่า HashMap โดยใช้รายการใน i และ j ภายใน for loops เพื่อกำหนดคีย์ของวัตถุ อย่างไรก็ตาม เพื่อตั้งค่ากราฟเพื่อคำนวณเส้นทางที่สั้นที่สุดจากโหนดหนึ่งไปอีกโหนดหนึ่งในภายหลัง ฉันจำเป็นต้องเพิ่มโหนดเหล่านี้ลงในกราฟ ฉันต้องการใช้อัลกอริทึมของ Djikstra เพื่อคำนวณเส้นทางที่สั้นที่สุด ฉันสามารถสร้างคำสั่งแบบมีเงื่อนไขเพื่อกำหนดว่าโหนดมุมและโหนดขอบคืออะไรในตารางและกำหนดว่ารายการใดที่จะมีขอบแบบสองทิศทาง แต่ดูเหมือนว่าจะเป็น 'การตัดยาว' มีวิธีใดในการเพิ่มโหนดลงในกราฟด้วยขนาดเมทริกซ์ที่กำหนดไว้ล่วงหน้า เช่น 20 X 20 ซึ่งคล้ายกับอาร์เรย์คู่หรือไม่

ด้านล่างนี้เป็นโค้ดตัวสร้างเกี่ยวกับวิธีที่ฉันสร้างสองรายการแรก (การสร้างอาร์เรย์คู่และ HashMap):

// **Constructor
// Construct a new Grid object. Sets up a HashMap of square object in order efficiently to get 
// and add Square objects later.
public ObjectGrid(Integer width, Integer height) 
{
    // View
    gui = new GUI();        // Instantiate GUI
    boardView = new BoardView(width,height);        // Instantiate BoardView

    // Initialize Gui, set time and add simulation event listener to model (ObjectGrid)
    gui.initGUI(BoardView);
    gui.addSimulationEventListener(this);

    // Initialize turnInSteps variable count to 0
    turnInSteps = 0;

    // Initialize numberOfDays variable count to 0
    numberOfDays = 1;

    // Instantiate HashMap
    objectHashMap = new HashMap();

    // Declare new object grid using double array of type objects.
    // Size determined by parameter Integer values in constructor
    myObjectGrid = new ObjectType[width][height];

    // Instantiate Graph object
    Graph graph = new ListGraph();

    // For loop sets up the initial grid with ObejctType using a double array. After
    // the completion of this loop, the grid will have XXX objects in the grid
    // each with a reference to an object. Objects are also added 
    // to HashMap using coordinates as keys and square objects as values.
    for(int i = 0; i < width; i++) 
    {  
        // Iterate through rows
        for(int j = 0; j < height; j++) 
        {  
            // Iterate through columns
            myObjectGrid[i][j] = new ObjectType();  // Instantiate a new Square at each row/column using default constructor
            gridView.addObjectView(myObjectGrid[i][j].getObjectView(), i, j);  // Add object view to each row/column placement
            String hashMapKey = (i + ", " + j); // Use values from i and j as Key for objects HashMap
            myObjectGrid[i][j].setID(hashMapKey);  // Add ID's for each ObjectView to display in object using values from i and j
            objectHashMap.add(hashMapKey, myObjectGrid[i][j]);  // Add object to HashMap using string value of coordinates as key
            listGraph.add(myObjectGrid[i][j]);

            // Pseudo code
            if (i != (width-height) && (j != height) etc) 
            {
                listGraph.addBidirectionalEdge(mySquareGrid[i][j], (mySquareGrid[i][j+1]), 1);
                listGraph.addBidirectionalEdge(mySquareGrid[i][j], (mySquareGrid[i+1][j]), 1);
                listGraph.addBidirectionalEdge(mySquareGrid[i][j], (mySquareGrid[i+1][j+1]), 1);
            }
        }
    }
}

person gwerner    schedule 24.12.2012    source แหล่งที่มา
comment
และคำถามของคุณคืออะไร?   -  person vishal_aim    schedule 24.12.2012
comment
ขออภัยที่ไม่เจาะจง (โพสต์แรกบนเว็บไซต์นี้) คำถามคือจะเพิ่มวัตถุเป็นโหนดลงในกราฟได้อย่างไรโดยใช้ for loop หาก for loop ไม่ใช่วิธีที่เหมาะสม คำแนะนำไปยังวิธีอื่นอาจช่วยได้ ด้วยการทดสอบหน่วยที่ฉันทำ จุดยอดในกราฟคืนค่าเป็นโมฆะ   -  person gwerner    schedule 24.12.2012
comment
เป็นการดีกว่าที่จะอัปเดตโพสต์ของคุณด้วยคำถามนี้   -  person tcb    schedule 24.12.2012
comment
สวัสดี ฉันได้แก้ไขคำถามตามคำแนะนำของ tcb   -  person gwerner    schedule 24.12.2012


คำตอบ (1)


ด้วยการทดสอบหน่วยที่ฉันทำ จุดยอดในกราฟคืนค่าเป็นโมฆะ

เหตุผลคือบรรทัดต่อไปนี้:

listGraph.addBidirectionalEdge(mySquareGrid[i][j], (mySquareGrid[i][j+1]), 1);
listGraph.addBidirectionalEdge(mySquareGrid[i][j], (mySquareGrid[i+1][j]), 1);
listGraph.addBidirectionalEdge(mySquareGrid[i][j], (mySquareGrid[i+1][j+1]), 1);

คุณอยู่ระหว่างการเริ่มต้น mySquareGrid และสร้างขอบด้วยโหนดจากอนาคต โหนดเหล่านี้ที่มี j+1 และ i+1 เป็นโมฆะในขณะนี้

ลองใช้วิธีแก้ปัญหาที่ง่ายที่สุด - หลังจากการกำหนดค่าเริ่มต้นของกริด ให้ทำการวนแบบเดียวกันผ่านกริดและสร้างขอบของกราฟ

นอกจากนี้คุณยังสามารถลองเปลี่ยนเป็นสิ่งต่อไปนี้:

listGraph.addBidirectionalEdge(mySquareGrid[i][j-1], (mySquareGrid[i][j]), 1);
listGraph.addBidirectionalEdge(mySquareGrid[i-1][j], (mySquareGrid[i][j]), 1);
listGraph.addBidirectionalEdge(mySquareGrid[i-1][j-1], (mySquareGrid[i][j]), 1);
person tcb    schedule 24.12.2012
comment
สมมติว่าจุดยอดคือ 4,4 (x และ y ตามลำดับ): [i][j-1] 4,3 ติดกับ 4,4 (ทิศเหนือ) [i-1][j] 3,4 ติดกับ 4,4 (ตะวันตก) [i-1][j-1] 3,3 ติดกับ 4,4 (ตะวันตกเฉียงเหนือ) อย่างไรก็ตาม [i-1][j-1] ถึง [i][j+1] คือ 3,3 ถึง 4,5 ซึ่งไม่อยู่ติดกัน อนุญาตให้มีขอบระหว่างโหนดที่ไม่อยู่ติดกันหรือไม่ - person gwerner; 24.12.2012
comment
ฉันเพิ่มคำสั่งแบบมีเงื่อนไขเพื่อให้สามารถระบุวัตถุมุมและวัตถุเส้นขอบ จากนั้นกำหนดว่าวัตถุใดที่อยู่ติดกันโดยใช้คำสั่งสาขาแบบมีเงื่อนไข: 'for (int i=0; i‹width; i++) { for (int j=0; j ‹ความสูง; j++) { myHashMap.get(i+, j); ถ้า (i==0; j==0) { int myRandom = Randomno.nextInt(3); { if (myRandom == 0) { // รหัสสำหรับย้ายวัตถุไปยังช่องสี่เหลี่ยมที่อยู่ติดกัน ตะเข็บนี้เหมือนเป็นการตัดยาวจริงๆ คุณคงคิดว่าจะมีวิธีที่ง่ายกว่าในการดำเนินการนี้หรือ API ที่มีฟังก์ชันนี้อยู่แล้ว - person gwerner; 25.12.2012
comment
มันขึ้นอยู่กับอัลกอริธึมที่คุณเลือกจริงๆ ลองเข้าไปดูที่ myObjectGrid มันให้ข้อมูลเกี่ยวกับโหนดที่อยู่ติดกันหรือไม่? หากใช่ คุณสามารถสร้างอัลกอริทึมการค้นหาโดยใช้ตารางนี้เท่านั้น คุณไม่จำเป็นต้องสร้างกราฟ - person tcb; 25.12.2012