Logo Search packages:      
Sourcecode: f-spot version File versions

Algos.cs

using System;
using System.Collections;

using SemWeb;
using SemWeb.Query;
using SemWeb.Util;

namespace SemWeb.Algos {

      class SubtractionSource : SelectableSource {
            SelectableSource a, b;
            public SubtractionSource(SelectableSource a, SelectableSource b) {
                  this.a = a;
                  this.b = b;
            }
            public bool Distinct { get { return a.Distinct; } }
            public bool Contains(Statement template) {
                  return Store.DefaultContains(this, template);
            }
            public void Select(StatementSink sink) {
                  Select(Statement.All, sink);
            }
            public void Select(Statement template, StatementSink sink) {
                  a.Select(template, new Tester(b, sink));
            }
            public void Select(SelectFilter filter, StatementSink sink) {
                  a.Select(filter, new Tester(b, sink));
            }
            class Tester : StatementSink {
                  SelectableSource b;
                  StatementSink c;
                  public Tester(SelectableSource b, StatementSink c) { this.b = b; this.c = c;}
                  public bool Add(Statement s) {
                        if (b.Contains(s)) return true;
                        return c.Add(s);
                  }
            }
      }

      // This class makes a graph lean.
      public class Lean {
            // A graph g is not lean if it can be decomposed
            // into a and b such that a entails b.  (where
            // 'decomposed' means a and b don't overlap
            // and their union is g.)
            // One graph a entails another graph b when:
            //   Let V be the set of variables, which is the
            //   set of blank nodes that are in b but not in a.
            //   Let M be a mapping from nodes to nodes taking
            //   nodes that aren't in V to themselves.
            //   Let M* be a mapping from graphs to graphs that
            //   maps a graph to the same graph except where 
            //   each node x is replaced by M(x).
            //   If there exists an M such that M*(b) is a
            //   subgraph of a, then a entails b.
            // Let a and b be a decomposition of g, and V be
            // the variables in b w.r.t. a (as defined above).

            // Assume a entails b.
            // |a| >= |b|.
            // Since a and b are nonoverlapping, every statement
            // in b must have a variable.  b therefore contains
            // all and only the statements in g that mention a
            // variable.  (If b had a statement without a variable,
            // M*(b) would still have that statement, so it could
            // not be a subgraph of a.)
            
            // Define a N-decomposition as a decomposition of
            //   a graph g into g1 and g2 such that the nodes of
            //   N each appear in either g1 or g2, but not both.
            //   In such a decomposition, there is no statement
            //   in g that mentions a node from N and g1 and
            //   also mention a node from N and g2.
            
            // Assume b has a V-decomposition into b1 and b2.
            // Then if a entails b, a entails b1 and a entails b2.
            // Thus, if b has a V-decomposition, b need not be
            // considered as its decomposed parts will be considered.
            
            // Define 'directly connected' as a relation between
            // two nodes and a graph that is true iff there is
            // a statement in the graph that mentions both nodes.
            // Define connected (generally) as a relation between
            // two nodes x and y, a graph g, and a set S that is true
            // iff x and y are directly connected in g or else there
            // exists another node z in S such that x and z are
            // connected and z and y are connected, in g with S.
            
            // If b has a V-decomposition, then V can be decomposed
            // into V1 and V2 and b can be decomposed into b1 and b2
            // such that all nodes in V1 appear in b1 and all nodes
            // in V2 appear in b2.  It can be seen that a node in
            // V1 cannot be connected to a node in V2 w.r.t. b and V.
            // Therefore iff every node in V is connected to every
            // other node in V, then b has no V-decomposition.
            
            // The only b's to consider are those whose variables V
            // are all connected to each other in b w.r.t. V.
            
            // The plan then is first to consider MSGs, and then
            // look at their subgraphs.
      
            public static void MakeLean(Store store) {
                  MakeLean(store, null, null);
            }

            public static void MakeLean(Store store, SelectableSource relativeTo) {
                  MakeLean(store, relativeTo, null);
            }
      
