class Graph

A graph with nodes and edges

Attributes

attrs[RW]

@return [Hash] the graph’s attributes

edges[RW]

@return [EdgeArray] the graph’s edges

nodes[RW]

@return [NodeArray] the graph’s nodes

Public Class Methods

get_label(n) click to toggle source

return the label of a node. Raise a TypeError exception if the argument is not a Node nor a String object. @param n [Node,String] A node with a ‘label’ or :label attribute, or a

string

@return [String]

# File lib/graph.rb, line 486
def Graph::get_label(n)
    label = n.is_a?(Node) \
                  ? n.label.to_s \
                  : n.is_a?(String) ? n : nil

     if label.nil?
        raise TypeError.new("#{n.inspect} must be a Node or String object.")
     end

    label
end
intersection(*graphs) click to toggle source

Return a new Graph which is the intersection of every given graph. Each node of the intersection is in every given graph (idem for edges). The last argument may be a hash of options. @option options [Boolean] :same_fields use only fields which are in

every graph to compare nodes/edges to perform
the intersection

@see Graph#& @see Graph.union @see Graph.xor @return [Graph]

# File lib/graph.rb, line 19
def Graph::intersection(*graphs)
     perform_graphs_group_op(*graphs, &:&)
end
new(nodes=nil, edges=nil) click to toggle source

Create a new Graph from one set of nodes and one set of edges @param nodes [Array] Nodes of the graph @param edges [Array] Edges of the graph

# File lib/graph.rb, line 212
def initialize(nodes=nil, edges=nil)
    @nodes = NodeArray.new(nodes || [])
    @edges = EdgeArray.new(edges || [])
    @attrs = { :directed => true }
end
union(*graphs) click to toggle source

Return a new {Graph} which is the union of every given graph. Each node of the union is in one or more given graph(s) (idem for edges). The last argument may be a hash of options. @option options [Boolean] :same_fields use only fields which are in

every graph to compare nodes/edges to perform
the union

@see Graph#| @see Graph.intersection @see Graph.xor @return [Graph]

# File lib/graph.rb, line 33
def Graph::union(*graphs)
    perform_graphs_group_op(*graphs, &:|)
end
xor(*graphs) click to toggle source

Perform a XOR operation on all given graphs, and returns the result. The last argument may be a hash of options. @option options [Boolean] :same_fields use only fields which are in every graph to compare nodes/edges to perform the XOR operation @see Graph#^ @see Graph.union @see Graph.intersection @return [Graph]

# File lib/graph.rb, line 45
def Graph::xor(*graphs)
    perform_graphs_group_op(*graphs, &:^)
end

Private Class Methods

keep_only_same_fields(*graphs) click to toggle source

return the provided set of graphs, from which every node/edge label which is not in all graphs has been removed. So every returned graph has same node/edge labels than each other

# File lib/graph.rb, line 503
def Graph::keep_only_same_fields(*graphs)
        graphs.map! {|g| g.clone}

        # every first node of every graphs
        nodes_ref = graphs.map {|g| g.nodes[0] || {}}
        # every first edge of every graphs
        edges_ref = graphs.map {|g| g.edges[0] || {}}

        nodes_keys_ref = nodes_ref.map {|n| n.keys}
        edges_keys_ref = edges_ref.map {|e| e.keys}

        # keep only same keys
        nodes_keys_uniq = nodes_keys_ref.inject {|i,e| i &= e}
        edges_keys_uniq = edges_keys_ref.inject {|i,e| i &= e}

        graphs.map do |g|
            g.nodes.map! do |n|

                newnode = {}

                n.each_key do |k|
                    newnode[k] = n[k] if nodes_keys_uniq.include?(k)
                end

                newnode
            end
            g.edges.map! do |n|

                newedge = {}

                n.each_key do |k|
                    newedge[k] = n[k] if edges_keys_uniq.include?(k)
                end

                newedge
            end
            g
        end
end
perform_graphs_group_op(*graphs, &block) click to toggle source

Perform an operation on a graphs group @param graphs [Array<Graph>] @param block [Block] operation @return [Graph]

# File lib/graph.rb, line 547
def Graph::perform_graphs_group_op(*graphs, &block)
    return if graphs.length == 0

    # options
    opts = {}

    # if the last arg is an hash, use it as a set of options and remove it
    # from the arguments
    if graphs[-1].is_a?(Hash)
        return if graphs.length == 1
        opts = graphs.pop
    end

    # return nil if one argument is not a graph
    graphs.each do |g|
        return if !g.is_a?(Graph)
    end

    # if :same_fields option is set, call `keep_only_same_fields` function
    graphs = keep_only_same_fields(*graphs) if opts[:same_fields]

    # perform an and operation on all graph list
    graphs.inject(&block)
