Packages

p

scalation

graph_db

package graph_db

The graph_db 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. graph_db
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Package Members

  1. package graph_algebra
  2. package pattern_matching

    The pattern_matching package contains classes, traits and objects for graph pattern matching such as graph simulation and subgraph isomorphism.

Type Members

  1. case class BiconnectedComp[TLabel](g_: Graph[TLabel]) extends Product with Serializable

    The BiconnectedComp class provides methods for finding the cut points and blocks in undirected graphs.

    The BiconnectedComp class provides methods for finding the cut points and blocks in undirected graphs. Removal of a cut point will make the graph disconnected. Cut points and blocks are also referred to as articulation points and biconnected components, respectively.

    g_

    the graph whose cut points/blocks are sought

  2. case class Block(_id: Int) extends Product with Serializable

    The Block class is used record information about biconnected components (blocks).

  3. class BoundedTreeWidthBN extends Error

    The BoundedTreeWidthBN class provides bounded treewidth Bayesian Networks.

  4. class Graph[TLabel] 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. ----------------------------------------------------------------------------

  5. class GraphDFS[TLabel] 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.

  6. class GraphGen[TLabel] extends Error

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

    The GraphGen object is used to build random graphs with various characteristics. Needs to generate vertex labels of various types including Int, Double, String, VectorD based on the TLabel type.

  7. class GraphIO[TLabel] extends Error

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

  8. class GraphMetrics[TLabel] 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.

  9. class MGraph[TLabel] extends Graph[TLabel] with Cloneable

    The MGraph class stores vertex/edge-labeled multi-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 MGraph class stores vertex/edge-labeled multi-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. ----------------------------------------------------------------------------

  10. class MGraphGen[TLabel] extends Error

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

    The MGraphGen object is used to build random graph with various characteristics. Needs to generate vertex labels of various types including Int, Double, String, VectorD based on the TLabel type.

  11. class MGraphIO[TLabel] extends Error

    The MGraphIO class is used to write multi-digraphs to a file.

  12. class MinSpanningTree extends Error

    The MinSpanningTree class is used to build minimum cost spanning trees from graphs.

    The MinSpanningTree class is used to build minimum cost spanning trees from graphs. Edge cost/weights are given by edge labels. MinSpanningTree implements Prim's algorithm.

    See also

    www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf

  13. type Pair = (Int, Int)

    The EdgeType object define basic type for representing edges

  14. class Partition[TLabel] extends AnyRef

    The Partition class is used to partition large directed graphs.

    The Partition class is used to partition large directed graphs. It support the following three algorithms: 'group_ran', 'group_ord', 'group_lp'.

    (1) Random Partitioning - excellent balance, poor edge cuts Each vertex is given a randomly assigned integer label 'ilabel' and is grouped accordingly.

    (2) Ordered Partitioning - excellence balance, edge cuts may or may not be good Each vertex is assigned an integer label 'ilabel' incrementally and is grouped accordingly, e.g., {0, 1, ..., 9}, {10, 11, ..., 19}, ...

    (3) Label Propagation partitioning - fair balance, fair edge cuts Each vertex is initially given a unique integer label 'ilabel'. On each iteration, each vertex will have its 'ilabel' reassigned to the most popular/frequent 'ilabel' in its neighborhood (which includes its children, parents and itself).

    See also

    research.microsoft.com/pubs/183714/Partition.pdf ----------------------------------------------------------------------------

  15. class SSShortestPath extends AnyRef

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

    The SSShortestPath class is used to solve shortest path problems for graphs stored in matrices. It solves the Single-Source Shortest Path 'SSSP' problem for directed graphs (both digraphs and multi-digraphs). The SSShortestPath companion object is used to form a matrix from an MGraph. ---------------------------------------------------------------------------- The edge cost/distance (must be non-negative) can be stored in either a dense or sparse matrix. Dijkstra's Algorithm is used.

    See also

    en.wikipedia.org/wiki/Dijkstra%27s_algorithm ---------------------------------------------------------------------------- For multi-digraphs, each multi-edge between a pair vertices has it own edge weight (TLabel = VectorD in this case). The minimum is taking when forming the corresponding matrix.

    thescipub.com/PDF/jcssp.2013.377.382.pdf ----------------------------------------------------------------------------

  16. class SpanningTree extends Error

    The SpanningTree class is used to build spanning trees from graphs.

  17. class Tree[TLabel] extends AnyRef

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

  18. class TreeNode[TLabel] 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 BiconnectedCompTest extends App

    The BiconnectedCompTest object tests the BiconnectedComp class.

    The BiconnectedCompTest object tests the BiconnectedComp class.

    See also

    www.geeksforgeeks.org/biconnected-components > runMain scalation.graph_db.BiconnectedCompTest

  4. object BiconnectedCompTest2 extends App

    The BiconnectedCompTest2 object tests the BiconnectedComp class.

    The BiconnectedCompTest2 object tests the BiconnectedComp class. See Figure 7.a in

    See also

    pluto.huji.ac.il/~galelidan/papers/ElidanGouldJMLR.pdf > runMain scalation.graph_db.BiconnectedCompTest2

  5. object BoundedTreeWidthBNTest extends App

    The BoundedTreeWidthBNTest is used to test the BoundedTreeWidthBN class.

    The BoundedTreeWidthBNTest is used to test the BoundedTreeWidthBN class. > runMain scalation.graph_db.BoundedTreeWidthBNTest

  6. object BoundedTreeWidthChains

    The BoundedTreeWidthChains object is used to find bounded tree width chains to add edges to a Bayesian Network graph.

  7. 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.
  8. object CycleTest extends App

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

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

  9. object ExampleGraphD

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

  10. object ExampleGraphI

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

  11. object ExampleGraphS

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

  12. object ExampleMGraphD

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

  13. object ExampleMGraphI

    The ExampleMGraphI object contains example query and data multi-digraphs in which the vertex label type TLabel is Int.

  14. object ExampleMGraphS

    The ExampleMGraphS object contains example query and data multi-digraphs in which the vertex label type TLabel is String.

  15. object Graph

    The Graph companion object contains build methods and example query digraphs.

  16. 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.mutable.GraphDFSTest

  17. object GraphGen

    The GraphGen companion object provides simple methods for creating data and query graphs.

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

    The GraphGenTest object is used to test the GraphGen class for building random graphs where a vertex's degree is uniformly distributed. This work build graphs with Int vertex labels. > runMain scalation.graph_db.GraphGenTest

  19. object GraphGenTest2 extends App

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

    The GraphGenTest2 object is used to test the GraphGen class for building random graphs where a vertex's degree is uniformly distributed. This work build graphs with Double vertex labels. > runMain scalation.graph_db.GraphGenTest2

  20. object GraphGenTest3 extends App

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

    The GraphGenTest3 object is used to test the GraphGen class for building random graphs where a vertex's degree is uniformly distributed. This work build graphs with String vertex labels. > runMain scalation.graph_db.GraphGenTest3

  21. object GraphGenTest4 extends App

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

    The GraphGenTest4 object is used to test the GraphGen class for building power law graphs. > runMain scalation.graph_db.GraphGenTest4

  22. object GraphGenTest5 extends App

    The GraphGenTest5 object is used to test the GraphGen class for extracting query graphs from data graphs (note: data graph should be connected).

    The GraphGenTest5 object is used to test the GraphGen class for extracting query graphs from data graphs (note: data graph should be connected). > runMain scalation.graph_db.GraphGenTest5

  23. object GraphGenTest6 extends App

    The GraphGenTest6 object is used to test the GraphGen companion object for generating both data and query graphs.

    The GraphGenTest6 object is used to test the GraphGen companion object for generating both data and query graphs. > runMain scalation.graph_db.GraphGenTest6

  24. object GraphGenTest7 extends App

    The GraphGenTest7 object is used to test the GraphGen companion object for generating data graphs.

    The GraphGenTest7 object is used to test the GraphGen companion object for generating data graphs. > runMain scalation.graph_db.GraphGenTest7

  25. object GraphGenTest8 extends App

    The GraphGenTest8 object is used to test the GraphGen companion object for generating both data and query graphs.

    The GraphGenTest8 object is used to test the GraphGen companion object for generating both data and query graphs. > runMain scalation.graph_db.GraphGenTest8

  26. object GraphIO extends Error

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

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

  28. object GraphMetrics

    The GraphMetrics companion object provides basic statistics about graphs.

  29. 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 > runMain scalation.garphalytics.mutable.GraphMetricsTest

  30. object GraphTest extends App

    The GraphTest object is used to test the Graph class using example digraphs from the ExampleGraphI object, which contains graph whose vertex labels are of type Int.

    The GraphTest object is used to test the Graph class using example digraphs from the ExampleGraphI object, which contains graph whose vertex labels are of type Int. > runMain scalation.graph_db.GraphTest

  31. object GraphTest2 extends App

    The GraphTest2 object is used to test the Graph class using example digraphs from the ExampleGraphD object, which contains graph whose vertex labels are of type Double.

    The GraphTest2 object is used to test the Graph class using example digraphs from the ExampleGraphD object, which contains graph whose vertex labels are of type Double. > runMain scalation.graph_db.GraphTest2

  32. object GraphTest3 extends App

    The GraphTest3 object is used to test the Graph class using the digraphs given in the Graph companion object.

    The GraphTest3 object is used to test the Graph class using the digraphs given in the Graph companion object. > runMain scalation.graph_db.GraphTest3

  33. object GraphTest4 extends App

    The GraphTest4 object is used to test the Graph class by calling the apply in the Graph companion object.

    The GraphTest4 object is used to test the Graph class by calling the apply in the Graph companion object. > runMain scalation.graph_db.GraphTest4

  34. object GraphTest5 extends App

    The GraphTest5 object is used to test the Graph class by calling the apply in the Graph companion object.

    The GraphTest5 object is used to test the Graph class by calling the apply in the Graph companion object. > runMain scalation.graph_db.GraphTest5

  35. object MGraph

    The MGraph companion object provides builder methods and example query multi-digraphs.

  36. object MGraphGen

    The MGraphGen companion object provides simple methods for creating data and query graphs.

  37. object MGraphGenTest extends App

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

    The 'MGraphGenTest' object is used to test the 'MGraphGen' class for building random graphs where a vertex's degree is uniformly distributed. This work build graphs with Int vertex/edge labels. > runMain scalation.graph_db.MGraphGenTest

  38. object MGraphGenTest2 extends App

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

    The MGraphGenTest2 object is used to test the MGraphGen class for building random graphs where a vertex's degree is uniformly distributed. This work build graphs with Double vertex/edge labels. > runMain scalation.graph_db.MGraphGenTest2

  39. object MGraphGenTest3 extends App

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

    The MGraphGenTest3 object is used to test the MGraphGen class for building random graphs where a vertex's degree is uniformly distributed. This work build graphs with String vertex/edge labels. > runMain scalation.graph_db.MGraphGenTest3

  40. object MGraphGenTest4 extends App

    The 'MGraphGenTest4' object is used to test the 'MGraphGen' class for building power law graphs.

    The 'MGraphGenTest4' object is used to test the 'MGraphGen' class for building power law graphs. > runMain scalation.graph_db.MGraphGenTest4

  41. object MGraphGenTest5 extends App

    The MGraphGenTest5 object is used to test the MGraphGen class for extracting query graphs from data graphs (note: data graph should be connected).

    The MGraphGenTest5 object is used to test the MGraphGen class for extracting query graphs from data graphs (note: data graph should be connected). > runMain scalation.graph_db.MGraphGenTest5

  42. object MGraphGenTest6 extends App

    The MGraphGenTest6 object is used to test the MGraphGen companion object for generating both data and query graphs.

    The MGraphGenTest6 object is used to test the MGraphGen companion object for generating both data and query graphs. > runMain scalation.graph_db.MGraphGenTest6

  43. object MGraphGenTest7 extends App

    The MGraphGenTest7 object is used to test the MGraphGen companion object for generating data graphs.

    The MGraphGenTest7 object is used to test the MGraphGen companion object for generating data graphs. > runMain scalation.graph_db.MGraphGenTest7

  44. object MGraphGenTest8 extends App

    The MGraphGenTest8 object is used to test the MGraphGen companion object for generating both data and query graphs.

    The MGraphGenTest8 object is used to test the MGraphGen companion object for generating both data and query graphs. > runMain scalation.graph_db.MGraphGenTest8

  45. object MGraphIO extends Error

    The MGraphIO object is the companion object to the MGraphIO class and is used for reading graphs from files or graph databases.

  46. object MGraphIOTest extends App

    The MGraphIOTest object is used to test the MGraphIO class and object.

    The MGraphIOTest object is used to test the MGraphIO class and object. > runMain scalation.graph_db.MGraphIOTest

  47. object MGraphTest extends App

    The MGraphTest object is used to test the MGraph class using examples from the ExampleMGraphI object, which contains multi-digraphs whose vertex and edge labels are of type Int.

    The MGraphTest object is used to test the MGraph class using examples from the ExampleMGraphI object, which contains multi-digraphs whose vertex and edge labels are of type Int. > runMain scalation.graph_db.MGraphTest

  48. object MGraphTest2 extends App

    The MGraphTest2 object is used to test the MGraph class using examples from the ExampleMGraphD object, which contains multi-digraphs whose vertex and edge labels are of type Double.

    The MGraphTest2 object is used to test the MGraph class using examples from the ExampleMGraphD object, which contains multi-digraphs whose vertex and edge labels are of type Double. > runMain scalation.graph_db.MGraphTest2

  49. object MinSpanningTreeTest extends App

    The MinSpanningTreeTest object is used to test the MinSpanningTree class.

    The MinSpanningTreeTest object is used to test the MinSpanningTree class. > runMain scalation.graph_db.MinSpanningTreeTest

  50. object MinSpanningTreeTest2 extends App

    The MinSpanningTreeTest2 object is used to test the MinSpanningTree class.

    The MinSpanningTreeTest2 object is used to test the MinSpanningTree class.

    See also

    www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf > runMain scalation.graph_db.MinSpanningTreeTest2

  51. object MinSpanningTreeTest3 extends App

    The MinSpanningTreeTest3 object is used to test the MinSpanningTree class.

    The MinSpanningTreeTest3 object is used to test the MinSpanningTree class. This test the Maximum Spanning Tree option.

    See also

    www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf > runMain scalation.graph_db.MinSpanningTreeTest3

  52. object PartitionTest extends App

    The PartitionTest object is used to test the Partition class.

    The PartitionTest object is used to test the Partition class. This test uses random partitioning. > runMain scalation.graph_db.PartitionTest

  53. object PartitionTest2 extends App

    The PartitionTest2 object is used to test the Partition class.

    The PartitionTest2 object is used to test the Partition class. This test uses ordered partitioning. > runMain scalation.graph_db.PartitionTest2

  54. object PartitionTest3 extends App

    The PartitionTest3 object is used to test the Partition class.

    The PartitionTest3 object is used to test the Partition class. This test uses label propagation for partitioning. > runMain scalation.graph_db.PartitionTest3

  55. object SSShortestPath

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

  56. object SSShortestPathTest extends App

    The SSShortestPathTest object is used to test the SSShortestPath class.

    The SSShortestPathTest object is used to test the SSShortestPath class. Input is in the form of matrices (MatrixD or SparseMatrixD). > runMain scalation.graph_db.SSShortestPathTest

  57. object SSShortestPathTest2 extends App

    The SSShortestPathTest2 object is used to test the SSShortestPath class.

    The SSShortestPathTest2 object is used to test the SSShortestPath class. Input is in the form of graphs (MGraph).

    See also

    http://thescipub.com/PDF/jcssp.2013.377.382.pdf (Fig. 1) > runMain scalation.graph_db.SSShortestPathTest2

  58. object SpanningTreeTest extends App

    The SpanningTreeTest object is used to test the SpanningTree class.

    The SpanningTreeTest object is used to test the SpanningTree class. > runMain scalation.graph_db.SpanningTreeTest

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

  60. 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.graph_db.TopSortTest

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

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

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

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

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

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