# mutable.rb

require 'laser/third_party/rgl/base'

module RGL

  # A MutableGraph can be changed via the addition or removal of edges and
  # vertices. 
  module MutableGraph

    include Graph

    # Add a new vertex _v_ to the graph.  If the vertex is already in the
    # graph (tested via eql?), the method does nothing.

    def add_vertex (v)
      raise NotImplementedError
    end

    # Inserts the edge (u,v) into the graph.
    #
    # Note that for undirected graphs, (u,v) is the same edge as (v,u), so
    # after a call to the function add_edge(), this implies that edge (u,v)
    # will appear in the out-edges of u and (u,v) (or equivalently (v,u))
    # will appear in the out-edges of v.  Put another way, v will be adjacent
    # to u and u will be adjacent to v. 

    def add_edge (u, v)
      raise NotImplementedError
    end

    # Add all objects in _a_ to the vertex set.

    def add_vertices (*a)
      a.each { |v| add_vertex v }
    end

    # Add all edges in the _edges_ array to the edge set.  Elements of the
    # array can be both two-element arrays or instances of DirectedEdge or
    # UnDirectedEdge. 

    def add_edges (*edges)
      edges.each { |edge| add_edge(edge[0], edge[1]) }
    end

    # Add the graph to the current graph. All vertices in the other graph
    # are added, as are all edges.
    
    def add_graph(graph)
      add_vertices(*graph.vertices)
      add_edges(*graph.edges)
    end
    
    # Adds all the given graphs to the current graph. See #add_graph.
    
    def add_graphs(*graphs)
      graphs.each { |graph| add_graph graph }
    end

    # Remove u from the vertex set of the graph.  All edges whose target is
    # _v_ are also removed from the edge set of the graph.
    #
    # Postcondition: num_vertices is one less, _v_ no longer appears in the
    # vertex set of the graph, and there no edge with source or target _v_.

    def remove_vertex (v)
      raise NotImplementedError
    end

    # Remove the edge (u,v) from the graph.  If the graph allows parallel
    # edges, this removes all occurrences of (u,v).
    # 
    # Precondition: u and v are vertices in the graph.
    # Postcondition: (u,v) is no longer in the edge set for g.

    def remove_edge (u, v)
      raise NotImplementedError
    end

    # Remove all vertices specified by the array a from the graph by calling
    # remove_vertex.

    def remove_vertices (*a)
      a.each { |v| remove_vertex v }
    end

    # Returns all minimum cycles that pass through a give vertex. 
    # The format is an Array of cycles, with each cycle being an Array
    # of vertices in the cycle.
    def cycles_with_vertex(vertex)
      cycles_with_vertex_helper(vertex, vertex, [])
    end

  protected
    def cycles_with_vertex_helper(vertex, start, visited) #:nodoc:
      adjacent_vertices(start).reject {|x| visited.include?(x)}.inject([]) do |acc, adj|
        local_visited = Array.new(visited) << adj
        acc << local_visited if (adj==vertex)
        acc = acc + cycles_with_vertex_helper(vertex,adj,local_visited)
      end
    end

  public
    # Returns an array of all minimum cycles in a graph
    #
    # This is not an efficient implementation O(n^4) and could
    # be done using Minimum Spanning Trees. Hint. Hint.
    def cycles
      g = self.clone
      self.inject([]) do |acc, v| 
        acc = acc.concat(g.cycles_with_vertex(v))
        g.remove_vertex(v); acc
      end
    end

  end		# module MutableGraph
end		# module RGL
