gistfile1.rb

require "spec_helper"

describe AdjacencyMatrix do

  context "undirected graph" do
    let(:pitt2pitt) {
      AdjacencyMatrix.connections({"Pittsburgh" => "Pittsburgh"}, false)
    }
    let(:pitt2clev) {
      AdjacencyMatrix.connections({"Pittsburgh" => "Cleveland"}, false)
    }

    it "has a link if an item is linked to itself" do
      pitt2pitt.connection_exists?("Pittsburgh", "Pittsburgh").should be_true
    end

    it "doesn't freak out if asked about an item that's not there, just says no connection" do
      # This way we don't have to explicitly specify those vertices that are
      # not connected at all.
      pitt2pitt.connection_exists?("Pittsburgh", "Cleveland").should be_false
    end

    it "has a link if two different items are linked, and no other links" do
      pitt2clev.connection_exists?("Pittsburgh", "Pittsburgh").should be_false
      pitt2clev.connection_exists?("Pittsburgh", "Cleveland" ).should be_true
      pitt2clev.connection_exists?("Cleveland",  "Pittsburgh").should be_true
      pitt2clev.connection_exists?("Cleveland",  "Cleveland" ).should be_false
    end

    it "has the same number of incoming and outgoing links for each item" do
      pitt2clev.incoming_connections("Pittsburgh").should eql(1)
      pitt2clev.outgoing_connections("Pittsburgh").should eql(1)
      pitt2clev.incoming_connections("Cleveland" ).should eql(1)
      pitt2clev.outgoing_connections("Cleveland" ).should eql(1)
    end
  end

  context "directed graph" do
    let(:pitt2pitt) {
      AdjacencyMatrix.connections({"Pittsburgh" => "Pittsburgh"})
    }
    let(:pitt2clev) {
      AdjacencyMatrix.connections({"Pittsburgh" => "Cleveland"})
    }
    let(:pitt2clev2chic) {
      AdjacencyMatrix.connections({"Pittsburgh" => "Cleveland",
                                   "Cleveland"  => "Chicago"})
    }

    it "has a link if an item is linked to itself" do
      pitt2pitt.connection_exists?("Pittsburgh", "Pittsburgh").should be_true
    end

    it "has a link if two different items are linked, and no other links" do
      pitt2clev.connection_exists?("Pittsburgh", "Pittsburgh").should be_false
      pitt2clev.connection_exists?("Pittsburgh", "Cleveland" ).should be_true
      pitt2clev.connection_exists?("Cleveland",  "Pittsburgh").should be_false
      pitt2clev.connection_exists?("Cleveland",  "Cleveland" ).should be_false
    end

    it "gets the row for an item" do
      pitt2clev.row("Pittsburgh").should eql([0, 1])
      pitt2clev.row("Cleveland" ).should eql([0, 0])
    end

    it "gets the column for an item" do
      pitt2clev.column("Pittsburgh").should eql([0, 0])
      pitt2clev.column("Cleveland" ).should eql([1, 0])
    end

    it "has different numbers of incoming and outgoing links" do
      pitt2clev.incoming_connections("Pittsburgh").should eql(0)
      pitt2clev.outgoing_connections("Pittsburgh").should eql(1)
      pitt2clev.incoming_connections("Cleveland" ).should eql(1)
      pitt2clev.outgoing_connections("Cleveland" ).should eql(0)
    end

    it "has all 0s if we square it if there are no links of length 2 between elements" do
      (pitt2clev ** 2).to_a.should eql([[0, 0], [0, 0]])
    end

    it "has 1s in the square of the matrix where there are links of length 2" do
      @squared = pitt2clev2chic ** 2
      @squared.connection_exists?("Pittsburgh", "Chicago").should be_true
    end
  end
end