1. Graph Programming with MASS

To promote agent-based graph analysis with MASS, we extended the Places class to GraphPlaces. Users can import graph data from a variety of file formats or define graphs dynamically by creating vertices and edges at runtime. The following example code propagates agents over a biological network to search for network motifs. This snippet starts by instantiating a new GraphPlaces object and reading graph data in from a DSL file. DSL files represent a proprietary format for graph data. It then adds a new vertex and edge to the graph, uses callAll to invoke the updateState method at each vertex within the graph, and exchangeAll to tell each vertex to invoke the forwardMsg method on each of its neighbors.

#!java
1  import MASS.*;
2    public class GraphCreation {
3      public void main(String[] args) {
4      MASS.init( );
5      int gpHandle = 0;
6      GraphPlaces graph = new GraphPlaces(gpHandle, BionetVertex.class.getName());
7      graph.loadDSLFile("/home/NETID/foobar/input.dsl");
8      graph.addVertex();
9      int srcVertex = 99;
10     int destVertex = 100;
11     graph.addEdge(srcVertex, destVertex);
12     int updateStateFuncID = 0;
13     graph.callAll(updateStateFuncID);
14     int forwardMsgFuncID = 1;
15     graph.exchangeAll(forwardMsgFuncID);
16     Agents searcher = new Agents(2, "Motif", graph, 101);
17     crawler.doWhile(()->crawlers.hasAgents());
18     MASS.finish();
19  }  }
20 public class Motif extends Agent {
21   @onCreation public void init( ) { ...; }
22   @onArrival public void walk( ) { ...; }
23 }

2. GraphPlaces Class

2.1 Constructor

Empty Graph Constructor

GraphPlaces(int handle, String className, int size)

Constructor initializes an empty graph.

arameters int handle - A unique identifier that designates a group of places. Must be unique over all machines.

String className - Name of the user-implemented class VertexPlaces are constructed from.

2.2 GraphPlaces Input Formats

GraphPlaces supports four file input types, two of which are propreitary to the UW Bothell distributed systems lab.

DSL (Distributed Systems Lab format)
SAR (A parallel file format)
MATSim
HIPPIE

DSL

The DSL file format is a proprietary graph file format that can be ingested by MASS in parallel by all nodes within the cluster. The format itself represents an adjacency list and looks as follows:

0=1,1
1=0,1;2,1;3,1;4,1
2=1,1;3,1
3=1,1;2,1;4,1
4=1,1;3,1

There is no header to the file and the vertices must be 0-indexed. The integer to the left of the = is the vertex ID and the comma-deliminted pairs to the right of it is its edge list (<vertex_id>;<edge_weight>). Files of this format can be imported into MASS by first instantiating a GraphPlaces object and then calling the loadDSLFile function and passing it the absolute path of the file. It must not be a relative path. This is because every node in the cluster will process the file and nodes other than master will need to the absolute path in order to find the file. An example can be seen below:

#!java
1  import MASS.*;
2    public class GraphCreation {
3      public void main(String[] args) {
4      MASS.init( );
5      int gpHandle = 0;
6      GraphPlaces graph = new GraphPlaces(gpHandle, BionetVertex.class.getName());
7      graph.loadDSLFile("/home/NETID/foobar/input.dsl");
8      MASS.finish();
9    }
10 }

SAR

SAR is another properietary file format for importing graphs into MASS. It was started as a parallel I/O graph file format and named after the group members whom would be benefiting from its design. Unfortunately, it is not complete and will not work for graphs with more than 10 vertices. As it is currrently, it should not be used. This document will be updated if/when it is ready for use. An example of the file format is shown below:

9,9,9,9,9,9,9,9,9,9
1   2   3   4   5   6   7   8   9
0   2   3   4   5   6   7   8   9
0   1   3   4   5   6   7   8   9
0   1   2   4   5   6   7   8   9
0   1   2   3   5   6   7   8   9
0   1   2   3   4   6   7   8   9
0   1   2   3   4   5   7   8   9
0   1   2   3   4   5   6   8   9
0   1   2   3   4   5   6   7   9
0   1   2   3   4   5   6   7   8

