I'm representing small directed graphs as 2D matrices.
(case (aref matrix x y)
(0 not connected)
(+1 x->y)
(-1 y->x))
This is convenient, but it doesn't print nicely...
#2A((0 1 1 1 0 0 0 0)
(-1 0 1 1 0 0 0 0)
(-1 -1 0 1 0 0 0 0)
(-1 -1 -1 0 0 0 0 0)
(0 0 0 0 0 1 0 0)
(0 0 0 0 -1 0 0 0)
(0 0 0 0 0 0 0 1)
(0 0 0 0 0 0 -1 0))
Is there a way to get lisp to print this with the columns lining up?
(portable/sbcl solutions preferred)
Its not hard to do this manually with format, but I was hoping for
something that would work transparently throughout a repl session.
In the meantime, I switched to using 0,1,2; but that seems less clean.
Thanks,
Daniel
On Jan 17, 12:17 am, D Herring <········@at.tentpost.dot.com> wrote:
> I'm representing small directed graphs as 2D matrices.
> (case (aref matrix x y)
> (0 not connected)
> (+1 x->y)
> (-1 y->x))
>
> This is convenient, but it doesn't print nicely...
>
> #2A((0 1 1 1 0 0 0 0)
> (-1 0 1 1 0 0 0 0)
> (-1 -1 0 1 0 0 0 0)
> (-1 -1 -1 0 0 0 0 0)
> (0 0 0 0 0 1 0 0)
> (0 0 0 0 -1 0 0 0)
> (0 0 0 0 0 0 0 1)
> (0 0 0 0 0 0 -1 0))
>
> Is there a way to get lisp to print this with the columns lining up?
> (portable/sbcl solutions preferred)
>
> Its not hard to do this manually with format, but I was hoping for
> something that would work transparently throughout a repl session.
>
> In the meantime, I switched to using 0,1,2; but that seems less clean.
>
> Thanks,
> Daniel
Hi Daniel,
I don't quite understand the notation. The representation I have seen
for directed graphs works by putting a 1 in (aref matrix x y) if there
is a directed edge from x to y, otherwise 0. The y->x edge would be a
1 in (aref matrix y x), not a -1 in (aref matrix x y). So it is just
1s and 0s in the matrix. You seen to be duplicating information in
your matrix (the lower triangle is -1 times the upper one, mirrored on
the diagonal), which is something extra you have to keep consistent.
Am I missing something?
Tamas
Tamas <······@gmail.com> writes:
> On Jan 17, 12:17 am, D Herring <········@at.tentpost.dot.com> wrote:
>> I'm representing small directed graphs as 2D matrices.
>> (case (aref matrix x y)
>> (0 not connected)
>> (+1 x->y)
>> (-1 y->x))
>>
>> This is convenient, but it doesn't print nicely...
>>
>> #2A((0 1 1 1 0 0 0 0)
>> (-1 0 1 1 0 0 0 0)
>> (-1 -1 0 1 0 0 0 0)
>> (-1 -1 -1 0 0 0 0 0)
>> (0 0 0 0 0 1 0 0)
>> (0 0 0 0 -1 0 0 0)
>> (0 0 0 0 0 0 0 1)
>> (0 0 0 0 0 0 -1 0))
>>
>> Is there a way to get lisp to print this with the columns lining up?
>> (portable/sbcl solutions preferred)
>>
>> Its not hard to do this manually with format, but I was hoping for
>> something that would work transparently throughout a repl session.
>>
>> In the meantime, I switched to using 0,1,2; but that seems less clean.
>>
>> Thanks,
>> Daniel
>
> Hi Daniel,
>
> I don't quite understand the notation. The representation I have seen
> for directed graphs works by putting a 1 in (aref matrix x y) if there
> is a directed edge from x to y, otherwise 0. The y->x edge would be a
> 1 in (aref matrix y x), not a -1 in (aref matrix x y). So it is just
> 1s and 0s in the matrix. You seen to be duplicating information in
> your matrix (the lower triangle is -1 times the upper one, mirrored on
> the diagonal), which is something extra you have to keep consistent.
Indeed, the OP representation is strange.
How would he represent ({x,y},{(x,y),(y,x)}) ?
0 1
1 0
or
0 -1
-1 0
?
What would
0 -1
1 0
mean? ({x,y},{(x,y),(x,y)}) ???
> Am I missing something?
--
__Pascal Bourguignon__
·························@anevia.com
http://www.anevia.com
Pascal J. Bourguignon wrote:
> Tamas <······@gmail.com> writes:
>
>> On Jan 17, 12:17 am, D Herring <········@at.tentpost.dot.com> wrote:
>>> I'm representing small directed graphs as 2D matrices.
>>> (case (aref matrix x y)
>>> (0 not connected)
>>> (+1 x->y)
>>> (-1 y->x))
>>>
>>> This is convenient, but it doesn't print nicely...
>>>
>>> #2A((0 1 1 1 0 0 0 0)
>>> (-1 0 1 1 0 0 0 0)
>>> (-1 -1 0 1 0 0 0 0)
>>> (-1 -1 -1 0 0 0 0 0)
>>> (0 0 0 0 0 1 0 0)
>>> (0 0 0 0 -1 0 0 0)
>>> (0 0 0 0 0 0 0 1)
>>> (0 0 0 0 0 0 -1 0))
>>>
>>> Is there a way to get lisp to print this with the columns lining up?
>>> (portable/sbcl solutions preferred)
>>
>> I don't quite understand the notation. The representation I have seen
>> for directed graphs works by putting a 1 in (aref matrix x y) if there
>> is a directed edge from x to y, otherwise 0. The y->x edge would be a
>> 1 in (aref matrix y x), not a -1 in (aref matrix x y). So it is just
>> 1s and 0s in the matrix. You seen to be duplicating information in
>> your matrix (the lower triangle is -1 times the upper one, mirrored on
>> the diagonal), which is something extra you have to keep consistent.
>
> Indeed, the OP representation is strange.
Special problem, special notation. I'm not storing general directed
graphs; a connection x->y essentially means that x<y; so x->y->x
doesn't make sense (equality is not an option). The algorithm I'm
working on starts with a set of unconnected elements and runs until
all combinations of nodes are connected; thus it seemed efficient to
store both ends of each connection. Simple rules govern how
connections are made, but the optimal algorithm remains elusive.
Getting away from "can't see the forest for the trees", is there a
simple way to have the lisp printer align the matrix columns. For
example, is there an option to have it use vertical tabs or the
equivalent?
Thanks,
Daniel
On Jan 17, 9:06 pm, D Herring <········@at.tentpost.dot.com> wrote:
> Pascal J. Bourguignon wrote:
> > Tamas <······@gmail.com> writes:
>
> >> On Jan 17, 12:17 am, D Herring <········@at.tentpost.dot.com> wrote:
> >>> I'm representing small directed graphs as 2D matrices.
> >>> (case (aref matrix x y)
> >>> (0 not connected)
> >>> (+1 x->y)
> >>> (-1 y->x))
>
> >>> This is convenient, but it doesn't print nicely...
>
> >>> #2A((0 1 1 1 0 0 0 0)
> >>> (-1 0 1 1 0 0 0 0)
> >>> (-1 -1 0 1 0 0 0 0)
> >>> (-1 -1 -1 0 0 0 0 0)
> >>> (0 0 0 0 0 1 0 0)
> >>> (0 0 0 0 -1 0 0 0)
> >>> (0 0 0 0 0 0 0 1)
> >>> (0 0 0 0 0 0 -1 0))
>
> >>> Is there a way to get lisp to print this with the columns lining up?
> >>> (portable/sbcl solutions preferred)
>
> >> I don't quite understand the notation. The representation I have seen
> >> for directed graphs works by putting a 1 in (aref matrix x y) if there
> >> is a directed edge from x to y, otherwise 0. The y->x edge would be a
> >> 1 in (aref matrix y x), not a -1 in (aref matrix x y). So it is just
> >> 1s and 0s in the matrix. You seen to be duplicating information in
> >> your matrix (the lower triangle is -1 times the upper one, mirrored on
> >> the diagonal), which is something extra you have to keep consistent.
>
> > Indeed, the OP representation is strange.
>
> Special problem, special notation. I'm not storing general directed
> graphs; a connection x->y essentially means that x<y; so x->y->x
> doesn't make sense (equality is not an option). The algorithm I'm
> working on starts with a set of unconnected elements and runs until
> all combinations of nodes are connected; thus it seemed efficient to
> store both ends of each connection. Simple rules govern how
> connections are made, but the optimal algorithm remains elusive.
Perhaps if you told us what you are trying to do, we could help more.
< suggests a transitive relation, which would allow a more efficient
data structure.
> Getting away from "can't see the forest for the trees", is there a
> simple way to have the lisp printer align the matrix columns. For
> example, is there an option to have it use vertical tabs or the
> equivalent?
Not that I know of. You would have to traverse the matrix twice, see
the print-object method in my cl-sparsematrix package (use cliki.net,
or asdf-install) for an example. You can use that directly, just
replace sm-ref with aref. Or you could use that package right away,
your matrices seem sparse anyhow.
Tamas
D Herring <········@at.tentpost.dot.com> writes:
> Pascal J. Bourguignon wrote:
>> Tamas <······@gmail.com> writes:
>>
>>> On Jan 17, 12:17 am, D Herring <········@at.tentpost.dot.com> wrote:
>>>> I'm representing small directed graphs as 2D matrices.
>>>> (case (aref matrix x y)
>>>> (0 not connected)
>>>> (+1 x->y)
>>>> (-1 y->x))
>>>>
>>>> This is convenient, but it doesn't print nicely...
>>>>
>>>> #2A((0 1 1 1 0 0 0 0)
>>>> (-1 0 1 1 0 0 0 0)
>>>> (-1 -1 0 1 0 0 0 0)
>>>> (-1 -1 -1 0 0 0 0 0)
>>>> (0 0 0 0 0 1 0 0)
>>>> (0 0 0 0 -1 0 0 0)
>>>> (0 0 0 0 0 0 0 1)
>>>> (0 0 0 0 0 0 -1 0))
>>>>
>>>> Is there a way to get lisp to print this with the columns lining up?
>>>> (portable/sbcl solutions preferred)
>>>
>>> I don't quite understand the notation. The representation I have seen
>>> for directed graphs works by putting a 1 in (aref matrix x y) if there
>>> is a directed edge from x to y, otherwise 0. The y->x edge would be a
>>> 1 in (aref matrix y x), not a -1 in (aref matrix x y). So it is just
>>> 1s and 0s in the matrix. You seen to be duplicating information in
>>> your matrix (the lower triangle is -1 times the upper one, mirrored on
>>> the diagonal), which is something extra you have to keep consistent.
>> Indeed, the OP representation is strange.
>
> Special problem, special notation. I'm not storing general directed
> graphs; a connection x->y essentially means that x<y; so x->y->x
> doesn't make sense (equality is not an option). The algorithm I'm
> working on starts with a set of unconnected elements and runs until
> all combinations of nodes are connected; thus it seemed efficient to
> store both ends of each connection. Simple rules govern how
> connections are made, but the optimal algorithm remains elusive.
>
> Getting away from "can't see the forest for the trees", is there a
> simple way to have the lisp printer align the matrix columns. For
> example, is there an option to have it use vertical tabs or the
> equivalent?
Well you cannot define a print-object method on a built-in class (an
ARRAY), but you can encapsulate it in a struct or CLOS object.
(defstruct matrix values)
(defmethod print-object ((self matrix) stream)
(let ((width (scan-max-width (matrix-values self))))
(format stream "#S(~S ~S #2A(" 'matrix ':values)
(loop :for row :from 0 :below (array-dimension (matrix-values self) 0)
:do (format stream "~%(")
:do (loop :for col :from 0 :below (array-dimension (matrix-values self) 1)
:do (format stream " ··@S" width (aref (matrix-values self) row col)))
:do (format stream ")"))
(format stream "))~%"))
self)
(defun scan-max-width (array)
;; Implementation left as an exercise for the reader.
4)
C/USER1[93]> (make-matrix :values #2A((0 1 1 1 0 0 0 0)
(-1 0 1 1 0 0 0 0)
(-1 -1 0 1 0 0 0 0)
(-1 -1 -1 0 0 0 0 0)
(0 0 0 0 0 1 0 0)
(0 0 0 0 -1 0 0 0)
(0 0 0 0 0 0 0 1)
(0 0 0 0 0 0 -1 0)))
#S(MATRIX :VALUES #2A(
( 0 1 1 1 0 0 0 0)
( -1 0 1 1 0 0 0 0)
( -1 -1 0 1 0 0 0 0)
( -1 -1 -1 0 0 0 0 0)
( 0 0 0 0 0 1 0 0)
( 0 0 0 0 -1 0 0 0)
( 0 0 0 0 0 0 0 1)
( 0 0 0 0 0 0 -1 0)))
C/USER1[94]> #S(MATRIX :VALUES #2A(
( 0 1 1 1 0 0 0 0)
( -1 0 1 1 0 0 0 0)
( -1 -1 0 1 0 0 0 0)
( -1 -1 -1 0 0 0 0 0)
( 0 0 0 0 0 1 0 0)
( 0 0 0 0 -1 0 0 0)
( 0 0 0 0 0 0 0 1)
( 0 0 0 0 0 0 -1 0)))
#S(MATRIX :VALUES #2A(
( 0 1 1 1 0 0 0 0)
( -1 0 1 1 0 0 0 0)
( -1 -1 0 1 0 0 0 0)
( -1 -1 -1 0 0 0 0 0)
( 0 0 0 0 0 1 0 0)
( 0 0 0 0 -1 0 0 0)
( 0 0 0 0 0 0 0 1)
( 0 0 0 0 0 0 -1 0)))
Then instead of passing around mere arrays, you just pass them boxed
inside a matrix structure.
--
__Pascal Bourguignon__
Den Thu, 17 Jan 2008 21:06:09 -0500 skrev D Herring:
> Getting away from "can't see the forest for the trees", is there a
> simple way to have the lisp printer align the matrix columns. For
> example, is there an option to have it use vertical tabs or the
> equivalent?
http://www.lisp.org/HyperSpec/Body/sec_22-3-6.html
Cheers,
Maciej
PS. You actually want horizontal, not vertical tabs. Vertical tabs result
in multiple lines being output, which is not what you want.