Nested Subgraphs

Aug 8, 2012 at 5:59 AM
Edited Aug 8, 2012 at 6:11 AM

Let me start by saying, fantastic library.

  One question though, does the current implementation support nested subgraphs? I stepped through the source and didn't see anything for it, but wanted to make sure I wasn't missing something. Trying to accomplish something along the lines of...

digraph "RootGraph" {
	graph [compound = "true", nodesep=1.0]
	node [shape=record]
	

	subgraph "cluster_location1" {
		label = "location1";
		subgraph "cluster_location1_group" {
			label = "group";
			"xxx" [label = "{xxx|x.x.x.x}"]
			"yyy" [label = "{yyy|x.x.x.x}"]
			"zzz" [label = "{zzz|x.x.x.x}"]			
		}
	}
...}

  Also probably helpful to mention I am not using the control, simply the core library to generate a dot file.

public void WriteGraphToFile(IGraph graph){
    using (FileStream fileStream = File.Create(@"c:\source.dot")){
        StreamWriter streamWriter = new StreamWriter(fileStream);

        GraphToDotConverter converter = new GraphToDotConverter();
        TextWriter originalWriter = streamWriter;

        IAttributesProvider additionalAttributesProvider = new SimpleAttributeProvider();
        converter.Convert(streamWriter, graph, additionalAttributesProvider);

        streamWriter.Close();
        fileStream.Close();
    }
}   
Coordinator
Aug 8, 2012 at 8:24 AM

Hi there,

thanks for the feedback :)

Graphviz4Net supports subgraphs so what you are describing should work just fine. The IGraph interface has SubGraphs property of type IEnumerable<ISubGraph> and the Graph class, which implements IGraph, provides some methods to add and remove subgraph instances. In the GraphToDotConverter class there is a loop over all subgraphs in which every subgraph should be written into the output stream.

Hope that helps,
Steve

Aug 9, 2012 at 1:56 AM
Edited Aug 9, 2012 at 1:59 AM

Steve,

  I am onboard with Graphs fully support Subgraphs. However, I am not following how a subgraph is added to another subgraph.

Graph<Node> graph = new Graph<Node>();
foreach (Location location in enterprise.Locations){
    SubGraph<Node> locationSubGraph = new SubGraph<Node>{Label = location.Name};
    locationSubGraph.AddVertex(new Node());
    graph.AddSubGraph(locationSubGraph);
    foreach (Domain domain in location.Domains){
        SubGraph<Node> domainSubGraph = new SubGraph<Node>(){Label = domain.Name};
        foreach (Server server in domain.Servers){
            server.Attributes.Add("label", "{" + server.Name + "|" + server.IP + "}");
            server.Attributes.Add("shape", "record");
            domainSubGraph.AddVertex(server);
        }
        locationSubGraph.AddSubGraph(domainSubGraph);
    }
}
On the green line the AddSubGraph method doesn't exist, but it should demonstrate more clearly how I am trying to use it. Also, when I look at the GraphToDotConverter portion that iterates over the subgraphs I don't see anywhere it would recurse.
var subGraphs = graph.SubGraphs.ToArray();
for (int i = 0; i < subGraphs.Length; i++)
{
    var subGraph = subGraphs[i];
    writer.WriteLine("subgraph cluster{0} {{ ", nodesMap.Count);
    idsMap.Add(subGraph, nodesMap.Count);
    nodesMap.Add(subGraph);
    writer.Indent++;

    // In order to have clusters labels always on the top:
    // when the direction is from bottom to top, change label location to bottom, 
    // which in this direction means top of the image
    string rankdir;
    if (graph is IAttributed &&
        ((IAttributed)graph).Attributes.TryGetValue("rankdir", out rankdir) &&
        rankdir == RankDirection.BottomToTop)
    {
        writer.WriteLine("graph [labelloc=b];");
    }

    if (subGraph is IAttributed)
    {
        writer.WriteLine("graph [{0}];", ((IAttributed)subGraph).GetAttributes());
    }

    foreach (var vertex in subGraph.Vertices)
    {
        writer.WriteLine("{0} [ {1} ];", nodesMap.Count, GetVertexAttributes(vertex, additionalAttributesProvider));
        idsMap.Add(vertex, nodesMap.Count);
        nodesMap.Add(vertex);
    }
    writer.Indent--;
    writer.WriteLine("}; ");
}
Coordinator
Aug 9, 2012 at 8:06 AM

