Packages

p

scalation

graphalytics

package graphalytics

The graphalytics package contains classes, traits and objects for graph analytics on Trees, 'DAG's and Directed Graphs. It provides an implicit conversion when needed for converting doubles to vectors.

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. graphalytics
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Type Members

  1. class APShortestPath extends AnyRef

    The APShortestPath class is used to solve shortest path problems for graphs stored in matrices.

    The APShortestPath class is used to solve shortest path problems for graphs stored in matrices. It solves the All-Pairs Shortest Path 'APSP' problem for directed graphs. The edge cost/distance (must be non-negative) can be stored in either a dense or sparse matrix. The Floyd-Warshall Algorithm is used.

    See also

    math.stackexchange.com/questions/240556/radius-diameter-and-center-of-graph

    http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm 'APSP' can be used to determine a graph's eccentricities, radius and diameter. These can also be computed using a BFS-based algorithm.

  2. class Ball extends AnyRef

    The Ball class provides an implementation for ball construction.

    The Ball class provides an implementation for ball construction. A ball consists of all vertices within a given radius of a given center.

    See also

    ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6691601&tag=1&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6691601%26tag%3D1

  3. class BipartiteMatcher extends AnyRef

    The BipartiteMatcher class provides an implementation of finding maximal Bipartite Matching.

    The BipartiteMatcher class provides an implementation of finding maximal Bipartite Matching.

    See also

    www.geeksforgeeks.org/maximum-bipartite-matching/

  4. class ColorDAG extends AnyRef

    The ColorDAG class provides a data structure Directed Acyclic Graphs 'DAG's with colored nodes.

    The ColorDAG class provides a data structure Directed Acyclic Graphs 'DAG's with colored nodes. The ColorDAG consists of source nodes (in-degree is 0), sink nodes (out-degree is 0) and internal nodes. The edges connecting nodes must have color compatibility. The ColorDAG is divided into 'k' stages: e.g., sources (stage 0), internals (stages 1..k-2) and sinks (stage k-1).

  5. class DualIso extends GraphMatcher

    The DualIso class provides an implementation for Subgraph Isomorphism that uses Dual Graph Simulation for pruning.

  6. class DualSim extends GraphMatcher

    The DualSim class provides an implementation for Dual Graph Simulation.

  7. class DualSim2 extends GraphMatcher

    The DualSim2 class provides a second implementation for Dual Graph Simulation.

    The DualSim2 class provides a second implementation for Dual Graph Simulation. It differs from DualSim by not using inverse adjacency sets ('pa') in order to save space.

  8. class Graph extends Cloneable

    The Graph class stores vertex-labeled directed graphs using an adjacency set 'ch' representation, e.g., 'ch = { {1, 2}, {0}, {1} }' means that the graph has the following edges { (0, 1), (0, 2), (1, 0), (2, 1) }.

    The Graph class stores vertex-labeled directed graphs using an adjacency set 'ch' representation, e.g., 'ch = { {1, 2}, {0}, {1} }' means that the graph has the following edges { (0, 1), (0, 2), (1, 0), (2, 1) }. Optionally, inverse adjacency via the 'pa' array can be stored at the cost of nearly doubling the storage requirements. ----------------------------------------------------------------------------

  9. class GraphDFS extends AnyRef

    The GraphDFS performs Depth First Search (DFS) or Breadth First Search (BFS) on a Directed Graph.

    The GraphDFS performs Depth First Search (DFS) or Breadth First Search (BFS) on a Directed Graph. The class currently supports three predicates: (1) to find a matching label, and (2) to see if a destination vertex is reachable.

  10. class GraphIO extends AnyRef

    The GraphIO class is used to write graphs to a file.

  11. class GraphIso extends AnyRef

    The GraphIso class determines whether two labelled directed graphs are Graph Isomorphic.

  12. abstract class GraphMatcher extends AnyRef

    The GraphMatcher abstract class serves as a template for implementing specific algorithms for graph pattern matching.

  13. class GraphMetrics extends AnyRef

    The GraphMetrics class provides methods for determining graph metrics that can be efficiently computed using Breadth-First Search (BFS).

    The GraphMetrics class provides methods for determining graph metrics that can be efficiently computed using Breadth-First Search (BFS). This works for undirected graphs. If a directed graph is passed in, it will be converted to a corresponding undirected graph.

  14. class GraphSim2 extends GraphMatcher

    The GraphSim2 class provides a second implementation for Simple Graph Simulation.

    The GraphSim2 class provides a second implementation for Simple Graph Simulation. It differ from GraphSim in the looping order in the main for-loop and early termination when 'phi(u)' is empty.

  15. class GraphSimIso extends GraphMatcher

    The GraphSimIso object provides an implementation for Subgraph Isomorphism that uses an adjacency set version of Ullmann's Algorithm.

  16. class GraphqlOpt extends AnyRef

    The 'GraphqlOpt' class provides an implementation for Subgraph Isomorphism of GraphQL's Algorithm.

    The 'GraphqlOpt' class provides an implementation for Subgraph Isomorphism of GraphQL's Algorithm.

    See also

    http://cs.ucsb.edu/~dbl/papers/he_sigmod_2008.pdf (GraphQL paper)

  17. trait IsomorphismChecker extends AnyRef

    The IsomorphismChecker trait check the validity of the isomorphic matches between the query graph 'q' and subgraphs of the data graph 'g'.

  18. type Pair = (Int, Int)

    The EdgeType object define basic type for representing edges

  19. class StrictSim extends GraphMatcher

    The 'StrictSim' class provides an implementation for strict simulation graph pattern matching.

    The 'StrictSim' class provides an implementation for strict simulation graph pattern matching. This version uses DualSim.

    See also

    hipore.com/ijbd/2014/IJBD%20Vol%201%20No%201%202014.pdf

  20. class StrictSim2 extends GraphMatcher

    The 'StrictSim2' class provides an implementation for strict simulation graph pattern matching.

    The 'StrictSim2' class provides an implementation for strict simulation graph pattern matching. This version uses DualSim2.

    See also

    hipore.com/ijbd/2014/IJBD%20Vol%201%20No%201%202014.pdf FIX: try to implement without using parent references 'pa'.

  21. class TightSim extends GraphMatcher

    The 'TightSim' class provides an implementation for tight simulation graph pattern matching.

    The 'TightSim' class provides an implementation for tight simulation graph pattern matching. This version uses DualSim.

    See also

    hipore.com/ijbd/2014/IJBD%20Vol%201%20No%201%202014.pdf

  22. class TightSim2 extends GraphMatcher

    The 'TightSim2' class provides an implementation for tight simulation graph pattern matching.

    The 'TightSim2' class provides an implementation for tight simulation graph pattern matching. This version uses DualSim2.

    See also

    hipore.com/ijbd/2014/IJBD%20Vol%201%20No%201%202014.pdf FIX: try to implement without using parent references 'pa'.

  23. class Tree extends AnyRef

    The Tree class provides a data structure for multi-way trees with colored nodes.

  24. class TreeLayout extends AnyRef

    The TreeLayout class is used to display multi-way trees with the root at the top and leaves at the bottom.

    The TreeLayout class is used to display multi-way trees with the root at the top and leaves at the bottom. It is translated from the pseudo-code given in

    See also

    onlinelibrary.wiley.com/doi/10.1002/spe.713/pdf

    Appendix A of Christoph Buchheim, Michael Junger and Sebastian Leipert paper.

  25. class TreeNode extends AnyRef

    The TreeNode class is for a node in a tree.