            public static void MakeLean(Store store, SelectableSource relativeTo, StatementSink removed) {
                  // Break the data source into MSGs.  Make each MSG
                  // lean first (in isolation).  Then check each lean MSG
                  // to see if it's already entailed by the whole store,
                  // or by relativeTo if it's provided (not null).
            
                  MSG.Graph[] msgs = MSG.FindMSGs(store, true);
                  
                  foreach (MSG.Graph msgg in msgs) {
                        // Load the MSG into memory.
                        MemoryStore msg = new MemoryStore(msgg); // unnecessary duplication...

                        // Make this MSG lean.  The "right" thing to do is
                        // to consider all of the 'connected' subgraphs of MSG
                        // against the whole store, rather than the MSG in
                        // isolation.  But that gets much too expensive.
                        MemoryStore msgremoved = new MemoryStore();
                        MakeLeanMSG(msg, msgg.GetBNodes(), msgremoved);
                        
                        // Whatever was removed from msg, remove it from the main graph.
                        store.RemoveAll(msgremoved.ToArray());
                        
                        // And track what was removed.
                        if (removed != null) msgremoved.Select(removed);
                        
                        // If this MSG is now (somehow) empty (shouldn't happen,
                        // but one never knows), don't test for entailment.
                        if (msg.StatementCount == 0) continue;

                        // Remove this MSG if it is already entailed.
                        
                        // The GraphMatch will treat all blank nodes in
                        // msg as variables.
                        GraphMatch match = new GraphMatch(msg);
                        QueryResultBufferSink sink = new QueryResultBufferSink();
                        match.Run(new SubtractionSource(store, msg), sink);
                        if (sink.Bindings.Count > 0) {
                              // This MSG can be removed.
                              store.RemoveAll(msg.ToArray());
                              if (removed != null) msg.Select(removed);
                        } else if (relativeTo != null) {
                              match.Run(relativeTo, sink);
                              if (sink.Bindings.Count > 0) {
                                    // This MSG can be removed.
                                    store.RemoveAll(msg.ToArray());
                                    if (removed != null) msg.Select(removed);
                              }
                        }
                  }
            }
            
            private static void MakeLeanMSG(Store msg, ICollection bnodecollection, StatementSink removed) {
                  // To make any graph lean, we try to eliminate duplicate
                  // paths through the graph, where duplicate means we
                  // take some subset of the bnodes and call them variables,
                  // and we relabel them as other bnodes from the remaining
                  // set (the fixed nodes).  But there are 2^N subsets of bnodes
                  // we could choose as variables (N=number of bnodes), so we can't
                  // reasonably iterate through them.
                  
                  // I'll make a simplifying assumption that bnode predicates
                  // in the graph will be considered always fixed.
                  // This lets us view the graph as actually a graph (with
                  // nodes and edges), and then we can make the observation that
                  // if variable node V is part of a subgraph that can be removed,
                  // if V directly connects to fixed node F via an edge labeled P,
                  // then F must connect to a fixed node G via an edge also
                  // labeled P.  That is, we can start our search looking for
                  // nodes that project two edges with the same label.
                  
                  // Also, we only want to consider contiguous 'paths' -- subsets
                  // of the bnodes connected only through those nodes --
                  // to see if there is another path in the MSG if we
                  // map bnodes in the first path to nodes in the MSG.
                  
                  // So the strategy is to start at each node in the graph
                  // and consider it fixed.  If it has two outgoing
                  // edges with the same property and one terminates on a
                  // bnode, this is the beginning of a possible pair
                  // of redundant paths (the one with the bnode being
                  // eliminable).
                  
                  // However, the path with the bnode
                  // has to be incremented with all of that bnode's
                  // outgoing edges.  The other path has to be
                  // incremented in parallel, following the same predicates
                  // to other nodes.  If that can't be done, then these
                  // paths are not duplicates.  If the parallel predicates
                  // terminate on the very same nodes, the bnode and its edges can
                  // be removed.
                  
                  // From there, each of the nodes the bnode edges terminate on,
                  // besides the initial node, can be considered fixed or
                  // a variable.  If it's a variable it might be able to have
                  // one of many possible values, but then the path has to
                  // be expanded to include all of the outgoing edges for this
                  // variable.
            
                  // Ok, here we go.
                  
                  // If there is only one bnode in the MSG, then
                  // there are no subgraphs to check.  That's nice.
                  if (bnodecollection.Count == 1) return;
                  
                  // Remember which bnodes have been removed in
                  // due course.
                  ResSet nodesremoved = new ResSet();
                  
                  // Remember which nodes are predicates and can't
                  // be considered variable.
                  ResSet predicates = new ResSet();
                  foreach (Statement s in msg.Select(Statement.All))
                        predicates.Add(s.Predicate);
                  
                  // Start with each bnode to consider fixed.
                  foreach (BNode b in bnodecollection) {
                        if (nodesremoved.Contains(b)) continue;
                        MakeLeanMSG2(msg, predicates, removed, nodesremoved, b);
                  }
            }
            
