Wed Nov 13 03:11:53 2024
EVENTS
 FREE
SOFTWARE
INSTITUTE

POLITICS
JOBS
MEMBERS'
CORNER

MAILING
LIST

NYLXS Mailing Lists and Archives
NYLXS Members have a lot to say and share but we don't keep many secrets. Join the Hangout Mailing List and say your peice.

DATE 2017-02-01

LEARN

2024-11-13 | 2024-10-13 | 2024-09-13 | 2024-08-13 | 2024-07-13 | 2024-06-13 | 2024-05-13 | 2024-04-13 | 2024-03-13 | 2024-02-13 | 2024-01-13 | 2023-12-13 | 2023-11-13 | 2023-10-13 | 2023-09-13 | 2023-08-13 | 2023-07-13 | 2023-06-13 | 2023-05-13 | 2023-04-13 | 2023-03-13 | 2023-02-13 | 2023-01-13 | 2022-12-13 | 2022-11-13 | 2022-10-13 | 2022-09-13 | 2022-08-13 | 2022-07-13 | 2022-06-13 | 2022-05-13 | 2022-04-13 | 2022-03-13 | 2022-02-13 | 2022-01-13 | 2021-12-13 | 2021-11-13 | 2021-10-13 | 2021-09-13 | 2021-08-13 | 2021-07-13 | 2021-06-13 | 2021-05-13 | 2021-04-13 | 2021-03-13 | 2021-02-13 | 2021-01-13 | 2020-12-13 | 2020-11-13 | 2020-10-13 | 2020-09-13 | 2020-08-13 | 2020-07-13 | 2020-06-13 | 2020-05-13 | 2020-04-13 | 2020-03-13 | 2020-02-13 | 2020-01-13 | 2019-12-13 | 2019-11-13 | 2019-10-13 | 2019-09-13 | 2019-08-13 | 2019-07-13 | 2019-06-13 | 2019-05-13 | 2019-04-13 | 2019-03-13 | 2019-02-13 | 2019-01-13 | 2018-12-13 | 2018-11-13 | 2018-10-13 | 2018-09-13 | 2018-08-13 | 2018-07-13 | 2018-06-13 | 2018-05-13 | 2018-04-13 | 2018-03-13 | 2018-02-13 | 2018-01-13 | 2017-12-13 | 2017-11-13 | 2017-10-13 | 2017-09-13 | 2017-08-13 | 2017-07-13 | 2017-06-13 | 2017-05-13 | 2017-04-13 | 2017-03-13 | 2017-02-13 | 2017-01-13 | 2016-12-13 | 2016-11-13 | 2016-10-13 | 2016-09-13 | 2016-08-13 | 2016-07-13 | 2016-06-13 | 2016-05-13 | 2016-04-13 | 2016-03-13 | 2016-02-13 | 2016-01-13 | 2015-12-13 | 2015-11-13 | 2015-10-13 | 2015-09-13 | 2015-08-13 | 2015-07-13 | 2015-06-13 | 2015-05-13 | 2015-04-13 | 2015-03-13 | 2015-02-13 | 2015-01-13 | 2014-12-13 | 2014-11-13 | 2014-10-13

Key: Value:

Key: Value:

MESSAGE
DATE 2017-02-28
FROM Ruben Safir
SUBJECT Re: [Learn] decision making tree for a euler walk
From learn-bounces-at-nylxs.com Tue Feb 28 19:20:42 2017
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id 12E4E161313;
Tue, 28 Feb 2017 19:20:42 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id EEC4A160E77
for ; Tue, 28 Feb 2017 19:20:37 -0500 (EST)
To: learn-at-nylxs.com
References: <319ecec7-f60a-a905-c6a4-9749c89b9404-at-mrbrklyn.com>
<87zihbx8rx.fsf-at-contrapunctus.net> <87fuiy2e22.fsf-at-contrapunctus.net>
From: Ruben Safir
Message-ID:
Date: Tue, 28 Feb 2017 19:20:37 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.6.0
MIME-Version: 1.0
In-Reply-To: <87fuiy2e22.fsf-at-contrapunctus.net>
Subject: Re: [Learn] decision making tree for a euler walk
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,

