* This document is still in writing *
organic is a project to reify and maintain organizations structure in a dynamic graph. An organization is a connected set of nodes that share a common meta index.
The algorithm uses a special attribute of node called meta index that allows to classify nodes into a restricted set of category. Then, the organizations manager try to extract connected structures from this classification and to maintain these structures through time without computing all the solution from scratch.
Two special operations have to be defined :
- this operation is used to merge two organizations. The smallest one is dissolved in the largest one. Organizations should have the same meta index.
- this operation is called while some links have been removed in an organization making it disconnected. The biggest set of connected nodes is kept to maintain the organization structure and one or more children are created with the remaining nodes.
Following is the list of events that can lead to change in organizations :
- edge added, can lead to a merge operation;
- edge removed, can lead to a mitose operation; edge is removed from its organization and checkOrganization is called
- node removed, changes the organization content; node is removed from its organization and checkOrganization is called
- node meta index changed, can lead to both merge or mitose operations.
This operation is used to set the root node of an organization as the node the most connected with other nodes of this organization.
- org : the organization to check the root.
root = none count = -1 for node in org.nodes: c = connections count of node if c > count: root = node count = c if root is not org.root: org.root = root trigger rootNodeUpdated
This operation checks if the organization structure is connected.
- org : the organization we want to check.
reached =  toVisit =  toVisit.append(org.root) while len(toVisit) > 0: node = toVisit.pop() reached.append(node) for edge in node.connectedEdges: if edge is in org: o = edge.oppositeOf(node) if o.metaOrganizationIndex == node.metaOrganizationIndex: toVisit.append(o) if reached != org.nodes: notReached = org.nodes - reached mitose(org, notReached) checkRootNode(org)
This operation merges two organizations. It has to be called when a connection is detected between these organizations.
- org1, org2 : two organizations to merge, assuming that org1 is biggest that org2.
- result of the merge : org1 increases with org2. org2 is removed in this operation.
nodes = org2.nodes for node in nodes: org2.remove(node) org1.include(node) trigger organizationMerged trigger organizationRemoved remove org2 checkRootNode(org1) invoke validation return org1
This operation is called when the organization structure is disconnected.
- base : the organization to split. orphans : list of nodes not connected anymore to the organization structure.
- produce at least one more organization.
for node in orphans: base.remove(node) assert base.nodes.size() > 0 suborg = create new organization including nodes in orphans trigger organizationCreated trigger organizationSplited checkOrganization(suborg) invoke validation
What event is triggered ?
- a new organization is created :
- an organization is removed :
- an organization is splited :
- two organizations are merged :
Organizations have a dedicated method to check the validity of their structure. The structure of an organization is valid if exactly all nodes of this organization can be reached from the root node by exploring connected nodes with the same organization index.
Following is the pseudo-algorithm used to check the integrity of the structure
reached =  toVisit =  toVisit.append(org.root) while len(toVisit) > 0: node = toVisit.pop() reached.append(node) for edge in node.connectedEdges: o = edge.oppositeOf(node) if o.metaOrganizationIndex == node.metaOrganizationIndex: toVisit.append(o) if len(reached - org.nodes) > 0: produce an error if len(org.nodes - reached) > 0: produce an error
This program is free software distributed under the terms of two licenses, the CeCILL-C license that fits European law, and the GNU Lesser General Public License. You can use, modify and/ or redistribute the software under the terms of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following URL http://www.cecill.info or under the terms of the GNU LGPL as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along with this program. If not, see http://www.gnu.org/licenses/.
The fact that you are presently reading this means that you have had knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.