Customize Traversal Class?

[Suli Yang]

Hi,

Seems like Dex offers an interface for the user to implement their own Traversal class. I am wondering if you could provide any sample Traversal class in implementation (in C++?)

In particular, Since the only graph navigation primitive Dex offers is Neighbors, I wonder how I could implement a DFS style traversal? 

(Yes, I am aware there is a TraversalDFS class available. But I need a slightly different version, where I might need to backoff from a path early).

Thanks. 

[c3po.ac]

Hi,

The traversal classes we provide are normal traversal implementations generic enough for the most usual usage. There is a common traversal class to unify the interface of all traversals as much as possible. You can use that interface if it suits your needs.

Neighbors is not the only graph navigation primitive Dex offers, I guess that, for your case, it would be better to look at the Explode.

If you are developing a traversal like the one from the wikipedia:

1  procedure DFS-iterative(G,v):
2      label v as discovered
3      let S be a stack
4      S.push(v)
5      while S is not empty        
6            t ← S.top 
7            if t is what we're looking for: 
8                return t
9            for all edges e in G.adjacentEdges(t) do
10               if edge e is already labelled 
11                   continue with the next edge
12               w ← G.adjacentVertex(t,e)
13               if vertex w is not discovered and not explored
14                   label e as tree-edge
15                   label w as discovered
16                   S.push(w)
17                   continue at 5
18               else if vertex w is discovered
19                   label e as back-edge
20               else
21                   // vertex w is explored
22                   label e as forward- or cross-edge
23           label t as explored
24           S.pop()

You can get the edges adjacent to a node by using the Explode operation. You can filter by edge type and edge direction too.
The other node connected by the same edge can be retrieved quickly just using the GetEdgePeer method or getting the edge information (GetEdgeData) and checking it's head and tail nodes.

You could use Objects collections to keep the discovered and the explored nodes. Use the Session::NewObjects method to create temporary Objects.  The same could be done for the tree-edge, back-edge and forward-edges.

Another option to label the edges visited could be using temporary attributes. You can create a temporary attribute using the NewSessionAttribute method. Or you could use persistent attributes if you plan on keeping that data.

If you want to use the same attribute for several node/edge types, you could create it as a global attribute using dex::gdb::Type::GlobalType in the NewSessionAttribute method.

Best regards.


El divendres 12 de juliol de 2013 4:22:21 UTC+2, Suli Yang va escriure: