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. Protected

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

    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.

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

  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 DualIsoCAR extends GraphMatcher

    The DualIsoCAR classes used DualSim2CAR for pruning, otherwise it works like DualIso, which uses DualSim2 for pruning.

  7. class DualSim extends GraphMatcher

    The DualSim class provides an implementation for Dual Graph Simulation.

  8. 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.

  9. class DualSim2CAR extends GraphMatcher

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

    The DualSim2CAR 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. It also enforces the cardinality restriction.

  10. 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. ----------------------------------------------------------------------------

  11. 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.

  12. class GraphIO extends AnyRef

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

  13. class GraphIso extends AnyRef

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

  14. abstract class GraphMatcher extends AnyRef

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

  15. 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.

  16. class GraphSim extends GraphMatcher

    The GraphSim class provides an implementation for Simple Graph Simulation.

  17. 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.

  18. class GraphSimIso extends GraphMatcher

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

  19. 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)

  20. 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'.

  21. type Pair = (Int, Int)

    The EdgeType object define basic type for representing edges

  22. 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

  23. 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'.

  24. 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

  25. 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'.

  26. class Tree extends AnyRef

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

  27. 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

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

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

  28. 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. def stringArray(a: Any*): Array[String]

    Convert the arguments to an array of strings.

    Convert the arguments to an array of strings.

    a

    the arguments

  4. object APShortestPath

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

  5. object APShortestPathTest extends App

    The APShortestPathTest object is used to test the APShortestPath class.

  6. object Answers

    The Answers object is used to test all the Graph pattern matchers.

  7. object Ball

    The Ball companion object provides functions involving Balls.

  8. object BipartiteMatcherTest extends App

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

  9. object ColorDAGTest extends App

    The ColorDAGTest object used to test the ColorDAG class.

  10. object Convert

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

  11. object ConvertTest extends App

    The ConvertTest object is used to test the Convert object.

    The ConvertTest object is used to test the Convert object. > runMain scalation.graphalytics.ConvertTest

  12. 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.
  13. 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). > runMain scalation.graphalytics.CycleTest

  14. object DualIsoCARTest extends App

    The DualIsoCARTest object is used to test the DualIsoCAR class.

    The DualIsoCARTest object is used to test the DualIsoCAR class. runMain scalation.graphalytics.DualIsoCARTest

  15. object DualIsoCARTest2 extends App

    The DualIsoCARTest2 object is used to test the DualIsoCAR class.

    The DualIsoCARTest2 object is used to test the DualIsoCAR class. runMain scalation.graphalytics.DualIsoCARTest2

  16. object DualIsoTest extends App

    The DualIsoTest object is used to test the DualIso class.

    The DualIsoTest object is used to test the DualIso class. > runMain scalation.graphalytics.DualIsoTest

  17. object DualIsoTest2 extends App

    The DualIsoTest2 object is used to test the DualIso class.

    The DualIsoTest2 object is used to test the DualIso class. > runMain scalation.graphalytics.DualIsoTest2

  18. object DualIsoTest3 extends App

    The DualIsoTest3 object is used to test the DualIso class.

    The DualIsoTest3 object is used to test the DualIso class. > runMain scalation.graphalytics.DualIsoTest3

  19. object DualSim2CARTest 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.DualSim2CARTest

  20. object DualSim2CARTest2 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.DualSim2CARTest2

  21. object DualSim2CARTest3 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.DualSim2CARTest3

  22. object DualSim2Test extends App

    The DualSim2Test object is used to test the DualSim2 class.

    The DualSim2Test object is used to test the DualSim2 class. > runMain scalation.graphalytics.DualSim2Test

  23. object DualSim2Test2 extends App

    The DualSim2Test2 object is used to test the DualSim2 class.

    The DualSim2Test2 object is used to test the DualSim2 class. > runMain scalation.graphalytics.DualSim2Test2

  24. object DualSim2Test3 extends App

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

    The DualSim2Test3 object is used to test the 'DualSim2' class. > runMain scalation.graphalytics.DualSim2Test3

  25. object DualSimTest extends App

    The DualSimTest object is used to test the DualSim class.

    The DualSimTest object is used to test the DualSim class. > runMain scalation.graphalytics.DualSimTest

  26. object DualSimTest2 extends App

    The DualSimTest2 object is used to test the DualSim class.

    The DualSimTest2 object is used to test the DualSim class. > runMain scalation.graphalytics.DualSimTest2

  27. 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. > runMain scalation.graphalytics.DualSimTest3

  28. object ExampleGraphS

    The ExampleGraphS object contains example query and data digraphs in which the vertex label type TLabel is Double.

  29. object Graph

    The Graph companion object contains the example query graphs.

  30. object GraphDFSTest extends App

    The GraphDFSTest is used to test the GraphDFS class.

    The GraphDFSTest is used to test the GraphDFS class. > runMain scalation.graphalytics.GraphDFSTest

  31. object GraphGen

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

  32. 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.

  33. object GraphGenTest2 extends App

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

  34. object GraphGenTest3 extends App

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

  35. object GraphIO

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

  36. 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. > runMain scalation.graphalytics.GraphIOTest

  37. object GraphIsoTest extends App

    The GraphIsoTest object is used to test the GraphIso class.

    The GraphIsoTest object is used to test the GraphIso class. > runMain scalation.graphalytics.GraphIsoTest

  38. 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 > runMain scalation.graphalytics.GraphMatcherTest

  39. 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

  40. object GraphPatternTest extends App

    The GraphPatternTest object is used to test all the Graph pattern matchers.

    The GraphPatternTest object is used to test all the Graph pattern matchers. > runMain scalation.graphalytics.GraphPatternTest

  41. object GraphSim2Test extends App

    The GraphSim2Test object is used to test the GraphSim2 class.

    The GraphSim2Test object is used to test the GraphSim2 class. > runMain scalation.graphalytics.GraphSim2Test

  42. object GraphSim2Test2 extends App

    The GraphSim2Test2 object is used to test the GraphSim2 class.

    The GraphSim2Test2 object is used to test the GraphSim2 class. > runMain scalation.graphalytics.GraphSim2Test2

  43. object GraphSim2Test3 extends App

    The GraphSim2Test3 object is used to test the GraphSim2 class.

    The GraphSim2Test3 object is used to test the GraphSim2 class. > runMain scalation.graphalytics.GraphSim2Test3

  44. object GraphSimIsoTest extends App

    The GraphSimIsoTest object is used to test the GraphSimIso class.

  45. object GraphSimTest extends App

    The GraphSimTest object is used to test the GraphSim class.

    The GraphSimTest object is used to test the GraphSim class. > runMain scalation.graphalytics.GraphSimTest

  46. object GraphSimTest2 extends App

    The GraphSimTest2 object is used to test the GraphSim class.

    The GraphSimTest2 object is used to test the GraphSim class. > runMain scalation.graphalytics.GraphSimTest2

  47. 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. > runMain scalation.graphalytics.GraphTest

  48. 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. > runMain scalation.graphalytics.GraphTest2

  49. object GraphqlOptTest extends App

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

  50. object GraphqlOptTest2 extends App

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

  51. object GraphqlOptTest3 extends App

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

  52. 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

  53. object StrictSim2Test extends App

    The StrictSim2Test object is used to test the StrictSim2 class.

    The StrictSim2Test object is used to test the StrictSim2 class. > runMain scalation.graphalytics.StrictSim2Test

  54. object StrictSim2Test2 extends App

    The StrictSim2Test2 object is used to test the StrictSim2 class.

    The StrictSim2Test2 object is used to test the StrictSim2 class. > runMain scalation.graphalytics.StrictSimTest2

  55. 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. > runMain scalation.graphalytics.StrictSim2Test3

  56. object StrictSimTest extends App

    The StrictSimTest object is used to test the StrictSim class.

    The StrictSimTest object is used to test the StrictSim class. > runMain scalation.graphalytics.StrictSimTest

  57. object StrictSimTest2 extends App

    The StrictSimTest2 object is used to test the StrictSim class.

    The StrictSimTest2 object is used to test the StrictSim class. > runMain scalation.graphalytics.StrictSimTest2

  58. 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. > runMain scalation.graphalytics.StrictSimTest3

  59. 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"

  60. object TightSim2Test extends App

    The TightSim2Test object is used to test the TightSim2 class.

    The TightSim2Test object is used to test the TightSim2 class. > runMain scalation.graphalytics.TightSim2Test

  61. object TightSim2Test2 extends App

    The TightSim2Test2 object is used to test the TightSim2 class.

    The TightSim2Test2 object is used to test the TightSim2 class. > runMain scalation.graphalytics.TightSimTest2

  62. 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. > runMain scalation.graphalytics.TightSim2Test3

  63. object TightSimTest extends App

    The TightSimTest object is used to test the TightSim class.

    The TightSimTest object is used to test the TightSim class. > runMain scalation.graphalytics.TightSimTest

  64. object TightSimTest2 extends App

    The TightSimTest2 object is used to test the TightSim class.

    The TightSimTest2 object is used to test the TightSim class. > runMain scalation.graphalytics.TightSimTest2

  65. 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. > runMain scalation.graphalytics.TightSimTest3

  66. 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.

  67. 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). > runMain scalation.graphalytics.TopSortTest

  68. 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).

  69. 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.

  70. object TreeLayoutTest extends App

    The TreeLayoutTest object is used to test the TreeLayout class.

    The TreeLayoutTest object is used to test the TreeLayout class. > runMain scalation.graphalytics.TreeLayoutTest

  71. 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. > runMain scalation.graphalytics.TreeTest

  72. 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. > runMain scalation.graphalytics.TreeTest2

  73. 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. > runMain scalation.graphalytics.TreeTest3

  74. 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. > runMain scalation.graphalytics.TreeTest4

Inherited from AnyRef

Inherited from Any

Ungrouped