Tuesday, August 27, 2019

Digest for comp.lang.c++@googlegroups.com - 5 updates in 2 topics

Frederick Gotham <cauldwell.thomas@gmail.com>: Aug 27 01:08AM -0700

Sorry I realise this is a C++ group but I can't find anywhere on the web a discussion forum for people using Graphiz and dot to make graphs. Has anyone got a link to any kind of forum or discussion group for Graphiz and its graph formats?
 
I've been trying to find a way to take a subsection of a graph, i.e. to set a new root, and to discard the parents and siblings of the new root node. I ended up writing my own code in an hour or two but I haven't tested it extensively... Surely this must have been done before... It should be in a toolkit of some sort. . .
 
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <sstream>
#include <cstdlib>
#include <cstdint>
 
using namespace std;
 
#define STR_LINKER " -> "
#define LEN_LINKER (sizeof(STR_LINKER)-1u)
#define LINK_SUFFIX " [style=solid] ;"
 
uintmax_t g_maxdepth = UINTMAX_MAX;
 
typedef vector<string> ChildContainer;
typedef map< string, ChildContainer > LinkContainer;
 
LinkContainer g_links;
 
inline void Print_Header(void) { cout << "digraph callgraph {" << endl; }
inline void Print_Footer(void) { cout << "}" << endl; }
 
/* The following function calls itself recursively. It is reentrant and thread-safe as it doesn't access any data of static-duration (nor any thread-local data). The C++ Standard functions called by this function e.g. "map::at, string::operator==" are hopefully implemented reentrant and thread-safe on your platform. */
 
static void Recursive_Is_Equal_Or_Is_Child_Of(string const &str_parent, string const &str_child, uintmax_t const level_of_recursion = 1)
{
if ( str_parent == str_child )
throw true;
 
if ( level_of_recursion >= g_maxdepth )
return;
 
LinkContainer::mapped_type const *p_children;
 
try { p_children = &g_links.at(str_parent); } catch (...) { return; } // The method 'at' will throw if no such key exists in the map
 
for (LinkContainer::mapped_type::const_iterator p = p_children->begin(); p != p_children->end(); ++p)
{
if ( str_child == *p )
throw true;
 
Recursive_Is_Equal_Or_Is_Child_Of(*p, str_child, level_of_recursion + 1);
}
}
 
bool Is_Equal_Or_Is_Child_Of(string const &str_parent, string const &str_child)
{
try
{
Recursive_Is_Equal_Or_Is_Child_Of(str_parent,str_child);
}
catch (bool)
{
return true;
}
 
return false;
}
 
void Print_With_New_Root(string const &str_root)
{
Print_Header();
 
LinkContainer::const_iterator p;
 
for (p = g_links.begin(); p != g_links.end(); ++p)
{
LinkContainer::mapped_type::const_iterator q;
 
for (q = p->second.begin(); q != p->second.end(); ++q)
{
if ( Is_Equal_Or_Is_Child_Of(str_root, p->first) )
{
cout << p->first << " -> " << *q << LINK_SUFFIX << endl;
}
}
}
 
Print_Footer();
}
 
int main(int argc, char **argv)
{
// USAGE: DOT_New_Root 3 main
// This sets 'main' as the root and goes down to a maximum depth of 3
// (For unlimited depth, specify 0)
 
if (3 != argc)
return EXIT_FAILURE;
 
stringstream( string(argv[1]) ) >> g_maxdepth;
 
if ( 0 == g_maxdepth )
g_maxdepth = UINTMAX_MAX;
 
string line;
 
while ( getline(cin,line) )
{
size_t pos = line.find(STR_LINKER); // Look for the linkage symbol " -> "
 
if ( string::npos == pos )
continue;
 
string str_parent = line.substr(1, pos-2);
 
string str_child = line.substr(pos + LEN_LINKER + 1, string::npos );
 
str_child.resize( str_child.find_first_of('\"') );
 
g_links[str_parent].push_back(str_child);
}
 
Print_With_New_Root(argv[2]);
 
return 0;
}
Frederick Gotham <cauldwell.thomas@gmail.com>: Aug 27 07:03AM -0700

> the web a discussion forum for people using Graphiz and dot to
> make graphs. Has anyone got a link to any kind of forum or discussion
> group for Graphiz and its graph formats?
 
Even if you're not into graphs, ya gotta like my use of throwing an exception to burst out of nested recursive function calls.
Tim Rentsch <tr.17687@z991.linuxsc.com>: Aug 27 08:27AM -0700

> of the new root node. I ended up writing my own code in an hour
> or two but I haven't tested it extensively...
 