            private static void MakeLeanMSG2(Store msg, ResSet predicates, StatementSink removed,
                  ResSet nodesremoved, BNode startingnode) {
                  
                  // Find every pair of two distinct outgoing edges from startingnode
                  // with the same predicate, targeting entities only.
                  
                  MultiMap edges = new MultiMap();
                  
                  foreach (Statement s in msg.Select(new Statement(startingnode, null, null)))
                        if (s.Object is Entity)
                              edges.Put(new Edge(true, startingnode, s.Predicate, null), s.Object);
                  foreach (Statement s in msg.Select(new Statement(null, null, startingnode)))
                        edges.Put(new Edge(false, startingnode, s.Predicate, null), s.Subject);
                  
                  foreach (Edge e in edges.Keys) {
                        // Make sure we have a distinct set of targets.
                        ResSet targets_set = new ResSet();
                        foreach (Entity r in edges.Get(e))
                              targets_set.Add(r);
                        if (targets_set.Count == 1) continue;
                        
                        IList targets = targets_set.ToEntityArray();
                        
                        // Take every pair of targets, provided
                        // one is a bnode that can be a variable.
                        for (int i = 0; i < targets.Count; i++) {
                              if (!(targets[i] is BNode) || predicates.Contains((BNode)targets[i])) continue;
                              if (nodesremoved.Contains((BNode)targets[i])) continue;
                              for (int j = 0; j < targets.Count; j++) {
                                    if (i == j) continue;
                                    // Create a new synchronous-path object.
                                    SyncPath p = new SyncPath();
                                    p.FixedNodes.Add((Resource)targets[j]);
                                    p.FrontierVariables.Add((Resource)targets[i]);
                                    p.Mapping[targets[i]] = targets[j];
                                    p.Path[new Edge(e.Direction, e.Start, e.Predicate, (BNode)targets[i])] = p.Path;
                                    if (MakeLeanMSG3(msg, predicates, removed, nodesremoved, p))
                                          break; // the target was removed
                              }
                        }
                  }
            }
            