Hey cwigley,

sorry i missed the word "nested" in your first post.

Well, nested subgraphs are not supported yet, but it sound like something i would like to add in the future. As far as i can say now, it would mean changing ISubGraph interface and its implementations plus few small tweaks like chaining Changed events and updating AddEdge method for subgraphs, then making the loop in GraphToDotConverter recursive and also method BuildSubGraphs in LayoutDirector.

Aug 10, 2012 at 2:46 AM

No worries. I will dig in and see if I can get it added. If I make any real progress I will submit a patch.

Aug 16, 2012 at 2:11 PM

I am also very much interested in nested subgraphs.  Let me know if there is anything I can do to help with the implementation.

Aug 18, 2012 at 10:43 AM
Edited Aug 18, 2012 at 9:29 PM

Hi CWigley - I'm also interested in having a hierachy of graphs.  Did you make any progress with this?  I'm thinking about giving it a go myself but would be a shame to repeat work you've already done - even if its just a question of identifying some dead ends.

cheers,

  Kwai

Aug 18, 2012 at 9:29 PM

Okay, I've got an initial implementation of nested sub-graphs, which works on at least one example! ;-)

I also changed the Edge implementation to not be templated; this allows a subgraph to be linked to a vertex, for example.

My changes need some tidying up before they are worth submitting and not sure when I will have the time to do so; if you are interested in the change in the meantime then let me know.

cheers,

Kwai

Aug 19, 2012 at 1:46 AM

I also have an implementation of nested subgraphs.  It required three uses of recursion: one in GraphToDotConverter and one in BuildSubGraphs, as suggested, plus a third in GetAllVertices.

I'm not sure if I interpreted "chaining Changed events" in the suggestion properly -- in my implementation, the FireChanged method in a nested subgraph invokes the same method in its enclosing subgraph.

Because I use Subversion and not Mercurial for source control, the easiest way for to submit my changes would be as a diff.  

Aug 19, 2012 at 5:12 PM

Would love to see what you guys put together for nested subgraphs. I created a fork that includes my updates for HTML labels and ports. Its the only fork out there called "additionalfeatures".

Aug 20, 2012 at 11:13 PM

I tried pushing a new branch into the Mercurial repository, but authorization did not succeed (see below for transcript).  Suggestions?

 

% hg --repository Z:\garland\Desktop\Tortoise push --new-branch --debug https://hg.codeplex.com/graphviz4net
pushing to https://hg.codeplex.com/graphviz4net
using https://hg.codeplex.com/graphviz4net
sending capabilities command
hg.codeplex.com certificate successfully verified
query 1; heads
sending batch command
searching for changes
all remote heads known locally
sending branchmap command
1 changesets found
list of changesets:
f100ec28e20a5043030294003a63224ef63d6f6b
sending unbundle command
sending 2513 bytes
http authorization required
realm: CodePlex
http auth: user sjgarland, password **********
hg.codeplex.com certificate successfully verified
http auth: user sjgarland, password **********
hg.codeplex.com certificate successfully verified
http auth: user sjgarland, password **********
hg.codeplex.com certificate successfully verified
http auth: user sjgarland, password **********
hg.codeplex.com certificate successfully verified
http auth: user sjgarland, password **********
hg.codeplex.com certificate successfully verified
http auth: user sjgarland, password **********
hg.codeplex.com certificate successfully verified
abort: authorization failed
[command returned code 255 Mon Aug 20 19:04:49 2012]

Aug 21, 2012 at 3:06 AM

It looks like you created your fork successfully. Now you could just create a clone then just copy your changes into it and sync. I was able to pull down your fork with the following settings.... sorry for the water mark, new machine and have installed my licenses yet.

 

Aug 21, 2012 at 12:56 PM

I don't know why I couldn't see my fork after I created it yesterday, but I was able to see and push my changes into it today.

These changes meet my immediate needs. However, additional work may be desirable to flesh out the implementation.

  1. Check that implementation works under Silverlight.
  2. Add methods GetAllSubGraphs to IGraph and ISubGraph.
  3. Further enhance the sample application to provide UI elements for
    1. creating a subgraph
    2. changing the subgraph to which a vertex belongs.
    3. linking subgraphs
  4. Kwai's changes for linking vertices and subgraphs.
Coordinator
Aug 21, 2012 at 8:39 PM

Hey guys, 

thanks for the effort! Sorry that i wasn't active for a while. I will check your code in the following days hopefully. 

Now regarding the workflow: i don't mind pulling changes from your forks and then reviewing them locally and pushing them to the master. That's what i did with HTML labels support patch. However, though the commit entry on the 'source code' tab here at codeplex shows chris_wigley as an author, it doesn't link to your profile. Don't know if that's by design... Anyway, if you wanted to do proper pull requests i wouldn't mind that either. Maybe it would be actually better at least with bigger changes, because with pull requests we could comment and discuss the code to be pulled.

And with the code itself (haven't had time to dig in it properly yet): there shouldn't be need for Edges to be non-'templated', the interface IEdge uses just objects and so does the IGraph interface. The idea was that the interfaces will use objects and will be used only for accessing the data (e.g. in GraphToDotConverter) and the default implementations, that is the Graph, Edge and SubGraphs classes, will provide strongly typed like API for creating and editing graphs. However, the default implementations still have to implement the interfaces and so an edge between a sub-graph and a vertex was possible, only there wasn't any method for adding such an edge in the Graph class, but it's scenario which should be supported by GraphToDotConverter.

Note on coding style (i should have written it in the documentation or somewhere): the intention is to follow reasonable rules from StyleCop, that is naming rules, members' order rules, spaces between arithmetic operators, spaces instead of tabs, curly brackets, method's arguments on separate lines, if the line would be too long etc., but not mandatory API documentation for every member, for example.

Cheers,
Steves 

Aug 21, 2012 at 9:02 PM
I hadn't started that yet at all. Would love to see what you came up with. I submitted a couple of patches for HTML labels and ports.

Think I will Fork the code tonight and we can consolidate some of these changes.
Aug 22, 2012 at 2:11 AM

Happy to contribute in whatever fashion works best for you. Not familiar with Mercurial much but I will look into the pull requests for any future changes. As for format I am good with whatever. I will setup a resharper config for this solution to keep me in check :)

Aug 22, 2012 at 1:21 PM

Let me know when there's a resharper config for this solution.  I found myself fighting ReSharper as I was trying to imitate stevesindelar's style.

Aug 22, 2012 at 1:27 PM
stevesindelar wrote:

The idea was that the interfaces will use objects and will be used only for accessing the data (e.g. in GraphToDotConverter) and the default implementations, that is the Graph, Edge and SubGraphs classes, will provide strongly typed like API for creating and editing graphs. However, the default implementations still have to implement the interfaces ...

 

I found it very awkward having to deal with both parameterized and unparameterized interfaces for IGraph and ISubGraph.  Is there any way to make GraphToDotConverter and the WPF data sources work with the parameterized interface, so that the unparameterized one can be eliminated?

Coordinator
Aug 22, 2012 at 8:09 PM

There's a R# configuration that i normally use in the last commit.

Not sure if we can eliminate non-'templated' interfaces. What would we gain? All the classes that depend on them would have to have type parameters as well. The idea was that vertices can be arbitrary objects, not necessarily of the same type, so that one can then have different WPF templates for different types of vertices (though one would have to do their own implementation of IGraph). However, that could be achieved by using object or some base class as a type parameter. You can certainly try that path and then we'll see if it made things any easier.

From my experience, i tent to have non-type-parametrized interfaces, because they give you more flexibility. For example if you wanted to have a List of graphs, all of them would have to have the same type parameters, or you'd use List<object> and then dynamic or casting, but casting to parametrized types is painful. I thought that non parametrized interface and then parametrized interface and implementation is a sort of a common pattern.

That said, i am glad that people are getting involved in the project and you can surely try to convince me otherwise. 

Steves

Aug 24, 2012 at 9:54 AM
sjgarland wrote:
stevesindelar wrote:

The idea was that the interfaces will use objects and will be used only for accessing the data (e.g. in GraphToDotConverter) and the default implementations, that is the Graph, Edge and SubGraphs classes, will provide strongly typed like API for creating and editing graphs. However, the default implementations still have to implement the interfaces ...

 

I found it very awkward having to deal with both parameterized and unparameterized interfaces for IGraph and ISubGraph.  Is there any way to make GraphToDotConverter and the WPF data sources work with the parameterized interface, so that the unparameterized one can be eliminated?

