Graphs (Asakusa Framework 0.10.4 API)

java.lang.Object
- com.asakusafw.utils.graph.Graphs

public final class Graphs
extends Object

Operations for Graph.

Method Summary

All Methods Static Methods Concrete Methods
Modifier and Type	Method and Description
`static <V> Set<V>`	`collectAllConnected(Graph<? extends V> graph, Collection<? extends V> startNodes)` Returns the transitively connected all vertices from the starting vertices.
`static <V> Set<V>`	`collectHeads(Graph<? extends V> graph)` Returns each head vertex in the graph, which has no preceding vertices.
`static <V> Set<V>`	`collectNearest(Graph<? extends V> graph, Collection<? extends V> startNodes, Predicate<? super V> matcher)` Returns the succeeding nearest vertices which match the condition, from the starting vertices, and vertices on their routes.
`static <V> Set<V>`	`collectTails(Graph<? extends V> graph)` Returns each tail vertex in the graph, which has no succeeding vertices.
`static <V> Graph<V>`	`copy(Graph<? extends V> graph)` Returns a copy of the target graph.
`static <V> Set<Set<V>>`	`findCircuit(Graph<? extends V> graph)` Returns the all cyclic sub-graphs in the target graph.
`static <V> Set<V>`	`findNearest(Graph<? extends V> graph, Collection<? extends V> startNodes, Predicate<? super V> matcher)` Returns the succeeding nearest vertices which match the condition, from the starting vertices.
`static <V> Set<Set<V>>`	`findStronglyConnectedComponents(Graph<? extends V> graph)` Returns the all strongly connected components in the target graph.
`static <V> Graph<V>`	`newInstance()` Creates a new `Graph` instance without any vertices.
`static <V> List<V>`	`sortPostOrder(Graph<? extends V> graph)` Sorts the vertices from the tail to head topologically, and returns their list.
`static <V> Graph<V>`	`subgraph(Graph<? extends V> graph, Predicate<? super V> matcher)` Creates a new subgraph from the target graph.
`static <V> Graph<V>`	`transpose(Graph<V> graph)` Creates a new transposed graph from the target graph.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Method Detail
  - newInstance
```
public static <V> Graph<V> newInstance()
```
    Creates a new Graph instance without any vertices.
    
    Type Parameters:
    
    V - the vertex value type
    
    Returns:
    
    the created instance
  - copy
```
public static <V> Graph<V> copy(Graph<? extends V> graph)
```
    Returns a copy of the target graph.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    Returns:
    
    the copy
    
    Throws:
    
    IllegalArgumentException - if the parameter is null
  - collectHeads
```
public static <V> Set<V> collectHeads(Graph<? extends V> graph)
```
    Returns each head vertex in the graph, which has no preceding vertices.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    Returns:
    
    the head vertices
    
    Throws:
    
    IllegalArgumentException - if the parameter is null
  - collectTails
```
public static <V> Set<V> collectTails(Graph<? extends V> graph)
```
    Returns each tail vertex in the graph, which has no succeeding vertices.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    Returns:
    
    the tail vertices
    
    Throws:
    
    IllegalArgumentException - if the parameter is null
  - collectAllConnected
```
public static <V> Set<V> collectAllConnected(Graph<? extends V> graph,
                                             Collection<? extends V> startNodes)
```
    Returns the transitively connected all vertices from the starting vertices. If a starting vertex is not connected to any vertices, the resulting set will not contain it even if it is a starting vertex.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    startNodes - the starting vertices
    
    Returns:
    
    the transitive connected vertices from the starting vertices
    
    Throws:
    
    IllegalArgumentException - if the parameters are null
  - findNearest
```
public static <V> Set<V> findNearest(Graph<? extends V> graph,
                                     Collection<? extends V> startNodes,
                                     Predicate<? super V> matcher)
```
    Returns the succeeding nearest vertices which match the condition, from the starting vertices. The nearest vertices must be a set of nearest which satisfies the following all conditions:
    - Is transitively connected from any starting vertices (collectAllConnected(graph, startNodes).contains(nearest))
    - Satisfies the matcher rule (matcher.test(nearest))
    - Reachable from any starting vertices, NOT via other nearest
    The resulting set may not contain the starting vertices, excepts the starting vertices also satisfies above the conditions.
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    startNodes - the starting vertices
    
    matcher - the matcher
    
    Returns:
    
    the nearest vertices
    
    Throws:
    
    IllegalArgumentException - if the parameters are null
  - collectNearest
```
public static <V> Set<V> collectNearest(Graph<? extends V> graph,
                                        Collection<? extends V> startNodes,
                                        Predicate<? super V> matcher)
```
    Returns the succeeding nearest vertices which match the condition, from the starting vertices, and vertices on their routes. In other words, this method returns all vertices on the searching route on findNearest(Graph, Collection, Predicate). The resulting set may not contain the starting vertices, excepts the starting vertices also on their searching route.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    startNodes - the starting vertices
    
    matcher - the vertices predicate
    
    Returns:
    
    the nearest vertices and vertices on their route
    
    Throws:
    
    IllegalArgumentException - if the parameters are null
  - findCircuit
```
public static <V> Set<Set<V>> findCircuit(Graph<? extends V> graph)
```
    Returns the all cyclic sub-graphs in the target graph.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    Returns:
    
    the sets of cyclic connected vertices
    
    Throws:
    
    IllegalArgumentException - if the parameter is null
  - findStronglyConnectedComponents
```
public static <V> Set<Set<V>> findStronglyConnectedComponents(Graph<? extends V> graph)
```
    Returns the all strongly connected components in the target graph.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    Returns:
    
    the strongly connected components
    
    Throws:
    
    IllegalArgumentException - if the parameter is null
  - sortPostOrder
```
public static <V> List<V> sortPostOrder(Graph<? extends V> graph)
```
    Sorts the vertices from the tail to head topologically, and returns their list. If the graph does not contain any cycles, the resulting result must satisfy the following:
```
for i = 0..list.size-1:
  for j = i+1..list.size-1:
    assert graph.isConnected(list[i], list[j]) == false;
```
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    Returns:
    
    the sorted vertices
    
    Throws:
    
    IllegalArgumentException - if the parameter is null
  - transpose
```
public static <V> Graph<V> transpose(Graph<V> graph)
```
    Creates a new transposed graph from the target graph. The transposed graph reverse must satisfy the following:
```
graph.contains(a) <=> reverse.contains(a), and
graph.isConnected(a, b) <=> reverse.isConnected(b, a).
```
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    Returns:
    
    the created graph
    
    Throws:
    
    IllegalArgumentException - if the parameter is null
  - subgraph
```
public static <V> Graph<V> subgraph(Graph<? extends V> graph,
                                    Predicate<? super V> matcher)
```
    Creates a new subgraph from the target graph.
    
    Type Parameters:
    
    V - the vertex value type
    
    Parameters:
    
    graph - the target graph
    
    matcher - only test to the subgraph members
    
    Returns:
    
    the created subgraph
    
    Throws:
    
    IllegalArgumentException - if the parameters are null

Class Graphs

Method Summary

Methods inherited from class java.lang.Object

Method Detail

newInstance

copy

collectHeads

collectTails

collectAllConnected

findNearest

collectNearest

findCircuit

findStronglyConnectedComponents

sortPostOrder

transpose

subgraph