end

Public Instance Methods

&(other) click to toggle source

Perform an intersection between the current graph and the other. Returns a new Graph which nodes are both in the current graph and the other (idem for edges). @param other [Graph] @return [Graph] @see Graph#^ @see Graph.intersection

# File lib/graph.rb, line 236
def &(other)
    return unless other.is_a?(Graph)

    nodes = @nodes & other.nodes
    edges = @edges & other.edges

    Graph.new(nodes, edges)
end
+(other) click to toggle source

Add two graphs, keeping duplicate nodes and edges @param other [Graph] @return [Graph]

# File lib/graph.rb, line 263
def +(other)
    return unless other.is_a?(Graph)

    nodes = @nodes + other.nodes
    edges = @edges + other.edges

    Graph.new(nodes, edges)
end
-(other) click to toggle source

Returns a new Graph, which is a copy of the current graph without nodes and edges which are in the given Graph. @param other [Graph] @return [Graph]

# File lib/graph.rb, line 290
def -(other)
    return unless other.is_a?(Graph)

    nodes = @nodes - other.nodes
    edges = @edges - other.edges

    Graph.new(nodes, edges)
end
==(other) click to toggle source

Test if current graph has same nodes and edges as the other graph. @param other [Graph] @return [Boolean]

# File lib/graph.rb, line 222
def ==(other)
    if (!other.is_a?(Graph))
        return false
    end
    (self.nodes === other.nodes) && (self.edges === other.edges)
end
^(other) click to toggle source

Perform a XOR operation between the current graph and the other. Returns a new Graph which nodes are in the current graph or in the other, but not in both (idem for edges). @param other [Graph] @return [Graph] @see Graph#&

# File lib/graph.rb, line 251
def ^(other)
    return unless other.is_a?(Graph)

    nodes = (@nodes - other.nodes) + (other.nodes - @nodes)
    edges = (@edges - other.edges) + (other.edges - @edges)

    Graph.new(nodes, edges)
end
clone() click to toggle source

Clone the current graph. All nodes and edges are also cloned. A new Graph is returned. @return [Graph] a new graph

# File lib/graph.rb, line 314
def clone()
    g = Graph.new
    g.nodes = self.nodes.clone
    g.edges = self.edges.clone

    g.nodes.map! {|h| h.clone}
    g.edges.map! {|h| h.clone}

    g
end
degree_of(n) click to toggle source

Return the degree of the node n in the current graph, i.e. the number of edges which are connected to this node. Note that this is useful only for a undirected graph, for a directed one, you should use Graph#in_degree_of and/or Graph#out_degree_of.

Edges must have the node1 and node2 attributes, which must contain the label attributes of nodes.

@param n [Node,String] A node or a label of one @return [Integer] @see Graph#in_degree_of @see Graph#out_degree_of

# File lib/graph.rb, line 367
def degree_of(n)
    label = Graph::get_label(n)

    degree = 0

    # This is more efficient than in_degree_of(n)+out_degree_of(n)
    # since it goes only once through the edges array
    self.edges.each do |e|
        degree += 1 if (e['node1'] || e[:node1]).to_s == label
        degree += 1 if (e['node2'] || e[:node2]).to_s == label
    end

    degree
end
directed?() click to toggle source

Return true if the Graph is directed. @return [Boolean] @see Graph.attrs

# File lib/graph.rb, line 307
def directed?()
    !!self.attrs[:directed]
end
get_neighbours(n) click to toggle source

return an array of the neighbours of a node in the current graph. @param n [Node,String] A node with a ‘label’ or :label attribute, or a

string

@return [Array<Node>]

# File lib/graph.rb, line 441
def get_neighbours(n)

    label = Graph::get_label n
    neighbours = NodeArray.new []

    self.edges.each do |e|

        l1 = e[:node1] || e['node1']
        l2 = e[:node2] || e['node2']

        if l2 && l1 == label

            n2 = self.get_node l2

            unless n2.nil? || neighbours.include?(n2)

                neighbours.push(n2)

            end

        end

        if l1 && l2 == label && !self.directed?

            n1 = self.get_node l1

            unless n1.nil? || neighbours.include?(n1)

                neighbours.push(n1)

            end

        end

    end

    neighbours

