On 1/1/21 12:12 PM, Jonathan Fine wrote:
> Hi Richard
>
> You suggested
>
> A very simple and in my mind reasonable use for this is to build a
> representation of a graph, where each node is represented by a
> list (or
> some other collection), and the connections are denoted by adding to
> that collection the nodes that are adjacent (or maybe a tuple of the
> node and the distance). This naturally creates a recursive structure
> unless connections are unidirectional and the graph is acyclical
> (i.e. a
> tree).
>
> For example, a 3 node fully connected graph might be:
>
> a = []
> b = []
> c = []
>
> a.append(b)
> a.append(c)
> b.append(a)
> b.append(c)
> c.append(a)
> c.append(b)
>
>
> According to https://en.wikipedia.org/wiki/Graph_theory#Graph
> <https://en.wikipedia.org/wiki/Graph_theory#Graph>, a graph is an
> ordered pair
> >>> G = (V, E)
> where V is a set of vertices, and E is a set of edges, where an edge
> is an unordered pair of vertices.
>
> You've given the complete graph on 3 vertices (although without
> explicitly stating the vertex set V).
> https://en.wikipedia.org/wiki/Complete_graph
> <https://en.wikipedia.org/wiki/Complete_graph>
>
> If we use the wikipedia definition (with vertices 'a', 'b' and 'c') we
> have
> >>> V = {'a', 'b', 'c'}
> >>> E = {{'a', 'b'}, {'a', 'c'}, {'b', 'c'}}
>
> I've shown how to represent graphs, by directly translating the
> mathematical definition into Python (without introducing any
> additional classes). You've produced a different way to represent graphs.
>
> Mathematically, your representation is this. There is a set V of
> vertices. Further, for each v in V there is associated a subset V_v of
> V. Further, if w in V_v then v in V_w.
>
> I wouldn't call what you've written down the Python representation of
> this mathematical definition. To explain this, I'll write down what I
> think it should be.
>
> Suppose G is a graph with vertices {'a', 'b', 'c', 'd'}. Using a dict
> to represent the map that v goes to V_v, we can write G as
> {
> 'a': {...},
> 'b': {...},
> # etc
> 'e': {...},
> }
>
> My initial post suggests that, purely on the basis of the loop in the
> data structure, there's a code smell in the representation you
> provided. I'd say that not agreeing with its own mathematical
> definition is a code smell (or worse).
>
> I'll put it another way. Suppose our vertices are called (or
> represent) Alice, Bob, Carol, Dave and Eve. Now let G be the graph
> whose edges represent the existence of cryptographically secure
> communication between X and Y. I claim that your code isn't able to
> represent such a graph.
>
> Thank you Richard for forcing me to think things through and find what
> I consider to be a flaw in the code you supplied.
>
> --
> Jonathan
>
This may be the practical difference betwen Theory and Practice (which
in Theory doesn't exist). There are times when processing a system that
can be represented as a graph, it is cleanest to think first of node,
and then by their connections. Your notation makes it inconvenient that
given you are at node A to know what nodes it connects to, you need to
search through the E structure to find all entries with the starting
node listed. You also get the 'name' of the node, not the node itself,
so you need another dictionary to map names to the actual nodes them
selves (where more information about the node might be stored).
Yes, maybe in pure graph theory all this isn't important, but if I am
USING a grahph for actual work, it might be.
Also, your example assumes that NAMES are the important piece, how would
you build your structure if names do not exist or are not unique, Once
you make the node themselves important, then making the links by the
node itself instead of by some arbitrary name makes sense.
Also, if the graph is directed, like Alice has a way to drop a message
into Bobs secure storage box, but Alice doesn't have access to one of
her own, so Bob can't use that method to send back to Alice, then it can
make sense to make the edge list not a total separate structure, but
each node includes the edges it can talk to itself.
It can be noted that this is very much like the model of the internet as
it exists today. Every machine (a node), keeps track of who it can
directly talk to, and a list of who it is next to and guess for who it
should try to send messages to in order to get a message to somone it is
not next to. There is no master list of edges in existance anywhere (I
once did see a master listing of the graph of the network in the early
days before automatic routing, such a map would be impossible to build
today).
Once you move the listing of links into the node itself, as opposed to
having a separate listing of all the vertices, and make the links to
node rather than names (to avoid an extra unneeded lookup) then you get
the recursive data structure.
For your example you say that can not be represented, let us build a
graph G as a dictionary, with the key being the name and the value being
the 'Node' for that person. (This assumes names are unique, otherwise it
might just need to be a list)
That node will be a dictionary, where we can store all sorts of
properties, but lets define one with a key 'secure' that has as its
value a listing of all the nodes this node knows how to directly send to.
Thus we could define the graph as:
g = {
'Alice': {'secure': []},
'Bob': {'secure': []},
'Carol': {'secure': []},
'Dave':, {'secure': []}.
'Eve':, {secure': []},
}
now we can add connections with something like:
g['Alice']['secure'].append(g['Bob'])
Note that this structure doesn't really even need g to exist at all, it
is only needed to initially find the nodes, the nodes could easily be
independent variables, or perhaps different nodes are in different
structures if they are obtained from different sources. (Node likely
will have a property in them to provide a human recognizable name for them).
Yes, perhaps at this point it might make sense to make the nodes an
actual class as opposed to just a dict, which sort of breaks the cycle
as by default __repr__ and such don't expand through class objects, but
that then changes the mindset from a data-driven to an object based
design, and depending what else the program needs to interface to one or
the other might be more complicated.
--
Richard Damon
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/KN6UQTIIGHLXYFYOAMY2PWLM44SNONE6/
Code of Conduct: http://python.org/psf/codeofconduct/