> [...code...]
 
Kind of a funny way of thinking of the problem. What I think you
want to is consider the set of nodes that are reachable from a
given starting point (what you call "the new root node").
 
The code you wrote is, hmmm, let me say tangled. I don't want to
say much more about it except that I think you're getting lost in
the details. A better approach is to write a general reachable
node finder, calling a function for each node in the graph subset
that is reachable from the given starting point.
 
In the code below I use your data structure for the graphs, except
I use different names for the types. I use the name 'Links' for
what you call 'ChildContainer', and for your 'LinkContainer' I
use the name 'Graph'.
 
Here is the code to enumerate and act on a reachable set, in
depth-first preorder (disclaimer: compiled, not tested):
 
#include <vector>
#include <map>
#include <set>
#include <string>
#include <functional>
 
using NodeName = ::std::string;
using Links = ::std::vector< NodeName >;
using Graph = ::std::map< NodeName, Links >;
using NodeDoer = ::std::function< void( Graph &, NodeName, unsigned, bool ) >;
using NodeSet = ::std::set< NodeName >;
 
void dfp_do( Graph &, NodeSet &, NodeName, unsigned, NodeDoer );
 
void
depth_first_preorder_do( Graph &g, NodeName root, NodeDoer what ){
NodeSet seen;
dfp_do( g, seen, root, 0, what );
}
 
void
dfp_do( Graph &g, NodeSet &seen, NodeName n, unsigned depth, NodeDoer what ){
bool seen_before = seen.count( n ) > 0;
what( g, n, depth, seen_before );
if( seen_before ) return;
 
seen.insert( n );
for( auto child : g.at( n ) ){
dfp_do( g, seen, child, depth+1, what );
}
}
 
Note that if a given NodeName is encounted more than once, the
callback function 'what' is called for each encounter, with the
boolean 'seen_before' being true for all but the first encounter.
The 'depth' argument is the distance from the root along the
current path (which could be different for different paths through
the graph).
 
Here is an example use, which prints out nodes in the subgraph
in a nested "call tree" fashion. Nodes that have been traversed
previously are shown with a '*' to mean seen before (once more,
this code is compiled but not tested):
 
#include <cstdio>
 
void
show_reachable_nodes_as_nested_hierarchy( Graph &g, NodeName root ){
depth_first_preorder_do( g, root,
[]( Graph &, NodeName name, unsigned depth, bool seen_before ){
const char *flag = seen_before ? "*" : " ";
printf( "%*s %s %s\n", depth, "", flag, &name[0] );
}
);
}
 
My code doesn't have as much control as yours does with the depth
limiter. That's partly because I'm not sure exactly what you were
doing and partly because I'm not sure why you want it. The
callback function in my code includes a depth parameter, so if you
want just to exclude nodes greater than a certain distance from
the root that is easy to do. Unfortunately how my code does its
processing that exclusion interacts with how cases that have been
seen before are processed, so it may not do the right thing. One
way to fix that is to make the node enumeration function more
flexible, adding a parameter to test whether a particular node
should be processed now (a callback function with a depth argument
and maybe also some other arguments to give some additional
capability). That should be fairly easy to do, so I leave it as
an exercise for the reader.
 
I hope you found this interesting and helpful.
Jorgen Grahn <grahn+nntp@snipabacken.se>: Aug 27 03:38PM

On Tue, 2019-08-27, Frederick Gotham wrote:
> web a discussion forum for people using Graphiz and dot to make
> graphs. Has anyone got a link to any kind of forum or discussion
> group for Graphiz and its graph formats?
 
Don't you mean Graphviz?
 
> the new root node. I ended up writing my own code in an hour or two
> but I haven't tested it extensively... Surely this must have been
> done before... It should be in a toolkit of some sort. . .
 
If I understand the question, it's a general and on-topic question:
C++ libraries for dealing with graphs (or DAGs?). I haven't used any,
but I think there's something in Boost.
 
When I've done stuff like this I've done it manually, and my data
structure has been similar to the Graphviz text format: a set of
node->node connections, by name. But that's partly because I did it
with Perl hashes and Python dicts.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
stdcerr <ron.eggler@gmail.com>: Aug 26 07:31PM -0700

On Thursday, August 22, 2019 at 7:44:57 AM UTC-7, Jorgen Grahn wrote:
 
> I think you do need a book, for the bigger picture at least.
 
> Stroustrup: The C++ Programming Language. The edition that covers
> C++11.
 
I used the Stroustrup book back in the 90ties too. It's a good piece! And yes, i I will pickup a newer version of it at some point! Thank you!
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)