scalation
API
Generated with
scalation/scalation/scalation.database/scalation.database.graph_pm

scalation.database.graph_pm

package scalation.database.graph_pm

Members list

Type members

Classlikes

class DualIso(g: Graph, q: Graph) extends GraphMatcher

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

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

Value parameters

g

the data graph G(V, E, l)

q

the query graph Q(U, D, k)

Attributes

Supertypes
trait GraphMatcher
class Object
trait Matchable
class Any
class DualSim(g: Graph, q: Graph) extends GraphMatcher

The DualSim class provides an implementation for Dual Graph Simulation. It differs from other algorithms by not using inverse adjacency sets (pa) in order to save space.

The DualSim class provides an implementation for Dual Graph Simulation. It differs from other algorithms by not using inverse adjacency sets (pa) in order to save space.

Value parameters

g

the data graph G(V, E, l)

q

the query graph Q(U, D, k)

Attributes

Supertypes
trait GraphMatcher
class Object
trait Matchable
class Any
object ExampleGraphD

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

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

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
object ExampleGraphS

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

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

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
case class Graph(ch: Array[Set[Int]], label: Array[ValueType], elabel: Map[(Int, Int), ValueType], inverse: Boolean, name: String, schema: Array[String]) extends Cloneable

The Graph class stores vertex/edge-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.

Value parameters

ch

the array of child (adjacency) vertex sets (outgoing edges)

elabel

the map of edge labels: (u, v) -> edge label

inverse

whether to store inverse adjacency sets (parents)

label

the array of vertex labels: v -> vertex label

name

the name of the digraph

schema

optional schema: map from label to label type

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait Cloneable
class Object
trait Matchable
class Any
Show all
object Graph

The Graph companion object provides builder methods and example query digraphs.

The Graph companion object provides builder methods and example query digraphs.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
Graph.type
case class Graph0(ch: Array[Set[Int]], label: Array[ValueType], inverse: Boolean, name: String) extends Cloneable

The Graph0 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.

Value parameters

ch

the array of child (adjacency) vertex sets (outgoing edges)

inverse

whether to store inverse adjacency sets (parents)

label

the array of vertex labels: v -> vertex label

name

the name of the digraph

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait Cloneable
class Object
trait Matchable
class Any
Show all
class GraphDFS(g: Graph, bfs: Boolean)

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.

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.

Value parameters

bfs

switch from DFS to BFS, if bfs flag is true (defaults to false)

g

the directed graph to search

Attributes

Supertypes
class Object
trait Matchable
class Any
class GraphGen(typeSelector: Char, stream: Int)

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

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

Value parameters

stream

the random number stream to use (0 to 999)

typeSelector

the variable for type matches (work around for generic erasure)

Attributes

Companion
object
Supertypes
class Object
trait Matchable
class Any
object GraphGen

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

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

Attributes

Companion
class
Supertypes
class Object
trait Matchable
class Any
Self type
GraphGen.type
class GraphIO(g: Graph)

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

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

Value parameters

g

the digraph to write

Attributes

Companion
object
Supertypes
class Object
trait Matchable
class Any
object GraphIO

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

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

Attributes

Companion
class
Supertypes
class Object
trait Matchable
class Any
Self type
GraphIO.type
trait GraphMatcher(g: Graph, q: Graph)

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

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

Value parameters

g

the data graph G(V, E, l) with vertices v in V

q

the query graph Q(U, D, k) with vertices u in U

Attributes

Supertypes
class Object
trait Matchable
class Any
Known subtypes
class DualIso
class DualSim
class GraphSim
class GraphMetrics(val g: Graph, isUndirected: Boolean)

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.

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.

Value parameters

g

the graph whose metrics are sought

isUndirected

indicates whether the graph is undirected

Attributes

Companion
object
Supertypes
class Object
trait Matchable
class Any
object GraphMetrics

The GraphMetrics companion object provides basic statistics about graphs.

The GraphMetrics companion object provides basic statistics about graphs.

Attributes

Companion
class
Supertypes
class Object
trait Matchable
class Any
Self type
class GraphSim(g: Graph, q: Graph) extends GraphMatcher

The GraphSim class provides an implementation for Simple Graph Simulation. For each vertex in a query graph q, it returns all matching vertices in the data graph g with the same vertex label and matching children.

The GraphSim class provides an implementation for Simple Graph Simulation. For each vertex in a query graph q, it returns all matching vertices in the data graph g with the same vertex label and matching children.

Value parameters

g

the data graph G(V, E, l)

q

the query graph Q(U, D, k)

Attributes

See also
Supertypes
trait GraphMatcher
class Object
trait Matchable
class Any
object MatchAnswers

