Graphs

From Bio++ Wiki
Revision as of 12:47, 31 July 2015 by Thomas Bigot (talk | contribs) (Roles of the Classes)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Introduction

In July 2015, new Graph structure is added in Bio++ master branch. It aims to be a generic tool to represent graphs, and hence trees in their structure and manage objects associated to this structure.

Whereas the classical bpp::Tree rationale is mainly included in its nodes, bpp::Graph manages its nodes and edges relations itself. EG: in the classical Tree, a tree knows its root, and the roots knows its sons, and so on. The nodes know their father. But the tree integrity cannot be guaranteed at all. In the new bpp::Graph, nodes and edges are not autonomous objects. They are just IDs in the graph representation. The graph manages the relations itself. It implies two main benefits:

  • the integrity of the graph can be easily checked,
  • the access to a certain node doesn’t need to browse recursively all the nodes from the root. With the standard implementation, a node can be found in O(log(n)).

Roles of the Classes

Graphes management is split into two classes: Graph which is a pure structure manager, and GraphObserver which observe the graph. Some GraphObservers, AssociationGraphObserver, can associate objects to nodes and edges.

Inheritance / interaction flowchart of graph classes

Graph

bpp::Graph API

A Graph only manages the structure : Nodes are linked using Edges. Nodes and Edges are only stored as unsigned ints. A Graph can be directed or not. One can retrieve outgoing / incoming (if applying) neighbours, an edge between two nodes, the reachable leaves from a certain node…

A Graph also knows its observers.

TreeGraph

bpp::TreeGraph API

(help text to be written)

GraphObserver

bpp::GraphObserver API

Observers must refer to one peculiar Graph. They subscribe to it when created, so they can be warned when the subject (= observed) Graph is modified. In this way, several Observers can watch to one unique Graph, and they can even manage subparts of this Graph, associate different type of objects to nodes and edges…

AssociationGraphObserver

bpp::AssociationGraphObserver API

This interface allows to associate zero or one object to each node and to each edge of the observed Graph. The object types (classes) associated to the nodes on the one and (noted N), and to the edges on the other hand (noted E) is chosen by the user. One can directly perform actions or queries using N and E types, wrapping the access to the subject Graph. For instance, one can query which object E is between two nodes of N.

Implementation and templates of implementations

Graph and Observer classes use the power of templates. For instance, Graph is an interface, and SimpleGraph is its basic implementation. AssociationGraphObserver is an interface and SimpleAssociationGraphObserver is its implementation. But there is no choice made concerning the type of the observed subject Graph. It can be a SimpleGraph, but it can also be another implementation. So if one wants to use a basic AssociationGraphObserver, the type to use is AssociationGraphObserver<N,E,SimpleGraph>.

More complicated: an AssociationTreeGraphObserver is a template which relies on a TreeGraph. One might want to use SimpleTreeGraph as the TreeGraph implementation, but SimpleTreeGraph is a template which relies itself on a Graph implementation, for instance SimpleTreeGraph. In this example, the AssociationTreeGraphObserver types would be SimpleAssociationTreeGraphObserver<N,E,SimpleTreeGraph<SimpleGraph>>. It looks a bit confusing, but once implementations choices are made, the user can just define a type alias for its classes.

Code Example

Here is an extract of the GraphObserver test program. In this example we manipulate a graph through an AssociationGraphObserver. This observer associates nodes to strings, and edges to integers. It uses the SimpleGraph as the Graph class implementation.

 SimpleAssociationGraphObserver<string,unsigned int,bpp::SimpleGraph> grObs(true);
 string zero = "zero";
 string one = "one";
 string two = "two";
 string three = "three";
 unsigned int r3 = 3;
 cout << "Creating node zero." << endl;
 grObs.createNode(&zero);
 
 cout << "Creating node one from the number zero." << endl;
 grObs.createNode(&zero,&one);
 
 cout << "Creating node two from the number one." << endl;
 grObs.createNode(&one,&two);
 
 cout << "Linking two to one." << endl;
 grObs.link(&two,&zero,&r3);
 
 cout << "Linking one to three." << endl;
 grObs.createNode(&one,&three);
 
 cout << "Linking three to zero." << endl;
 grObs.link(&three,&zero);
 
 // so now we have zero -> one -> two -> zero
 // and one -> three -> zero
 
 // now getting neighbours (singletons in this case):
 vector<string*> fromOne = grObs.getOutgoingNeighbors(&zero);
 vector<string*> fromThree = grObs.getOutgoingNeighbors(&two);
 
 bool test = (*(fromOne.begin()) == &one) && (*(fromThree.begin()) == &zero);
 
 // displaying the corresponding Graph:
 grObs.getGraph()->outputToDot(std::cout,"myTestDirGrObs");

Result:

 digraph myTestDirGrObs {
   0 -> 1 -> 2 -> 0;
   1 -> 3 -> 0;
 }

Status

Changelog

2015-07-27 Initial merge in master

To Do

  • Graph interface is quite empty. When the reference implementation SimpleGraph is stable, the methods will be copied to the interface.