2.3 GraphPlaces Methods

public void loadDSLFile(String filePath)

loadDSLFile loads the DSL formatted graph file, from the provided path, into the distributed GraphPlaces object.

Parameters:

String filePath - The path to the DSL formatted graph file. Note that this MUST be an absolute path if running MASS with more than one node.

public void loadSARFile(String filePath)

loadSARFile loads the SAR formatted graph file, from the provided path, into the distributed GraphPlaces object.

Parameters:

String filePath - The path to the SAR formatted graph file. Note that this MUST be an absolute path if running MASS with more than one node.

public int size()

Return:

The total size of the distributed graph.

Parameters:

int vertexId – The vertex ID.

Return:

The ID of the node that owns the vertex associated with the provided vertex ID.

public boolean addEdge(int vertexId, int neighborId)

Adds an edge to the graph between the provided vertexID and neighborID with a default weight of 1.0. The vertex and neghbor vertices must exist at the time of edge creation.

Parameters:

int vertexId – The source vertex ID.

int neighborId - The neighbor/destination ID.

Return:

True if the edge was successfully added, false otherwise.

public boolean addEdge(int vertexId, int neighborId, double weight)

Adds an edge to the graph between the provided vertexID and neighborID with the provided weight. The vertex and neghbor vertices must exist at the time of edge creation.

Parameters:

int vertexId – The source vertex ID.

int neighborId - The neighbor/destination ID.

double weight – Weight of the edge.

Return:

True if the edge was successfully added, false otherwise.

public boolean addEdge(Object vertexId, Object neighborId)

Adds an edge to the graph between the provided vertexID and neighborID with a default weight of 1.0. The vertex and neghbor vertices must exist at the time of edge creation.

Parameters:

Object vertexId – Unique Identifier of the source vertex. Must be unique and implement the hashCode and equals methods.

Object neighborId - Unique Identifier of the destination vertex. Must be unique and implement the hashCode and equals methods.

Return:

True if the edge was successfully added, false otherwise.

public boolean addEdge(Object vertexId, Object neighborId, double weight)

Adds an edge to the graph between the provided vertexID and neighborID with the provided weight. The vertex and neghbor vertices must exist at the time of edge creation.

Parameters:

Object vertexId – Unique Identifier of the source vertex. Must be unique and implement the hashCode and equals methods.

Object neighborId - Unique Identifier of the destination vertex. Must be unique and implement the hashCode and equals methods.

double weight – Weight of the edge.

Return:

True if the edge was successfully added, false otherwise.

public boolean removeEdge(int vertexId, int neighborId)

Removes the edge between the provided vertex and neighbor IDs.

Parameters:

int vertexId – The vertex ID of the source vertex.

int neighborId – The vertex ID of the neighbor or destination.

Return:

True if the edge was successfully removed, false otherwise.

public boolean removeEdge(Object vertexId, Object neighborId)

Removes the edge between the provided vertex and neighbor IDs.

Parameters:

Object vertexId – Unique Identifier of the vertex that is the source of the edge. Must be unique and implement the hashCode and equals methods.

Object neighborId – Unique Identifier of the vertex that is the neighbor/destination of the edge. Must be unique and implement the hashCode and equals methods.

Return:

True if the edge was successfully removed, false otherwise.

public GraphModel getGraph()

Creates a GraphModel object containing all the vertices as instances of VertexModel. Each instance of VertexModel object contains a a list of neighors. Weight is not supported

Return

GraphModel object representing GraphPlaces graph

public void setGraph(final GraphModel newGraph)

Reinitilizes graph to blank and creates a new distributed graph based on the provided GraphModel. Weighted edges not supported.

Parameters:

final GraphModel newGraph – GraphModel object that will be the new graph.

public VertexMetaValues getVertexMetaValues(Object vertexId)

