graph :: HashDigraph
graph :: HashDigraph :: defaultinit
graph $ HashDigraph :: SELF
Type of this instance, automatically specialized in every classgraph $ HashDigraph :: has_vertex
Returns true if and only ifu
exists in this graph.
graph $ HashDigraph :: num_vertices
The number of vertices in this graph.graph $ HashDigraph :: predecessors
Returns the predecessors ofu
.
graph $ HashDigraph :: remove_arc
Removes the arc(u,v)
from this graph.
graph $ HashDigraph :: remove_vertex
Removes the vertexu
from this graph and all its incident arcs.
graph $ HashDigraph :: vertices_iterator
Returns an iterator over the vertices of this graph.graph :: Digraph :: a_shortest_path
Returns a shortest path from vertexu
to v
.
graph :: MutableDigraph :: add_arcs
Adds all arcs ofarcs
to this digraph.
graph :: MutableDigraph :: add_vertex
Adds the vertexu
to this graph.
graph :: MutableDigraph :: add_vertices
Adds all vertices ofvertices
to this digraph.
graph :: Digraph :: arcs_iterator
Returns an iterator over the arcs of this graphcore :: Object :: class_factory
Implementation used byget_class
to create the specific class.
graph :: HashDigraph :: defaultinit
graph :: MutableDigraph :: defaultinit
graph :: Digraph :: defaultinit
core :: Object :: defaultinit
graph :: Digraph :: eulerian_path
Build a path (or circuit) from the vertexstart
that visits every edge exactly once.
graph :: MutableDigraph :: get_all_predecessors
Returns the all predecessors ofu
.
graph :: MutableDigraph :: get_all_successors
Returns the all successors ofu
.
graph :: Digraph :: has_circuit
Returns true if and only ifvertices
is a circuit of this digraph.
graph :: Digraph :: has_vertex
Returns true if and only ifu
exists in this graph.
graph :: Digraph :: incoming_arcs
Returns the incoming arcs of vertexu
.
graph :: Digraph :: is_predecessor
Returns true if and only ifu
is a predecessor of v
.
core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
graph :: Digraph :: is_successor
Returns true if and only ifu
is a successor of v
.
graph :: Digraph :: num_vertices
The number of vertices in this graph.graph :: Digraph :: out_degree
Returns the number of arcs whose source isu
.
graph :: Digraph :: outgoing_arcs
Returns the outgoing arcs of vertexu
.
core :: Object :: output_class_name
Display class name on stdout (debug only).graph :: Digraph :: predecessors
Returns the predecessors ofu
.
graph :: MutableDigraph :: remove_arc
Removes the arc(u,v)
from this graph.
graph :: MutableDigraph :: remove_eulerian_path
Build a path (or circuit) that removes every edge exactly once.graph :: MutableDigraph :: remove_vertex
Removes the vertexu
from this graph and all its incident arcs.
graph :: Digraph :: strongly_connected_components
Returns the strongly connected components of this digraph.graph :: Digraph :: successors
Returns the successors ofu
.
graph :: Digraph :: vertices_iterator
Returns an iterator over the vertices of this graph.graph :: Digraph :: weakly_connected_components
Returns the weak connected components of this digraph.
# A directed graph represented by hash maps
class HashDigraph[V: Object]
super MutableDigraph[V]
# Attributes
#
private var incoming_vertices_map = new HashMap[V, Array[V]]
private var outgoing_vertices_map = new HashMap[V, Array[V]]
private var number_of_arcs = 0
redef fun num_vertices do return outgoing_vertices_map.keys.length end
redef fun num_arcs do return number_of_arcs end
redef fun add_vertex(u)
do
if not has_vertex(u) then
incoming_vertices_map[u] = new Array[V]
outgoing_vertices_map[u] = new Array[V]
end
end
redef fun has_vertex(u) do return outgoing_vertices_map.keys.has(u)
redef fun remove_vertex(u)
do
if has_vertex(u) then
for v in successors(u) do
remove_arc(u, v)
end
for v in predecessors(u) do
remove_arc(v, u)
end
incoming_vertices_map.keys.remove(u)
outgoing_vertices_map.keys.remove(u)
end
end
redef fun add_arc(u, v)
do
if not has_vertex(u) then add_vertex(u)
if not has_vertex(v) then add_vertex(v)
if not has_arc(u, v) then
incoming_vertices_map[v].add(u)
outgoing_vertices_map[u].add(v)
invalidated_all_cache
number_of_arcs += 1
end
end
redef fun has_arc(u, v)
do
return outgoing_vertices_map[u].has(v)
end
redef fun remove_arc(u, v)
do
if has_arc(u, v) then
outgoing_vertices_map[u].remove(v)
incoming_vertices_map[v].remove(u)
number_of_arcs -= 1
end
end
redef fun predecessors(u): Array[V]
do
if incoming_vertices_map.keys.has(u) then
return incoming_vertices_map[u].clone
else
return new Array[V]
end
end
redef fun successors(u): Array[V]
do
if outgoing_vertices_map.keys.has(u) then
return outgoing_vertices_map[u].clone
else
return new Array[V]
end
end
redef fun vertices_iterator: Iterator[V] do return outgoing_vertices_map.keys.iterator
end
lib/graph/digraph.nit:939,1--1022,3