[HN Gopher] How Graphviz thinks the USA is laid out
___________________________________________________________________
How Graphviz thinks the USA is laid out
Author : signa11
Score : 211 points
Date : 2021-01-02 07:21 UTC (15 hours ago)
(HTM) web link (shitpost.plover.com)
(TXT) w3m dump (shitpost.plover.com)
| jonahrd wrote:
| I assume RI is "bordering" NY because of the ferry to Block
| Island, but this feels somewhat wrong to me...
| joejohnson wrote:
| Came here to comment on this too. I guess the author included
| the maritime borders?
|
| https://en.m.wikipedia.org/wiki/Geography_of_New_York_(state...
| raldi wrote:
| State territory includes certain waterways. If two states'
| territories meet in the water, it counts.
| awinter-py wrote:
| hmm if the layout system had edge weights representing distance
| btwn centroids, this would be pretty exact with not that much
| extra information
| cowsandmilk wrote:
| The decision to say Michigan borders Minnesota and Illinois is
| weird to me. They have borders that are in the water and none on
| land.
| zeckalpha wrote:
| Many states have borders in the middle of a river. Just pretend
| the lakes are wide rivers, topologically.
| OskarS wrote:
| What about California and Hawaii or Alaska then? Where do you
| draw the line?
| greggyb wrote:
| International borders? There is not-US between each of
| Hawaii and Alaska and any other part of the country.
|
| There is no not-US between Michigan and Minnesota.
| macintux wrote:
| > There is not-US between each of Hawaii and Alaska and
| any other part of the country.
|
| What's the not-US between Hawaii and California?
|
| Update: oops, I get it. The ocean itself. Never mind,
| move along, nothing to see here.
| [deleted]
| raldi wrote:
| State territories, which include the waters of the Great
| Lakes but not the entirety of the Pacific Ocean
| Lammy wrote:
| I would draw the line when I could stand on one shore and
| not visually see the other side.
| pmiller2 wrote:
| So? The political boundaries between the states lie inside Lake
| Superior and Lake Michigan, respectively.
| willcipriano wrote:
| PA is similarly disconnected from NJ via the Delaware river,
| would you also say they don't border each other?
|
| https://en.wikipedia.org/wiki/Delaware_River#/media/File:Del...
| Retric wrote:
| So in your mind Alaska borders Texas?
| Quai wrote:
| Your comment is a good example of a strawman.
| Retric wrote:
| No, it's a serious question as topologically they do
| border each other. So, are they arguing being able to
| sail from A to B is enough or must they be sailing across
| freshwater etc. Borders do get drawn across bodies of
| water all the time, but deciding if France and the UK
| border each other but Spain and Italy don't is arbitrary.
| function_seven wrote:
| It's not arbitrary. You can get from France to UK without
| entering international waters, and without crossing
| waters controlled by another entity.
|
| I don't think you can do that with Spain and Italy? To
| get from one to the other you'd have to go through French
| or Algerian waters I think.
|
| And I might be agreeing with you; not sure here.
| Conversation went from rivers to lakes to "a coffee cup
| is the same as a donut" pretty quickly :)
| Retric wrote:
| Spain is the closest country to some parts of Italy. So,
| they limit each others economic exclusion zones. That
| said it's close to 400 miles between them across open
| ocean. Further economic exclusion zones are a fairly
| recent and thus an arbitrary thing.
| kgwgk wrote:
| Land borders are also arbitrary.
| bregma wrote:
| Topologically, Alaska borders Texas.
|
| Politically, since you can't walk from one to the other
| without crossing intervening political entities or relying
| on bulk transportation carriers, no.
|
| Then again, same with Minnesota and Michigan.
| greggyb wrote:
| Get in a row boat in Michigan. Row really hard. You can
| get to Minnesota without crossing any other border. And
| you'll come out the other side with ripped arms!
| Retric wrote:
| People can make the Atlantic crossing in a rowboat as
| well. https://www.cnn.com/2020/04/29/uk/rowing-solo-
| trans-atlantic...
|
| I suspect with the right boat someone could row from
| Alaska to Texas. Though it would probably take a full
| year.
| greggyb wrote:
| Yeah, but those would leave US territorial waters....
| bregma wrote:
| That may be the real key. Michigan to Minnesota stays
| within US territory. New York to Rhode Island and
| Providence Plantation stays within US territory. Texas to
| Alaska does not, no matter which mode of travel you
| chose. Texas to New York _might_. Shall we go there?
| cowsandmilk wrote:
| Lake Superior is the largest freshwater body of water in the
| world. Claiming there isn't a material difference between
| that and the Delaware River is weird.
|
| When we are looking at a map of the US, they don't draw the
| Delaware River. They do draw the Great Lakes.
| mbeex wrote:
| > freshwater body
|
| This implies volume. Baikal doubles LS in this respect.
| jrockway wrote:
| I think it implies surface area.
| fennecfoxen wrote:
| Lake Michigan-Huron is hydrologically just one lake and
| outsizes Lake Superior.
| mantap wrote:
| We are talking about a political map. So the essential question
| is: Are the Great Lakes managed by the federal government or by
| the states?
| maxerickson wrote:
| The answer to the question is yes.
| hirsin wrote:
| Adding bodies of water (great lakes, gulf, 2 oceans) may help
| fix the Rhode island issue and this one. Or perhaps make it
| worse (my expectation is they'd act as anchors of a sort)
| coldtea wrote:
| > _They have borders that are in the water and none on land._
|
| So? They still have borders. Borders are a geopolitical
| construct (that is, decided by treates and politics), not a
| geographical.
|
| They are merely informed/influenced by geography.
| siltpotato wrote:
| Ah, then the post should have gone farther: every coastal
| state, including Alaska and Hawaii, should have been bordered
| by each other.
| coldtea wrote:
| > Ah, then the post should have gone farther: every coastal
| state, including Alaska and Hawaii, should have been bordered
| by each other.
|
| That's not how geopolitical borders work. A country's
| segments (e.g. states) could have borders between them, but
| that doesn't mean that each has border with each other.
|
| They just all belong to the same entity (e.g. here, the US).
|
| (And state borders != country borders).
| alisonkisk wrote:
| What does that mean? What is the difference between
| "borders" and "border"?
| coldtea wrote:
| No difference, that grammatical change from plurar to
| singural wasn't part of my point. You can also read it
| as:
|
| "A country's segments (e.g. states) could have borders
| between them, but that doesn't mean that each has borders
| with each other."
|
| Another commenter explained what I meant well, but here's
| my explanation:
|
| The US might have a border with Canada, but doesn't mean
| that Colorado also has a border with Canada.
|
| Similarly, Alaska and Hawaii might be part of the US, and
| thus their borders are the US borders too, but that
| doesn't mean e.g. Hawaii borders Nebraska.
|
| Now borders might be on land or on water, but they're
| still borders. As long as another entity is not in
| between (e.g. Canada, as is the case between e.g. US and
| Alaska, or the Ocean between the US and Hawaii).
| SAI_Peregrinus wrote:
| Sufficiently far out from land (IIRC 10 miles) the ocean
| becomes "international waters", and no country legally
| controls it. There's a border between the territorial
| waters of a given country and these international waters
| along the coast.
|
| There's also noun/verb confusion. A state has borders
| (noun). A state can border another (verb). State A has a
| border, state B has a border, and A borders B.
|
| California has a border with International Waters. Hawaii
| is directly surrounded by International Waters.
| California does not border Hawaii, though both have
| borders and border International Waters.
| Semiapies wrote:
| I wonder whether adding Canada and Mexico as nodes would
| "improve" some of the first few graphs.
| tel wrote:
| I would like to see this done more granularly (counties?) and
| again using population flows to weight edges (and thus
| introducing non-local edges). I'm somewhat surprised I've never
| seen this before and think it'd be very illustrative.
| sleavey wrote:
| These are commonly drawn in circular layout, like this:
| https://sites.google.com/a/parishepiscopal.org/mr-rick-
| dunn/....
| ink_13 wrote:
| I'll wager the New England problem could be resolved by
| reordering the input data. GraphViz outputs are not independent
| of the ordering of inputs.
| someguy101010 wrote:
| What is the New England problem? Hard to google for this.
| matt_kantor wrote:
| It's from the article. Some of the New England states get
| flipped around relative to their actual geographic positions:
|
| > New England is where it should be, but Vermont should be
| switched with Connecticut and Rhode Island.
| mattst88 wrote:
| It's funny that he would notice that but not notice that RI
| and CT are reversed in his graph. E.g., NY
| -- PA, RI, VT
|
| New York borders Connecticut, but not Rhode Island.
| kevin_thibedeau wrote:
| There is a water border between long island and Rhode
| Island.
| jpindar wrote:
| New York borders Rhode Island in the water.
|
| Google maps shows a border.
|
| https://www.google.com/maps/place/Long+Island+Sound/@41.3
| 418...
| [deleted]
| andromeduck wrote:
| This is mostly an artifact of how eastern states states are
| smaller because most states on accession to the union were within
| an order of magnitude vs peers population wise and the east was
| much more densely populated.
|
| I do wonder though if the west coast wouldn't be better managed
| if the states were split up a bit more population wise like in
| the east.
| zimpenfish wrote:
| I tried the same thing in 2004 with the London Underground map
| connections. It was not entirely a disaster.
|
| https://f000.backblazeb2.com/file/rjp-hosted-files/bigneatot...
|
| (Also the linked graphviz file has FL only linked to GA - surely
| it should have AL as well since AL is linked to FL?)
| drran wrote:
| Maybe, qvge (editor for graphs) may help you.
|
| https://github.com/ArsMasiuk/qvge
| zimpenfish wrote:
| This was just to see if an automatic layout algorithm could
| make sense of connections between stations. ("Kinda. If you
| squint.")
| prionassembly wrote:
| I don't have the image at hand anymore, but I did Brazilian
| states (with Graphviz defaults) many years ago and boy, it
| was excellent.
| ddek wrote:
| It amuses me how the Northern line is generally the right
| shape, but is upside down.
| bibinou wrote:
| Florida is already linked to Alabama at the top:
| > AL -- FL, GA, MS, TN
| zimpenfish wrote:
| Oh, yeah, but I figured it'd include both links, not just the
| first one alphabetically. But I guess it doesn't make much
| odds either way.
| ehvatum wrote:
| A physical adjacency graph of fairly regular shapes will end up
| resembling the original arrangement, when laid out to minimize
| edge lengths.
| phreeza wrote:
| Weird that it plots a planar graph in a slightly non-planar way
| in the northeast.
| ygra wrote:
| Force-directed layout has no guarantees that a planar graph
| will be drawn planar. It often comes out that way, given how
| the algorithm works, but not always. Especially nodes that are
| "trapped" between others may have trouble "escaping" to the
| other side of an edge at times, due to the forces involved.
|
| It may help increasing the dimensions for Graphviz (I think its
| force-directed layout can work in up to 10 dimensions), but
| there's still a step involved that projects everything to 2D in
| the end, so it might still happen.
| graphviz wrote:
| Yes, force-directed layout doesn't consider number of
| crossings. dot is the only graphviz program that reduces
| crossings, and because of the level assignment constraint,
| even small graphs like K_4 or K_2,2 have crossings that could
| be avoided by just routing edges differently.
|
| Yes, you can set NDim,
| https://graphviz.org/doc/info/attrs.html#d:dim I'm not sure
| why we said up to 10. It's hard to see even in 8 dimensional
| space!
|
| In terms of drawing graphs of the U.S. states or data like
| that, it should be possible to, say, create a point at the
| centroid of every region, then connect the adjacent regions
| to form a mesh, then feed the mesh to neato with some options
| to relax the layout but retain the mesh. This is what the
| overlap removal algorithm does anyway. See
| https://www.graphviz.org/Documentation/GH10.pdf, at least the
| figures.
|
| There's plenty of recent work that improves on some of the
| graphviz algorithms. It's a pity that without a convenient
| way to incorporate such inventions in a larger system, it
| tends to languish and not have as much impact or isn't easily
| available to people that could use it. Nocaj/Ortmann/Brandes
| work on untangling hairballs is another example:
| http://jgaa.info/accepted/recent/NocajOrtmannBrandes.pdf We
| even have this prototyped in a directory somewhere but it
| would be more work to merge it into the release.
| gspr wrote:
| I wonder how a SOM [1] would lay it out.
|
| [1] https://en.wikipedia.org/wiki/Self-organizing_map
| amelius wrote:
| Different kind of map.
| sleavey wrote:
| It'd be fun to see this for the whole world. It would also make
| it easy to compute the answers to common quiz questions involving
| doubly landlocked countries, countries with most borders, etc.
| brokensegue wrote:
| here's the whole world done this way using Wikidata
| https://twitter.com/derenrich/status/1228508337559392261/pho...
| but the labels are removed and it includes maritime borders to
| make it a (very hard) guessing game
| macintux wrote:
| Curiously that doesn't seem to be accessible without logging
| in to Twitter, and I'm not inclined to do so at the moment;
| do you have another link to the game?
| brokensegue wrote:
| odd. the link works for me in a logged out/incognito
| window.
|
| here's an imgur link: https://imgur.com/a/MppJE4c
| macintux wrote:
| Yeah, I'm not sure what to make of it. Can't remember the
| last time Twitter told me I couldn't retrieve a link...
|
| And this time I checked, it's accessible. Must have been
| a transitory glitch.
|
| Thanks.
| genera1 wrote:
| I think Twitter might be throttling anonymous/not logged
| in users. On desktop, where I'm logged in I've never had
| an issue with retrieving content, on mobile, where I'm
| not, no matter the browser, it's hit or miss (I'd
| estimate around 30% of the time I need to refresh)
| read_if_gay_ wrote:
| I'm seeing that too sometimes, a refresh usually fixes
| it.
| X-Istence wrote:
| Did you open it in a tab that was not immediately made
| active?
|
| There seems to be some sort of issue with Twitter whereby
| the javascript to fetch/render the tweet doesn't fire if
| you open it in a background tab and then visit the tab.
|
| Refreshing the page causes the javascript to correctly fire
| and the tweet is displayed. This is due to Twitter no
| longer pre-rendering the page server side, its all done
| client side.
|
| Also makes it impossible to use Twitter from a browser with
| javascript disabled.
| cma wrote:
| Why does Twitter hate tabs so much? Sometimes it is
| impossible to open threads on there in a new tab through
| middle mouse or long press on mobile.
| amw-zero wrote:
| The idea of optimizing a graph layout based on the subject matter
| that its modeling is a really interesting idea. I'm in the camp
| of always interested in more visual programming techniques /
| aids, so it would be really great for us to be able to visualize
| something as complex as a large program this way.
| matt_kantor wrote:
| I've used dot+graphviz to visualize algorithms and data
| structures before. The syntax makes it really easy to get
| started with, just print out "x -> y;" in your inner loop or
| whatever.
| jnurmine wrote:
| Would it help to provide more information by adding edge weight
| as the length of the shared border between the two states?
| ape4 wrote:
| Weighted by distance between capitals perhaps.
| Someone wrote:
| Capitals can be very much eccentric in a state (the distance
| from Cheyenne, Wyoming to Helena, Montana is (eyeballing)
| about three times that to Denver, Colorado, for example, but
| I would say Wyoming borders Montana about as much as it
| borders Colorado)
|
| Average distance of all pairs of points in the two states
| (hm, maybe not. That could behave weirdly for states that
| aren't very 'compact') or geometric mean of the fraction of a
| state's border shared with the neighboring state would be
| fairer. Or maybe, the geometric mean of the fraction of the
| area of State S is closest to state T and the fraction of the
| area of state T that is closest to S?
|
| Alternatively, make the states clusters, add all cities on
| highways as vertices, and use highways stretches between
| cities as edges.
| jnurmine wrote:
| Hmm, good idea. Or weighted by distance between midpoint of
| state?
|
| The idea being that, to my knowledge, the state capitals are
| not in the middle always, thus leading to some form of
| distortion.
| spc476 wrote:
| Byte Magazine had an article in 1986 that drew the US based on
| distances between cities. https://archive.org/details/byte-
| magazine-1986-08/page/n103/...
| raldi wrote:
| See also: US map made entirely out of rectangles
|
| https://www.reddit.com/r/MapPorn/comments/bg8e7v/united_stat...
| UncleOxidant wrote:
| OR dominates the west coast!
| jackcosgrove wrote:
| This map makes it clear that it's New York, not Pennsylvania,
| which is the keystone state.
| jgalt212 wrote:
| It also makes you google why St. Louis lost out to Chicago.
___________________________________________________________________
(page generated 2021-01-02 23:02 UTC)