Given the object ID of the vertex, it returns a VertexMetaValues object containing meta values such as the vertex ID and node ID where the vertex is located.

Parameters:

Object vertexId – Unique Identifier of the vertex. Must be unique and implement the hashCode and equals methods.

Return:

The VertexMetaValues object associated with the provided vertexId object.

public void callAll( int functionId )

Initiates a callAll across all vertices within the graph to invoke the function associated with the provided functionId.

Parameters:

int functionId - The ID associated with the function the caller wishes to invoke on the vertices within the graph.

public void callAll(int functionId, Object argument)

Initiates a callAll across all vertices within the graph to invoke the function associated with the provided functionId.

Parameters:

int functionId - The ID associated with the function the caller wishes to invoke on the vertices within the graph.

Object argument - An object containing the argument the caller wishes to pass to the invoked function.

public Object[] callAll(int functionId, Object argument[])

Initiates a callAll across all vertices within the graph to invoke the function associated with the provided functionId.

Parameters:

int functionId - The ID associated with the function the caller wishes to invoke on the vertices within the graph.

Object argument - An object containing the argument the caller wishes to pass to the invoked function.

Return:

An array of return values from the invoked functions on each vertex, ordered by vertex ID.

public void exchangeAll( int destinationHandle, int functionId )

ExchangeAll tells all vertices within the graph to invoke the function associated with the provided functionID on each of its neighboring vertices and store the data within the calling vertex.

Parameters:

int destinationHandle - The handle of the GraphPlaces object for which the exchangeAll results should be aggregated to. This will most often be the handle of the GraphPlaces object that is calling the function.

int functionId - The ID associated with the function the caller wishes to invoke on neighboring vertices.

2.4 VertexPlace Methods

VertexPlace is the base class for which vertex implementation can be created and used within GraphPlaces.

public Object [] getNeighbors()

eturn

An array containing the vertex IDs of each of the vertices neighbors.

public Object [] getWeights()

eturn:

An array containing the weights of each of the edges between this vertex and each of its neighbors. Note that this isn’t ordered but will share an index with the array returned from getNeighbors. To determine which edge the weight belongs to, use the index of weight to lookup the neighbor from this function call.

2.5 HIPPIE Support

The HIPPIE file format describes a protein network in the form of an edge list. Each line in a HIPPIE tab-delimited file represents a protein-protein interaction and a mapping of attributes associated with that interaction. Support is provided by the Hippie class and is found within the edu.uw.bothell.css.dsl.MASS.graph.hippie package. This class extends from GraphPlaces and provides facilities for reading in, and working with, HIPPIE graph data. When adding edges to the graph, HIPPIE attributes can be added as well. These are provided as a String and follow the same format as the attributes field within the HIPPIE file format. An example attributes string looks like this: experiments:in vivo;pmids:9334256,16189514,16713569;sources:HPRD,I2D,Rual05,Lim06. The are key/list pairs that are semi-colon delimited. keys are separated from value lists using a colon, and list values are comma delimited. The example attribute string will create the following edge attribute map:

Map<String, String[]>{
    "experiments": {"in vivo"},
    "pmids": {"9334256","16189514","16713569"},
    "sources": {"HPRD","I2D","Rual05","Lim06"},
}

An example of the file format is as follows:

AL1A1_HUMAN 216 AL1A1_HUMAN 216 0.76    experiments:in vivo,Two-hybrid;pmids:12081471,16189514,25416956;sources:HPRD,BioGRID,IntAct,MINT,I2D,Rual05
ITA7_HUMAN  3679    ACHA_HUMAN  1134    0.73    experiments:in vivo,Affinity Capture-Western,affinity chromatography technology;pmids:10910772;sources:HPRD,BioGRID,I2D
NEB1_HUMAN  55607   ACTG_HUMAN  71  0.65    experiments:in vitro,in vivo;pmids:9362513,12052877;sources:HPRD
SRGN_HUMAN  5552    CD44_HUMAN  960 0.63    experiments:in vivo;pmids:9334256,16189514,16713569;sources:HPRD,I2D,Rual05,Lim06
GRB7_HUMAN  2886    ERBB2_HUMAN 2064    0.9 experiments:in vitro,in vivo,Reconstituted Complex,protein array,affinity chromatography technology,nuclear magnetic resonance,x-ray crystallography,competition binding,pull down;pmids:9079677,16273093,12975581,12061724,17875712;sources:HPRD,BioGRID,MINT,I2D,IntAct
PAK1_HUMAN  5058    ERBB2_HUMAN 2064    0.73    experiments:in vivo,Affinity Capture-Western,affinity chromatography technology;pmids:9774445;sources:HPRD,BioGRID,I2D,STRING

public Hippie(int handle)

Constructs a HIPPIE graph with the provided handle and defaults to using the HIPPIEVertex class as its vertex implementation.

Parameters:

int handle - The handle to be assigned to the HIPPIE instance. Must be unique.

public Hippie(int handle, String className)

Constructs a HIPPIE graph with the provided handle and allows the caller to specify the vertex implementation to use.

Parameters:

int handle - The handle to be assigned to the HIPPIE instance. Must be unique.
String className - The class name of the vertex class implementation to be used by the graph. This MUST extend from HippieVertex.

public Hippie(int handle, String className, String filePath)

Constructs a HIPPIE graph with the provided handle, className, and HIPPIE filePath. This will populate the graph with the data from the provided file.

Parameters:

int handle - The handle to be assigned to the HIPPIE instance. Must be unique.
String className - The class name of the vertex class implementation to be used by the graph. This MUST extend from HippieVertex.
String filePath - Path to the HIPPIE formatted graph file. Note that this must be an absolute path if running MASS with more than one node.

void loadFromFile(String filePath)

loadFromFile loads graph data from the provided HIPPIE formatted graph file.

Parameters:

String filePath - Path to the HIPPIE formatted graph file. Note that this must be an absolute path if running MASS with more than one node.

2.6 MATSim Support

MATSim is an XML format that was created as a traffic simulation framework called Multi-Agent Traffic Simulation. The MATSim network file is an edge list format with two second-level lists: nodes and links. The nodes list contains a list of all vertices within the network whereas the links list contains the list of edges. Support for this file format is provided by the Matsim class and is found within the edu.uw.bothell.css.dsl.MASS.graph.matsim package. Edges within MATSim graphs can contain all of the edge attribute data found within the file. This can consist of speed, capacity, number of lanes, etc… An example of this file format is as follows:

<network>
    <nodes>
        <node id="1" x="665498.5915828889" y="6600721.058093354" ></node> <node id="10" x="658803.7360160261"         y="6575644.324923517"></node> <node id="100" x="566282.7735573719" y="6454558.626888261"></node> <node id="10000" x="408774.9462956431" y="6233917.802557087"></node> <node id="10001" x="408772.02211252623" y="6234167.648466459"></node> ...
    </nodes> 
    <links>
        <link id="pt_99992" from="pt_740057809" to="pt_740057653" length="257.27792215211286" freespeed="8.333333333333334" capacity="500.0" permlanes="1.0" oneway="1" modes="pt" ></link>
        <link id="pt_99996" from="pt_740057599" to="pt_740057756" length="157.21884660387735" freespeed="8.333333333333334" capacity="500.0" permlanes="1.0" oneway="1" modes="pt" ></link>
        <link id="pt_99997" from="pt_740057688" to="pt_740057647" length="207.21244492773178" freespeed="8.333333333333334" capacity="500.0" permlanes="1.0" oneway="1" modes="pt" ></link>
        <link id="pt_99998" from="pt_740057647" to="pt_740057623" length="378.77959250564095" freespeed="8.333333333333334" capacity="500.0" permlanes="1.0" oneway="1" modes="pt" ></link>
        <link id="pt_99999" from="pt_740057623" to="pt_740057686" length="292.07787848782823" freespeed="8.333333333333334" capacity="500.0" permlanes="1.0" oneway="1" modes="pt" ></link>
    </links> 