List-Archive:
List-Post:
List-Help:
List-Subscribe: ,

Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: quoted-printable
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"

On 02/28/2017 04:36 PM, Christopher League wrote:
> =

> I can't believe you influenced me to try this, but I converted my
> previous Euler solution to avoid maps, sets, typedefs, and iterators.
> Instead it uses a vertex class and bunches of pointers. There is one
> usage of `std::find` from `` -- in order to remove a
> particular element from a vector (and that uses an iterator behind the
> scenes, but I didn't have to declare `something::iterator` anywhere).
> =

> CL

I didn't mean to do that at all. I'm interested in your implentation,
I'm just trying to schedule the time in to become less stupid.

> =

> ~~~~ {.cpp}
> // euler3.cpp
> #include
> #include
> #include
> #include
> #include "assertions.hh"
> #define LOG_LEVEL LOG_TRACE
> #include "debug-log.hh"
> using namespace std;
> =

> template
> struct vertex {
> vertex(const T& _data) : data(_data) { }
> void add_edge(vertex* dest);
> void remove_edge(vertex* dest);
> int degree() { return edges.size(); }
> ostream& show(ostream&);
> void add_directed_edge(vertex* dest) { edges.push_back(dest); }
> void remove_directed_edge(vertex* dest);
> T data;
> vector*> edges;
> };
> =

> // This adds undirected edge (both directions).
> template
> void vertex::add_edge(vertex* dest)
> {
> assert(dest !=3D NULL);
> add_directed_edge(dest);
> dest->add_directed_edge(this);
> }
> =

> template
> void vertex::remove_edge(vertex* dest)
> {
> assert(dest !=3D NULL);
> remove_directed_edge(dest);
> dest->remove_directed_edge(this);
> }
> =

> template
> void vertex::remove_directed_edge(vertex* dest)
> {
> edges.erase(find(edges.begin(), edges.end(), dest));
> }
> =

> template
> ostream& vertex::show(ostream& out)
> {
> out << data << ':';
> for(unsigned i =3D 0; i < edges.size(); i++) {
> out << ' ' << edges[i]->data;
> }
> return out << '\n';
> }
> =

> // Now graph is a thin wrapper around a set of vertices.
> template
> struct graph {
> ~graph(); // destructor
> vertex* add_vertex(const T& _data);
> vector*> euler_path();
> ostream& show(ostream&);
> private:
> vector*> vertices;
> };
> =

> template
> graph::~graph()
> {
> for(unsigned i =3D 0; i < vertices.size(); i++) {
> delete vertices.at(i);
> }
> vertices.clear();
> }
> =

> template
> vertex* graph::add_vertex(const T& _data)
> {
> vertex* v =3D new vertex(_data);
> vertices.push_back(v);
> return v;
> }
> =

> // Print the graph's adjacency list
> template
> ostream& graph::show(ostream& out)
> {
> for(unsigned i =3D 0; i < vertices.size(); i++) {
> vertices[i]->show(out);
> }
> return out;
> }
> =

> template
> ostream& operator << (ostream& out, graph& g)
> {
> return g.show(out);
> }
> =

> // Calculate and return an euler path. Algorithm basically taken from
> // here: http://www.graph-magics.com/articles/euler.php
> //
> // NOTE: this is destructive -- it removes edges from the graph. So if
> // you need the graph afterwards, make a copy.
> template
> vector*> graph::euler_path()
> {
> // If all vertices have even degree, choose any of them.
> unsigned i =3D 0;
> vertex* curr =3D vertices.at(i);
> // If there are exactly 2 vertices having an odd degree: choose one
> // of them. This will be the current vertex.
> unsigned num_odd =3D 0;
> for( ; i < vertices.size(); i++) {
> if(vertices.at(i)->degree() % 2 =3D=3D 1) {
> num_odd++;
> curr =3D vertices.at(i);
> }
> }
> log(LOG_INFO, "There were " << num_odd << " odd-degree vertices.");
> vector*> path;
> stack*> stack;
> if(num_odd !=3D 2 && num_odd !=3D 0) {
> log(LOG_ERROR, "Sorry, no Euler path exists.");
> return path;
> }
> log(LOG_DEBUG, "Starting at " << curr->data << '\n' << *this);
> // Repeat until the current vertex has no more neighbors and the
> // stack is empty.
> while(curr->degree() > 0 || stack.size() > 0) {
> // If current vertex has no neighbors,
> if(curr->degree() =3D=3D 0) {
> log(LOG_DEBUG, "* Adding " << curr->data << " to path.");
> // Add it to path
> path.push_back(curr);
> // Remove the last vertex from the stack and set it as the
> // current one.
> curr =3D stack.top();
> stack.pop();
> log(LOG_DEBUG, " New curr is " << curr->data);
> }
> else {
> // Add the vertex to the stack
> log(LOG_DEBUG, "* Pushing " << curr->data << " to stack.");
> stack.push(curr);
> // Take any of its neighbors, remove the edge between selected
> // neighbor and that vertex, and set that neighbor as the
> // current vertex
> vertex* n =3D curr->edges.at(0);
> log(LOG_DEBUG, " Removing " << curr->data << " <-> " << n->data);
> curr->remove_edge(n);
> curr =3D n;
> log(LOG_TRACE, *this);
> }
> }
> path.push_back(curr);
> return path;
> }
> =

> template
> ostream& operator << (ostream& out, const vector*>& vec)
> {
> for(unsigned i =3D 0; i < vec.size(); i++) {
> if(i > 0) {
> out << ", ";
> }
> out << vec.at(i)->data;
> }
> return out;
> }
> =

> graph* rubensburg_demo()
> {
> // Set up graph
> graph* gr =3D new graph;
> vertex* a =3D gr->add_vertex('A');
> vertex* b =3D gr->add_vertex('B');
> vertex* c =3D gr->add_vertex('C');
> vertex* d =3D gr->add_vertex('D');
> vertex* e =3D gr->add_vertex('E');
> vertex* f =3D gr->add_vertex('F');
> vertex* g =3D gr->add_vertex('G');
> a->add_edge(b);
> a->add_edge(b);
> a->add_edge(e);
> a->add_edge(f);
> a->add_edge(g);
> b->add_edge(e);
> b->add_edge(f);
> c->add_edge(d);
> e->add_edge(c);
> e->add_edge(g);
> =

> assert_eq(5, a->degree());
> assert_eq(2, g->degree());
> assert_eq(1, d->degree());
> =

> return gr;
> }
> =

> graph* even_degree_demo()
> {
> graph* gr =3D new graph;
> vertex* a =3D gr->add_vertex(13);
> vertex* b =3D gr->add_vertex(16);
> vertex* c =3D gr->add_vertex(18);
> a->add_edge(b);
> a->add_edge(c);
> b->add_edge(c);
> assert_eq(2, a->degree());
> assert_eq(2, b->degree());
> assert_eq(2, c->degree());
> return gr;
> }
> =

> // This is the actual K=F6nigsberg graph, for which no Euler path
> // exists.
> graph* impossible_demo()
> {
> graph* gr =3D new graph;
> vertex* a =3D gr->add_vertex("austin");
> vertex* b =3D gr->add_vertex("baltimore");
> vertex* c =3D gr->add_vertex("chicago");
> vertex* d =3D gr->add_vertex("dallas");
> a->add_edge(b);
> a->add_edge(b);
> a->add_edge(d);
> b->add_edge(c);
> b->add_edge(c);
> b->add_edge(d);
> c->add_edge(d);
> return gr;
> }
> =

> int main()
> {
> cout << "=3D=3D=3D=3D=3D=3D=3D Even-degree test\n";
> graph* g0 =3D even_degree_demo();
> cout << g0->euler_path() << '\n';
> delete g0;
> =

> cout << "=3D=3D=3D=3D=3D=3D=3D Odd-degree test\n";
> graph* g1 =3D rubensburg_demo();
> cout << g1->euler_path() << '\n';
> delete g1;
> =

> cout << "=3D=3D=3D=3D=3D=3D=3D Impossible test\n";
> graph* g2 =3D impossible_demo();
> cout << g2->euler_path() << '\n';
> delete g2;
> =

> return 0;
> }
> ~~~~
> =

> =

> =

> _______________________________________________
> Learn mailing list
> Learn-at-nylxs.com
> http://lists.mrbrklyn.com/mailman/listinfo/learn
> =



-- =

So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com

DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
http://www.nylxs.com - Leadership Development in Free Software
http://www2.mrbrklyn.com/resources - Unpublished Archive
http://www.coinhangout.com - coins!
http://www.brooklyn-living.com

Being so tracked is for FARM ANIMALS and and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn

  1. 2017-02-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] NP Complete
  2. 2017-02-06 Wayne Callahan <callahans2-at-msn.com> Subject: [Learn] [dinosaur] ISPH 2017
  3. 2017-02-07 James E Keenan <jkeen-at-verizon.net> Subject: [Learn] ny.pm tech meeting next Monday; TPC call for presentations
  4. 2017-02-08 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Immigration Executive Order Update
  5. 2017-02-08 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] Immigration Executive Order Update
  6. 2017-02-08 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Justine Bateman
  7. 2017-02-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Does this look like a Euler Path to you?
  8. 2017-02-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] Does this look like a Euler Path to you?
  9. 2017-02-09 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Does this look like a Euler Path to you?
  10. 2017-02-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] Does this look like a Euler Path to you?
  11. 2017-02-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] =?utf-8?q?Fwd=3A_An_Evening_for_Educators_with_Dr=2E_B?=
  12. 2017-02-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Does this look like a Euler Path to you?
  13. 2017-02-10 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] Choosing a programming language
  14. 2017-02-10 Christopher League <league-at-contrapunctus.net> Subject: [Learn] Choosing a programming language
  15. 2017-02-10 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Alternatives to Syntax Trees
  16. 2017-02-10 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Compiler positions available for week ending January 29
  17. 2017-02-10 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [Accu-contacts] Software engineer position
  18. 2017-02-10 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Euchambersia (Therapsida) envenoming
  19. 2017-02-11 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] lions and tigers and snow leopards
  20. 2017-02-11 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] New Neuronet theory
  21. 2017-02-11 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Researchers use artificial neural network to simulate a
  22. 2017-02-11 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Robotics
  23. 2017-02-11 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] WebRTC coding in html5
  24. 2017-02-12 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] fellowship positition
  25. 2017-02-15 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Starting with R
  26. 2017-02-15 Rick Moen <rick-at-linuxmafia.com> Subject: [Learn] [conspire] [svlug] AnC side-channel attack: In which ASLR
  27. 2017-02-16 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] are you here
  28. 2017-02-16 ruben <ruben-at-mrbrklyn.com> Subject: [Learn] chew on this
  29. 2017-02-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] ct scan
  30. 2017-02-16 Christopher League <league-at-contrapunctus.net> Subject: [Learn] Should I name "makefile" or "Makefile"?
  31. 2017-02-20 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] overloading operator== and casting
  32. 2017-02-20 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Vector Documentation
  33. 2017-02-22 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Network Patterns
  34. 2017-02-24 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] decision making tree for a euler walk
  35. 2017-02-24 Christopher League <league-at-contrapunctus.net> Re: [Learn] decision making tree for a euler walk
  36. 2017-02-24 Christopher League <league-at-contrapunctus.net> Re: [Learn] decision making tree for a euler walk
  37. 2017-02-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] decision making tree for a euler walk
  38. 2017-02-27 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Computational Phylogenies and fossil scanning
  39. 2017-02-28 Christopher League <league-at-contrapunctus.net> Re: [Learn] decision making tree for a euler walk
  40. 2017-02-28 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] decision making tree for a euler walk
  41. 2017-02-28 Nicholas Rodin <nikbbwil-at-icloud.com> Re: [Learn] thesis update
  42. 2017-02-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] thesis update
  43. 2017-02-28 Don Brinkman <Don.Brinkman-at-gov.ab.ca> Re: [Learn] visit
  44. 2017-02-28 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] [Hangout-NYLXS] Peer Review

NYLXS are Do'ers and the first step of Doing is Joining! Join NYLXS and make a difference in your community today!