General Confusion

[Chuck Brotman]

I'm confused! I may have bitten off more than I can chew!

This question may be more about OOP ion general than Ruby, but since I'm
implementing in Ruby (trying to, anyway) I thought I'd start here. If I
should be posting elsewhere please let me know.

Here's the problem:
I'm trying to write my own graph theory library. I'm aware of
Adjacency matrices and the like, but I want to do this as OO as
possible, using objects of class node and edge to implement.

Each node has a name and an array of adjacent nodes. How can I add a
reference to a node which is adjacent,if I haven't created that node
yet? Or, do I have to create all the nodes first (without adjacencies
and then back fill them?) Or??

I feel like this should be doable, but I'm having trouble "wrapping my
head around it!". Here's an early cut at my class def for Node:

TYhanks for any help you are able to provide...

Chuck

#Node ----------------------------------.
class Node
attr_accessor :name, :nextnode, :adjacencies

def initialize(name, adjacencies)
@name = name
@adj = adjacencies
self.report "***new node #{@name}, created= [{#{@name} |
#{@adj.inspect}]\n"
end #initialize

def to_s
return "001 [#{@name.inspect}),#{@adj.insert ","}]"
end # to_s

end #node class-----------

#Edge --------------------

class Edge
attr_accessor :name, :N1, :N2

def initialize (name,n1, n2)
@name = name
@n1 = n1
@n2 = n2
print ("\n200:new edge, [#{@name}] created= [#{@n1}-#{@n2}]")
end # initialize
end # edge class ------------------

 

[Robert Klemme]

This question may be more about OOP ion general than Ruby, but since I'm
implementing in Ruby (trying to, anyway) I thought I'd start here. If I
should be posting elsewhere please let me know.

The place is perfectly OK.

Here's the problem:
I'm trying to write my own graph theory library. I'm aware of
Adjacency matrices and the like, but I want to do this as OO as
possible, using objects of class node and edge to implement.

Each node has a name and an array of adjacent nodes. How can I add a
reference to a node which is adjacent,if I haven't created that node
yet? Or, do I have to create all the nodes first (without adjacencies
and then back fill them?) Or??

You need to have the node created before you add it if you want to keep
direct references. I'd say that is pretty much straightforward. Note
that you do not need to create *all* nodes before you start creating edges.

If you implement your graph in a way so nodes have ids (say integers)
you could use those for referencing other nodes. But then you also need
some mechanism to record which nodes are there, i.e. you could create
another class Graph which holds that information.

Kind regards

robert

 

[Chuck Brotman]

Robert,

Thanks for your response!
You wrote:

"You need to have the node created before you add it if you want to keep
direct references. I'd say that is pretty much straightforward. Note
that you do not need to create *all* nodes before you start creating
edges.

If you implement your graph in a way so nodes have ids (say integers)
you could use those for referencing other nodes. But then you also need
some mechanism to record which nodes are there, i.e. you could create
another class Graph which holds that information.

"

Please help me better understand this.
1) Direct references vs ??? Pleas elaborate on the alternative(s)
2) When you say "you do not need to create *all* nodes before you start
creating edges." I assume that you mean I can create an edge as soon as
the end nodes for that edge have been created, even if other edges are
still non-existant. Do I understand that correctly?
3)I expected that I would nee to create a class "Graph" so I think I'm
in sync with your second paragraph

Sometimes I look at this stuff and it seems "so obvious". Then, I try to
implement it and it no longer seems so....


Thanks again,
Chuck

 

[Robert Klemme]

Robert,

Thanks for your response!

You're welcome.

You wrote:

"You need to have the node created before you add it if you want to keep
direct references. =A0I'd say that is pretty much straightforward. =A0Not= e
that you do not need to create *all* nodes before you start creating
edges.

If you implement your graph in a way so nodes have ids (say integers)
you could use those for referencing other nodes. =A0But then you also nee= d
some mechanism to record which nodes are there, i.e. you could create
another class Graph which holds that information.

"

Please help me better understand this.
1) Direct references vs ??? =A0Pleas elaborate on the alternative(s)

Assume nodes are not that interesting for your problem but it's rather
the edges. In that case you could use integers as keys and do
something like

Node =3D Struct.new :graph, :node_id do
def edges
graph.edges(node_id)
end
end

class Graph
include Enumerable

def initialize
@nodes =3D []
end

def each_node(&b)
@nodes.keys.each(&b)
self
end

alias each each_node

def add_edge(from, to)
(@nodes[from] ||=3D []) << to
self
end

def edges(node_id)
@nodes[node_id] || []
end

def node(node_id)
Node.new(self, node_id)
end
end

Where from and to must be Fixnums. This is of course only half baked
and not very consistent. I tried to illustrate a situation where you
work with node_ids most of the time. This is probably only reasonable
when working with large graphs where saving the memory can be crucial.
From a usability point of view your original approach is much better
to handle and easier to grasp I believe.

