From 81fac775b56038c14d5559858005c71cf4f78aed Mon Sep 17 00:00:00 2001
From: "Pascal J. Bourguignon"
Date: Tue, 31 Jan 2012 22:31:14 +0100
Subject: [PATCH] Added methods to obtain arcs from edges in undirected graphs.

p80.lisp  37 ++++++++++++++++++++++++++++
1 file changed, 28 insertions(+), 9 deletions()
diff git a/p80.lisp b/p80.lisp
index 6bfc8d7..21cbd74 100644
 a/p80.lisp
+++ b/p80.lisp
@@ 162,21 +162,12 @@ directedgraph and undirectedgraph that can be represented in several
ways.
"))
(defmethod printobject ((self graph) stream)
 (printunreadableobject (self stream :identity t :type t)
 (let ((repname (classname (classof (slotvalue self 'representation)))))
 (format stream "as a~:[~;n~] ~A" (find (char (string repname) 0) "AEIOUY") repname))
 (format stream " with ~A node~:*~P and ~A edge~:*~P"
 (length (nodes self)) (length (edges self))))
 self)

(defclass undirectedgraph (graph)
()
(:documentation "
Undirected graphs can have only representations with edges.
"))

(defclass attributes ()
((propertylist :initform '()
:accessor propertylist :initarg :propertylist
@@ 190,6 +181,15 @@ An undirected edge. The order of the two nodes in the edgenodes list
is irrelevant.
"))
+(defmethod printobject ((self undirectedgraph) stream)
+ (printunreadableobject (self stream :identity t :type t)
+ (let ((repname (classname (classof (slotvalue self 'representation)))))
+ (format stream "as a~:[~;n~] ~A" (find (char (string repname) 0) "AEIOUY") repname))
+ (format stream " with ~A node~:*~P and ~A edge~:*~P"
+ (length (nodes self)) (length (edges self))))
+ self)
+
+
(defgeneric edgeswithnode (graph node)
(:documentation "Returns a list of the edges in GRAPH associating the given NODE.")
(:method ((g graph) node) (edgeswithnode (slotvalue g 'representation) node)))
@@ 210,6 +210,14 @@ A directed arc, from the FROM node to the TO node.
Note: the API allow for unidrected
"))
+(defmethod printobject ((self directedgraph) stream)
+ (printunreadableobject (self stream :identity t :type t)
+ (let ((repname (classname (classof (slotvalue self 'representation)))))
+ (format stream "as a~:[~;n~] ~A" (find (char (string repname) 0) "AEIOUY") repname))
+ (format stream " with ~A node~:*~P and ~A arc~:*~P"
+ (length (nodes self)) (length (arcs self))))
+ self)
+
(defgeneric arcsfromnode (graph node)
(:documentation "Returns a list of the arcs in GRAPH from the NODE.
@@ 432,6 +440,17 @@ Returns GR.
(removeifnot (lambda (edge) (member node (edgenodes edge))) (edges gr)))
+(defmethod arcsfromnode ((gr edgelistrepresentation) from)
+ (mapcar (lambda (edge)
+ (makeinstance 'arc :from from :to (first (remove from (edgenodes edge)))))
+ (edgeswithnode gr from)))
+
+(defmethod arcstonode ((gr edgelistrepresentation) to)
+ (mapcar (lambda (edge)
+ (makeinstance 'arc :to to :from (first (remove to (edgenodes edge)))))
+ (edgeswithnode gr to)))
+
+
;;; Edge list and nodes representation
;;; In this representation in addition to the list of edge, we
;;; maintain a list of nodes, so we may have isolated nodes too.

2.1.4