abstract class CGL::AbstractDiGraph(V)

Direct Known Subclasses

Defined in:

cgl/algorithms/components/connected.cr
cgl/algorithms/components/strongly_connected.cr
cgl/igraph.cr

Instance Method Summary

Instance methods inherited from class CGL::AnyGraph(V)

==(other : self)
==(other) ==, accept(visitor : Visitor(V)) accept, add_edge(u : V, v : V)
add_edge(edge : AnyEdge(V)) add_edge, add_vertex(v : V) add_vertex, breadth_first_search(from vertex : V) : Iterator(V)
breadth_first_search(from vertex : V, &) breadth_first_search, clear clear, clone clone, count_simple_paths(source : V, target : V) count_simple_paths, degree_of(v : V) : Int32 degree_of, density : Float64 density, depth_first_search(from vertex : V) : Iterator(V)
depth_first_search(from vertex : V, &)
depth_first_search(vertex : V, *, colors : Hash(V, Color), &)
depth_first_search(&)
depth_first_search : Iterator(V) depth_first_search, directed? : Bool directed?, dup dup, each_adjacent(u : V) : Iterator(V)
each_adjacent(u : V, & : V -> ) each_adjacent, each_edge : Iterator(AnyEdge(V))
each_edge(& : AnyEdge(V) -> ) each_edge, each_edge_from(u : V, & : AnyEdge(V) -> ) each_edge_from, each_vertex(& : V -> )
each_vertex : Iterator(V) each_vertex, edge(u : V, v : V)
edge(u : V, v : V, &) edge, edge?(u : V, v : V) edge?, edges : Array(AnyEdge(V)) edges, empty? : Bool empty?, has_edge?(edge : Labelable) : Bool
has_edge?(u : V, v : V, weight, label) : Bool
has_edge?(u : V, v : V) : Bool
has_edge?(edge : Weightable) : Bool
has_edge?(edge : AnyEdge(V)) : Bool has_edge?, has_vertex?(v : V) : Bool has_vertex?, hash(hasher) hash, in_degree_of(v : V) : Int32 in_degree_of, label_of(u : V, v : V) label_of, label_of?(u : V, v : V) label_of?, labeled? : Bool labeled?, order : Int32 order, out_degree_of(v : V) : Int32 out_degree_of, remove_edge(u : V, v : V) remove_edge, remove_vertex(v : V) remove_vertex, shortest_path(source : V, target : V) shortest_path, shortest_path_dijkstra(source : V, target : V) shortest_path_dijkstra, shortest_path_unweighted(source : V, target : V) shortest_path_unweighted, size : Int32 size, subgraph(vertices : Enumerable(V), *, clone : Bool = false) : AnyGraph(V)
subgraph(edges : Enumerable(AnyEdge(V)), *, clone : Bool = false) : AnyGraph(V) subgraph, to_a : Array(AnyEdge(V)) to_a, to_dot(path : String)
to_dot(io : IO) to_dot, weight_of(u : V, v : V) weight_of, weight_of?(u : V, v : V) weight_of?, weighted? : Bool weighted?

Instance Method Detail

def count_strongly_connected_components : Int32 #

Returns the number of strongly connected components in self.


def count_weakly_connected_components : Int32 #

Returns the number of weakly connected components in self.


def degree_of(v : V) : Int32 #
Description copied from class CGL::AnyGraph(V)

Returns the degree of the given vertex v.

For directed graphs, the value equals #out_degree_of.

For undirected graphs, the value is the sum of #in_degree_of and #in_degree_of.


def density : Float64 #
Description copied from class CGL::AnyGraph(V)

Returns the density of self.

Self loops are counted in the total number of edges so graphs with self loops can have density higher than 1.


def directed? : Bool #
Description copied from class CGL::AnyGraph(V)

Whether self is directed.


def each_edge(& : AnyEdge(V) -> ) #
Description copied from class CGL::AnyGraph(V)

Yields each edges in the graph.


def each_edge_from(u : V, & : AnyEdge(V) -> ) #
Description copied from class CGL::AnyGraph(V)

Yields each edge incident to u in the graph.


def each_strongly_connected_component(&) #

Yields each strongly connected component of self as an `Array'.

Note: Based on (Tarjan, 1972) and (Nuutila and Soisalon-Soinen, 1994)


def each_strongly_connected_component : Iterator(Array(V)) #

Returns an iterator of strongly connected components.


def each_successor(u : V, &block : V -> ) #

Yields each successor of u in the graph.


def each_weakly_connected_component(&) #

Yields each connected component of self as an `Array'.


def each_weakly_connected_component : Iterator(Array(V)) #

Returns an Iterator of connected components.


def strongly_connected? : Bool #

Whether self is strongly connected.


def weakly_connected? : Bool #

Whether self is weakly connected.