            private static bool MakeLeanMSG3(Store msg, ResSet predicates, StatementSink removed,
                  ResSet nodesremoved, SyncPath path) {
                  // The variable path has to be expanded by including the statements
                  // connected to the variables on the frontier.  Statements
                  // mentioning a variable node have already been considered.
                  // The target of each such statement can be considered fixed
                  // or variable. If a variable is considered fixed, the edge
                  // must exist in the MSG substituting the variables for their
                  // values.  If it's variable, it has to have at least one
                  // match in the MSG but not as any of the variable nodes.
                  // If all targets are considered fixed (and have matches),
                  // then the variables so far (and their edges) can all be
                  // removed and no more processing needs to be done.
                  // There are (2^N)-1 other considerations.  For each of those,
                  // the targets considered variables all become the new
                  // frontier, and this is repeated. 
                  
                  // First, get a list of edges from the frontier that we
                  // haven't considered yet.
                  
                  ArrayList alledges = new ArrayList();
                  foreach (BNode b in path.FrontierVariables) {
                        // Make sure all edges are kept because even the ones
                        // to literals have to be removed when duplication is found.
                        foreach (Statement s in msg.Select(new Statement(b, null, null)))
                              alledges.Add(new Edge(true, b, s.Predicate, s.Object));
                        foreach (Statement s in msg.Select(new Statement(null, null, b)))
                              alledges.Add(new Edge(false, b, s.Predicate, s.Subject));
                  }
                  
                  ArrayList newedges = new ArrayList();
                  ResSet alltargets = new ResSet();
                  ResSet fixabletargetsset = new ResSet(); // can be fixed
                  ResSet variabletargetsset = new ResSet(); // must be variable
                  foreach (Edge e in alledges) {
                        if (path.Path.ContainsKey(e)) continue;
                        path.Path[e] = e;
                        
                        // This checks if we can keep the target of this edge
                        // fixed, given the variable mappings we have so far.
                        bool isTargetFixable =
                              msg.Contains(e.AsStatement().Replace(path.Mapping));

                        // If the target of e is any of the following, we
                        // can check immediately if the edge is supported
                        // by the MSG under the variable mapping we have so far:
                        //    a named node, literal, fixed node, or predicate
                        //    a variable we've seen already
                        // If it's not supported, this path fails.  If it is
                        // supported, we're done with this edge.
                        if (!(e.End is BNode)
                              || path.FixedNodes.Contains(e.End)
                              || predicates.Contains(e.End)
                              || path.VariableNodes.Contains(e.End)) {
                              if (!isTargetFixable) return false;
                              continue; // this edge is supported, so we can continue
                        }
                        
                        // The target of e is a new BNode.
                        // If this target is not fixable via this edge, it's
                        // not fixable at all.
                        
                        if (!isTargetFixable) {
                              fixabletargetsset.Remove(e.End);
                              variabletargetsset.Add(e.End);
                        }
                        
                        if (!alltargets.Contains(e.End)) {
                              alltargets.Add(e.End);
                              fixabletargetsset.Add(e.End);
                        }
                        
                        newedges.Add(e);
                  }
                  
                  // If all of the targets were fixable (trivially true also
                  // if there simple were no new edges/targets), then we've reached
                  // the end of this path.  We can immediately remove
                  // the edges we've seen so far, under the variable mapping
                  // we've chosen.
                  if (variabletargetsset.Count == 0) {
                        foreach (Edge e in path.Path.Keys) {
                              Statement s = e.AsStatement();
                              msg.Remove(s);
                              if (removed != null) removed.Add(s);
                        }
                        foreach (Entity e in path.Mapping.Keys)
                              nodesremoved.Add(e);
                        return true;
                  }
                  
                  // At this point, at least one target must be a variable
                  // and we'll have to expand the path in that direction.
                  // We might want to permute through the ways we can
                  // take fixable nodes as either fixed or variable, but
                  // we'll be greedy and assume everything fixable is
                  // fixed and everything else is a variable.
                  
                  path.FixedNodes.AddRange(fixabletargetsset);
                  path.VariableNodes.AddRange(variabletargetsset);

                  // But we need to look at all the ways each variable target
                  // can be mapped to a new value, which means intersecting
                  // the possible matches for each relevant edge.
                  Entity[] variables = variabletargetsset.ToEntityArray();
                  ResSet[] values = new ResSet[variables.Length];
                  Entity[][] values_array = new Entity[variables.Length][];
                  int[] choices = new int[variables.Length];
                  for (int i = 0; i < variables.Length; i++) {
                        foreach (Edge e in newedges) {
                              if (e.End != variables[i]) continue;
                              
                              // Get the possible values this edge allows
                              Resource[] vr;
                              if (e.Direction)
                                    vr = msg.SelectObjects((Entity)path.Mapping[e.Start], e.Predicate);
                              else
                                    vr = msg.SelectSubjects(e.Predicate, (Entity)path.Mapping[e.Start]);
                              
                              // Filter out literals and any variables
                              // on the path!  The two paths can't intersect
                              // except at fixed nodes.
                              ResSet v = new ResSet();
                              foreach (Resource r in vr) {
                                    if (r is Literal) continue;
                                    if (path.Mapping.ContainsKey(r)) continue;
                                    v.Add(r);
                              }
                              
                              // Intersect these with the values we have already.
                              if (values[i] == null)
                                    values[i] = v;
                              else
                                    values[i].RetainAll(v);
                                    
                              // If no values are available for this variable,
                              // we're totally done.
                              if (values[i].Count == 0) return false;
                        }
                        
                        choices[i] = values[i].Count;
                        values_array[i] = values[i].ToEntityArray();
                  }
                  
                  // Now we have to permute through the choice of values.
                  // Make an array of the number of choices for each variable.
                  Permutation p = new Permutation(choices);
                  int[] pstate;
                  while ((pstate = p.Next()) != null) {
                        SyncPath newpath = new SyncPath();
                        newpath.FixedNodes.AddRange(path.FixedNodes);
                        newpath.VariableNodes.AddRange(path.VariableNodes);
                        newpath.Mapping = (Hashtable)path.Mapping.Clone();
                        newpath.Path = (Hashtable)path.Path.Clone();
                        
                        newpath.FrontierVariables = variabletargetsset;
                        
                        for (int i = 0; i < variables.Length; i++) {
                              Entity value = values_array[i][pstate[i]];
                              newpath.Mapping[variables[i]] = value;
                              newpath.FixedNodes.Add(value);
                        }

                        if (MakeLeanMSG3(msg, predicates, removed,
                              nodesremoved, newpath)) return true;
                  }
                  
                  return false;
            }
            
            private class Edge {
                  bool direction;
                  Entity start, predicate;
                  Resource end;
                  public Edge(bool direction, Entity start, Entity predicate, Resource end) {
                        this.direction = direction;
                        this.start = start;
                        this.predicate = predicate;
                        this.end = end;
                  }
                  public bool Direction { get { return direction; } }
                  public Entity Start { get { return start; } }
                  public Entity Predicate { get { return predicate; } }
                  public Resource End { get { return end; } }
                  public override int GetHashCode() { return predicate.GetHashCode(); }
                  public override bool Equals(object other) {
                        Edge e = (Edge)other;
                        return Direction == e.Direction
                              && Start == e.Start
                              && Predicate == e.Predicate
                              && End == e.End;
                  }
                  public Statement AsStatement() {
                        if (Direction) return new Statement(Start, Predicate, End);
                        else return new Statement((Entity)End, Predicate, Start);
                  }
            }
            
            private class SyncPath {
                  public ResSet FixedNodes = new ResSet();
                  public ResSet VariableNodes = new ResSet();
                  public ResSet FrontierVariables = new ResSet();
                  public Hashtable Mapping = new Hashtable();
                  public Hashtable Path = new Hashtable();
            }

            private class Sink : StatementSink {
                  ResSet variables;
                  Store store;
                  public Sink(ResSet variables, Store store) {
                        this.variables = variables;
                        this.store = store;
                  }
                  public bool Add(Statement s) {
                        s.Meta = Statement.DefaultMeta;
                        if (store.Contains(s)) return true;
                        if (variables.Contains(s.Subject)
                              || variables.Contains(s.Predicate)
                              || variables.Contains(s.Object))
                              store.Add(s);
                        return true;
                  }
            }
      }

      public class MSG {

            // These methods find minimal self-contained graphs
            // in a graph by recursively expanding a subgraph.
      
            public static MemoryStore FindMSG(SelectableSource store, Entity node) {
                  MemoryStore ret = new MemoryStore();
                  FindMSG(store, node, ret);
                  return ret;
            }
            
            public static void FindMSG(SelectableSource store, Entity node, Store msg) {
                  if (node.Uri != null) throw new ArgumentException("node must be anonymous");
                  
                  ResSet nodesSeen = new ResSet();
                  ResSet nodesToAdd = new ResSet();
                  
                  nodesToAdd.Add(node);
                  
                  while (nodesToAdd.Count > 0) {
                        ResSet nodes = nodesToAdd;
                        nodesToAdd = new ResSet();
                        
                        Sink sink = new Sink(msg, nodesToAdd);
                        foreach (Entity n in nodes) {
                              if (nodesSeen.Contains(n)) continue;
                              nodesSeen.Add(n);
                              store.Select(new Statement(n, null, null, null), sink);
                              store.Select(new Statement(null, n, null, null), sink);
                              store.Select(new Statement(null, null, n, null), sink);
                        }
                  }
            }
            
            private class Sink : StatementSink {
                  Store msg;
                  ResSet add;
                  public Sink(Store msg, ResSet add) {
                        this.msg = msg;
                        this.add = add;
                  }
                  public bool Add(Statement s) {
                        if (msg.Contains(s)) return true;
                        msg.Add(s);
                        if (s.Subject.Uri == null) add.Add(s.Subject);
                        if (s.Predicate.Uri == null) add.Add(s.Predicate);
                        if (s.Object is Entity && s.Object.Uri == null) add.Add(s.Object);
                        return true;
                  }
            }
            
            // This method finds all minimal self-contained graphs
            // by painting nodes colors (the colors happen to be
            // objects) in one pass over the statements and then doing
            // a second pass to put each statement mentioning a bnode
            // into the appropriate graph structure.
            public static Graph[] FindMSGs(SelectableSource source, bool loadIntoMemory) {
                  FindMSGsSink sink = new FindMSGsSink(source, loadIntoMemory);
                  source.Select(Statement.All, sink);
                  ArrayList graphs = new ArrayList(sink.colors.Keys);
                  return (Graph[])graphs.ToArray(typeof(Graph));
            }
            
            public class Graph : StatementSource {
                  SelectableSource source;
                  internal ResSet entities = new ResSet();
                  internal MemoryStore statements;

                  internal Graph(SelectableSource source)  {
                        this.source = source;
                  }
                  
                  public bool Distinct { get { return source.Distinct; } }
                  public bool Contains(Entity e) {
                        return entities.Contains(e);
                  }
                  public ICollection GetBNodes() {
                        return entities.Items;
                  }
                  public void Select(StatementSink s) {
                        if (statements == null)
                              source.Select(Statement.All, new Sink(this, s));
                        else
                              statements.Select(s);
                  }

                  private class Sink : StatementSink {
                        Graph g;
                        StatementSink s;
                        public Sink(Graph g, StatementSink s) {
                              this.g = g;
                              this.s = s;
                        }
                        public bool Add(Statement s) {
                              if (g.Contains(s.Subject)
                                    || g.Contains(s.Predicate)
                                    || (s.Object is Entity && g.Contains((Entity)s.Object)))
                                    return this.s.Add(s);
                              return true;
                        }
                  }
                  public static void LoadGraphs(Graph[] graphs) {
                  }
            }
            
            class FindMSGsSink : StatementSink {
                  SelectableSource source;
                  bool loadin;
                  Hashtable bnodecolors = new Hashtable();
                  public Hashtable colors = new Hashtable();
                  public FindMSGsSink(SelectableSource source, bool loadIntoMem) { this.source = source; loadin = loadIntoMem; }
                  public bool Add(Statement s) {
                        // Get the color of any painted entity in the statement.
                        int numcon = 0;
                        Graph color = null;
                        if (s.Subject.Uri == null) { Go1(s.Subject, ref color); numcon++; }
                        if (s.Predicate.Uri == null) { Go1(s.Predicate, ref color); numcon++; }
                        if (s.Object.Uri == null && s.Object is Entity) { Go1((Entity)s.Object, ref color); numcon++; }
                        
                        // If there isn't a blank node here, nothing to do.
                        if (numcon == 0)
                              return true;
                        
                        // No nodes were colored yet, so pick a new color.
                        if (color == null) {
                              color = new Graph(source);
                              if (loadin)
                                    color.statements = new MemoryStore();
                              colors[color] = color;
                        }
                        
                        // Apply that color to all of the nodes.
                        if (s.Subject.Uri == null) Go2(s.Subject, ref color);
                        if (s.Predicate.Uri == null) Go2(s.Predicate, ref color);
                        if (s.Object.Uri == null && s.Object is Entity) Go2((Entity)s.Object, ref color);
                        
                        // And put this statement into that color
                        if (loadin)
                              color.statements.Add(s);
                        
                        return true;
                  }
                  void Go1(Entity e, ref Graph color) {
                        if (color == null && bnodecolors.ContainsKey(e)) {
                              color = (Graph)bnodecolors[e];
                        }
                  }
                  void Go2(Entity e, ref Graph color) {
                        if (bnodecolors.ContainsKey(e)) {
                              Graph curcolor = (Graph)bnodecolors[e];
                              if (curcolor != color) {
                                    // Everyone that has the color curcolor
                                    // has to switch to the color color.
                                    foreach (Entity e2 in curcolor.entities)
                                          bnodecolors[e2] = color;

                                    color.entities.AddRange(curcolor.entities);
                                    if (loadin)
                                          foreach (Statement s in curcolor.statements)
                                                color.statements.Add(s);
                                                
                                    colors.Remove(curcolor);
                              }
                        } else {
                              bnodecolors[e] = color;
                              color.entities.Add(e);
                        }
                  }
            }
            
      }
      
