graphalytics

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://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

   http://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 BipartiteMatching extends AnyRef

   

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

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

   See also

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

4. class ColorDAG extends Error

   

   The ColorDAG class provides a data structure Directed Acyclic Graphs (DAGs) with colored nodes.

   The ColorDAG class provides a data structure Directed Acyclic Graphs (DAGs) 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 ColorTree extends AnyRef

   

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

6. class Cycle extends AnyRef

   

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

   The Cycle class 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.

7. class DualIso extends PatternMatcher

   

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

8. class DualSim extends PatternMatcher

   

   The 'DualSim' classs provides an implementation for Dual Graph Simulation.

9. class DualSim2 extends PatternMatcher

   

   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 ('par') in order to save space.

10. class DualSim3 extends PatternMatcher2

    

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

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

11. case class Graph(adj: Array[ISet], label: Array[Int] = Array.ofDim (0), inverse: Boolean = false) extends Cloneable with Product with Serializable

    

    The Graph class stores vertex-labeled directed graphs using an adjacency set ('adj') representation, e.g., adj = { {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 ('adj') representation, e.g., adj = { {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 'par' array can be stored at the cost of nearly doubling the storage requirements.

    adj

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

    label

    the array of verter labels

    inverse

    whether to store inverse adjacency sets (parents)

12. case class Graph2(adj: Array[AList], label: Array[TLabel] = Array.ofDim [TLabel] (0), elabel: Map[(Int, Int), TLabel] = Map (), inverse: Boolean = false) extends Product with Serializable

    

    The Graph2 class is used for representing "Directed Graphs".

    The Graph2 class is used for representing "Directed Graphs". It uses an adjacency list 'adj' representation, e.g., adj = { (1, 2), (0), (1) } means that the graph has the following edges { (0, 1), (0, 2), (1, 0), (2, 1) }. Options: (1) the graph may have vertex labels, (2) the graph may have edge labels, and (3) the graph may maintain inverse adjacency via the parent 'par' array can be stored at the cost of nearly doubling the storage requirements.

    adj

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

    label

    the array of vertex labels

    elabel

    the map of edge labels

    inverse

    whether to store inverse adjacency list (parents)

13. class GraphBFS extends AnyRef

    

    The GraphBFS performs Breadth First Search on a Directed Graph.

14. class GraphIso extends AnyRef

    

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

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 PatternMatcher

    

    The GraphSim class provides an implementation for Simple Graph Simulation.

17. class GraphSim2 extends PatternMatcher

    

    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 GraphSim3 extends PatternMatcher2

    

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

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

19. class GraphSimIso extends PatternMatcher

    

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

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

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

22. abstract class PatternMatcher extends AnyRef

    

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

23. abstract class PatternMatcher2 extends AnyRef

    

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

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

    http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

25. class TightSimulation extends AnyRef

    

    The 'TightSimulation' class provides an implementation for graph pattern matching.

    The 'TightSimulation' class provides an implementation for graph pattern matching.

    See also

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

26. class TreeNode extends AnyRef

    

    The TreeNode class is for a node in the color tree.