I found a cute problem :
>From Wikipedia:
The Erdos number, honouring the late Hungarian mathematician Paul
Erdos, one of the most prolific writers of mathematical papers, is a
way of describing the "collaborative distance", in regard to
mathematical papers, between an author and Erdos.
An author's Erdos number is defined inductively as follows:
Paul Erdos has an Erdos number of zero.
The Erdos number of author M is one plus the minimum among the Erdos
numbers of all the authors with whom M coauthored a mathematical paper.
Erdos wrote around 1500 mathematical articles in his lifetime, mostly
co-authored. He had 509 direct collaborators; these are the people with
Erdos number 1. The people who have collaborated with them (but not
with Erdos himself) have an Erdos number of 2 (6,984 people), those
who have collaborated with people who have an Erdos number of 2 (but
not with Erdos or anyone with an Erdos number of 1) have an Erdos
number of 3, and so forth.
The problem :
Find the Erdos number for given author and given library .
(defvar library
(paper1 author1 author2...)
(paper2 author4 auhot5 ...))
Solution with calculating the Erdos numbers of all authors is simple ,
but does anybody has a solution finding the erdos number if you're
not calculating numbers of all authors?
cheers
bobi
"fireblade" <········@YAHOO.COM> writes:
> I found a cute problem :
>
>>From Wikipedia:
> The Erdos number, honouring the late Hungarian mathematician Paul
> Erdos, one of the most prolific writers of mathematical papers, is a
> way of describing the "collaborative distance", in regard to
> mathematical papers, between an author and Erdos.
>
> An author's Erdos number is defined inductively as follows:
>
> Paul Erdos has an Erdos number of zero.
> The Erdos number of author M is one plus the minimum among the Erdos
> numbers of all the authors with whom M coauthored a mathematical paper.
>
> Erdos wrote around 1500 mathematical articles in his lifetime, mostly
> co-authored. He had 509 direct collaborators; these are the people with
> Erdos number 1. The people who have collaborated with them (but not
> with Erdos himself) have an Erdos number of 2 (6,984 people), those
> who have collaborated with people who have an Erdos number of 2 (but
> not with Erdos or anyone with an Erdos number of 1) have an Erdos
> number of 3, and so forth.
>
> The problem :
> Find the Erdos number for given author and given library .
> (defvar library
> (paper1 author1 author2...)
> (paper2 author4 auhot5 ...))
The third argument to defvar must be a string!
> Solution with calculating the Erdos numbers of all authors is simple ,
> but does anybody has a solution finding the erdos number if you're
> not calculating numbers of all authors?
Run a breath first search from the author to Erdos.
;;; Some graph abstraction.
;; Assuming a undirected graph given as a list of cons of label and list
;; of nodes fully connected by edges labelled with this label, such as:
;;
;; (defvar *library*
;; '((paper1 author1 author2)
;; (paper2 author4 author5)
;; (paper3 author2 author5)
;; (paper4 author5 erdos)))
(defun nodes (graph)
(remove-duplicates (apply (function concatenate)
(quote list)
(mapcar (function cdr) graph))))
(defstruct labelled-edge from to label)
(defun edges-from (graph node)
(mapcan (lambda (edges)
(mapcar (lambda (to)
(make-labelled-edge :from node
:label (car edges)
:to to))
(remove node (cdr edges))))
(remove-if-not (lambda (edges) (member node (cdr edges))) graph)))
;;; Given the above graph abstraction, here is a breadth-first-search
(defun breadth-first-search (graph root compute-property complete-predicate
&key (test (function eql)) root-property)
(loop
:with arc = (list root)
:with properties = (make-hash-table :test test) ; node -> (walked . prop)
:while arc
:initially (setf (gethash root properties) (cons nil root-property))
:do (let* ((current (pop arc))
(prop (gethash current properties)))
(when (funcall complete-predicate graph current (cdr prop))
(loop-finish))
;; (print `(:current ,current :prop ,prop))
(unless (car prop)
(setf (car prop) t)
(dolist (edge (edges-from graph current))
(unless (car (gethash (labelled-edge-to edge) properties))
(setf (gethash (labelled-edge-to edge) properties)
(cons nil
(funcall compute-property graph edge (cdr prop))))
;; (print `(:next ,(labelled-edge-to edge) :prop
;; ,(gethash (labelled-edge-to edge) properties)))
(setf arc (nconc arc (list (labelled-edge-to edge))))))))
:finally (return properties)))
;;; Finally, the Erdos-number of author is simply:
(defun erdos-number-of-author (author)
(breadth-first-search *library* author
(lambda (g e p)
(declare (ignore g e))
(1+ p))
(lambda (g to p)
(declare (ignore g))
;; (print `(:to ,to))
(when (eql to 'erdos)
;; short-cut exit:
(return-from erdos-number-of-author p)))
:root-property 0))
(defvar *library*
'((paper1 author1 author2)
(paper2 author4 author5)
(paper3 author2 author5)
(paper4 author5 erdos)))
(mapcar (lambda (author) (cons author (erdos-number-of-author author)))
(nodes *library*))
--> ((AUTHOR1 . 3) (AUTHOR4 . 2) (AUTHOR2 . 2) (AUTHOR5 . 1) (ERDOS . 0))
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."
"fireblade" <········@YAHOO.COM> writes:
> I found a cute problem :
>
>>From Wikipedia:
> The Erdos number, honouring the late Hungarian mathematician Paul
> Erdos, one of the most prolific writers of mathematical papers, is a
> way of describing the "collaborative distance", in regard to
> mathematical papers, between an author and Erdos.
>
> An author's Erdos number is defined inductively as follows:
>
> Paul Erdos has an Erdos number of zero.
> The Erdos number of author M is one plus the minimum among the Erdos
> numbers of all the authors with whom M coauthored a mathematical paper.
>
> Erdos wrote around 1500 mathematical articles in his lifetime, mostly
> co-authored. He had 509 direct collaborators; these are the people with
> Erdos number 1. The people who have collaborated with them (but not
> with Erdos himself) have an Erdos number of 2 (6,984 people), those
> who have collaborated with people who have an Erdos number of 2 (but
> not with Erdos or anyone with an Erdos number of 1) have an Erdos
> number of 3, and so forth.
>
> The problem :
> Find the Erdos number for given author and given library .
> (defvar library
> (paper1 author1 author2...)
> (paper2 author4 auhot5 ...))
>
> Solution with calculating the Erdos numbers of all authors is simple ,
> but does anybody has a solution finding the erdos number if you're
> not calculating numbers of all authors?
>
I can't see how you can. The number depends on the minimum number of
the co-authors, so you surely need to know the Erdos number of the other
authors to know who has the minimum unless you define not calculating
as having a representation which abstracts the relationship - but even
to get that representation, the erdos number would have to be
calculated at some point.
At the uni I attended, all the office workstations in the building
were called erdos and had the erdos number of the person in that
building - we didn't have any 1's, but I think there was a couple of
twos and a few threes.
Tim
--
tcross (at) rapttech dot com dot au
Tim X <····@nospam.dev.null> writes:
> "fireblade" <········@YAHOO.COM> writes:
>
>> I found a cute problem :
>>
>>>From Wikipedia:
>> The Erdos number, honouring the late Hungarian mathematician Paul
>> Erdos, one of the most prolific writers of mathematical papers, is a
>> way of describing the "collaborative distance", in regard to
>> mathematical papers, between an author and Erdos.
>>
>> An author's Erdos number is defined inductively as follows:
>>
>> Paul Erdos has an Erdos number of zero.
>> The Erdos number of author M is one plus the minimum among the Erdos
>> numbers of all the authors with whom M coauthored a mathematical paper.
>>
>> Erdos wrote around 1500 mathematical articles in his lifetime, mostly
>> co-authored. He had 509 direct collaborators; these are the people with
>> Erdos number 1. The people who have collaborated with them (but not
>> with Erdos himself) have an Erdos number of 2 (6,984 people), those
>> who have collaborated with people who have an Erdos number of 2 (but
>> not with Erdos or anyone with an Erdos number of 1) have an Erdos
>> number of 3, and so forth.
>>
>> The problem :
>> Find the Erdos number for given author and given library .
>> (defvar library
>> (paper1 author1 author2...)
>> (paper2 author4 auhot5 ...))
>>
>> Solution with calculating the Erdos numbers of all authors is simple ,
>> but does anybody has a solution finding the erdos number if you're
>> not calculating numbers of all authors?
>>
>
> I can't see how you can. The number depends on the minimum number of
> the co-authors, so you surely need to know the Erdos number of the other
> authors to know who has the minimum unless you define not calculating
> as having a representation which abstracts the relationship - but even
> to get that representation, the erdos number would have to be
> calculated at some point.
Not at all. Read again the definition for the Erdos number:
>> Paul Erdos has an Erdos number of zero.
>> The Erdos number of author M is one plus the minimum among the Erdos
>> numbers of all the authors with whom M coauthored a mathematical paper.
The authors and co-authoring relationship define a undirected graph.
The Erdos number is the distance in this graph from an author to
Erdos. This distance is the minimal length of any path from this
author to Erdos (infinite if no such path exist). Obviously, distance
is a symetrical notion! You can easily compute this distance starting
from an author. See my other post for an example.
Note that by definition, for all paper, there exist e such as the set
of Erdos numbers of coauthors of this paper is always either {e} or
{e,e+1}. If it is {e}, (unless it's {0}), then all these coauthors
have written at least one other paper of which the set of coauthors'
Erdos numbers is {e-1,e}. A path using one of these edges will be
shorter than a path using the edges of the first paper.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush