This blog presents the filtering tools that QuickGraph contains. Filters enables you to create a filtered view of a vertex collection, edge collection, a vertex list graph or other more advanced graphs.

The basics:

All the filters relay on two interfaces: IVertexPredicate and IEdgePredicate. Both those interface have a Test method that takes a IVertex (resp. IEdge) as argument and returns true if the instance should be kept, or false if it should be filtered out. Special collection, in the System.Collections.Filtered namespace, can be used to create a filtered enumeration of vertices and edges.

Examples

Let's take the file dependency example, as introducted in Fun with Graphs (2): Drawing graphs with QuickGraph and NGraphviz

This graph is part of the QuickGraphTest demo project:

BidirectionalGraph graph = GraphProvider.FileDependency();

Filtering Vertices

The BidirectionalGraph class supports methods Select** that take a predicate as argument. We can use it to filter the vertices and display the source vertex only (a source has no in-edge):

Console.WriteLine("Source vertices:");
foreach(NamedVertex v in graph.SelectVertices(Preds.SourceVertex(graph)))
{
    Console.WriteLine("\t{0}",v.Name);
}

[Output]
Source vertices:
        zow.h
        boz.h
        dax.h

Preds is an static helper class. Preds.SourceVertex returns a SourceVertexPreicate instance implemented as follows:

using System;
namespace QuickGraph.Predicates
{
    using QuickGraph.Concepts;
    using QuickGraph.Concepts.Predicates;
    using QuickGraph.Concepts.Traversals;

    public class SourceVertexPredicate : IVertexPredicate
    {
        private IBidirectionalGraph graph;
        public SourceVertexPredicate(IBidirectionalGraph graph)
        {
            if (graph==null)
                throw new ArgumentNullException("graph");
            this.graph = graph;
        }

        bool IVertexPredicate.Test(IVertex v)
        {
            return this.graph.InEdgesEmpty(v);
        }
    }
}

In the case your graph does not implement Select methods, you can directly use filtered enumerable collection such as the FilteredVertexEnumerable. Here we will show the sinks of the graph:

Console.WriteLine("Sink vertices:");
FilteredVertexEnumerable filteredVertices =
    new FilteredVertexEnumerable(
        graph.Vertices,
        Preds.SinkVertex(graph)
    );
foreach (NamedVertex v in filteredVertices)
{
    Console.WriteLine("\t{0}",v.Name);
}

[Output]
Sink vertices:
        killerapp

Filtering edges

Edges can be filtered similarly to vertices using IEdgePredicate instances. The EdgePredicate class can be used to combine a IEdgePredicate and 2 IVertexPredicate for the source and the target of the edge.

Filtering entire graph

One can also creating filtered views of entire graphs. Let's consider another graph for this example: the finite state machine of a calculator:

In this case, we would like to filter out the S4 state and all the edges attached to this sate. One possible solution is to create a dictionary of vertices colors (VertexColorDictionary) where all the vertices are white, except S4 which is set to black.

// create and fill the dictionary
VertexColorDictionary vertexColors = new VertexColorDictionary();
IVertexPredicate pred = new NameEqualPredicate("S4");
foreach (IVertex v in graph.Vertices)
{
    if (pred.Test(v))
        vertexColors[v] = GraphColor.Black;
    else
        vertexColors[v] = GraphColor.White;
}

Then we can create the filters to ignore black vertices:

// create filters for the main graph
// no back vertex
IVertexPredicate vp = new NoBlackVertexPredicate(vertexColors);

// all edge that do not start or end on a blackvertex
IEdgePredicate ep = new EdgePredicate(
    Preds.KeepAllEdges(),
    vp
   );

At last, we use FilteredVertexAndEdgeListGraph to create a filtered IVertexListGraph

IVertexAndEdgeListGraph filteredGraph = new FilteredVertexAndEdgeListGraph(graph,ep,vp);

The image belows shows the result of the filtering. The S4 state and all its adjacent edges are gone.