OpenAnalysis::DGraph
DGraph is the base class for a general directed graph (DGraph) that is in turn derived from BaseGraph. Algorithms that operate upon abstract directed graphs should, normally, use only this base DGraph class for maximum portability.
Synopsis
Base Classes
Name |
Description |
BaseGraph is the abstract base class (the "interface") for a general graph. It defines graph properties common to directed and undirected graphs. It leaves out some loose ends in the interface: 1. A node has no notion of incident edges or neighboring nodes because the number of kinds of incident edges or neighboring nodes is dependent upon the graph being directed or undirected. 2. For the same reason, the method delete(node) cannot delete any incident edges. Therefore the directed or undirected graph must override it with a more complete version. Similarly, the method delete(edge) cannot delete the edge from the list(s) of the nodes involved. 3. In an analogous manner, the method add(edge) must be overridden with a more complete version that adds the edge into the records of the nodes involved, if needed. |
Types
Name |
Description |
The BFSIterator here is just an extension of BaseGraph::DFSIterator to allow proper casting. |
|
The BiDirNodesIterator is just an extension of BaseGraph::BiDirNodesIterator to provide access to DGraph nodes. |
|
The DFSIterator here is just an extension of BaseGraph::DFSIterator to allow proper casting. |
|
The EdgesIterator is just and extension of BaseGraph::EdgesIterator to provide access to DGraph edges. |
|
Iterator to enumerate all the incoming edges into a node. |
|
An node in an undirected graph has a list of neighboring nodes and a list of incident edges. |
|
The NodesIterator is just and extension of BaseGraph::NodesIterator to provide access to DGraph nodes. |
|
Iterator to enumerate all the outgoing edges from a node. |
|
Iterator to enumerate all the sink nodes. |
|
Iterator to enumerate all the source nodes. |
Member Functions
Private Member Functions
Name |
|
|
Friends
Name |
Description |
The BFSIterator here is just an extension of BaseGraph::DFSIterator to allow proper casting. |
|
The DFSIterator here is just an extension of BaseGraph::DFSIterator to allow proper casting. |
Derived Classes
Name |
Description |
CFG is a DGraph (directed graph) with enhanced nodes and edges. Each node in the CFG points to a list of statements that together represent a basic block. The entire program would be represented by a set of CFGs, one for each subroutine, and one for the main program. |
Description
No extra restrictions are placed on nodes and edges in addition to those imposed by BaseGraph. This means that self‐edges, and multiple edges between two nodes, are allowed.
A directed graph, DGraph, extends BaseGraph by adding DFS and BFS iterators, as well as iterators to enumerate source nodes, sink nodes, incoming edges, and outgoing edges for a node.
NOTE ON friend CLASSES: Many classes (especially DGraph, DGraph::Node, and DGraph::Edge) have many friend classes. This is not a kludge. It is simulating package‐style visibility. We want a limited public interface to Node and Edge and yet give more permissions to methods within the Graph class.
Created with MrDocs