I de-parameterised the Edge class because having the parameters resulted in a lot of duplicate methods on the Graph class.  I handled the strong typing issue by introducing an IConnectable interface, and required the things an edge was connected to to be Connectable.  Obviously that does limit the vertices a little; you can't just feed a String in as a vertex anymore, without wrapping it into a ConnectableString.

With regard to the DotGraph etc. extensions, I was strongly tempted to turn these into partial classes of the main Graph, SubGraph etc.  That way you wouldn't need to create the DotGraph at all so there isn't much impact on the layout generators; the design as it stands doesn't support multiple different simultaneous views anyway.

Incidentally, I use a wide range of vertex classes in my graphs with different WPF templates, but all with a common parent class used to instantiate the Graph.

Kwai

Coordinator
Aug 24, 2012 at 10:31 AM
Kwai wrote:
I de-parameterised the Edge class because having the parameters resulted in a lot of duplicate methods on the Graph class.  I handled the strong typing issue by introducing an IConnectable interface, and required the things an edge was connected to to be Connectable.  Obviously that does limit the vertices a little; you can't just feed a String in as a vertex anymore, without wrapping it into a ConnectableString. 

Is your repository available somewhere?

What would be IConnectable good for? I liked that vertices can be arbitrary objects. It's true that if we wanted to introduce possibility of adding edges for every scenario (vertex - subgraph, subgraph - subgraph, etc.), then we would need lots of types for different edges and lots of AddEdge methods.

What if Edge was non-type-parametrized at all and Graph had only three type-parameters: TVertex, TSubGraph and TEdge and methods AddEdge(TEdge), etc., then users would be able to at least choose whether they want to use some base class for all the edges with some common properties like Color etc., but the vertices in edge would have to be of type object. However, in AddEdge method we would test if the vertices belong to the graph anyway.

Not sure what you mean by turning DotGraph into partial class? Like having all the things that belong to DotGraph in once class, but the division of general stuff and DOT related stuff would be done only by splitting the class into two files? Could you please explain more what you mean by simultaneous views?

Steves

Aug 24, 2012 at 12:20 PM

I haven't had a chance to work out how to upload yet, unfortunately - day job is a bit overwhelming and I've not submitted anything on codeplex before.  Also, my changes break all your UTs since I've not updated them...

IConnectable was just there for stronger typing really; avoiding accidentally adding an inappropriate type in a way detectable at compile time.  It doesn't expose any interface elements, just a personal style thing I guess.

Re: partial classes, I was tempted to make the parameterised Graph partial, and then instead of the DotGraph class just have another partial Graph that added the Dot capabilities to it (and similarly for the other Dot objects).  You would need an IDotGraph interface too.  This would mean that layout would no longer need a local DotGraph, just the passed in parameter which it would query for the Dot representation of the objects and update with the positions.  Conceptually, the limitation with this approach is that Graph design would not be threadsafe due to the calculations and updates being made on the presentation of it by the layout algorithm.  It isn't threadsafe at the moment, but the current design is closer to being able to split the model elements (the vertex elements etc.) from the presentational elements such as the layout, which is dependent on the WPF graphical representation of the vertex entities.

Incidentally, my version of Graph also inherits from SubGraph, both at the implementation and the interface level.  My thinking was that Graph essentially is a SubGraph just with some added capability to represent the top-level.  That way all the vertex and other low-level capabilty becomes common.

cheers,

  Kwai

Dec 13, 2012 at 11:23 AM

Hi Steves,

First of all, thanks for this great library. I am testing it at the moment for a new project I am working on.

The only feature I am missing for now is precisely the nested graph support, which this thread is about.

Has this been integrated into the master yet ?

Many thanks,

Andrei

Coordinator
Dec 16, 2012 at 7:05 PM

Hi Marand,

as you can see above there have been some attempts, but it seems that no one was really finished (?).

I myself started working on nested-graphs support some time ago, but i couldn't find time to finish it off either :-( However, now i at least pushed what i have (it's in a new branch called subgraphs), but it's definitely not working yet. The main problem was how to design the API of graph related data structures so that we can still have some nice robust and strongly typed interface (through generics probably), but at the same time interface flexible enough to implement nested sub-graphs. I reckon that some hack-ish sort of support for nested graphs would not be that difficult, so to say...

I wish i had enough time to finish it, but to be honest, i can't see it happening in next couple moths. In a long run, i am planning to work on it, though.

Steves