Graph Navigation

Many applications must navigate the symbols and links on the canvas as a directed or undirected graph. A graph is a set of connected edges and nodes, where an edge defines a path between two nodes. The edges that are connected to a node are incident to the node. The degree of a node is defined as the number of edges incident to the node. Each node in a directed graph has 0 to N edges entering it and 0 to N edges leaving it. In an undirected graph, no distinction is made between edges leaving a node and edges entering a node. Nodes that share an edge are connected by the edge and are said to be adjacent. Two nodes are connected if there is a path of edges and nodes between them.

Figure 65 – Graph navigation example.

In the figure shown above, the following node pairs are adjacent: (A,B), (A,C), and (B,D). We say that Node A is adjacent to Node B because the directed edge <A,B> leads from A to B. Conversely, Node B is adjacent from Node A because the directed edge <A,B> goes from A to B. Node D is connected from Node A because D is reachable from A.

Graph Navigation Interfaces

Objective Views defines a set of interfaces that allow applications to navigate the components on a canvas as a collection of nodes and edges. These interfaces are mixed into existing concrete classes in the library to implement the graph navigation capabilities. The default implementation treats the model as a graph, symbols as nodes, and links as edges. However, these interfaces can be implemented by any component subclass, so it is possible to create entirely new types of components or symbols that behave as either nodes or edges.

Some of the graph navigation functions use component IDs to retrieve nodes or edges in the graph. The component IDs used for graph navigation are the same ones used to uniquely identify components on the canvas. Component IDs are generated by the CODModel object and are unique within a model.

The graph navigation functions return interface pointers for edges and nodes. These functions always increment the reference count on the associated object using AddRef() before returning the interface pointer to the caller. The caller must decrement the reference count using Release() when the interface pointer is no longer needed.

Each graph navigation interface is assigned a GUID, so classes that support the IODObject interface can be interrogated for a specific interface using QueryInterface().

Node and Edge Collections

Graph navigation methods that return multiple edges or nodes use the IODEdgeCollection and IODNodeCollection interfaces. These minimal collection interfaces provide a type-safe way for the graph navigation routines to add objects to a collection and determine if an object belongs to a collection. Any type of collection that supports these interfaces can be used with the graph navigation interfaces. Array and map implementations for these interfaces are provided with the library, but developers can easily add their own collection types by mixing these interfaces into their own collection classes.

IODGraph Interface

The IODGraph interface is implemented by the CODModel class. It contains methods for retrieving nodes and edges in the graph using unique component identifiers. The GetNode() method takes an CODComponentId and returns a pointer to an IODNode interface. The GetEdge() method is identical to GetNode(), except that it returns a pointer to an IODEdge interface.

IODNode Interface

The IODNode interface is implemented by the CODSymbolComponent class. It contains methods for retrieving incident edges and adjacent nodes. There are functions to support both directed and undirected node and edge traversal. Directed edge functions have names that indicate whether they look for edges entering or leaving the node. Directed node functions have names that indicate whether to look for nodes that are adjacent to or adjacent from the given node. Undirected traversal functions have names that do not indicate a direction.

The following example takes the currently selected node and finds all of the nodes adjacent from the node. Example 4 is an example of directed node traversal. It finds nodes that are pointed to by the currently selected node.

Example 4 – Directed node traversal

void CMyController::OnOdNodesAdjacentFrom()

{

CODComponent* pComp = NULL;

if (GetSelection()->GetSize() == 1)

pComp = GetSelection()->GetAt(0);

if (pComp != NULL)

{

IODNode* pINode;

pINode = guid_cast<IODNode*>(pComp);

if(pINode != NULL)

{

pINode->GetNodesAdjacentFrom(&m_animateNodes);

m_nAnimateCounter = 10;

SetTimer(ANIMATE_TIMER, 50, NULL);

pINode->Release();

}

}

IODEdge Interface

The IODEdge interface is implemented by the CODLinkComponent class. It contains methods that return the nodes that are adjacent to the link. Each directed edge has a head and a tail node. This interface has a GetHeadNode() to retrieve the head node and a GetTailNode() method to retrieve the tail node. The function GetNodesAdjacent() returns both adjacent nodes without regard to direction. This interface also has a GetWeight() virtual method that can be overridden by developers for implementing weighted edges. Weighted edges typically represent a distance or some other application specific quantity, and can be used to implement algorithms such as shortest path.