abstract class CGL::AnyGraph(V)

Direct Known Subclasses

Defined in:

cgl/algorithms/paths/shortest.cr
cgl/algorithms/paths/simple.cr
cgl/format/dot.cr
cgl/igraph.cr
cgl/traversal/breadth_first_search.cr
cgl/traversal/depth_first_search.cr
cgl/traversal/visitor.cr

Instance Method Summary

Instance Method Detail

def ==(other : self) #

Whether self is equal to other.


def ==(other) #
Description copied from class Reference

Returns false (other can only be a Value here).


def accept(visitor : Visitor(V)) #

abstract def add_edge(u : V, v : V) #

Add an edge between vertices u and v.

The given vertices are automatically added if they are not already part of the graph.

A weight and/or a label can be associated to the edge if the concrete class supports it.


abstract def add_edge(edge : AnyEdge(V)) #

Add the given edge to the graph.

See #add_edge(u : V, v : V, weight, label)


abstract def add_vertex(v : V) #

Add a single vertex (a.k.a. node) to this graph.

g = CGL::Graph(String).new
g.add_vertex("Hello")

def breadth_first_search(from vertex : V) : Iterator(V) #

Returns an iterator over vertices from the given source v in a breadth-first search (DFS).


def breadth_first_search(from vertex : V, &) #

Yields vertices from the given source v in a breadth-first search (DFS).


abstract def clear #

Empties an AnyGraph and returns it.


def clone #

Returns a deep copy of self.

Similar to #dup, but duplicates the nodes and edges attributes as well.


def count_simple_paths(source : V, target : V) #

Count all simple paths between the two given vertices, where a simple path is a path with no repeated nodes.


abstract def degree_of(v : V) : Int32 #

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.


abstract def density : Float64 #

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 depth_first_search(from vertex : V) : Iterator(V) #

Returns an iterator over vertices from the given source v in a depth-first search (DFS).


def depth_first_search(from vertex : V, &) #

Yields vertices from the given source v in a depth-first search (DFS).


def depth_first_search(vertex : V, *, colors : Hash(V, Color), &) #

def depth_first_search(&) #

Yields all vertices of self, which are traversed following a depth-first search (DFS) on the whole graph.


def depth_first_search : Iterator(V) #

Returns an iterator over all vertices of self, which are traversed following a depth-first search (DFS) on the whole graph.


abstract def directed? : Bool #

Whether self is directed.


def dup #

Returns a shallow copy of self.

The internal data structures are copied, not


abstract def each_adjacent(u : V) : Iterator(V) #

Returns an iterator over each vertex adjacent to u in the graph.


abstract def each_adjacent(u : V, & : V -> ) #

Yields each vertex adjacent to u in the graph.

g = Graph(String).new(edges: [{"b", "a"}, {"a", "c"}])
g.each_adjacent("a") do |v|
  puts v
end

Output:

b
c

For directed graphs, adjacent vertices are found following outgoing edges.

g = DiGraph(String).new(edges: [{"b", "a"}, {"a", "c"}])
g.each_adjacent("a") do |v|
  puts v
end

Output:

c

def each_edge : Iterator(AnyEdge(V)) #

Returns an iterator over each edge in the graph.


abstract def each_edge(& : AnyEdge(V) -> ) #

Yields each edges in the graph.


abstract def each_edge_from(u : V, & : AnyEdge(V) -> ) #

Yields each edge incident to u in the graph.


abstract def each_vertex(& : V -> ) #

Yields each vertex of the graph.


abstract def each_vertex : Iterator(V) #

Returns an iterator over each vertex of the graph.


def edge(u : V, v : V) #

Returns an edge data structure between u and v if present in the graph, otherwise raises an EdgeError.


def edge(u : V, v : V, &) #

Returns an edge data structure between u and v if present in the graph, otherwise returns the value of the given block.


def edge?(u : V, v : V) #

Returns an edge data structure between u and v if present in the graph, otherwise returns nil.


def edges : Array(AnyEdge(V)) #

Returns an array of edges belonging to this graph.


def empty? : Bool #

Whether the graph is empty.


def has_edge?(edge : Labelable) : Bool #

Whether the given edge is part of the graph.


abstract def has_edge?(u : V, v : V, weight, label) : Bool #

Whether the edge between u and v with the given attributes is part of the graph.


abstract def has_edge?(u : V, v : V) : Bool #

Whether the edge between u and v is part of the graph.


def has_edge?(edge : Weightable) : Bool #

Whether the given edge is part of the graph.


def has_edge?(edge : AnyEdge(V)) : Bool #

Whether the given edge is part of the graph.


abstract def has_vertex?(v : V) : Bool #

Whether the given vertex v is part of the graph.


def hash(hasher) #

See Object#hash(hasher)


abstract def in_degree_of(v : V) : Int32 #

Returns the incoming degree of the given vertex v.

For undirected graphs, the value equals #degree_of.


abstract def label_of(u : V, v : V) #

Returns the label associated with the given edge if it exists, raises EdgeError otherwise


abstract def label_of?(u : V, v : V) #

Returns the label associated with the given edge if it exists, otherwise returns nil.


abstract def labeled? : Bool #

Whether edges are labeled.


abstract def order : Int32 #

Returns the number of vertices in self.


abstract def out_degree_of(v : V) : Int32 #

Returns the outgoing degree of the given vertex v.

For undirected graphs, the value equals #degree_of.


def remove_edge(u : V, v : V) #

Deletes the given edge and returns it, otherwise returns nil.


abstract def remove_vertex(v : V) #

Remove given vertex v from this graph. Edges incident to v are also removed.

Raises a GraphError if vertex is not part of the graph.

g = CGL::Graph(String).new(edges: [{"a", "b"}, {"b", "c"}])
g.size # => 2
g.remove_vertex("b")
g.size # => 0

def shortest_path(source : V, target : V) #

Returns a shortest path between the given vertices.

Note: Tries to select the most appropriate algorithm for self.


def shortest_path_dijkstra(source : V, target : V) #

Returns the shortest weighted path between the given vertices.

Raises if self is not a weighted graph.

Note: Uses Dijkstra's algorithm. Not appropriate for graphs with negative weights and/or negative cycles.


def shortest_path_unweighted(source : V, target : V) #

Returns the shortest unweighted path between the given vertices.


abstract def size : Int32 #

Returns the number of edges in self.


def subgraph(vertices : Enumerable(V), *, clone : Bool = false) : AnyGraph(V) #

Returns a subgraph containing the given vertices as well as the existing edges between those vertices.

If copy is set to true, the vertices as well as edge attributes are deep copies, otherwise they are shallow copies.


def subgraph(edges : Enumerable(AnyEdge(V)), *, clone : Bool = false) : AnyGraph(V) #

Returns a subgraph containing the given edges.

If copy is set to true, the vertices as well as edge attributes are deep copies, otherwise they are shallow copies.


def to_a : Array(AnyEdge(V)) #

See #edges.


def to_dot(path : String) #

Generates a DOT file representing the graph at the given path.


def to_dot(io : IO) #

Generates a DOT representation of the graph using the given IO.


abstract def weight_of(u : V, v : V) #

Returns the weight associated with the given edge if it exists, otherwise EdgeError otherwise.


abstract def weight_of?(u : V, v : V) #

Returns the weight associated with the given edge if it exists, otherwise returns nil.


abstract def weighted? : Bool #

Whether edges are weighted.