Graphs (Mathematics) - singa-bio/singa GitHub Wiki

In general a Graph is a data structure that contains objects in which some or all of the objects are in some way related to each other. The objects in this structure are called nodes and the relationships between them are referred to as edges.

In SiNGA all nodes and edges in a graph are accessed through identifiers. Here a graph acts like a HashMap, where adding of an additional node object with an identifier that is already present in the graph results in the replacement of the previous node. Generally, the graph handles choosing the identifier for the next node. Edges are stored in the same way and connect nodes by referencing their identifiers. Additionally each node holds a reference to its neighbouring nodes. Further each node can be assigned a Vector that represents its position.

Each graph is characterized by

• NodeType - any object that extends Node.
• EdgeType - any Edge that is able to reference between NodeTypes
• IdentifierType - any object that can be used to identify a Node.
• VectorType - The kind of vector that describes the position of a Node in the graph.

The documentation details the available methods and usability.

The GenericGraph class is an implementation of this concept where some content can be assigned to each node.

GenericGraph<String> genericGraph = new GenericGraph<>();
genericGraph.addNode("N1");
genericGraph.addNode("N2");
genericGraph.addNode("N3");
genericGraph.addEdgeBetween("N1", "N3");

Creating a graph of strings.

For undirected graphs, the edges have no orientation. The nodes are unordered pairs. For example, with two nodes N1 and N2, the edge (N1, N2) and (N2, N1) are equivalent.

Directed graphs contain directed edges. The edges have an orientation. Neighborhood relations are unique. If a node N1 is connected with node N2, the edge runs in the direction of N2. N1 has the neighbor N2 but N2 does not have the neighbor N1.

Grid graphs are graphs that can be displayed in one plane. All nodes lie on an integer coordinate system. In the class GridGraph the nodes are described by the RectangularCoordinates.

Binary trees are also made up of vertices and edges. The vertices, however, have at most two direct offspring. The origin of the structure is called a root and this is divided into two child nodes, the right and left child.

Red-black trees are self-balanced binary-search-trees. Internally each node is color coded in either red or black allowing for an optimal arrangement of the leaf nodes in the tree, decreasing the search time specific nodes.

MoleculeGraphs can be parsed from SMILES Strings using the SmilesParser.

String smilesString = "[H]C(=O)[C@H](O)[C@@H](O)[C@H](O)[C@H](O)COS([O-])(=O)=O";
MoleculeGraph moleculeGraph = SmilesParser.parse(smilesString);

This is the graph representation of the two-dimensional molecular structure of chemical species, allowing to apply graph algorithms.

The AutomatonGraph is the underlying structure of Cellular Graph Automata as used for simulations in the singa-simulation package. Each node represents a container of chemical entities that are assigned a concentration. The neighbourhood relation is used to define the interactions between the nodes during simulation.

These class Graphs contains a some functions that can be useful when working with graphs, especially to create them. The following table shows some methods and their function.

Extract all disconnected subgraphs.

List<UndirectedGraph> disconnectedSubgraphs = DisconnectedSubgraphFinder.findDisconnectedSubgraphs(graph);

Extract neighbourhoods.

UndirectedGraph neighborhood = NeighbourhoodExtractor.extractNeighborhood(undirectedGraph, referencenode, depth);

Find and track shortest paths.

LinkedList<RegularNode> shortestPath = ShortestPathFinder.findBasedOnPredicate(sourceNode, targetNode -> targetNode.getIdentifier() == 1);

Graphs can be used in biology to identify correlations and relationships in biological networks at various levels (e.G. protein-protein interaction, metabolic interaction, transcription factor binding, similarity of ligands) The algorithm takes a pattern graph and a target graph and then looks for any isomorphic mapping of a pattern graph in the target graph.

In SiNGA the class RISubgraphFinder provides an algorithm to perform the search of subgraph isomorphism. The implementation follows the description by [Bonnici 2013]. This subgraph detection algorithm can be applied on any Graph and allows the flexible definition of isomorphism conditions using Functions.

    RISubgraphFinder finder = new RISubgraphFinder<>(patternGraph, targetGraph,
      // function detmermining if nodes are considered isomorph
      // here two nodes are considered equal if their content is equal
      (a, b) -> a.getContent().equals(b.getContent()),
      // function detmermining if edges are considered isomorph
      // here two nodes are always considered equal
      (a, b) -> true);

    List<List<GenericNode<String>>> matches = finder.getFullMatches();

The singa-javafx package allows for visualization of any graph that implements the graph interface and whose nodes are represented with two-dimensional coordinates. The graph arrangement can be optimized using a force directed layout algorithm and voronoi iteration.

Setting the graph in the GraphDisplayApplication and launching the application opens a JavaFX application with the graph.

GraphDisplayApplication.graph = Graphs.buildTreeGraph(3, new Rectangle(400, 400));
Application.launch(GraphDisplayApplication.class);

Additionally renderers can be used and defined to refine display of any graph.

GraphDisplayApplication.graph = SmilesParser.parse("[H]C(=O)[C@H](O)[C@@H](O)[C@H](O)[C@H](O)COS([O-])(=O)=O");
GraphDisplayApplication.renderer = new MoleculeGraphRenderer();
Application.launch(GraphDisplayApplication.class);

Using renderers you are also able so draw additional features on the same canvas.

    GraphDisplayApplication.graph = Graphs.buildRandomGraph(30, 0.03, new Rectangle(200, 200));
    GraphRenderer<RegularNode, UndirectedEdge, Integer, UndirectedGraph> renderer = new GraphRenderer<>();
    GraphDisplayApplication.renderer = renderer;

    renderer.setRenderBefore((currentGraph) -> {
        renderer.getGraphicsContext().setStroke(Color.DARKBLUE);
        List<Vector2D> vectors = currentGraph.getNodes().stream()
            .map(Node::getPosition)
            .collect(Collectors.toList());
        ConvexHull convexHull = ConvexHull.calculateHullFor(vectors);
        renderer.connectPoints(convexHull.getHull());
    });

    Application.launch(GraphDisplayApplication.class);

​