Value Members

  1. val BASE_DIR: String

    The relative path for base directory

  2. val EXT: String

    The standard file extension for graphs

  3. object APShortestPath

    The APShortestPath companion object provides factory methods for the APShortestPath class.

  4. object APShortestPathTest extends App

    The APShortestPathTest object is used to test the APShortestPath class.

  5. object Ball

    The Ball companion object provides functions involving Balls.

  6. object BipartiteMatcherTest extends App

    The 'BipartiteMatcherTest' object is used to test BipartiteMatcher class.

  7. object ColorDAGTest extends App

    The ColorDAGTest object used to test the ColorDAG class.

  8. object Convert

    The Convert object is used to convert between an Adjacency Matrix representation to an Adjacency Sets representation.

  9. object ConvertTest extends App

    The ConvertTest object is used to test the Convert object.

    The ConvertTest object is used to test the Convert object. > run-main scalation.graphalytics.ConvertTest

  10. object Cycle

    The Cycle object provides a means for building a precedence/directed graph and checking it for cycles.

    The Cycle object provides a means for building a precedence/directed graph and checking it for cycles. For cycle detection, vertices are marked with traffic-light colors:

    • GreeN means go/unexplored,
    • YelloW means caution/been there before,
    • ReD mean stop/already fully explored.
  11. object CycleTest extends App

    The CycleTest object tests the Cycle object using a label-free precedence graph.

    The CycleTest object tests the Cycle object using a label-free precedence graph. Graphs are created by passing in an array of adjacency sets (one for each vertex). > run-main scalation.graphalytics.CycleTest

  12. object DualIsoTest extends App

    The DualIsoTest object is used to test the DualIso class.

    The DualIsoTest object is used to test the DualIso class. > run-main scalation.graphalytics.DualIsoTest

  13. object DualIsoTest2 extends App

    The DualIsoTest2 object is used to test the DualIso class.

    The DualIsoTest2 object is used to test the DualIso class. > run-main scalation.graphalytics.DualIsoTest2

  14. object DualIsoTest3 extends App

    The DualIsoTest3 object is used to test the DualIso class.

    The DualIsoTest3 object is used to test the DualIso class. > run-main scalation.graphalytics.DualIsoTest3

  15. object DualSim2Test extends App

    The DualSim2Test object is used to test the DualSim2 class.

    The DualSim2Test object is used to test the DualSim2 class. > run-main scalation.graphalytics.DualSim2Test

  16. object DualSim2Test2 extends App

    The DualSim2Test2 object is used to test the DualSim2 class.

    The DualSim2Test2 object is used to test the DualSim2 class. > run-main scalation.graphalytics.DualSim2Test2

  17. object DualSim2Test3 extends App

    The DualSim2Test3 object is used to test the 'DualSim2' class.

    The DualSim2Test3 object is used to test the 'DualSim2' class. > run-main scalation.graphalytics.DualSim2Test3

  18. object DualSimTest extends App

    The DualSimTest object is used to test the DualSim class.

    The DualSimTest object is used to test the DualSim class. > run-main scalation.graphalytics.DualSimTest

  19. object DualSimTest2 extends App

    The DualSimTest2 object is used to test the DualSim class.

    The DualSimTest2 object is used to test the DualSim class. > run-main scalation.graphalytics.DualSimTest2

  20. object DualSimTest3 extends App

    The DualSimTest3 object is used to test the DualSim class.

    The DualSimTest3 object is used to test the DualSim class. Read the query graph 'q' and data graph 'g' from files. > run-main scalation.graphalytics.DualSimTest3

  21. object Graph

    The Graph companion object contains the example query graphs.

  22. object GraphDFSTest extends App

    The GraphDFSTest is used to test the GraphDFS class.

    The GraphDFSTest is used to test the GraphDFS class. > run-main scalation.graphalytics.GraphDFSTest

  23. object GraphGen

    The GraphGen object is used to build random graph with various characteristics.

  24. object GraphGenTest extends App

    The GraphGenTest object is used to test the GraphGen class for building random graphs where a vertex's degree is uniformly distributed.

  25. object GraphGenTest2 extends App

    The GraphGenTest2 object is used to test the GraphGen class for building power law graphs.

  26. object GraphGenTest3 extends App

    The GraphGenTest3 object is used to test the GraphGen class for extracting query graphs from data graphs.

  27. object GraphIO

    The GraphIO object is the companion object to the GraphIO class and is used for reading graphs from files.

  28. object GraphIOTest extends App

    The GraphIOTest object is used to test the GraphIO class and object.

    The GraphIOTest object is used to test the GraphIO class and object. > run-main scalation.graphalytics.GraphIOTest

  29. object GraphIsoTest extends App

    The GraphIsoTest object is used to test the GraphIso class.

  30. object GraphMatcherTest extends App

    The 'GraphMatcherTest' object runs six pattern matching algorithms on the above test graph.

    The 'GraphMatcherTest' object runs six pattern matching algorithms on the above test graph. The algorithms tested are the following: GraphSim - Simple Graph Simulation GraphSim2 - Simple Graph Simulation (with early termination) DualSim - Dual Graph Simulation DualSim2 - Dual Graph Simulation (with reduced memory footprint) UllmannIso - Adjacency List Version of Ullmann's Subgraph Isomorphism Algorithm DualIso - Subgraph Isomorphism using Dual Simulation for Pruning

  31. object GraphMetricsTest extends App

    The GraphMetricsTest object is used to test the GraphMetrics class.

    The GraphMetricsTest object is used to test the GraphMetrics class.

    See also

    http://math.stackexchange.com/questions/240556/radius-diameter-and-center-of-graph

  32. object GraphSim2Test extends App

    The GraphSim2Test object is used to test the GraphSim2 class.

    The GraphSim2Test object is used to test the GraphSim2 class. > run-main scalation.graphalytics.GraphSim2Test

  33. object GraphSim2Test2 extends App

    The GraphSim2Test2 object is used to test the GraphSim2 class.

    The GraphSim2Test2 object is used to test the GraphSim2 class. > run-main scalation.graphalytics.GraphSim2Test2

  34. object GraphSim2Test3 extends App

    The GraphSim2Test3 object is used to test the GraphSim2 class.

    The GraphSim2Test3 object is used to test the GraphSim2 class. > run-main scalation.graphalytics.GraphSim2Test3

  35. object GraphSimIsoTest extends App

    The GraphSimIsoTest object is used to test the GraphSimIso class.

  36. object GraphTest extends App

    The GraphTest object is used to test the Graph class using the graphs given in the Graph companion object.

    The GraphTest object is used to test the Graph class using the graphs given in the Graph companion object. > run-main scalation.graphalytics.GraphTest

  37. object GraphTest2 extends App

    The GraphTest2 object is used to test the Graph class using a randomly generated graph.

    The GraphTest2 object is used to test the Graph class using a randomly generated graph. > run-main scalation.graphalytics.GraphTest2

  38. object GraphqlOptTest extends App

    The GraphqlOptTest object randomly generates the data graph and corresponding query graph to test GraphqlOpt class.

  39. object GraphqlOptTest2 extends App

    The GraphqlOptTest2 object test the GraphqlOpt class by feeding the value of data graph and query graph.

  40. object GraphqlOptTest3 extends App

    The GraphqlOptTest3 object test the GraphqlOpt class by feeding data graph and query graph relative file path.

  41. object LabelType

    The LabelType specifies (data) type for vertex and edge labels.

    The LabelType specifies (data) type for vertex and edge labels. TLabel must be a subtype of Ordering [Any].

    See also

    www.scala-lang.org/api/current/#scala.math.Ordering

  42. object StrictSim2Test extends App

    The StrictSim2Test object is used to test the StrictSim2 class.

    The StrictSim2Test object is used to test the StrictSim2 class. > run-main scalation.graphalytics.StrictSim2Test

  43. object StrictSim2Test2 extends App

    The StrictSim2Test2 object is used to test the StrictSim2 class.

    The StrictSim2Test2 object is used to test the StrictSim2 class. > run-main scalation.graphalytics.StrictSimTest2

  44. object StrictSim2Test3 extends App

    The StrictSim2Test3 object test the StrictSim2 class by passing data graph and query graph relative file paths.

    The StrictSim2Test3 object test the StrictSim2 class by passing data graph and query graph relative file paths. > run-main scalation.graphalytics.StrictSim2Test3

  45. object StrictSimTest extends App

    The StrictSimTest object is used to test the StrictSim class.

    The StrictSimTest object is used to test the StrictSim class. > run-main scalation.graphalytics.StrictSimTest

  46. object StrictSimTest2 extends App

    The StrictSimTest2 object is used to test the StrictSim class.

    The StrictSimTest2 object is used to test the StrictSim class. > run-main scalation.graphalytics.StrictSimTest2

  47. object StrictSimTest3 extends App

    The StrictSimTest3 object test the StrictSim class by passing data graph and query graph relative file paths.

    The StrictSimTest3 object test the StrictSim class by passing data graph and query graph relative file paths. > run-main scalation.graphalytics.StrictSimTest3

  48. object TestGraphContainer

    The GraphMatcherTest object creates data graph and query graph that can be used to test the results produced by the pattern matching algorithms.

    The GraphMatcherTest object creates data graph and query graph that can be used to test the results produced by the pattern matching algorithms.

    See also

    MS Thesis, "A Comparison of Techniques for Graph Analytics on Big Data"

  49. object TightSim2Test extends App

    The TightSim2Test object is used to test the TightSim2 class.

    The TightSim2Test object is used to test the TightSim2 class. > run-main scalation.graphalytics.TightSim2Test

  50. object TightSim2Test2 extends App

    The TightSim2Test2 object is used to test the TightSim2 class.

    The TightSim2Test2 object is used to test the TightSim2 class. > run-main scalation.graphalytics.TightSimTest2

  51. object TightSim2Test3 extends App

    The TightSim2Test3 object test the TightSim2 class by passing data graph and query graph relative file paths.

    The TightSim2Test3 object test the TightSim2 class by passing data graph and query graph relative file paths. > run-main scalation.graphalytics.TightSim2Test3

  52. object TightSimTest extends App

    The TightSimTest object is used to test the TightSim class.

    The TightSimTest object is used to test the TightSim class. > run-main scalation.graphalytics.TightSimTest

  53. object TightSimTest2 extends App

    The TightSimTest2 object is used to test the TightSim class.

    The TightSimTest2 object is used to test the TightSim class. > run-main scalation.graphalytics.TightSimTest2

  54. object TightSimTest3 extends App

    The TightSimTest3 object test the TightSim class by passing data graph and query graph relative file paths.

    The TightSimTest3 object test the TightSim class by passing data graph and query graph relative file paths. > run-main scalation.graphalytics.TightSimTest3

  55. object TopSort

    The TopSort object provides the 'topSort' method for creating a topological sort of the vertices in a directed graph.

    The TopSort object provides the 'topSort' method for creating a topological sort of the vertices in a directed graph. It also perform cycle detection.

  56. object TopSortTest extends App

    The TopSortTest object tests the TopSort object using a directed graph.

    The TopSortTest object tests the TopSort object using a directed graph. Graphs are created by passing in an array of adjacency sets (one for each vertex). > run-main scalation.graphalytics.TopSortTest

  57. object TrafficLight extends Enumeration

    The TrafficLight object is an enumeration object for traffic light colors.

    The TrafficLight object is an enumeration object for traffic light colors. Vertices are marked GreeN (unvisited), YelloW (processing), or ReD (done with).

  58. object Tree

    The Tree companion object provides methods for building trees.

    The Tree companion object provides methods for building trees. Toggle 'ANIMATE' flag to turn animation on/off.

  59. object TreeLayoutTest extends App

    The TreeLayoutTest object is used to test the TreeLayout class.

    The TreeLayoutTest object is used to test the TreeLayout class. > run-main scalation.graphalytics.TreeLayoutTest

  60. object TreeTest extends App

    The TreeTest object is used to test the Tree class by randomly building a tree.

    The TreeTest object is used to test the Tree class by randomly building a tree. > run-main scalation.graphalytics.TreeTest

  61. object TreeTest2 extends App

    The TreeTest2 object is used to test the Tree class by manually building a tree.

    The TreeTest2 object is used to test the Tree class by manually building a tree. > run-main scalation.graphalytics.TreeTest2

  62. object TreeTest3 extends App

    The TreeTest3 object is used to test the Tree class by manually building a tree.

    The TreeTest3 object is used to test the Tree class by manually building a tree. > run-main scalation.graphalytics.TreeTest3

  63. object TreeTest4 extends App

    The TreeTest4 object is used to test the Tree class by manually building a tree.

    The TreeTest4 object is used to test the Tree class by manually building a tree. No animation. > run-main scalation.graphalytics.TreeTest4

Inherited from AnyRef

Inherited from Any

Ungrouped