技術(shù)領(lǐng)域

本發(fā)明涉及可視化編程領(lǐng)域圖形化程序的拓?fù)渑判颉?/p>

背景技術(shù)

首先介紹拓?fù)渑判蛑械膸讉€(gè)基本概念，可同時(shí)結(jié)合圖1a和圖1b所示：

拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉Ｔ诖a生成中指根據(jù)符號(hào)的連接關(guān)系，決定符號(hào)的調(diào)用順序。

偏序：若集合X上的關(guān)系R是自反的、反對(duì)稱的和傳遞的，則稱R是集合X上的偏序關(guān)系。

全序：設(shè)R是集合X上的偏序，如果對(duì)每個(gè)x,y∈X必有xR?y或者yRx，則稱R是集合X上的全序關(guān)系。

直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員可比較。

AOV-網(wǎng)：圖中頂點(diǎn)表示程序符號(hào)塊（活動(dòng)），有向邊（弧）表示先決條件，如符號(hào)a是b的先決條件，則圖中有弧<a,b>。這種用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity?On?Vertex?NetWork)，簡(jiǎn)稱AOV-網(wǎng)。在網(wǎng)中，若從頂點(diǎn)a到頂點(diǎn)b有一條有向路徑,則a是b的前驅(qū)，b是a的后繼。若<a,b>是網(wǎng)中一條弧，則a是b的直接前驅(qū)，b是a的直接后繼。

可視化編程是一種面向?qū)ο蟮膱D形化軟件開發(fā)方法，為了實(shí)現(xiàn)應(yīng)用功能，用各種的編程符號(hào)搭建程序模型和配置數(shù)據(jù)流，用原理圖表示程序語(yǔ)言。圖形化程序的符號(hào)執(zhí)行順序是代碼生成的關(guān)鍵技術(shù)，已經(jīng)公開的排序算法有：全部人工指定順序、或者完全根據(jù)位置坐標(biāo)來(lái)排序。人工指定順序存在的問(wèn)題是當(dāng)可視化頁(yè)面數(shù)量很多時(shí)，設(shè)置維護(hù)的工作量很大，例如在編程中間插入一個(gè)符號(hào)時(shí)，需要手工調(diào)整后續(xù)符號(hào)的排序值。按照位置坐標(biāo)的方法，是把可視化頁(yè)面x坐標(biāo)劃分成幾個(gè)區(qū)間，在單個(gè)區(qū)間內(nèi)按照從上到下的順序輸出，這種方法的問(wèn)題是沒(méi)有考慮到兩個(gè)區(qū)間內(nèi)符號(hào)的數(shù)據(jù)流依賴關(guān)系，而且同一個(gè)區(qū)間內(nèi)只能畫一排垂直符號(hào)，不能繪制平行符號(hào)，單頁(yè)程序的符號(hào)數(shù)量有限，單個(gè)功能往往需要拆分為多個(gè)頁(yè)面實(shí)現(xiàn)。

在AOV網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，這意味著某項(xiàng)活動(dòng)應(yīng)以自己為先決條件，而對(duì)程序的數(shù)據(jù)流圖來(lái)說(shuō)，則表明存在一個(gè)死循環(huán)。目前還缺乏針對(duì)可視化閉環(huán)圖形程序的有效合理的智能解決方法，為此設(shè)計(jì)了一個(gè)破環(huán)符號(hào)，由程序編輯人員指定破環(huán)點(diǎn)。

基于上述分析，本發(fā)明人針對(duì)現(xiàn)有圖形程序的拓?fù)渑判蚍椒ǖ牟蛔阒庍M(jìn)行深入研究，本案由此產(chǎn)生。

發(fā)明內(nèi)容

本發(fā)明的目的，在于提供一種可視化圖形程序拓?fù)渑判蚍椒ǎ淇蓽p少人工干預(yù)過(guò)程，解決閉環(huán)死鎖依賴，以數(shù)據(jù)流依賴關(guān)系形成執(zhí)行分支，提高程序運(yùn)行效率。

為了達(dá)成上述目的，本發(fā)明的解決方案是：

一種可視化圖形程序拓?fù)渑判蚍椒ǎㄈ缦氯糠郑?/p>

第一部分，先將符號(hào)按照先橫向x坐標(biāo)進(jìn)行升序排列，x坐標(biāo)相同的按縱向y坐標(biāo)升序排列，即按照從上到下、從左到右的Z字型掃描順序，形成初步順序，按照坐標(biāo)排序符合可視化頁(yè)面程序的機(jī)器視覺；按照位置坐標(biāo)進(jìn)行初次排序，可以解決當(dāng)兩個(gè)符號(hào)都同時(shí)滿足出棧條件時(shí)（0輸入點(diǎn)或所有輸入點(diǎn)都已知），那個(gè)符號(hào)優(yōu)先自動(dòng)出棧的問(wèn)題。由于可視化圖形程序的符號(hào)存儲(chǔ)是按照先繪制先存儲(chǔ)的原則，按照位置坐標(biāo)的排序可以解決符號(hào)先繪制、后刪除、再繪制時(shí)存儲(chǔ)順序變化導(dǎo)致排序結(jié)果不同的問(wèn)題；

第二部分，設(shè)計(jì)閉環(huán)圖形網(wǎng)絡(luò)中的破環(huán)符號(hào)BreakLoop，把與閉環(huán)符號(hào)輸出點(diǎn)相連接的后繼符號(hào)的輸入點(diǎn)置為已知，可去除死鎖依賴；針對(duì)存在反饋閉環(huán)的圖形程序，設(shè)計(jì)了破環(huán)符號(hào)，該符號(hào)為單輸入單輸出，變量類型可設(shè)置，輸出值等于上一個(gè)周期的輸入點(diǎn)值，把與破環(huán)符號(hào)輸出點(diǎn)相連接的后繼符號(hào)的輸入點(diǎn)自動(dòng)置為已知狀態(tài)，從而去除死鎖依賴，所有的破環(huán)符號(hào)的代碼執(zhí)行放在最后，提供了一種簡(jiǎn)單直觀的圖形化設(shè)置破環(huán)的方法，提高了靈活性；

第三部分，按照深度優(yōu)先和數(shù)據(jù)流依賴關(guān)系進(jìn)行拓?fù)渑判颍x拓?fù)渑判虺鰲５囊?guī)則，當(dāng)一個(gè)符號(hào)沒(méi)有輸入點(diǎn)或者所有輸入點(diǎn)都處于已知狀態(tài)時(shí)，該符號(hào)可以置為已知狀態(tài)優(yōu)先出棧，并置和該符號(hào)輸出點(diǎn)相連接的后繼符號(hào)的輸入點(diǎn)已知；并且根據(jù)輸入輸出點(diǎn)相連接的數(shù)據(jù)流依賴關(guān)系，優(yōu)先判斷緊隨該符號(hào)的后繼符號(hào)狀態(tài)是否已知，把有數(shù)據(jù)流依賴關(guān)系的符號(hào)按分支遍歷排序，這樣形成的運(yùn)行代碼效率高，提高了CPU的扇入扇出命中率；根據(jù)輸入輸出相連接的數(shù)據(jù)流依賴關(guān)系，形成有向無(wú)環(huán)圖，根據(jù)依賴關(guān)系形成符號(hào)的前驅(qū)后繼分支，然后按照深度優(yōu)先的遍歷原則，形成符號(hào)的執(zhí)行順序。