02/28
19:21
IT python

拓扑排序——移植的顺序

最近想把PTAMM项目移植到opencv,PTAMM属于一个比较小的系统,但是在移植的时候遇到的麻烦不少。其他问题暂不讨论,在这篇文章,我们来探讨如何移植一个工程。
首先,你可能不熟悉这个工程,以至于它的各个组件具体是干什么的不是很了解。
然后,由于这个工程还是具有一定规模,各个组件有一定的耦合。
最后,当你先随机由一个文件入手,你会发现他依赖了很多本项目实现的其他文件,所以你不得不又跑去移植其他文件。
最最后,你发现你被整个项目整得头晕脑胀。

没错,写这篇文章的目的就是为了来解决这个问题! :)

其实原理很简单,每个文件会#include它的上一级文件,这样例如A include B,那么我们将它们描述为B->A的无环图。最后当所有的文件都形成这样的规则,我们将形成一大张有向无环图。
那么我们对整张图进行拓扑排序,就能得到我们的移植顺序了。 :mrgreen:

我使用的是深度优先搜索递归,这样原理上看上去比较简单。
这个是伪代码

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no outgoing edges
for each node n in S do
    visit(n) 
function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edgefrom m to ndo
            visit(m)
        add n to L

这个是python实现的代码

import os,sys
import re
import Queue
pattern = re.compile(r'#include(.)*("|<)(.+)(\.h)?("|>)')

### get the directory of project files
def walk_dir(dir,topdown=True):
    filenames = []
    for root,dirs,files in os.walk(dir,topdown):
        for name in files:
            split_name = os.path.splitext(name)
            # you can modify as whatever suffix you want
            if split_name[1] == '.h' or split_name[1] == '.cc':
                #print name
                filenames.append(name)
    return filenames

### fetch the #include line and filename
def read_file(fname):
    ff = open(fname)
    res_list = []
    for line in ff:
        #print line
        match = pattern.match(line)
        if match:
            #print line
            #print match.group()
            res = pattern.findall(line)
            #print res[0][2]
            res_list.append(res[0][2])
    return res_list

### define a node type
class GraphNode:
    def __init__(self,name,indegree=0,outdegree=0):
        self.name = name
        self.indegree = indegree
        self.visit = False
        self.outdegree = outdegree
    def print_node(self):
        print self.name,self.indegree,self.outdegree
        
### Graph used to toposort
class Graph:
    def __init__(self):
        self.nodes = {}
        self.graph = [[],[]]
        self.L = []
        self.S = Queue.Queue()
        
    def insertNode(self,node,innodes):
        try:
            self.nodes[node].indegree += len(innodes)
        except:
            tmpnode = GraphNode(node,len(innodes))
            self.nodes[node] = tmpnode
            
        for eachnode in innodes:
            self.graph[0].append(eachnode)
            self.graph[1].append(node)
            
        for eachnode in innodes:
            self.insertNode(eachnode,[])        
            

    def init_nodes_S(self):
        for n in self.graph[0]:
            self.nodes[n].outdegree += 1
        for eachnode in self.nodes.values():
            if eachnode.outdegree == 0:
                self.S.put(eachnode.name)
        
    
    def visit_node(self,node):
        if not self.nodes[node].visit:
            self.nodes[node].visit = True
            for i in range(len(self.graph[1])):
                if self.graph[1][i] == node:
                    self.visit_node(self.graph[0][i])
            self.L.append(node)
            #print node
            
            
    def topoSort_DFS(self):            
        self.init_nodes_S()
        while not self.S.empty():
            x = self.S.get()
            self.visit_node(x)
        return self.L
          
if __name__ == "__main__":
    filenames = walk_dir("src/")
    graph = Graph()
    for fname in filenames:
        #print fname,":"
        innodes = read_file("src/"+fname)
        graph.insertNode(fname,innodes)
        
    L = graph.topoSort_DFS()
    
    for ss in L:
        print ss

这个是运行结果

TooN/TooN.h
cvd/image.h
cvd/byte.h
CalibCornerPatch.h
GL/gl.h
GL/glext.h
OpenGL/gl.h
OpenGL/glext.h
GL/glew.h
cvd/gl_helpers.h
OpenGL.h
TooN/helpers.h
cvd/vector_image_ref.h
cvd/vision.h
cvd/utility.h
cvd/convolution.h
cvd/image_interpolate.h
TooN/Cholesky.h
cassert
SmallMatrixOpts.h
CalibCornerPatch.cc
cvd/rgb.h
VideoSource.h
videoInput.h
gvars3/instances.h
windows.h
VideoSource_Win32_LibVideoInput.cc
cvd/glwindow.h
GLWindow2.h
vector
map
gvars3/gvars3.h
GLWindowMenu.h
stdlib.h
gvars3/GStringUtil.h
X11/keysym.h
GLWindow2.cc
cvd/thread.h
TooN/se3.h
Map.h
set
KeyFrame.h
cmath
ATANCamera.h
queue
MapMaker.h
MiniPatch.h
TooN/se2.h
SmallBlurryImage.h
Relocaliser.h
sstream
list
Tracker.h
algorithm
MEstimator.h
ShiTomasi.h
cvd/image_ref.h
cvd/timer.h
MapPoint.h
LevelHelpers.h
PatchFinder.h
TrackerData.h
cvd/fast_corner.h
TooN/wls.h
fstream
fcntl.h
Tracker.cc
CalibImage.h
CameraCalibrator.h
TooN/SVD.h
CameraCalibrator.cc
GLWindowMenu.cc
iostream
System.h
main.cc
MapViewer.h
iomanip
MapViewer.cc
EyeGame.h
ARDriver.h
ARDriver.cc
SmallBlurryImage.cc
KeyFrame.cc
Windows.h
1394Camera.h
VideoSource_Win32_CMU1394.cc
Relocaliser.cc
MiniPatch.cc
EyeGame.cc
Bundle.h
HomographyInit.h
TooN/SymEigen.h
MapMaker.cc
tmmintrin.h
PatchFinder.cc
utility
HomographyInit.cc
ATANCamera.cc
System.cc
math.h
ShiTomasi.cc
Bundle.cc
Map.cc
MapPoint.cc
CalibImage.cc

最后附上附件
附件

发表评论