Prev: Namespacing a class
Next: IMPORTANT: tr dropper.gen Trojan inside Ruby Installers for Windows
From: Chuck Brotman on 20 Jun 2010 14:20
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 ------------------
--
Posted via http://www.ruby-forum.com/.

From: Robert Klemme on 20 Jun 2010 16:55
On 20.06.2010 20:20, Chuck Brotman wrote:

> 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


--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/
From: Chuck Brotman on 21 Jun 2010 15:41
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


--
Posted via http://www.ruby-forum.com/.

From: Robert Klemme on 21 Jun 2010 17:14
2010/6/21 Chuck Brotman <brotman(a)nc.rr.com>:
> 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.  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)

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 = Struct.new :graph, :node_id do
def edges
graph.edges(node_id)
end
end

class Graph
include Enumerable

def initialize
@nodes = []
end

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

alias each each_node

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

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.  Do 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....  :(

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-2nd-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


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

From: Chuck Brotman on 21 Jun 2010 19:07
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
--
Posted via http://www.ruby-forum.com/.

 |  Next  |  Last
Pages: 1 2
Prev: Namespacing a class
Next: IMPORTANT: tr dropper.gen Trojan inside Ruby Installers for Windows