      public class Connectivity {
      
            public static void Build(StatementSource graph, out bool[,] connectivity, Hashtable indexes) {
                  connectivity = new bool[indexes.Count, indexes.Count];
                  graph.Select(new Sink(connectivity, indexes));
            }
            
            class Sink : StatementSink {
                  bool[,] connectivity;
                  Hashtable indexes;
                  public Sink(bool[,] connectivity, Hashtable indexes) {
                        this.connectivity = connectivity;
                        this.indexes = indexes;
                  }
                  public bool Add(Statement st) {
                        int s = indexes.ContainsKey(st.Subject) ? (int)indexes[st.Subject] : -1;
                        int p = indexes.ContainsKey(st.Predicate) ? (int)indexes[st.Predicate] : -1;
                        int o = indexes.ContainsKey(st.Object) ? (int)indexes[st.Object] : -1;
                        if (s != -1 && p != -1) { connectivity[s,p]=true; connectivity[p,s]=true; }
                        if (s != -1 && o != -1) { connectivity[s,o]=true; connectivity[o,s]=true; }
                        if (p != -1 && o != -1) { connectivity[p,o]=true; connectivity[o,p]=true; }
                        return true;
                  }
            }
      }

      // This class uses a connectivity matrix to iterate
      // through the connected subsets of the nodes, that is,
      // subsets of the nodes that are connected by traveling
      // just through those nodes.  The Next() method returns
      // a bool[] indicating the nodes in the subgraph.
      public class SubgraphIterator {
            // This is based on something I read.
            // We'll maintain a queue of connected
            // subgraphs to process.  The queue will
            // start with a one-node subgraph for each
            // bnode.  Then each time we process a
            // subgraph, we'll extend the graph by one
            // node every way we can and add all of those
            // new subgraphs into the queue -- unless we've
            // already processed the subgraph.  
      
            int n;
            bool[,] conn;
            Queue queue = new Queue();
            Hashtable processed = new Hashtable();
            
            public SubgraphIterator(bool[,] connectivity) {
                  this.conn = connectivity;
                  n = conn.GetLength(0);
                  for (int i = 0; i < n; i++)
                        QueueSubgraph(null, i);
            }
            
            void QueueSubgraph(Subgraph a, int b) {
                  Subgraph s = new Subgraph();
                  s.nodes = new bool[n];
                  s.touching = new bool[n];
                  if (a != null) {
                        a.nodes.CopyTo(s.nodes, 0);
                        a.touching.CopyTo(s.touching, 0);
                  }
                  s.nodes[b] = true;

                  s.sum = unchecked((a != null ? a.sum : 0) + b);
                  if (processed.ContainsKey(s)) return;
                  
                  for (int i = 0; i < n; i++)
                        if (conn[b,i])
                              s.touching[i] = true;
                              
                  processed[s] = processed;
                  queue.Enqueue(s);
            }
            
            public bool[] Next() {
                  if (queue.Count == 0) return null;
                  Subgraph s = (Subgraph)queue.Dequeue();
                  
                  // Create a new s for every node touching
                  // s but not in s.
                  for (int i = 0; i < n; i++)
                        if (!s.nodes[i] && s.touching[i])
                              QueueSubgraph(s, i);
                  
                  return s.nodes;
            }
            
            class Subgraph {
                  public bool[] nodes;
                  public bool[] touching;
                  public int sum;
                  
                  public override int GetHashCode() { return sum; }
                  public override bool Equals(object o) {
                        Subgraph g = (Subgraph)o;
                        for (int i = 0; i < nodes.Length; i++)
                              if (nodes[i] != g.nodes[i])
                                    return false;
                        return true;
                  }
            }
      }
            
}

Generated by  Doxygen 1.6.0   Back to index