Class: Roby::Relations::IncrementalTransitiveClosure

Inherits:
Object
  • Object
show all
Defined in:
lib/roby/relations/incremental_transitive_closure.rb

Overview

This class represents an incremental transitive closure graph, where edges and vertices can be added or removed incrementally, while keeping track of reachability information (i.e., transitive closure).

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ IncrementalTransitiveClosure

Initializes an empty directed graph using BidirectionalDirectedAdjacencyGraph



37
38
39
40
 
# File 'lib/roby/relations/incremental_transitive_closure.rb', line 37

def initialize
    @graph =
        Relations::BidirectionalDirectedAdjacencyGraph.new
end

Instance Attribute Details

#graph ⇒ Object (readonly)

Returns the value of attribute graph.



33
34
35
 
# File 'lib/roby/relations/incremental_transitive_closure.rb', line 33

def graph
  @graph
end

Instance Method Details

#added_edge(source, target) ⇒ Object

Adds an edge from ‘source’ to ‘target’ to the graph It also ensures that transitive reachability is updated by adding edges from the ‘source’s parents vertices to ‘target’. Adding edges from the from ‘source’ to ‘target’s children vertices. As well as adding edges from ‘source’s parent vertices to ‘target’s children

Parameters:

  • source (Object) —

    The source vertex

  • target (Object) —

    The target vertex



50
51
52
53
54
55
56
57
 
# File 'lib/roby/relations/incremental_transitive_closure.rb', line 50

def added_edge(source, target)
    return if @graph.has_edge?(source, target) ||
              source == target

    @graph.add_edge(source, target)

    @graph.propagate_transitive_closure(source, target)
end

#discover_vertex(source, source_graph) ⇒ Object

Discovers vertices reachable from ‘source’ and adds them to the transitive closure. This method performs a DFS to explore the graph incrementally.

Parameters:

  • source (Object) —

    The source vertex to start the DFS

  • graph (Graph) —

    The graph to explore during the DFS



119
120
121
122
 
# File 'lib/roby/relations/incremental_transitive_closure.rb', line 119

def discover_vertex(source, source_graph)
    vis = IncrementalTransitiveClosureVisitor.new(source_graph, self)
    source_graph.depth_first_visit(source, vis) {}
end

#reachable?(source, target, source_graph) ⇒ Boolean

Checks if there is a directed edge from ‘source’ to ‘target’ (i.e., if ‘target’ is reachable from ‘source’).

If the incremental transitive closure already has this node discovered, it will simply test if this edge exists. If not, it will execute a depth first visit, exploring the nodes and their relations along the way.

to ‘target’, false otherwise

Parameters:

  • source (Object) —

    The source vertex

  • target (Object) —

    The target vertex

  • source_graph (Graph) —

    The graph to check for the edge

Returns:

  • (Boolean) —

    Returns true if there is a direct edge from ‘source’



107
108
109
110
111
 
# File 'lib/roby/relations/incremental_transitive_closure.rb', line 107

def reachable?(source, target, source_graph)
    discover_vertex(source, source_graph) unless @graph.has_vertex?(source)

    @graph.has_edge?(source, target)
end

#removed_edge(source, target) ⇒ Object

Removes an edge from the graph. If the target vertex has adjacent vertices, or the source vertex has parent vertices the entire graph is reset. Otherwise, it simply removes the edge.

Parameters:

  • source (Object) —

    The source vertex

  • target (Object) —

    The target vertex



82
83
84
85
86
87
88
89
90
91
92
 
# File 'lib/roby/relations/incremental_transitive_closure.rb', line 82

def removed_edge(source, target)
    return unless @graph.has_edge?(source, target)

    if @graph.leaf?(target) &&
       @graph.root?(source)
        @graph.remove_edge(source, target)
    else
        @graph =
            Relations::BidirectionalDirectedAdjacencyGraph.new
    end
end

#removed_vertex(vertex) ⇒ Object

Removes a vertex from the graph if it has no adjacent vertices (i.e., no outgoing edges) If there are adjacent vertices, the entire graph is reset (rebuilds the graph)

Parameters:

  • vertex (Object) —

    The vertex to be removed



65
66
67
68
69
70
71
72
73
74
 
# File 'lib/roby/relations/incremental_transitive_closure.rb', line 65

def removed_vertex(vertex)
    return unless @graph.has_vertex?(vertex)

    if @graph.leaf?(vertex)
        @graph.remove_vertex(vertex)
    else
        @graph =
            Relations::BidirectionalDirectedAdjacencyGraph.new
    end
end