#include "DynamicGraph.h"
using namespace DynamicGraphs;
DynamicGraph::DynamicGraph(Structure::Graph *fromGraph)
{
this->mGraph = fromGraph;
this->uniqueID = 0;
this->uniqueEdgeID = 0;
if(mGraph == NULL) return;
// Add nodes
foreach(Structure::Node * n, mGraph->nodes)
addNode( SingleProperty("original", n->id) );
// Add edges
foreach(Structure::Link * e, mGraph->edges)
addEdge( nodeIndex("original", e->n1->id), nodeIndex("original", e->n2->id) );
}
DynamicGraph DynamicGraph::clone()
{
DynamicGraph g;
g.mGraph = this->mGraph;
g.nodes = this->nodes;
g.edges = this->edges;
g.adjacency = this->adjacency;
g.uniqueID = this->uniqueID;
g.uniqueEdgeID = this->uniqueEdgeID;
return g;
}
int DynamicGraph::addNode(Properties properties, int index)
{
if(index < 0) index = nodes.size();
nodes[index] = SimpleNode(index);
nodes[index].property = properties;
// Always increasing global identifier
uniqueID++;
return index;
}
int DynamicGraph::addEdge(int fromNode, int toNode)
{
//if(fromNode == toNode) assert(0);
SimpleEdge e(fromNode, toNode);
int edgeIndex = uniqueEdgeID;
edges[edgeIndex] = e;
uniqueEdgeID++;
adjacency[fromNode].insert(e);
adjacency[toNode].insert(e);
return edgeIndex;
}
int DynamicGraph::nodeIndex( QString property_name, QVariant property_value )
{
foreach(SimpleNode n, nodes)
{
if(n.property.contains(property_name) && n.property[property_name] == property_value)
return n.idx;
}
assert(0);
return -1;
}
std::vector<int> DynamicGraph::nodesWith( QString property_name, QVariant property_value )
{
std::vector<int> result;
foreach(SimpleNode n, nodes)
{
if(n.property.contains(property_name) && n.property[property_name] == property_value)
result.push_back(n.idx);
}
return result;
}
QString DynamicGraph::nodeType( int index )
{
return mGraph->getNode(nodes[index].str("original"))->type();
}
void DynamicGraph::removeNode( int idx )
{
// Remove edges
foreach(int adj, adjNodes(idx))
removeEdge(idx, adj);
// Remove node and adjacency list
nodes.remove(idx);
adjacency.remove(idx);
}
void DynamicGraph::removeEdge(int fromNode, int toNode)
{
if(fromNode == toNode) assert(0);
SimpleEdge e(fromNode, toNode);
QMapIterator<int, SimpleEdge> i(edges);
while (i.hasNext()) {
i.next();
if(i.value() == e){
edges.remove(i.key());
break;
}
}
adjacency[fromNode].remove(e);
adjacency[toNode].remove(e);
}
QSet<int> DynamicGraph::adjNodes(int index)
{
QSet<int> adj;
foreach(SimpleEdge e, adjacency[index])
adj.insert( e.n[0] == index ? e.n[1] : e.n[0] );
return adj;
}
GraphState DynamicGraph::State()
{
GraphState state;
state.numSheets = numSheets();
state.numCurves = numCurves();
state.numSheetEdges = numEdges(SAME_SHEET);
state.numCurveEdges = numEdges(SAME_CURVE);
state.numMixedEdges = numEdges(CURVE_SHEET);
return state;
}
void DynamicGraph::printState()
{
GraphState state = this->State();
state.print();
}
int DynamicGraph::numEdges( EdgeType t )
{
int count = 0;
foreach(SimpleEdge e, edges){
switch(t)
{
case ANY_EDGE : count++; break;
case CURVE_SHEET:if(nodeType(e.n[0]) != nodeType(e.n[1])) count++; break;
case SAME_CURVE :if(nodeType(e.n[0]) == Structure::CURVE && nodeType(e.n[0]) == nodeType(e.n[1])) count++; break;
case SAME_SHEET :if(nodeType(e.n[0]) == Structure::SHEET && nodeType(e.n[0]) == nodeType(e.n[1])) count++; break;
}
}
return count;
}
QVector<int> DynamicGraph::getSheets()
{
QVector<int> sheets;
foreach(SimpleNode n, nodes)
if(nodeType(n.idx) == Structure::SHEET)
sheets.push_back(n.idx);
return sheets;
}
int DynamicGraph::numSheets()
{
return getSheets().size();
}
QVector<int> DynamicGraph::getCurves()
{
QVector<int> curves;
foreach(SimpleNode n, nodes)
if(nodeType(n.idx) == Structure::CURVE)
curves.push_back(n.idx);
return curves;
}
int DynamicGraph::numCurves()
{
return getCurves().size();
}
int DynamicGraph::cloneNode( int index, bool cloneEdges )
{
int newIndex = addNode( nodes[index].property, uniqueID );
if(cloneEdges){
QSet<int> adj = adjNodes( index );
foreach(int ni, adj)
addEdge(newIndex, ni);
}
return newIndex;
}
void DynamicGraph::printNodeInfo( int index )
{
qDebug() << "\nNode:";
qDebug() << " idx : " << nodes[index].idx;
qDebug() << " type : " << nodeType(index);
// Adjacent info
QStringList adjList;
foreach(int ni, adjNodes(index)) adjList << QString::number(ni);
qDebug() << " adj : " << adjList.join(", ");
}
GraphState DynamicGraph::difference( GraphState & other )
{
GraphState diff;
GraphState my = State();
diff.numSheets = my.numSheets - other.numSheets;
diff.numCurves = my.numCurves - other.numCurves;
diff.numSheetEdges = my.numSheetEdges - other.numSheetEdges;
diff.numCurveEdges = my.numCurveEdges - other.numCurveEdges;
diff.numMixedEdges = my.numMixedEdges - other.numMixedEdges;
return diff;
}
Structure::Graph * DynamicGraph::toStructureGraph()
{
Structure::Graph * graph = new Structure::Graph();
QMap<int,QString> nodeMap;
QMap<int,QString> originalNodeIds;
// Add nodes
foreach(SimpleNode n, nodes)
{
QString nodeId = n.str("original");
QString newId = nodeId + QString("_%1").arg(n.idx);
if(nodeType(n.idx) == Structure::SHEET)
{
Structure::Sheet * s = (Structure::Sheet *) mGraph->getNode(nodeId);
graph->addNode( new Structure::Sheet(s->surface, newId) );
}
if(nodeType(n.idx) == Structure::CURVE)
{
Structure::Curve * s = (Structure::Curve *) mGraph->getNode(nodeId);
graph->addNode( new Structure::Curve(s->curve, newId) );
}
nodeMap[n.idx] = newId;
originalNodeIds[n.idx] = nodeId;
}
// Add edges
QMapIterator<int, SimpleEdge> i(edges);
while (i.hasNext()){
i.next();
int edgeIndex = i.key();
SimpleEdge e = i.value();
QString id1 = nodeMap[e.n[0]];
QString id2 = nodeMap[e.n[1]];
QString orig_id1 = originalNodeIds[e.n[0]];
QString orig_id2 = originalNodeIds[e.n[1]];
Structure::Node *n1 = graph->getNode(id1), *n2 = graph->getNode(id2);
graph->addEdge( n1, n2, Array1D_Vector4d(1, Vector4d(0,0,0,0)), Array1D_Vector4d(1, Vector4d(0,0,0,0)), graph->linkName(n1, n2) );
// Copy edge coordinates
Structure::Link *toEdge = graph->getEdge(id1, id2);
Structure::Link *fromEdge;
if(fromEdge = mGraph->getEdge(orig_id1,orig_id2))
{
toEdge->setCoord(id1, fromEdge->getCoord(id1));
toEdge->setCoord(id2, fromEdge->getCoord(id2));
}
// Assign coordinates to special edges
if( specialCoords.contains(edgeIndex) )
{
// Deal with special coordinates
toEdge->setCoord(id1, specialCoords[edgeIndex][e.n[0]]);
toEdge->setCoord(id2, specialCoords[edgeIndex][e.n[1]]);
toEdge->property["special"] = true;
}
// Track movable nodes
if( movable.contains(edgeIndex) )
{
QString movableNode = nodeMap[movable[edgeIndex]];
toEdge->property["movable"] = movableNode;
}
if( growingCurves.contains(edgeIndex) )
{
toEdge->property["growing"] = nodeMap[growingCurves[edgeIndex].first];
toEdge->property["growAnchor"] = growingCurves[edgeIndex].second.first;
toEdge->property["growFactor"] = growingCurves[edgeIndex].second.second;
}
if( growingSheets.contains(edgeIndex) )
{
QString growingNodeID = nodeMap[growingSheets[edgeIndex].first];
toEdge->property["growing"] = growingNodeID;
QVariant val; val.setValue(growingSheets[edgeIndex].second);
toEdge->property["deltas"] = val;
QVariant cpts; cpts.setValue(((Structure::Sheet*)toEdge->getNode(growingNodeID))->surface.mCtrlPoint);
toEdge->property["cpts"] = cpts;
}
}
return graph;
}
QVector<DynamicGraph> DynamicGraph::candidateNodes(DynamicGraph & targetGraph)
{
QVector<DynamicGraph> candidate;
GraphState futureState = targetGraph.State();
// Compute graph difference
GraphState diff = difference( futureState );
// Should return no candidates when they are exactly the same
if( diff.isZero() ) return candidate;
QVector<int> activeNodes;
bool isAdding = true;
int discrepancy = 0;
// Missing nodes: nodes have precedent
if(diff.numSheets != 0 || diff.numCurves != 0)
{
// Sheets and curves: sheet have precedent
if(diff.numSheets != 0)
{
activeNodes = getSheets();
if(diff.numSheets > 0) isAdding = false;
discrepancy = abs(diff.numSheets);
}
else if(diff.numCurves != 0)
{
activeNodes = getCurves();
if(diff.numCurves > 0) isAdding = false;
discrepancy = abs(diff.numCurves);
}
}
if(activeNodes.size() < 1) return candidate;
// Try all sets of new edges of size
std::vector<int> nodesSet = activeNodes.toStdVector();
std::vector<int>::iterator begin = nodesSet.begin(), end = nodesSet.end();
do {
std::vector<int> currentSet (begin, begin + discrepancy);
// Add operation as a candidate graph
DynamicGraph g = clone();
foreach(int ci, currentSet)
{
if(isAdding)
g.cloneNode(ci);
else
g.removeNode(ci);
}
candidate.push_back(g);
} while (next_combination(begin, begin + discrepancy, end));
return candidate;
}
QVector<DynamicGraph> DynamicGraph::candidateEdges(DynamicGraph & targetGraph)
{
QVector<DynamicGraph> candidate;
GraphState futureState = targetGraph.State();
// Compute graph difference
GraphState diff = difference( futureState );
// Should return no candidates when they are exactly the same
if( diff.isZero() ) return candidate;
QVector<int> groupA, groupB;
QSet<SimpleEdge> exploredEdges;
bool isAdding = true;
int discrepancy = 0;
// Add existing edges as explored
foreach(SimpleEdge e, edges)
exploredEdges.insert(e);
if(diff.numMixedEdges != 0)
{
// Curve-Sheet edges
if(diff.numMixedEdges > 0) isAdding = false;
groupA = getSheets();
groupB = getCurves();
discrepancy = abs(diff.numMixedEdges);
}
else if(diff.numSheetEdges != 0)
{
// Sheet-Sheet edges
if(diff.numSheetEdges > 0) isAdding = false;
groupA = getSheets();
groupB = groupA;
discrepancy = abs(diff.numSheetEdges);
}
else if(diff.numCurveEdges != 0)
{
// Curve-Curve edges
if(diff.numCurveEdges > 0) isAdding = false;
groupA = getCurves();
groupB = groupA;
discrepancy = abs(diff.numCurveEdges);
}
// Find all possible new edges
QMap<int, SimpleEdge> uniqueEdges;
foreach(int a, groupA)
{
foreach(int b, groupB)
{
SimpleEdge e(a, b);
// Uniqueness check:
if(a == b || exploredEdges.contains(e)) continue;
exploredEdges.insert(e);
uniqueEdges[uniqueEdges.size()] = e;
}
}
// Try all sets of new edges of size
std::vector<int> uniqueEdgesIdx;
foreach(int key, uniqueEdges.keys()) uniqueEdgesIdx.push_back(key);
std::vector<int>::iterator begin = uniqueEdgesIdx.begin(), end = uniqueEdgesIdx.end();
do {
std::vector<int> currentSet (begin, begin + discrepancy);
// Add operation as a candidate graph
DynamicGraph g = clone();
foreach(int key, currentSet)
{
SimpleEdge e = uniqueEdges[key];
if(isAdding)
g.addEdge(e.n[0], e.n[1]);
else
g.removeEdge(e.n[0], e.n[1]);
}
candidate.push_back(g);
} while (next_combination(begin, begin + discrepancy, end));
return candidate;
}
int DynamicGraph::valence( int nodeIndex )
{
return adjacency[nodeIndex].size();
}
QVector< QPairInt > DynamicGraph::valences(bool isPrint)
{
std::vector<int> vals;
std::vector<unsigned int> indx;
foreach(int ni, nodes.keys())
{
vals.push_back( adjacency[ni].size() );
indx.push_back( ni );
}
// Sort by valence
paired_sort(indx, vals, true);
// DEBUG:
if(isPrint){
QStringList vstr;
foreach(int v, vals) vstr << QString::number(v);
qDebug() << vstr;
}
QVector< QPairInt > valPair;
for(int i = 0; i < (int) vals.size(); i++)
valPair.push_back( qMakePair(vals[i], (int)indx[i]) );
return valPair;
}
bool DynamicGraph::sameValences( DynamicGraph & other )
{
QVector< QPairInt > myValence = valences();
QVector< QPairInt > otherValence = other.valences();
for(int i = 0; i < (int) myValence.size(); i++){
if(otherValence[i].first != myValence[i].first)
return false;
}
return true;
}
QVector< QPairInt > DynamicGraph::correspondence( DynamicGraph & other, double & score, bool isPrint )
{
QVector< QPairInt > corr;
QVector< QPairInt > vme = valences();
QVector< QPairInt > vother = other.valences();
// Build the set for the other graph
QMap< int, QList<int> > vset;
foreach(QPairInt p, vother)
{
vset[ p.first ].push_back( p.second );
}
if(isPrint) qDebug() << "Correspondence map:";
// Test correspondence score and assign to smallest
foreach(QPairInt p, vme)
{
int valence = p.first;
int nodeID = p.second;
QMap<double, int> scoreBoard;
std::vector<Vector3> nf = noFrame();
QString n1_id = nodes[nodeID].str("original");
Structure::Node * n1 = this->mGraph->getNode( n1_id );
Vector3 center1(0,0,0); n1->get(Vector4d(0.5,0.5,0.5,0.5), center1, nf);
// Test against possible corresponding nodes
foreach( int curID, vset[ valence ] )
{
QString n2_id = other.nodes[curID].str("original");
Structure::Node * n2 = other.mGraph->getNode( n2_id );
Vector3 center2(0,0,0); n2->get(Vector4d(0.5,0.5,0.5,0.5), center2, nf);
double currScore = (center1 - center2).norm();
scoreBoard[ currScore ] = curID;
}
// Add minimum score to total
double minScore = scoreBoard.keys().first();
score += minScore;
int otherID = scoreBoard[ minScore ];
vset[ valence ].removeAll( otherID );
// Pair current node with minimum one
corr.push_back( qMakePair(nodeID, otherID) );
if(isPrint)
qDebug() << nodes[nodeID].str("original") << " <--> " << other.nodes[otherID].str("original");
}
if(isPrint) qDebug() << "===\n";
return corr;
}
void DynamicGraph::flagNodes( QString propertyName, QVariant value )
{
foreach(int i, nodes.keys())
nodes[i].property[propertyName] = value;
}
QVector<QVariant> DynamicGraph::flags( QString propertyName )
{
QVector<QVariant> f;
foreach(int i, nodes.keys())
f.push_back(nodes[i].property[propertyName]);
return f;
}
SimpleNode * DynamicGraph::getNode( QString originalID )
{
foreach(int i, nodes.keys())
if(nodes[i].str("original") == originalID)
return &nodes[i];
return NULL;
}
QMap<int, SimpleEdge> DynamicGraph::getEdges( int nodeIDX )
{
QMap<int, SimpleEdge> result;
foreach(int i, edges.keys()){
if(edges[i].n[0] == nodeIDX || edges[i].n[1] == nodeIDX)
result[i] = edges[i];
}
return result;
}
Structure::Link * DynamicGraph::getOriginalLink( QString originalID1, QString originalID2 )
{
QString n1_id = nodes[getNode(originalID1)->idx].str("original");
QString n2_id = nodes[getNode(originalID2)->idx].str("original");
return mGraph->getEdge(n1_id, n2_id);
}
bool DynamicGraph::hasEdge( int n1_index, int n2_index )
{
return edges.values().contains(SimpleEdge(n1_index,n2_index));
}
Array1D_Vector4d DynamicGraph::firstSpecialCoord( int node_index )
{
typedef QMap< int, Array1D_Vector4d > NodeCoord;
foreach(NodeCoord nodeCoord, specialCoords.values())
{
if(nodeCoord.contains(node_index))
return nodeCoord[node_index];
}
return Array1D_Vector4d(1, Vector4d(0,0,0,0));
}
/*
void DynamicGraph::correspondTo( DynamicGraph & other )
{
double score = 0;
QVector< QPairInt > corr = correspondence(other, score);
foreach( QPairInt p, corr )
{
int from = p.first;
int to = p.second;
if(from == to) continue;
// Swap
QString from_original = nodes[from].property["original"];
QString to_original = nodes[to].property["original"];
nodes[from].property["original"] = to_original;
nodes[to].property["original"] = from_original;
}
}*/