It's an interesting exercise to implement graph algorithms in a way
that they are independent from graph representation. That way you can
exchange the graph representation (objects with references, adjacency
matrix etc.) and keep the algorithm implementation.

2) When you say "you do not need to create *all* nodes before you start
creating edges." I assume that you mean I can create an edge as soon as
the end nodes for that edge have been created, even if other edges are
still non-existant. =A0Do I understand that correctly?
Absolutely.

3)I expected that I would nee to create a class "Graph" so I think I'm
in sync with your second paragraph

It might not be needed in all cases but it can be a handy tool for
operations that affect the whole graph (e.g. enumerate all Nodes).

Sometimes I look at this stuff and it seems "so obvious". Then, I try to
implement it and it no longer seems so.... =A0

Hehe. In my experience it takes a bit of practice to get used to OO.
I personally find one of the most comprehensive works on the matter
the book by Bertrand Meyer:
http://docs.eiffel.com/book/method/object-oriented-software-construction-2n=
d-edition

It is quite large so you might not want to read it cover to cover but
it also serves as a good encyclopedia of all important OO terms and
concepts.

Kind regards

robert


--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Chuck Brotman]

Robert,

Thanks again for your (second) response. I will probably print it out
and study it. I appreciate you taking your time to explain and provide
examples

And yes, it occurred to me (last night) that I should work to hide the
implementation... but first I want to have an implementation to hide

Best regards,

Chuck

 

[Chuck Brotman]

Robert,

Thanks again for your (second) response. I will probably print it out
and study it. I appreciate you taking your time to explain and provide
examples

And yes, it occurred to me (last night) that I should work to hide the
implementation... but first I want to have an implementation to hide


Also a big thank you to Gary Wright Whose reply reached me by email, but
I haven't seen in the forum. He also gave me a lengthy reply, replete
with sound advice and examples!

Thanks, I'll be reviewing both responses until I get a handle on this

Best regards,

Chuck

 

[Chuck Brotman]

Robert,

In looking over the code samples you provided:
------------
def add_edge(from, to)
(@nodes[from] ||= []) << to
self
end

def edges(node_id)
@nodes[node_id] || []
end

def node(node_id)
Node.new(self, node_id)
end
end
------------
I find I am a puzzled:
Even given that to, from are fixnums:
1) what does "@nodes[node_id] || []" return?
2) same question for: "@nodes[from] ||= []) << to"
I could find no reference to this " ||= " syntax (in Pickax, or
other ruby texts, nor online Nor do I understand it's semantics...

3) how about Node.new(self, node_id) I have trouble with the use of
"self" here, the whole usage of "self" has caused me confusion, ever
since I started playing with OO (back when java was IT!)

Thanks,
Chuck

 

[Robert Klemme]

Robert,

In looking over the code samples you provided:
------------
def add_edge(from, to)
(@nodes[from] ||= []) << to
self
end

def edges(node_id)
@nodes[node_id] || []
end

def node(node_id)
Node.new(self, node_id)
end
end

It returns @nodes[node_id] if that is not nil and not false - otherwise
you get a new empty Array (from [] which is just special syntax for
Array.new). This is done so the caller can rely on an Array being
returned from this method under all circumstances so you can do

gr.edges(17).each do |node|
puts "17 -> #{node}"
end

and do not have to verify that the result of #edges is non nil.

2) same question for: "@nodes[from] ||= []) << to"
I could find no reference to this " ||= " syntax (in Pickax, or
other ruby texts, nor online Nor do I understand it's semantics...

I don't have my Pickaxe here right now but I would be surprised to find
||= not explained. There also were some threads about operator ||=
recently. It boils down to

a ||= b

being short for

a || (a = b)

In this case

@nodes[from] || (@nodes[from] = [])

In prose: set @nodes[from] to an empty Array if unset.

The "<< to" at the end simply concatenates to the Array returned from
the expression in brackets.

3) how about Node.new(self, node_id) I have trouble with the use of
"self" here, the whole usage of "self" has caused me confusion, ever
since I started playing with OO (back when java was IT!)

In a Ruby program at any point in time "self" points to an object. You
cannot assign to "self". "self" is implicitly set when a method call
with an explicit receiver is executed. If you execute "a.foo" then
"self" is set to "a" while inside the method.

Maybe you have a look at Chris Pine's learning to program. A general
advice: if you are unsure about expressions you find in programs or
postings here you can pretty easily try them out in IRB and see what
they do.

Kind regards

robert

 

[Chuck Brotman]

Robert

The more I learn about Ruby, the more impressed I am! (though it takes a
fair amount of work to try and get a handle on it all)

I wrote you a line by line response to your latest reply, but it appears
that it got swallowed by "the system" and hasn't shown up here yet! In
any case, I'll be away for a a week or two and will reestablish activity
in this thread when I return -- or can find a pc to correspond from.

TTY then...

Thanks again for you help!

Chuck