The MatchAnswers object contains answers for the graph matching problem given in the following paper: John A. Miller, Lakshmish Ramaswamy, Arash J.Z. Fard and Krys J. Kochut, "Research Directions in Big Data Graph Analytics," Proceedings of the 4th IEEE International Congress on Big Data (ICBD'15), New York, New York (June-July 2015) pp. 785-794. FIX: merge with Answers.

The MatchAnswers object contains answers for the graph matching problem given in the following paper: John A. Miller, Lakshmish Ramaswamy, Arash J.Z. Fard and Krys J. Kochut, "Research Directions in Big Data Graph Analytics," Proceedings of the 4th IEEE International Congress on Big Data (ICBD'15), New York, New York (June-July 2015) pp. 785-794. FIX: merge with Answers.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
class ShortestPath(c: MatrixD, s: Int)

To extend to multi-digraphs, each multi-edge between a pair vertices has it own edge weight. Take the minimum when forming the corresponding matrix.

The ShortestPath 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. The ShortestPath companion object is used to form a matrix from a Graph.

The edge cost/distance (must be non-negative) is stored in a dense matrix. Dijkstra's Algorithm is used: @see en.wikipedia.org/wiki/Dijkstra%27s_algorithm

To extend to multi-digraphs, each multi-edge between a pair vertices has it own edge weight. Take the minimum when forming the corresponding matrix.

Value parameters

c

the cost/distance matrix, where a value of zero implies no connection. If the actual distance is zero, use a very small number instead.

s

the single-source vertex

Attributes

See also
Companion
object
Supertypes
class Object
trait Matchable
class Any
object ShortestPath

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

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

Attributes

Companion
class
Supertypes
class Object
trait Matchable
class Any
Self type
object TopSort

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

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

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
TopSort.type
enum TrafficLight

The TrafficLight object is an enumeration type for traffic light colors. Vertices are marked Green (unvisited), Yellow (processing), or Red (done with).

The TrafficLight object is an enumeration type for traffic light colors. Vertices are marked Green (unvisited), Yellow (processing), or Red (done with).

Attributes

Supertypes
trait Enum
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
final class dualIsoTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class dualIsoTest2

Attributes

Supertypes
class Object
trait Matchable
class Any
final class dualIsoTest3

Attributes

Supertypes
class Object
trait Matchable
class Any
final class dualSimTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class dualSimTest2

Attributes

Supertypes
class Object
trait Matchable
class Any
final class dualSimTest3

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphDFSTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest2

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest3

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest4

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest5

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest6

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest7

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphGenTest8

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphIOTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphMetricsTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphSimTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphSimTest2

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphSimTest3

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphSimTest4

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphTest2

Attributes

Supertypes
class Object
trait Matchable
class Any
final class graphTest4

Attributes

Supertypes
class Object
trait Matchable
class Any
final class matchAnswersTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class shortestPathTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class shortestPathTest2

Attributes

Supertypes
class Object
trait Matchable
class Any
final class topSortTest

Attributes

Supertypes
class Object
trait Matchable
class Any

Value members

Concrete methods

def dualIsoTest(): Unit

The dualIsoTest main function is used to test the DualIso class.

The dualIsoTest main function is used to test the DualIso class.

runMain scalation.database.graph_pm.dualIsoTest

Attributes

def dualIsoTest2(): Unit

The dualIsoTest2 main function is used to test the DualIso class.

The dualIsoTest2 main function is used to test the DualIso class.

runMain scalation.database.graph_pm.dualIsoTest2

Attributes

def dualIsoTest3(): Unit

The dualIsoTest3 main function is used to test the DualIso class.

The dualIsoTest3 main function is used to test the DualIso class.

runMain scalation.database.graph_pm.dualIsoTest3

Attributes

def dualSimTest(): Unit

The dualSimTest main function is used to test the DualSim class.

The dualSimTest main function is used to test the DualSim class.

runMain scalation.database.graph_pm.dualSimTest

Attributes

def dualSimTest2(): Unit

The dualSimTest2 main function is used to test the DualSim class.

The dualSimTest2 main function is used to test the DualSim class.

runMain scalation.database.graph_pm.dualSimTest2

Attributes

def dualSimTest3(): Unit

The dualSimTest3 main function is used to test the DualSim class.

The dualSimTest3 main function is used to test the DualSim class.

runMain scalation.database.graph_pm.dualSimTest3

Attributes

def graphDFSTest(): Unit

The graphDFSTest main function is used to test the GraphDFS class.

The graphDFSTest main function is used to test the GraphDFS class.

runMain scalation.database.graph_pm.graphDFSTest

Attributes

def graphGenTest(): Unit

The graphGenTest main function 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/edge labels.

The graphGenTest main function 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/edge labels.

runMain scalation.database.graph_pm.graphGenTest

Attributes

def graphGenTest2(): Unit

The graphGenTest2 main function 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/edge labels.

The graphGenTest2 main function 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/edge labels.

runMain scalation.database.graph_pm.graphGenTest2

Attributes

def graphGenTest3(): Unit

The graphGenTest3 main function 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/edge labels.

The graphGenTest3 main function 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/edge labels.

runMain scalation.database.graph_pm.graphGenTest3

Attributes

def graphGenTest4(): Unit

The graphGenTest4 main function is used to test the GraphGen class for building power law graphs.

The graphGenTest4 main function is used to test the GraphGen class for building power law graphs.

runMain scalation.database.graph_pm.graphGenTest4

Attributes

def graphGenTest5(): Unit

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

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

runMain scalation.database.graph_pm.graphGenTest5

Attributes

def graphGenTest6(): Unit

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

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

runMain scalation.database.graph_pm.graphGenTest6

Attributes

def graphGenTest7(): Unit

The graphGenTest7 main function is used to test the GraphGen companion object for generating data graphs.

The graphGenTest7 main function is used to test the GraphGen companion object for generating data graphs.

runMain scalation.database.graph_pm.graphGenTest7

Attributes

def graphGenTest8(): Unit

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

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

runMain scalation.database.graph_pm.graphGenTest8

Attributes

def graphIOTest(): Unit

The graphIOTest main function is used to test the GraphIO class and object.

The graphIOTest main function is used to test the GraphIO class and object.

runMain scalation.database.graph_pm.graphIOTest

Attributes

def graphMetricsTest(): Unit

The graphMetricsTest main function is used to test the GraphMetrics class.

The graphMetricsTest main function is used to test the GraphMetrics class.

Attributes

See also

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

runMain scalation.database.graph_pm.graphMetricsTest

def graphSimTest(): Unit

The graphSimTest main function is used to test the GraphSim class.

The graphSimTest main function is used to test the GraphSim class.

runMain scalation.database.graph_pm.graphSimTest

Attributes

def graphSimTest2(): Unit

The graphSimTest2 main function is used to test the GraphSim class.

The graphSimTest2 main function is used to test the GraphSim class.

runMain scalation.database.graph_pm.graphSimTest2

Attributes

def graphSimTest3(): Unit

The graphSimTest3 main function is used to test the GraphSim class.

The graphSimTest3 main function is used to test the GraphSim class.

runMain scalation.database.graph_pm.graphSimTest3

Attributes

def graphSimTest4(): Unit

The graphSimTest4 main function is used to test the GraphSim class.

The graphSimTest4 main function is used to test the GraphSim class.

runMain scalation.database.graph_pm.graphSimTest4

Attributes

def graphTest(): Unit

The graphTest main function tests the Graph class using examples from the ExampleGraphD object, which contains digraphs whose vertex and edge labels are of type Double.

The graphTest main function tests the Graph class using examples from the ExampleGraphD object, which contains digraphs whose vertex and edge labels are of type Double.

runMain scalation.database.graph_pm.graphTest

Attributes

def graphTest2(): Unit

The graphTest2 main function tests the Graph class using examples from the ExampleGraphD object, which contains digraphs whose vertex and edge labels are of type String.

The graphTest2 main function tests the Graph class using examples from the ExampleGraphD object, which contains digraphs whose vertex and edge labels are of type String.

runMain scalation.database.graph_pm.graphTest2

Attributes

def graphTest4(): Unit

The graphTest4 main function tests the Graph class by building a graph from an adjacency matrix called cmi for Conditional Mutual Information.

The graphTest4 main function tests the Graph class by building a graph from an adjacency matrix called cmi for Conditional Mutual Information.

Attributes

See also

scalation.modeling.classifying.BayesClassifier

runMain scalation.database.graph_pm.graphTest4

def matchAnswersTest(): Unit

The matchAnswersTest main function is used to test the MatchAnswers object.

The matchAnswersTest main function is used to test the MatchAnswers object.

runMain scalation.database.graph_pm.matchAnswersTest

Attributes

def shortestPathTest(): Unit

The shortestPathTest main function is used to test the ShortestPath class. Input is in the form of matrices (MatrixD).

The shortestPathTest main function is used to test the ShortestPath class. Input is in the form of matrices (MatrixD).

runMain scalation.database.graph_pm.ShortestPathTest

Attributes

def shortestPathTest2(): Unit

The shortestPathTest2 main function is used to test the ShortestPath class. Input is in the form of graphs (Graph).

The shortestPathTest2 main function is used to test the ShortestPath class. Input is in the form of graphs (Graph).

Attributes

See also

http://thescipub.com/PDF/jcssp.2013.377.382.pdf (Fig. 1)

runMain scalation.database.graph_pm.shortestPathTest2

def topSortTest(): Unit

The topSortTest main method tests the TopSort object using a directed graph. Graphs are created by passing in an array of adjacency sets (one for each vertex).

The topSortTest main method 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.database.graph_pm.topSortTest

Attributes

Generated with