Using the Grapher Class

The Grapher class is the main data structure and class for managing graphs in the software. It provides a generic interface to Graphs - defined as a structure with vertices related to each other by edges. The generic interface allows any data stored to be stored as either nodes or edges.

Nodes are stored as an adjacency list but there are also maps for fast access to the associated data elements so that data access can be O(1).

To construct a new Grapher class you need to provide it three template parameters: the node data type, the edge data type and a comparator function for nodes. Therefore the data type looks like the following: Grapher.

To add a node to the graph use the add_node() function and to add an edge the add_edge(). The add_node function takes as an argument an object of NodeType. NodeType can be a pointer, a reference or an object (in which case the copy constructor will be called and the object copy stored in the Graph). When a node is added to the Graph it is assigned an internal index (of Grapher::index_type_t type). This internal index is used to access the information about the Graph from the adjacency lists.

Generally, however, it is sufficient to use the object of NodeType to access any given node in the Graph. The NodeComparator is used to ensure the uniqueness of elements in the Graph.

Builders

Builders are used as factories to create specific graphs from an inputted Linkler object. Given a Linkler object they output that Linkler object in the representation of a Grapher object. At present we have had support for two graphs:

Graphs between Modules, that is node_type is Module* and edge type Dependency<Module,Module>*. This builder is called ModuleGraphBuilder.
Graphs between SWUs, that is node_type is SWU* and edge type is Dependency<SWU, SWU>*. This builder is called SWUGraphBuilder.

In both cases pointers are stored to the data stored in the Linkler. The assumption is that the Linkler data remains static and is not freed throughout the usage of the Grapher object (at least not until the Grapher object has been removed).

Other types of Graphers can naturally be constructed if a need should emerge.

To build a graph, you first need a Linkler, this Linkler is then passed to the Builder and using the methods of the builder you can select which nodes are built:

XMLParser p;
Linkler* l = p.parse_xml("my_linkgen.xml"); 
SWUGraphBuilder swub(l);
swub.graph_all(); //  graphs all SWUs as nodes
swub.graph_all_dependencies(); // graphs all dependencies as actions
...
swub.graph_single("SWUXXYY"); // graph SWUXXYY as a node
swub.graph_dependencies("SWUXXYY"); // graph all dependencies of SWUXXYY as nodes and add edges from these to SWUXXYY

int nodes = swub.grapher().num_nodes(); // fetch number of nodes in the grapher

Layout algorithms

Layout algorithms are an important part of the Grapher object and can be run using Graphers Layout method. At present there are three layout algorithms - Force directed, Bubble and Hierarchy. You pass a constant to the Layout() method to specify which to use, it will operate on the current graph and generate a position_map. This maps the current graph objects to x,y coordinates in a Cartesian space. To access these use the position() method which will return a position value given a specific node.

XMLParser p;
Linkler* l = p.parse_xml("my_linkgen_2.xml"); 
SWUGraphBuilder swub(l);

SWU* a = l->find_swu("AAXXYY");
swub.grapher().Layout(100, 100, SWUGraphBuilder::GraphType::BUBBLE); // create a bubble graph layout
std::pair<int, int> pos = swub.grapher().position(a); // fetch the position of the node a
pos[0] // <-- X positions
pos[1] // <-- Y positions

Filters

Filters can be applied to a Graph when nodes and/or edges are added to the Graph. The filters need to define an operator(NodeType/EdgeType) which returns true if the node or edge should be included in the Graph (that is if Grapher should allow adding of the node to the Graph) and false otherwise.

To set a filter, use the set_filter method and provide it with an object of the GraphFilterList type. This needs to be set prior to adding nodes to the Graph, as filters do not operate retroactively, meaning that existing nodes in the Graph will remain untouched.

See more details about filters in the filter guide.

XMLParser p;
Linkler* l = p.load_xml("test.xml"); 
SWUGraphBuilder swub(l);

swub.graph_single("AAXXYY"); // will graph AAXXYY regardless of degree

GraphFilerList filters;

DepednencyDegreeFilter* deg_filter = new DependencyDegreeFilter("my degree filter", 1, 10);
HideAction* hideAction = new HideAction(deg_filter);

filters.add(hideAction);

swub.grapher().set_filter(&filters);

swub.graph_all(); // will add all nodes to the graph with degree 1 to 10, keeping AAXXYY intact
swub.graph_all_dependencies(); // will add all dependencies, including all dependencies of AAXXYY with degrees 1...10

SetPropertyAction

Beyond HideAction, there is also SetPropertyAction. Set Property Action will set properties for nodes or edges using a GraphProperties object. There is such a properties object in any instance of Grapher, which can be accessed via Grapher::properties() which can be used for properties that are intended to be persistent throughout the lifetime of the Grapher. It is also possible to define a local Properties data structure which can be passed to the filters on which the filter then will set the filter. This can be used to achieve properties that are not persistent with the Grapher. An example of how to do this is below:

typedef GraphType SWUGraphBuilder::GraphType;

XMLParser p;
Linkler* l = p.load_xml("test.xml"); 
SWUGraphBuilder swub(l);

GraphFilterList<GraphType> filter;
GraphProperties<GraphType> properties;

DependencyDegreeFilter* f = new DependencyDegreeFilter("my degree filter", 1, 10);
SetPropertyAction* prop = new SetPropertyAction(properties,f);
prop->set_property("color", "blue");

filter.add(prop);

for(GraphType::node_iterator it = g_->node_begin(); it != g_->node_end(); ++it) {
  if(!filter(*it)) 
    std::cerr << "Node should not be included: " << (*it)->name() << std::endl;
  //<<--- if the filter matches then the property "color" will be set in the property list properties
}

properties.get_property( .., "color"); // <-- to acces the property

EdgeTypeFilter e = new EdgeTypeFilter("my edge filter", GraphTool::LPM);
SetPropertyAction* prop2 = new SetPropertyAction(gb.grapher().properties(), e); 
prop2->set_property("color", "green");

filter.add(prop2);

for(GraphType::edge_iterator it = g_->edge_begin(); it != g_->edge_end(); ++it) {
  if(!filter(*it)) 
    std::cerr << "Edge should not be included: " << (*it)->from()->name() << " " << (*it)->to()->name() << std::endl;
  //<<--- since DepDegreeFilter has no impact on edges it won't run, but EdgeType will setting all matching edges property of "color" to green in the grapher()
}

gb.grapher().properties().get_property( .., "color"); // <-- to access

Exporting

There is an exporter function to write to graphviz format, this is defined in the GraphExporter class. It takes a stream as argument which can be either cout or a filestream.

XMLParser p;
Linkler* l = p.load_xml("test.xml"); 
SWUGraphBuilder swub(l);

swub.graph_all();
swub.graph_all_dependents();
swub.graph_all_dependencies();

GraphExporter(std::cout, swub.grapher()).write_graphviz();

An optional GraphProperties datastructure can be provided to the write_graphviz() method which would allow you to specify properties which have been generated for example by using filters (or even manually). All those properties will be included in the output in addition to any properties set in the Grapher itself.

Iterators

There are two iterators defined for Grapher:

Grapher<>::node_iterator
Grapher<>::edge_iterator

These can be iterated using node_begin(), node_end() and edge_begin(), edge_end() respectively.

As the names indicate they are used for iterating all nodes and all edges in the graph.

for(GraphType::node_iterator it = g_->node_begin(); it != g_->node_end(); ++it) {
  GraphType::node_value_type node = *it;
  //...
}

for(GraphType::edge_iterator it = g_->edge_begin(); it != g_->edge_end(); ++it) {
  GraphType::edge_value_type node = *it;
  //...
}