Example Graph Paths - Revision history

Peter at 15:08, 7 July 2021

2021-07-07T15:08:10Z

Peter at 05:19, 5 November 2020

2020-11-05T05:19:56Z

Peter: Created page with "Many Graph operations can be performed using linear algebra and this connection is the subject of much recent research. EJML now has basic "Graph BLAS" capabilities as this ex..."

2020-11-05T05:19:12Z

Created page with "Many Graph operations can be performed using linear algebra and this connection is the subject of much recent research. EJML now has basic "Graph BLAS" capabilities as this ex..."

New page

Many Graph operations can be performed using linear algebra and this connection is the subject of much recent research. EJML now has basic "Graph BLAS" capabilities as this example shows.

External Resources:
* [https://github.com/lessthanoptimal/ejml/blob/v0.40/examples/src/org/ejml/example/ExampleGraphPaths.java ExampleGraphPaths.java code]

== Example Code ==

<syntaxhighlight lang="java">
/**
* Example including one iteration of the graph traversal algorithm breath-first-search (BFS),
* using different semirings. So following the outgoing relationships for a set of starting nodes.
*
* More about the connection between graphs and linear algebra can be found at:
* https://github.com/GraphBLAS/GraphBLAS-Pointers.
*
* @author Florentin Doerre
*/
public class ExampleGraphPaths {
private static final int NODE_COUNT = 4;

public static void main(String[] args) {
DMatrixSparseCSC adjacencyMatrix = new DMatrixSparseCSC(NODE_COUNT, 4);

// For the example we will be using the following graph:
// (3)<-[cost: 0.2]-(0)<-[cost: 0.1]->(2)<-[cost: 0.3]-(1)

adjacencyMatrix.set(0, 2, 0.1);
adjacencyMatrix.set(0, 3, 0.2);
adjacencyMatrix.set(2, 0, 0.1);
adjacencyMatrix.set(3, 2, 0.3);

// Semirings are used to redefine + and * f.i. with OR for + and AND for *
DSemiRing lor_land = DSemiRings.OR_AND;
DSemiRing min_times = DSemiRings.MIN_TIMES;
DSemiRing plus_land = new DSemiRing(DMonoids.PLUS, DMonoids.AND);

// sparse Vector (Matrix with one column)
DMatrixSparseCSC startNodes = new DMatrixSparseCSC(1, NODE_COUNT);
// setting the node 0 as the start-node
startNodes.set(0, 0, 1);

DMatrixSparseCSC outputVector = startNodes.createLike();

// Compute which nodes can be reached from the node 0 (disregarding the costs of the relationship)
CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, lor_land, null, null);

System.out.println("Node 3 can be reached from node 0: " + (outputVector.get(0, 3) == 1));
System.out.println("Node 1 can be reached from node 0: " + (outputVector.get(0, 1) == 1));

// Add node 3 to the start nodes
startNodes.set(0, 3, 1);

// Find the number of path the nodes can be reached with
CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, plus_land, null, null);
System.out.println("The number of start-nodes leading to node 2 is " + (int) outputVector.get(0, 2));

// Find the path with the minimal cost (direct connection from one of the specified starting nodes)
// the calculated cost equals the cost specified in the relationship (as both startNodes have a weight of 1)
// as an alternative you could use the MIN_PLUS semiring to consider the existing cost specified in the startNodes vector
CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, min_times, null, null);
System.out.println("The minimal cost to reach the node 2 is " + outputVector.get(0, 2));
}
}
</syntaxhighlight>

@@ Line 3: / Line 3: @@
 External Resources:
-* [https://github.com/lessthanoptimal/ejml/blob/v0.40/examples/src/org/ejml/example/ExampleGraphPaths.java ExampleGraphPaths.java]
+* [https://github.com/lessthanoptimal/ejml/blob/v0.41/examples/src/org/ejml/example/ExampleGraphPaths.java ExampleGraphPaths.java]
 == Example Code ==
@@ Line 20: / Line 20: @@
      private static final int NODE_COUNT = 4;
-     public static void main(String[] args) {
+     public static void main( String[] args ) {
          DMatrixSparseCSC adjacencyMatrix = new DMatrixSparseCSC(NODE_COUNT, 4);
@@ Line 44: / Line 44: @@
          // Compute which nodes can be reached from the node 0 (disregarding the costs of the relationship)
-         CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, lor_land, null, null);
+         CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, lor_land, null, null, null);
          System.out.println("Node 3 can be reached from node 0: " + (outputVector.get(0, 3) == 1));
@@ Line 53: / Line 53: @@
          // Find the number of path the nodes can be reached with
-         CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, plus_land, null, null);
+         CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, plus_land, null, null, null);
-         System.out.println("The number of start-nodes leading to node 2 is " + (int) outputVector.get(0, 2));
+         System.out.println("The number of start-nodes leading to node 2 is " + (int)outputVector.get(0, 2));
          // Find the path with the minimal cost (direct connection from one of the specified starting nodes)
          // the calculated cost equals the cost specified in the relationship (as both startNodes have a weight of 1)
          // as an alternative you could use the MIN_PLUS semiring to consider the existing cost specified in the startNodes vector
-         CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, min_times, null, null);
+         CommonOpsWithSemiRing_DSCC.mult(startNodes, adjacencyMatrix, outputVector, min_times, null, null, null);
          System.out.println("The minimal cost to reach the node 2 is " + outputVector.get(0, 2));
+     }
+}
 </syntaxhighlight>