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
|
|