end
get_node(label) click to toggle source

return the first node which mach the given label in the current graph @param label [String] A node’s label @return [Node]

# File lib/graph.rb, line 431
def get_node(label)
    label = Graph::get_label(label)

    self.nodes.find { |n| n.label == label }
end
in_degree_of(n) click to toggle source

Return the “in degree” of the node n in the current graph, i.e. the number of edges which are directed to this node. Note that the graph must be oriented.

Edges must have the node1 and node2 attributes, which must contain the label attributes of nodes.

@param n [Node,String] A node or a label of one @return [Integer] @see Graph#degree_of @see Graph#out_degree_of

# File lib/graph.rb, line 393
def in_degree_of(n)
    label = Graph::get_label(n)

    degree = 0

    self.edges.each do |e|
        degree += 1 if (e['node2'] || e[:node2]).to_s == label
    end

    degree
end
not(other) click to toggle source

(see Graph#-)

# File lib/graph.rb, line 300
def not(other)
    self - other
end
out_degree_of(n) click to toggle source

Return the “out degree” of the node n in the current graph, i.e. the number of edges which are directed from this node. Note that the graph must be oriented.

Edges must have the node1 and node2 attributes, which must contain the label attributes of nodes.

@param n [Node,String] A node or a node’s label @return [Integer] @see Graph#degree_of @see Graph#out_degree_of

# File lib/graph.rb, line 416
def out_degree_of(n)
    label = Graph::get_label(n)

    degree = 0

    self.edges.each do |e|
        degree += 1 if (e['node1'] || e[:node1]).to_s == label
    end

    degree
end
to_gdf(opts=nil) click to toggle source

Returns a GDF version of the current graph @param opts [Hash] A customizable set of options @return [String] @see GDF.unparse

# File lib/graphs/gdf.rb, line 12
def to_gdf(opts=nil)
    GDF::unparse(self, opts)
end
to_json(opts=nil) click to toggle source

Returns a JSON version of the current graph @param opts [Hash] A customizable set of options @return [String] @see JSONGraph.unparse

# File lib/graphs/json.rb, line 12
def to_json(opts=nil)
    JSONGraph::unparse(self, opts)
end
write(filename, opts=nil) click to toggle source

Write the current Graph into a file. @param filename [String] A valid filename @param opts [Hash] A customizable set of options @return [] @option opts [Boolean] :gephi Should be true if the file will be

used with Gephi.
# File lib/graph.rb, line 331
def write(filename, opts=nil)

    has_ext = filename.split('.')
    ext = (has_ext.length>1) ? has_ext[-1] : 'unknow'

    m = (self.methods - Object.methods).map {|e| e.to_s}

    if (m.include? 'write_'+ext.downcase)
        self.send('write_'+ext.downcase, filename, opts)

    elsif (ext == 'unknow' || ext == 'yml')
        # YAML (default)
        nodes = self.nodes.to_a
        edges = self.edges.to_a

        data = {'nodes'=>nodes, 'edges'=>edges}.to_yaml
        f = open(filename, 'w')
        f.write(data)
        f.close
    else
        raise NoMethodError.new("No method to handle #{ext} file extension.")
    end
end
write_gdf(filename, opts=nil) click to toggle source

Write the current graph into a GDF file. This method is used internally, use Graph#write instead. @param filename [String] a valid filename @return [] @see GDF.unparse

# File lib/graphs/gdf.rb, line 21
def write_gdf(filename, opts=nil)
    gdf = GDF::unparse(self, opts)
    f = File.open(filename, 'w')
    f.write(gdf)
    f.close
end
write_json(filename, opts=nil) click to toggle source

Write the current graph into a JSON file. This method is used internally, use Graph#write instead. @param filename [String] a valid filename @return [] @see JSON.unparse

# File lib/graphs/json.rb, line 21
def write_json(filename, opts=nil)
    json = JSONGraph::unparse(self, opts)
    f = File.open(filename, 'w')
    f.write(json)
    f.close
end
|(other) click to toggle source

Perform an OR operation on the current Graph and the given one. Returns a new graph which every node is in the current Graph and/or the other (idem for edges). @param other [Graph] @return [Graph]

# File lib/graph.rb, line 277
def |(other)
    return unless other.is_a?(Graph)

    nodes = @nodes | other.nodes
    edges = @edges | other.edges

    Graph.new(nodes, edges)
end