</network>

public Matsim(int handle)

Constructs a MATSim graph with the provided handle and defaults to using the MatsimVertex class as its vertex implementation.

Parameters:

int handle - The handle to be assigned to the MATSim instance. Must be unique.

public Matsim(int handle, String className)

Constructs a MATSim graph with the provided handle and allows the caller to specify the vertex implementation to use.

Parameters:

int handle - The handle to be assigned to the MATSim instance. Must be unique.
String className - The class name of the vertex class implementation to be used by the graph. This MUST extend from MatsimVertex.

public Matsim(int handle, String className, String filePath)

Constructs a MATSim graph with the provided handle, className, and MATSim filePath. This will populate the graph with the data from the provided file.

Parameters:

int handle - The handle to be assigned to the MATSim instance. Must be unique.
String className - The class name of the vertex class implementation to be used by the graph. This MUST extend from MatsimVertex.
String filePath - Path to the MATSim formatted graph file. Note that this must be an absolute path if running MASS with more than one node.

void loadFromFile(String filePath)

loadFromFile loads graph data from the provided MATSim formatted graph file.

Parameters:

String filePath - Path to the MATSim formatted graph file. Note that this must be an absolute path if running MASS with more than one node.

3. Cytoscape Integration

The MASS library uses Cytoscape as a GUI tool for interactive graph construction, editing, and visualization. The two main reasons are: Cytoscape’s popularity among scientific users and its well-defined plug-ins. Integrating MASS with Cytoscape requires two key interactions between the two systems through Cytoscape plug-ins:

’‘’Import-network plug-in’’’: pulling an in-memory graph from MASS and re-building it inside of Cytoscape into a native CyNetwork with a combination of CyNode and CyEdge entities.
’‘’Export-network plug-in’’’: serializing the currently selected Cytoscape CyNetwork into the MASS Graph- Places for sending to MASS.

To facilitate communication between Cytoscape and MASS, a user must run CytoscapeListener in her/his MASS main program as shown in the listing below on line 6. Then, Cytoscape plug-ins establish a TCP socket to communicate with MASS. Since a user interacts with Cytoscape on her/his graph visualization, Cytoscape invokes both import- and export-network plug-ins. They respectively send the following commands to MASS, followed by a transfer of a lightweight graph representation with only essential information such as the vertex IDs and their neighbors:

’‘’getGraph’’’: initiates retrieving the in-memory graph from MASS that sends the serialized message to Cytoscape.
’‘’setGraph’’’: sends the current CyNetwork to MASS that rebuilds the corresponding GraphPlaces object inside of it.

These two commands are interpreted by CytoscapeListener automatically and are applied to a given graph in parallel of the main program. With its command interpretation in background, a user can repeatedly observe the progress of graph computation (line 7 below).

#!java
1  import MASS.*;
2  public class GraphVisualization {
3    public void main(String[] args) {
4    MASS.init( );
5    GraphPlaces graph = new GraphPlaces(1, "EmptyGraph");
6    MASSListener listener = new CytoscapeListener(graph);
7    ...; // Graph computation
8    listener.finish();
9    MASS.finish();
10 } }

As shown below, in a snapshot of Cytoscape’s GUI, by selecting the “Import Network” menu option, Cytoscape’s import-network plug-in kicks off the ImportNetworkTask module that sends a getGraph request to MASS CytoscapeListener to retrieve its in-memory graph. The plug-in then de-serializes the MASS response into a Cytoscape representation of the graph: a CyNetwork. To achieve a simple and consistent visualization of a graph, a few minor styles were applied to the Cytoscape nodes created (vertices with neighbors in blue rectangles, those with no neighbors in red circles, and a userclicked vertex in a yellow rectangle).

Cytoscale Graph Creation