The Whiteboard

Jimmy Hoffa

9:08 PM

@gnat who throws someone out of a dinner party for that???

last I checked that is the description of what gets you invited...

user114359

I don't know about the cheap American beer but everything else sounds like the start of a good story

gnat

@JimmyHoffa yeah. Throwing out of party for Iron Maiden is terribly wrong...

iron Maiden - Powerslave

►

Robert Harvey

9:23 PM

@gnat That's classic.

gnat

@RobertHarvey yes! ...and therefore, totally appropriate at "formal dinner party" :)

with tuxedo

Ampt

you know, I agree that SE is like a wiki, but I feel that we lack the constant refinement that a Wiki has

Uncalled for

please change it back.

We mark questions as duplicates, but we never really consolidate that information

user41796

I had meant to play that better so I could say "FTFY, See we refine all the time."

user41796

@Ampt We could do better at requesting merges too

Ampt

I feel that the fact that mods can put words in my mouth is extremely unpleasant. If something is so bad that you need to edit it, you should just delete it

I'm sure there are legitimate uses out there but I'm definitely not a fan of it.

user41796

9:30 PM

@Ampt Sorry. I was just trying to tease you.

Ampt

I know :) but it's a little unnerving to have the words I typed out changed in front of me

user41796

To my knowledge, it's very rarely done. And when done, it's usually because of playing around.

Ampt

Nothing like losing your voice, eh?

user41796

@Ampt < Resisting the urge to edit this />

Jimmy Hoffa

-2

Q: What is the opposite or dual of a tree data structure?

Does have an opposite or dual? If so, what's it called? Maybe I'm missing something completely obvious. I could not find anything useful is searching on Google. Maybe that's because I'm not a native English speaker.

data-structures

^-- retract close votes if you have them... this question makes sense, it's just a little more conceptual than we normally get... perhaps it should be put in CS?

Robert Harvey

9:32 PM

[headdesk]

Jimmy Hoffa

it says "opposite or dual" he means, inverse.

user114359

please don't use CS as your toilet bowl

Jimmy Hoffa

It's not a toilet bowl

Robert Harvey

Someone better clarify that question in a hurry, or I'm breaking out the BFG-3000.

Jimmy Hoffa

I would like to keep it here

Robert Harvey

9:33 PM

17 secs ago, by Robert Harvey

Someone better clarify that question in a hurry, or I'm breaking out the BFG-3000.

Jimmy Hoffa

but if people here are determined not to know what he's talking about, CS will know what an inverse is

Robert Harvey

There's no such thing. How can you have an anti-tree, and how would it in any way be useful if you did?

Annihilation of real trees?

user114359

what happens if a tree and an anti-tree collide? Is it like matter and anti-matter? KABOOOOOOM!

Jimmy Hoffa

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union. Cographs have been discovered independently by several authors since the 1970s; early references include Jung (1978), Lerchs (1971), Seinsche (1974), and Sumner (1974). They have also been called D*-graphs (Jung 1978), hereditary Dacey graphs (after the related work of James C. Dacey...

^-- probably the answer

user41796

@JimmyHoffa Would you edit please so it's more accessible to the rest of us?

user41796

9:35 PM

And then I'll put the 5th VTC on there and we can vote to re-open quickly

Robert Harvey

> any single vertex graph is a cograph;

That's a tree.

Jimmy Hoffa

@GlenH7 ah, I'll see what I can do

@RobertHarvey ? huh

Robert Harvey

With no leaves.

user114359

that makes enough sense now, I retracted my vote

Robert Harvey

Fine, retracted my voted as well.

Jimmy Hoffa

9:42 PM

the answer's kinda in the question now...

The cotree T^* of a spanning tree T in a connected graph G is the spacing subgraph of G containing exactly those edges of G which are not in T (Harary 1994, p. 39).

user114359

Sounds like an answer to me. Also, might be worth cleaning up all those comments.

Jimmy Hoffa

A connected graph appears to be defined as a graph where all nodes can reach all nodes in all directions. So a cotree would be if you took a tree, drew lines to complete the graph, subtracted the relations definable in the initial tree, and tada.

Robert Harvey

Yeah, but why?

Jimmy Hoffa

because somebody was asking about it... if they were independently discovered structures, surely somebody was working towards something and bumped into them on multiple occasions, wouldn't have happened if they didn't serve as a solution to some people

Robert Harvey

Perhaps it belongs on Math then, if none of us know what purpose it would serve.

The Wikipedia article (and Wolfram) are less than helpful.

Jimmy Hoffa

9:47 PM

which is also why I mentioned CS... it is kinda somewhere more on the theoretic space... though it is reminiscent of the solution I was talking with @psr about recently for how you parse a left associative grammar with a right recursion

user114359

I made it through a B.S. and an M.S. in computer science without ever hearing about that data structure, nor have I used it in 15 years of development.

Jimmy Hoffa

you can parse left associative grammars with left recursion in a tree, but to do so with right recursion you have to turn the tree upside down

@Snowman you've never heard of a monoid but unknowingly used those on numerous occasions, sometimes formality is just that, formality - irrelevant details added to things that occur informally.

Robert Harvey

Are you saying that the node pointers would be reversed in an anti-tree?

How the hell would you get to the adjoining branch?

Jimmy Hoffa

@RobertHarvey they would definitely be reversed - in fact the trees pointers would not be there at all. The cotree excludes the edges in the original tree - and includes all possible edges that aren't in that tree (root->lowest children edges aren't in the tree, so they're in the cotree)

user114359

@JimmyHoffa I mean I have never used a data structure described that way regardless of its name. I am not saying it is useless, merely esoteric.

Jimmy Hoffa

9:56 PM

@Snowman again, if I described monoid to you as a closed set under an associative binary operation which had an identity element you'd say you've never used something that was "described that way" but you have used them a lot.

that's formality - a bunch of irrelevant details. Look at an informal example and you may realize "o, that thing, yeah I've used that"

user41796

I think I'm going to go VTC that question as "off-topic because it's something only Jimmy and the Haskell folk understand."

2

Jimmy Hoffa

@GlenH7 <|> mempty

:|

user41796

Yanking your chain, that's all

user41796

Er, shaking the tree?

Jimmy Hoffa

...Haskell puns FTW. you can't take anything seriously that involves insulting you with code :P

Telastyn

10:09 PM

I don't remember my inverses, I never learned that stuff formally.

or even informally.

Jimmy Hoffa

@Telastyn same here, but you talk about Haskell enough, I presumed you figured out co- means inverse by now

comonad, comonoid, cofunctor, coblabla

all inverses

Telastyn

sure, but so should've a lot of other people. Others that hopefully have a more solid grasp on the concept to provide a good answer.

Jimmy Hoffa

@Telastyn pfleh... you're FP answers are better than mine, I'm not doing it... and lord knows those "lots of other people" aren't on P.SE. If you want those who have a solid grasp to answer it, we should migrate it to TCS.SE, CS.SE, or Math.SE

It's sheer luck we have people who can answer some of these things here at all

Telastyn

probably should. I try to avoid FP answers since I've written like 500 lines of code in FP languages ever.